Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
add comment

2 Answers 2

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.

share|improve this answer
add comment

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.

share|improve this answer
    
Can you explain why there must be an $x \in M_2$ such that $G(x)$ is false? Also, what does it mean for a model to prove itself nonstandard? –  Keshav Srinivasan Sep 30 '13 at 23:23
    
I assume every element of $Z_2$ maps to a unique natural number in $M_2$. Assume $-1 \in Z_2$ maps to $x-1 \in M_2$. Then $M_2 \bmod x$ is the same as $Z_2$. $G(x)$ must be false in $M_2$ because statement (1) is false for $Z_2$. $G(x)$ can only be false for non-standard natural numbers and $M_2$ can prove there is such an $x$. –  Russell Easterly Oct 3 '13 at 1:43
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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