Definable set

From Wikipedia, the free encyclopedia

In mathematical logic, a definable set is an n-ary relation on the domain of a structure whose elements are precisely those elements satisfying some formula in the structure. A set can be defined with or without parameters, which are elements of the domain that can be referenced in the formula defining a set. Note that a unary relation on the domain of a structure is simply a subset of the domain, and when we refer to the definable sets in a structure we often mean the definable subsets of the domain. Formally,

For a given first-order language \mathcal{L}, let \mathcal{M} be an \mathcal{L}-structure with domain M and X\subseteq M. We say that A\subseteq M^m is definable in \mathcal{M} with parameters from X if and only if there exists a formula \varphi(x_1,\ldots,x_m,y_1,\ldots,y_n) and elements b_1,\ldots,b_n\in X such that for all a_1,\ldots,a_m\in M,
(a_1,\ldots,a_m)\in A if and only if \mathcal{M}\models\varphi[a_1,\ldots,a_m,b_1,\ldots,b_n]
(Note that the bracket notation above indicates the semantic evaluation of the free variables in the formula.) We say that A is definable in \mathcal{M} without parameters if and only if it is definable in \mathcal{M} with parameters from the empty set.

[edit] Examples

Let \mathcal{N}=(\mathbb{N},<) be the structure consisting of the natural numbers with the usual ordering. Then every natural is definable in \mathcal{N} without parameters--the number 0 by the formula \varphi(x) stating there exist no elements less than me:

\varphi=\neg\exists y(y<x)

and every natural n > 0 by the formula \varphi(x) stating there exist exactly n elements less than me:

\varphi=\exists x_0\cdots\exists x_{n-1}(x_0<x_1\land\cdots\land x_{n-1}<x\land\forall y(y<x\rightarrow(y\equiv x_0\lor\cdots\lor y\equiv x_{n-1})))

In contrast, one cannot define an integer without parameters in the structure \mathcal{Z}=(\mathbb{Z},<) consisting of the integers with the usual ordering (this can be proved formally using the automorphism theorem for definable sets; see below).

Consider the structure \mathcal{R}=(\mathbb{R},0,1,+,\cdot) consisting of the field of real numbers. Note that an ordering relation is not included in this structure, but we can define what it means to be nonnegative in the reals (on the usual ordering) by noting that all and only the nonnegative reals have square roots. Set

\varphi=\exists y(y\cdot y\equiv x)

Then for a\in\R, a is nonnegative if and only if \mathcal{R}\models\varphi[a]. In conjunction with a formula that defines the additive inverse of a real number in \mathcal{R}, one can use \varphi to define the usual ordering in \mathcal{R}: for a,b\in\R, we set a\le b if and only if b − a is nonnegative. Thus we gain no expressive power by considering the structure \mathcal{R}^{\le}=(\mathbb{R},0,1,+,\cdot,\le) (this can be proved formally using syntactic interpretations).

Note that the theory of \mathcal{R}^{\le} has quantifier elimination. Thus the definable sets are boolean combinations of solutions to polynomial equalities and inequalities i.e. they are semi-algebraic sets.

[edit] Results and Applications

An important result about definable sets is that they are preserved under automorphisms. Formally,

Let \mathcal{M} be an \mathcal{L}-structure with domain M, X\subseteq M, and A\subseteq M^m definable in \mathcal{M} with parameters from X. Let \pi:M\to M be an automorphism of \mathcal{M} which is the identity on X. Then for all a_1,\ldots,a_m\in M,
(a_1,\ldots,a_m)\in A if and only if (\pi(a_1),\ldots,\pi(a_m))\in A

(The proof is immediate from definitions and we omit it here.) This result is very useful in the classification of the definable subsets of a given structure. For example, in the case of \mathcal{Z}=(\mathbb{Z},<) above, we note that any translation of \mathcal{Z} is an automorphism preserving the empty set of parameters, hence it is impossible to define an integer without parameters in \mathcal{Z}. In fact, we see that the only subsets of the integers definable in \mathcal{Z} without parameters are the empty set and \mathbb{Z} itself.

Definable sets have many applications within mathematical logic. We note, for example, how they can be used in the Tarski-Vaught test to characterize the elementary substructures of a given structure.

[edit] References

  • Rudin, Walter. Principles of Mathematical Analysis, 3rd. ed. McGraw-Hill, 1976.
  • Slaman, Theodore A. and W. Hugh Woodin. Mathematical Logic: The Berkeley Undergraduate Course. Spring 2006.