What is a definable set?

Solution 1:

So even though the question talks about the language of set theory specifically, let me answer the question more generally.

Also, I'll talk about definable subsets of $M$, as opposed to definable sbsets of the Cartesian powers of $M$ - for example, we can ask "When is a set of ordered pairs of elements of $M$ definable?" The answer is a straightforward generalization of what I write below, and coming up with it is a good exercise.

Let me first describe definability without parameters. That is, what I talk about below will be not taking into account the $a_i$s of your question; I'll get to those later.

Suppose I have any first-order structure $M$ in some language $L$. Say, $L$ is the language of rings ($+, \times, 0, 1$) and $M$ is the ring $\mathbb{Z}$.

Then $M$ has (of course) many subsets, but some of these subsets are much nicer than others, in the sense of being "describable" using the language $L$. For example, let $E$ be the set of even numbers. Then $E$ is the set of $x$ such that "There is some $y$ such that $x=y+y$." More formally, $E$ is the set of elements $x$ of $M$ such that the statement "there is some $y$ such that $x=y+y$" is a true statement about $M$. This is what is meant by "$M$ satisfies . . . " It's just saying, "... is true in $M$." In particular, being very formal we would write $$E=\{x: M\models \exists y(x=y+y)\}.$$ The formal definition of "$\models$" is actually somewhat annoying; at first, I think it's better to just think of it informally, so "$M\models \varphi$" means "$\varphi$ is a true statement about $M$." But see here, or any good logic textbook.

A set like this - such that there is a formula $\varphi(x)$ in the language $L$, so that the set is equal to $\{x: M\models\varphi(x)\}$ - is called definable without parameters. Other definable subsets of $M$ include the set of perfect squares, the set of positive numbers (this one takes some work, since we don't have the symbol "$<$"!), and the set of primes.

Note that the definability of a subset of $M$ depends crucially on the language of $M$. For example, consider the structure $M'$ whose underlying set is $\mathbb{Z}$ as before, but whose language is the empty language (no symbols except =). Then no subset of $M'$ is definable without parameters except the whole structure and the emptyset; this is a consequence of the fact, provable by induction, that definable sets are preserved by automorphisms: if $\alpha$ is an automorphism of $M$ and $D$ is a definable subset of $M$, then $\alpha(D)=D$. The claim about $M'$ now follows since every permutation of $M'$ is an automorphism of $M'$.

OK, now what about those $a_i$s? Well, there's a few ways to treat this.

First, given any set $A\subset M$ of a structure in a language $L$, we can consider an expanded language $L_A=L\sqcup\{c_a: a\in A\}$ gotten by adding a new constant symbol for each element of $A$, and the expansion $M_A$ of $M$ gotten by taking $M$, and interpreting the symbol $c_a$ as $a$ for each $a\in A$.

The act of passing from $M$ to $M_A$ is all about adding expressive power. Specifically, more sets are definable in $M_A$ than were definable in $M$! For example, every finite subset of $A$ is now definable in $M_A$; and we might get more, besides. On the other hand, because definitions can only use finitely many symbols, the whole set $A$ might not be definable in $M_A$ (for example, take $M'$ from before and $A=\{evens\}$).

That is, in defining a set, we only use finitely many symbols: for a specific set $D\subset M$, $D$ is definable in $M_A$ iff $D$ is definable in $M_{A_0}$ for some finite $A_0\subset A$.

We say a set $D\subset M$ is definable from parameters (usually, we just say "definable") if, for some $A$, $D$ is a definable subset of $M_A$. Note that by the above paragraph, we can assume $A$ is finite - $A$ is just the set $\{a_0, a_1, . . . , a_n\}$ of your OP!

So then $Def(M)$ is the collection of definable-with-parameters subsets of $M$. Since this is a collection of subsets of $M$, it's a subset of the powerset of $M$.

Alternatively, if you don't want to think of expanding $M$, we can think of a formula $\varphi$ in $n+1$ variables as describing a whole bunch of sets, one for each $n$-tuple of elements of $M$: given the tuple $a_1, . . . , a_n$, we get the set $$\varphi_{a_1, . . . , a_n}=\{m\in M: M\models \varphi(m, a_1, . . . , a_n)\}.$$ Then a set is definable with parameters if it is of the form $\varphi_{a_1, . . . , a_n}$ for some formula $\varphi$ and tuple of elements of $M$ $a_1, . . . , a_n$.

I find this approach more difficult to think about, but it is certainly shorter. On the other hand, one advantage of it is that it connects nicely with definable subsets of higher Cartesian powers: a formula $\varphi$ in $n+1$ variables defines - without parameters - a subset of $M^{n+1}$; then we have that a subset of $M$ is definable-with-parameters iff it is a projection of some definable-without-parameters subset of a higher Cartesian power of $M$. This is kind of nice!