21
$\begingroup$

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)?

  • 3
    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).2011-05-06
  • 0
    "That's why nonstandard models exist at all" clarifies a lot to me. And it's a good slogan. Thanks.2011-05-06

1 Answers 1

21

${\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

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.

  • 0
    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.2011-05-06
  • 4
    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}$.2011-05-06
  • 0
    Thanks, boumol. And something I unfortunately know not much about is what restrictions the order type may have when $M\models$PA is uncountable.2011-05-06
  • 0
    Why is $\mathbb{N}$ **more** than an ordered set with successor (+ induction)? Isn't addition and multiplication *definable* on every such set?2011-05-06
  • 0
    @Hans: how do you define addition and multiplication on such a set?2011-05-06
  • 0
    By the axioms of addition and multiplication? (From which all the facts about addition and multiplication follow by induction.)2011-05-06
  • 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.2011-05-06
  • 0
    @Andres: Thank you very much for this demonstrative explanation. I think I got the picture!2011-05-06
  • 0
    By the way: My question mentioned explicitly the axiom of induction, which I never wanted to neglect!2011-05-06
  • 0
    @Andres: I've just learned that Dedekind found non-standard models with *any* number of copies of $\mathbb{Z}$. Shouldn't this be stressed explicitly: the non-standard models depend on which axioms you choose: (i) only successor (+induction) $\rightarrow$ any number of copies of $\mathbb{Z}$ (Dedekind), (ii) successor + addition (+induction) $\rightarrow$ discretely-ordered infinite sequence of copies of $\mathbb{Z}$ (Presburger), (iii) successor + addition + multiplication (+induction) $\rightarrow$ densily-ordered infinite sequence of copies of $\mathbb{Z}$ (Skolem)2011-05-09
  • 0
    @Hans: Nice finding; I didn't know the result was Dedekind's!2011-05-09
  • 1
    See http://books.google.com/books?id=v4tBTBlU05sC&pg=PA98&lpg=PA98&dq=wang+keferstein&source=bl&ots=KOfigLOiBS&sig=ri6YYMDB-sqhD3gilXucfnYzUvI&hl=en&ei=7fvHTZTYJ43GtAarh_WEDw&sa=X&oi=book_result&ct=result&resnum=1&ved=0CBUQ6AEwAA#v=onepage&q=wang%20keferstein&f=false and http://www.jstor.org/stable/29641762011-05-09
  • 0
    @Andres How do we have any structure, besides *possibly* the ordering of "less than", on N necessarily? How does N even have the successor operation on it *necessarily* to begin with? Presburger arithmetic, deals with N. The successor operation comes as a unary function. Presburger arithmetic has a binary function on N, and no unary functions. There doesn't exist any multiplication in Presburger arithmetic also.2011-06-13