Can we prove that odd and even numbers alternate without using induction?

Solution 1:

Take $M = \{P = a_nx^n + \ldots + a_0 \in \Bbb Z[x] / a_n > 0 \}$, with the usual addition and multiplication on polynomials. Interprete $S(P)$ as $P(X)+1$.

Then $M$ is a model of Robinson arithmetic, but there are long strings of "not-even" numbers, such as $X,X+1,X+2,\ldots$. So in this model, it is false that if $n$ is not even then $n+1$ is even.

If you define "$n$ is odd" as "$\exists k / n= k+k+1$", then it is false that every number is even or odd.

However, it is still true in $M$ that addition is associative and commutative, and so if $n$ is odd then $n+1$ is even, and if $n$ is even, then $n+1$ is odd. (you will need a stranger model for this to fail)

If you want a model in which $a^2-2b^2 = 0$ has a solution, you can pick $M = \{ P \in \Bbb Z[X,Y]/(X^2-2Y^2) / \lim_{y \to \infty} P(\sqrt 2 y,y) = + \infty$ or $P \in \Bbb N \}$

Solution 2:

This is just a partial answer. Let $\mathcal L =\{S,<\}$ be the language with an unary function $S$ and a binary relation $<$. Consider the structure $(\mathbb N, S,<)$ ($S$ is the successor function), then $E=\{2n:n\in\mathbb N\}$ is not definable in $(\mathbb N, S,<)$. To see this consider the elementary extension $\mathfrak C=(\mathbb N\sqcup \mathbb Z, S,<)$, and define an automorphism $\Phi:\mathfrak C\to \mathfrak C$ as follows $\Phi(n)=n$ if $n\in\mathbb N$ and $\Phi(n)=S(n)$ otherwise. It is easy to see, using $\Phi$, that there is no formula defining $E$.