[Math] 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.