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.

I've learned that there are (at least) three types of countable non-standard models of arithmetic, depending on the primitive operations:

  1. successor only → $\mathbb{N}$ followed by a copy of $\mathbb{Z}$ (due to Dedekind, see here or here)
  2. successor + addition → $\mathbb{N}$ followed by a discretely-ordered infinite sequence of copies of $\mathbb{Z}$
  3. successor + addition + multiplication → $\mathbb{N}$ followed by a densely-ordered infinite sequence of copies of $\mathbb{Z}$

[Thanks to Andres and boumol for explaining the order type in cases (2) and (3)]

In any case there are numbers inaccessible from 0 by finite application of the successor function.

What I still don't understand is: Isn't the axiom (schema) of induction saying that one can reach every number from 0 by finite application of the successor function? It seems to say this at first sight, but it actually doesn't. But what else does it say then, i.e. what are equivalent formulations making it clearer why there are non-standard models? And how then can the inaccessible numbers "inherit" their properties from 0? (Or isn't the induction axiom about inheritance?)

Heuristic guess: The induction axiom schema doesn't talk about finite application of the successor function, and by applying the successor function infinitely often one can pass from the $\mathbb{N}$ part to the $\mathbb{Z}$ part (but obviously one does not have to).

Another question: In which respect exactly is the first order axiom schema of induction weaker than its second order counterpart which outrules non-standard models? (I know that there are uncountably many subsets of $\mathbb{N}$ but only countable many definable ones, but is this all there is to say?) Does the second order axiom actually say that every number can be finitely reached from 0 (and the first order axiom fails to say this)?

share|improve this question

1 Answer 1

up vote 5 down vote accepted

What I still don't understand is: Isn't the axiom (schema) of induction saying that one can reach every number from 0 by finite application of the successor function? It seems to say this at first sight, but it actually doesn't.

It doesn't say that at all. The axiom schema of induction says, more or less, that any formula which is true for $0$ and which is true for $S(x)$ if it's true for $x$ is true for all $x$. The statement "$x$ can be reached from $0$ by applying the successor function finitely many times" is not a first-order formula, so it isn't covered. (Indeed, you can prove that no first-order formula with this property exists precisely by constructing a non-standard model of Peano arithmetic.)

by applying the successor function infinitely often one can pass from the N part to the Z part (but obviously one does not have to).

You can't get to the non-standard part of a non-standard model from $0$ using the successor function at all. Any finite application will give you a standard integer and applying the successor function "infinitely often" doesn't make sense without significant qualification about what this means.

share|improve this answer
    
You paraphrase the axiom schema not "more or less" but verbatim. But I am looking for a paraphrase that reveals what is tried to be said and why it fails. (I guess what is tried to be said is that the natural numbers form an infinite sequence.) –  Hans Stricker May 10 '11 at 9:51
    
How then can the induction axiom (schema) hold? How then can the non-standard numbers "inherit" their properties from 0? –  Hans Stricker May 10 '11 at 9:52
    
@Hans: I say "more or less" because I didn't mention parameters. I don't understand your first question; I can't think of a clearer way to say what the induction axiom says than what I just said. To answer your second question, they "inherit" their properties by the induction axiom because the induction axiom is true, by definition, in any non-standard model. I think your confusion will be resolved if you learn how to actually construct non-standard models (e.g. using the compactness theorem). –  Qiaochu Yuan May 10 '11 at 9:58
    
Can definitely no sense be made of this line of reasoning? One wants to capture the idea that the natural numbers are a "simple infinite system" (Dedekind) and tries one's best by the axiom (schema) of induction (which sounds very different, but tries to say essentially this). But alas, in first order it doesn't work. But hooray, in second order it works (and is indeed equivalent to the fact that the so defined natural numbers form a simple infinite system). –  Hans Stricker May 10 '11 at 13:06

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.