# Show that not all sets of Natural Numbers are definable

I'm kind of lost on this problem; I think it has something to do with showing that there are uncountably many relations among N(assuming an included set of functions such as successor, addition, and multiplication) with there only being countably many defining formulas in the structure. That being said, I'm unsure of how to proceed. Any pointing in the right direction would be much appreciated.

-
At first glance, I would try to find a bijection between certain sets of natural numbers and some uncountable subset of $(0,1)$. –  Robert Mastragostino Oct 15 '12 at 5:10
Have you seen that there are uncountably many subsets of $\mathbb{N}$? –  Arthur Fischer Oct 15 '12 at 5:34

Your plan is exactly right:

1. To keep things simple consider just the one-place relations on $\mathbb{N}$, i.e. the numerical properties. Do you know how to prove that these are uncountably many? [To every property $P$ there corresponds an infinite binary string $a_0a_1a_2a_3\ldots$ where $a_n = 1$ iff $n$ has property $P$, and $a_n = 0$ otherwise. Why are the infinite binary strings uncountable? You use a Cantor-style diagonal argument ...]
2. Do you know how to prove that the one-place predicates constructible in a first-order language whose non-logical vocabulary is just '$0$', '$S$', '+', '$\times$' are only countably infinite in number? [Every such predicate is a finite string from a finite basic repertoire of symbols (assuming the variables are e.g. $x, x', x'', x''', \ldots$, i.e. built from a finite alphabet): how many such strings can there be? Order them 'alphabetically', the strings of length one, then those of length two, then those of length three ... Why does that show that there are only countably many such strings?]

Establishing the results in (1) and (2) -- as you indicate -- gives the result you want.

-
Of course the result here is correct, but if the argument was simply "there are uncountably many sets, there are countably many formulas" then it would also go through if we replace "arithmetical formula" with "formula of set theory". By way of comparison, ACA$_0$ proves that "there is no sequence that includes all subets of $\mathbb{N}$" but it it is consistent with ACA$_0$ that every subset of $\mathbb{N}$ is arithmetically definable. A vital ingredient in the proof is to work in a metatheory that is able to define truth for the class of formulas being studied. –  Carl Mummert Oct 15 '12 at 11:31
I'm not pointing this out because I think you are unfamiliar with it - it's just an issue that seems to often lead to misunderstanding when people see informal treatments of definability. –  Carl Mummert Oct 15 '12 at 11:33
@CarlMummert Yes indeed. –  Peter Smith Oct 15 '12 at 12:56
There is a concrete way to do this, by simply giving an example of a set that is not definable by any arithmetical formula. Since you know the set of arithmetical formulas is countable, list all the ones with one free variable into a sequence $( \phi_k(x) : k \in \mathbb{N})$. Then define a set $A \subseteq \mathbb{N}$ by saying that for each $n$, $n \in A$ if and only if $\phi_n(n)$ is false.
If $A$ was definable by some arithmetical formula $\phi_m(x)$, we would have $(\forall n)[n \in A \Leftrightarrow \phi_m(n)]$. In particular, we would have $m \in A \Leftrightarrow \phi_m(m)$. But by construction, $m \in A \Leftrightarrow \lnot \phi_m(m)$. This is a contradiction, so $A$ is indeed not definable by any formula in the original sequence.
It is worth noting that this argument work fine when the set of formulas is just the formulas of arithmetic. It may be tempting to generalize it to the set of all formulas of set theory, to get a set $A$ that is even "more undefinable". But it is consistent with ZFC that every set of natural numbers is definable by a formula of set theory! Here is a link to a MathOverflow answer about that. This is not a problem with the proof for arithmetical formulas - that is fine. But it is worth knowing that this sort of argument requires having a metatheory in which we can talk about the truth of the formulas, in order to define the set $A$.
Yes, this uses the same method as proving the set of definable sets is uncountable - but by avoiding the general machinery of uncountability we can get a more parsimonious proof. The explicit version also makes it clear how the metatheory is being used (at the end of the first paragraph, the definition of $A$ is not arithmetical). –  Carl Mummert Oct 15 '12 at 11:35