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.
Show that not all sets of Natural Numbers are definable
3
$\begingroup$
logic
-
3At first glance, I would try to find a bijection between certain sets of natural numbers and some uncountable subset of $(0,1)$. – 2012-10-15
-
2Have you seen that there are _uncountably_ many subsets of $\mathbb{N}$? – 2012-10-15