# What is a definable set?

I've read the definition a bunch of times but I don't quite understand it. What is meant by $(M,\in)$ satisfies $\varphi(x;a_1,\ldots)$?

Recall that a set $X$ is a definable over a model $(M, \in)$, where $M$ is a set, if there exists a formula $\varphi$ in the set of formulas for the language $\{\in\}$, and some elements $a_1, \ldots, a_n \in M$ such that $X=\{ x\in M: (M, \in ) \vDash \varphi[x, a_1, \ldots, a_n]\}$.

Let $$\operatorname{def}(M) = \{X\subset M : X \text{ is definable over }(M, \in)\}$$

Is there a simple example that will make it more clear? And why is it a subset of the powerset? Thanks.

• This is not really a question about set theory, it's a question about logic and models. – Asaf Karagila Feb 18 '15 at 21:04
• @AsafKaragila I suppose, however the set theory tag explicitly states that it includes questions about definability, and this is definitely about definability. – user2034 Feb 19 '15 at 4:05

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 "$\Vdash$" 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 http://en.wikipedia.org/wiki/First-order_logic#Semantics, 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!

• Thank you, this makes it very clear! Exactly what I was looking for. – user2034 Feb 18 '15 at 20:53
• @user28111 you should write a book! Your language is easy to understand and is enjoyable to read! – Conor O'Brien Feb 19 '15 at 5:02
• Thanks, I hope to someday! – Noah Schweber Feb 24 '15 at 9:12
• Noob question: In the $M'$ example you say that the only definable sets are $\emptyset$ and $\mathbb{Z}$. We could define them, respectively, by the formulas $\phi(x): \neg(x=x)$ and $\phi(x): x=x$? – Xablau123 Oct 30 '17 at 9:18
• @Xablau123 Yes, that's right. – Noah Schweber Oct 30 '17 at 9:22