Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Why is (1) a copy of $\mathbb{N}$ "followed by" a copy of $\mathbb{Z}$ not a (non-standard) model of arithmetic, neither (2) a copy of $\mathbb{N}$ followed by an infinite sequence of copies of $\mathbb{Z}$, but (3) a copy of $\mathbb{N}$ followed by infinitely many densely ordered copies of $\mathbb{Z}$ is? (see the Wikipedia entry on non-standard models)

Can this intuitively be seen, or be explained in laymans terms?

The axioms concerning the successor function hold in all of these (pseudo-)models, don't they?

But the induction axiom really puzzles me! Naively, it can be interpreted as describing essentially an infinite row of dominoes: knocking over the first will let fall all of them. How can this be understood in the non-standard model (3), where there is no immediate "contact" between the building blocks? What's the "true" interpretation of induction then? And why does it work in (3) but not in (2) or (1)?

share|improve this question
2  
Something is a model of arithmetic if and only if it satisfies the Peano axioms (I assume you are talking about the Peano axioms). The only axiom that is somewhat nontrivial to verify is the induction axiom. Naive induction is second-order; the induction allowed by the Peano axioms, which are first-order, is restricted (and that's why nonstandard models exist at all). It only applies to subsets that can be described by the language (so only countably many subsets). –  Qiaochu Yuan May 6 '11 at 14:30
    
"That's why nonstandard models exist at all" clarifies a lot to me. And it's a good slogan. Thanks. –  Hans Stricker May 6 '11 at 15:51

1 Answer 1

up vote 15 down vote accepted

${\mathbb N}$ is more than an ordered set with successor. You have addition (and multiplication) as well. Let $M$ be a nonstandard model; we can identify its beginning with ${\mathbb N}$. Given $n\in M$ let $[n]$ be the collection of all $m$ that are at finite distance from $n$. Note $[n]={\mathbb N}$ if $n$ is finite, and otherwise $[n]$ has the same order type as ${\mathbb Z}$, because every number has a successor, and every number other than zero has a predecessor.

If $n$ is an infinite nonstandard number, then $n+n$ is also infinite but, moreover, it is infinitely away from $n$, so just from $M$ being nonstandard we deduce that there is no largest copy of ${\mathbb Z}$ in the order of $M$.

Also, either $n$ or $n+1$ is even, so there is an $m$ such that $m+m=n$ or $m+m=n+1$. This $m$ is infinite, so the copy $[m]$ of ${\mathbb Z}$ is before the copy $[n]$. This shows that there is no first copy of ${\mathbb Z}$ in $M$.

Finally, given $n<k$ and infinitely apart, $n+k$ or $n+k+1$ is even, and if $l$ is its half, then $n<l<k$, and $l$ is infinitely apart from both. This shows that between any two copies of ${\mathbb Z}$ we have another.

We have shown that, removing the original ${\mathbb N}$, and taking the quotient that identifies all elements in a class $[n]$ as a single point, we are left with a linear order that is dense in itself and has no end points. If $M$ is countable, this order is ${\mathbb Q}$. Otherwise, it is even more complicated.

share|improve this answer
    
But note we use a few instances of induction in the argument I gave. If all we have is a successor operation, then we don't even have a linear order, and the classes $[n]$ do not need to be related to one another. –  Andres Caicedo May 6 '11 at 14:51
3  
It is worth saying that if you consider Presburger arithmetic (just forget about multiplication, and take the corresponding fragment of Peano arithmetic) then you can have non-standard models of the following kind: a copy of $\mathbb{N}$ followed by a discretely-ordered infinite sequence of copies of $\mathbb{Z}$. –  boumol May 6 '11 at 14:53
    
Thanks, boumol. And something I unfortunately know not much about is what restrictions the order type may have when $M\models$PA is uncountable. –  Andres Caicedo May 6 '11 at 15:01
1  
Hans: You said it yourself: "succesor (+induction)"; that is more than "successor". You need induction in order for the defining axioms of addition to uniquely characterize addition. –  Andres Caicedo May 6 '11 at 16:57
1  

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.