1
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ "The hardest part of the proof was showing induction is valid in Z2. " why? induction is an axiomscheme in PA so what is the problem in proving it? $\endgroup$ – Willemien Sep 17 '13 at 21:16
  • $\begingroup$ Induction is also an axiom schema in MA. To prove $Z_2$ is a model of MA requires proving induction is valid in $Z_2$. Proving induction is valid in a p-adic ring isn't easy. See the answer to my question on MO. $\endgroup$ – Russell Easterly Sep 18 '13 at 1:13
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ "0 is not the successor of any number" how do you get this? the question even mentions that there is a nummber whose successor is 0 . $\endgroup$ – Willemien Sep 17 '13 at 21:14
  • $\begingroup$ @Willemien I was giving proofs in $PA$, although I did mention at the end that the first proof carries over to $MA$ and the second does not. $\endgroup$ – Keshav Srinivasan Sep 18 '13 at 1:00
  • $\begingroup$ You prove a number can't be both even and odd. My question is about numbers that are neither even nor odd. Your statement is independent of MA. It is false in odd size models. Consider modulo 5: 0=0+0, 1=3+3, 2=1+1, 3=4+4, 4=2+2 mod 5. Every number is both even and odd in any odd size model of MA. $\endgroup$ – Russell Easterly Sep 18 '13 at 1:21
  • $\begingroup$ @RussellEasterly I proved two things in my answer. First I proved in PA that every number is even or odd, i.e. no number is neither even nor odd. That proof works just as well in MA. Then I proved in PA that no number is both even and odd. That proof does not work in MA, as you said. $\endgroup$ – Keshav Srinivasan Sep 18 '13 at 5:49
  • $\begingroup$ @KeshavSrinivasan sorry, but as logician I can hardly call it a proof at all (I would like a formal axiomatic proof) the OP defined MA as PA without $ \forall x (Sx \neq 0 ) $ (I think there is no need to add $ \exists x( Sx = 0) $ ) $\endgroup$ – Willemien Sep 19 '13 at 4:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.