Show that not all sets of Natural Numbers are definable

Question

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.

Answer 1

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.

Answer 2

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$.