Let $A\subseteq\mathbb{N}$ be defineable over $(\mathbb{N},0,S)$. Then is $A$ or $\mathbb{N}\setminus A$ finite. $S$ is here the successor-function $S(n)=n+1$.
Hello,
I have a question to this task. First of all it is clear, that every natural number is definable about this model. $1=S(0), 2=S(S(0)), ..., S^x(0):=\underbrace{S(S(...S(0)...))}_{\text{x-times}}=x$ for $x\neq 0$.
I think a proof through contradiction is not wise, since it should need quantifire elimination, which I would like to avoid.
I want to understand what the problem is, when $A$ is a set with $A$ and $\mathbb{N}\setminus A$.
For example: $A=\{0,2,4,6,...\}$ the set of every even natural number.
The following should not be an appropriate formula:
$\varphi\equiv ((v_0=0)\wedge (v_1=S^2(0))\wedge (v_3=S^4(0))\wedge\dotso\wedge v_n=S^{2n}(0))$
This formula uses the natural numbers, which are definable, but also multiplication (2n). But the main point is, that this formula is infinite, because it contains infinite terms.
So I guess that the problem for those sets is, that you have to give a "rule" how to generate the elements of $A$. My example is simple, and yet a rule, just using 0 and S, should not exist. So when A gets more complex, like the set of prime-numbers, it is impossible to define it.
Can I proof this by differentiation of the cases:
A is finite
A is infinite
Case 1 is easy. When A is finite I can give the formula just like in the example. I can list every element.
When A is infinite, and I know $\mathbb{N}\setminus A$ is finite, I can use negation and list the elements of $\mathbb{N}\setminus A$, but I should show, that A is really finite. Here I use that $A$ is definable. So a formula exists. When I know I can not give a "rule" to generate the elements, it should be simple. But how do I show, that such a rule does not exist?
Would this work? Or are my thoughts missleading and wrong?
Thanks in advance for your comments.