I confused myself and the OP when I tried to answer a recent question. Modular arithmetic (MA) has the same axioms as first order PA except $\forall x(Sx \neq 0)$ is replaced with $\exists x(Sx=0)$. Every model of PA has exactly one model of MA for each natural number. In Even XOR Odd Infinities? I asked if every model of MA is exclusively even or exclusively odd. 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$. The hardest part of the proof was showing induction is valid in $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 exclusive or to an inclusive or.
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 our $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.
Is $Z_2$ is an initial segment of some model of PA? If so, is statement (2) true in this model?
Best Answer
Let me summarize what I said in the comments of my question thread. 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 of your statement 2 in $PA$:
$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 of $\forall x(\exists y(y+y=x) \overline{\vee} \exists y(y+y+1=x))$ in $PA$:
$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, for all $n$, $n$ is even XOR $n$ is odd.
I think the first proof would go through in $MA$ as well, but the second proof would not go through in $MA$, because the second proof uses the fact that $0$ is not the successor of any number.