Neither Even Nor Odd Natural Numbers

Question

Modular arithmetic (MA) has the same axioms as first order Peano arithmetic (PA) except $\forall x(Sx \neq 0)$ is replaced with $\exists x(Sx=0)$. In Even XOR Odd Infinities? I asked if this statement is a theorem of MA:

1) $\exists x(x \neq 0 \land x+x = 0) \overline{\vee} \exists x(x+x = 1)$

The answer was no. One counter-example was the 2-adic integers, $Z_2$. There is no 2-adic integer, $m \neq 0$, such that $2m=0 \lor 2m=1$. Notice both sides of statement (1) are false in $Z_2$. Statement (1) is not a theorem of MA even if I weaken the $\overline{\vee}$ to $\lor$. Consider this second statement:

2) $\forall x(\exists y(y+y=x) \lor \exists y(y+y+1=x))$

There are numerous inductive proofs in PA of statement (2) on the internet. I have always assumed the universe of any model of MA is an initial segment of some model of PA. Let $M_2$ be a model of PA that has $Z_2$ as an initial segment. I don't see how statement (2) can be true in $M_2$. Let $m \in M_2$ be the non-standard natural number that corresponds to -1 in a $Z_2$ model of MA. We know $\forall x((x=0 \lor x+x \neq Sm) \land (x+x \neq SSm))$. This means $SSm$ is not even and, since $Sm$ is not even, $SSm$ can't be odd.

My question is whether $Z_2$ is an initial segment of some model of PA? If so, is statement (2) true in this model?

I previously asked this question on Stack Exchange.

Answer 1

Let me reiterate what I said in Math.SE: Let us define an even number to be any number of the form $2m$, and an odd number to be any number of the form $2m + 1$.

Proof 1. Here is a proof, in both $PA$ and $MA$, that $\forall x(\exists y(y+y=x) \lor \exists y(y+y+1=x))$ (statement 2):

$0$ is even, so it is even or odd. Suppose that $n$ is even or odd. If $n$ is even, then $n = 2m$ for some $m$, so $n + 1 = 2m + 1$, so $n + 1$ is odd, so it is even or odd. If $n$ is odd, then $n = 2m + 1$ for some $m$, so $n + 1 = 2m + 2 = 2(m + 1)$, so $n + 1$ is even, so it is even or odd. Therefore, by induction, for all $n$, $n$ is even or odd.

Proof 2: Here is a proof, in $PA$ but not $MA$, that $\forall x(\exists y(y+y=x) \overline{\vee} \exists y(y+y+1=x))$

$0$ is not the successor of any number, so it cannot be written as $2m + 1$, so it is not odd, and thus it is not both even and odd. Suppose that $n$ is not both even and odd, and suppose for sake of contradiction that $n + 1$ is both even and odd. Since $n + 1$ is even, $n + 1 = 2m$ for some $m$, so $n = 2m - 1 = 2(m-1) + 1$, so $n$ is odd. Since $n + 1$ is odd, $n +1 = 2k + 1$ for some $k$, so $n = 2k$, so $n$ is even. So $n$ is both even and odd, contradicting the assumption that it's not both even and odd. Thus $n + 1$ is not both even and odd. Therefore, by induction, for all n, n is not both even and odd. Thus, by statement 2 (i.e. the statement proven in proof 1), for all $n$, $n$ is even XOR $n$ is odd.

Answer 2

I will attempt to answer my own question. I hope someone will point out any obvious error.

Notice that statement (1) is true in all finite models of MA, the rings $\mathbb{Z} / n \mathbb{Z}$ . Statement (1) can only be false in an infinite model of MA and all infinite models of MA are non-standard.

Let $G(n) = Ex( (x \neq 0 \land x+x=0 \bmod n) \lor (x+x=1 \bmod n) )$

Let $M_2$ be a model of PA that has $Z_2$ as a definable initial segment. There exists $x \in M_2$ such that $G(x)$ is false. Since $x$ must be non-standard, $M_2$ can prove itself non-standard. If PA is consistent then no model of PA can prove itself non-standard.

$Z_2$ can not be a definable initial segment of any model of PA.

I find this result surprising. If valid, this shows MA has models that are not definable initial segments of any model of PA.