# Proof that number of definable sets is countable

I did the following two related exercises in Just/Weese on page 114:

18: Show that if $z$ is a finite set and $y \subset z$ then there exists a formula $\varphi(x)$ of $L_S$ such that $y = \{x \in z: \varphi (x) \}$.

19: Let $Y$ be the collection of all $y \subset \omega$ for which there exists a formula $\varphi (x)$ without parameters such that $y = \{x \in \omega : \varphi (x) \}$. Show that $Y$ is countable.

One problem I have is that the first one is rated "difficult" and the second one is rated "extra difficult" but both of my answers are not only very simple but it also only took me a minute to come up with each so both are probably wrong and I am missing something. Here they are:

18: Let $y$ be the set $y = \{y_1 , \dots , y_n \} \subset z$. Let $\varphi(x) = (x = y_1) \lor \dots (x=y_n)$. Then $y = \{ x \in \omega : \varphi (x) \}$.

19: Let $F_n$ be the set of all formulas $\varphi$ in $L_S$ such that $\varphi$ consists of $n$ characters. Since there are only finitely many symbols in $L_S$, logical and non-logical combined, $F_n$ is finite. Then $F = \bigcup_{n \in \mathbb N} F_n$, the set in which each element corresponds to a definable $y \subset \omega$, is a countable union of finite sets and hence countable.

Could you point out what I am missing? Thanks for your help!

• What are $y_1,y_2,\dots$? All we are given is a set $A$ that satisfies the formal condition of finiteness. – André Nicolas Nov 25 '12 at 17:26
• @AndréNicolas I thought if it's finite I can enumerate it. – Rudy the Reindeer Nov 25 '12 at 20:00
• We are looking for a formula in the language of say ZF. The expression in the post was at most an outline of how one might construct such a formula, with all the hard detail missing. – André Nicolas Nov 25 '12 at 20:19
• 18 is deeper than it looks -- if it is true at all, it depends on the Axiom of Foundation/Regularity, which is not something you see every day. (Without Foundation, $z$ could be a set of two different Quine atoms, and those cannot be distinguished by any formula). This suggests that there's probably an induction on the rank of the sets hidden somewhere. – Henning Makholm Nov 26 '12 at 13:00
• By the way, notice that what you're asked to prove in 18 doesn't assume that $z\subseteq \omega$. – Henning Makholm Nov 26 '12 at 13:03

The problem with your solution to 19 is the the correspondence between $F_n$ and $y$ is not itself definable by a formula within the system (there's a diagonalization argument showing this). Therefore you have no guarantee that this correspondence is a set, which means that you cannot be sure that a bijection between the countably many formulas and the describable subsets exists as a set.

(In fact it is not even clear to me a priori that $Y$ is necessarily a set).

• Is it necessary to make this collection internally definable? – Asaf Karagila Nov 25 '12 at 17:36
• @AsafKaragila: The correspondence must be internally definable if one just wants to wave his hand and construct a function (as a set) from it. I'm not sure it is essential to make the collection internally definable, but it sure needs to be a set if it is to be countable. – Henning Makholm Nov 25 '12 at 17:39
• @Matt: As regards 18 I agree with Asaf(s now deleted answer) that "$(x=y_1)$" is not necessarily a formula. For example, suppose $z$ is a set of 100 well-orderings for $\mathbb R$. Then $y_1$ well-orders $\mathbb R$, and as we know it is not easy to write a formula that expressed that $x$ is exactly that well-ordering of $\mathbb R$. – Henning Makholm Nov 25 '12 at 21:47
• My feeling is that 18 would be easier to attack in the equivalent form "if $x\ne y$ then there is a formula $\phi$ such that $\phi(x)$ and $\neg\phi(y)$". But the details elude me. – Henning Makholm Nov 25 '12 at 22:17
• To complement what Henning is saying, this MO answer elaborates on the issues of defining definability. – Miha Habič Nov 26 '12 at 12:40

In your solution to (19), $F_{n}$ the set of all formulas $\varphi$ in $L_{S}$ such that $\varphi$ consists of $n$ characters is not finite, because the set of all atomic formulas $P=\lbrace p_{1},p_{2}, \ldots \rbrace$ usually is not finite.

• There are really just two atomic formulas in one free variable. $x=x$ and $x\in x$. – Asaf Karagila Nov 26 '12 at 10:29
• So I did not get the question correctly. You say that it means we have no variable except x. THANKS ASAF KARAGILA – Farshad Nahangi Nov 26 '12 at 10:35
• Oh, you did make a good point, and Matt did ignore that which is a mistake. But not an actual mistake, as we only want formulas with one free variable. – Asaf Karagila Nov 26 '12 at 10:42
• The solution to (18) seems to be true. – Farshad Nahangi Nov 26 '12 at 10:47
• @AsafKaragila Please do not invent stories of your own that people not mentioned in the story cannot distinguish from reality. I did not ignore anything. – Rudy the Reindeer Nov 26 '12 at 13:08