Non-standard models of arithmetic for Dummies (2)
I've learned that there are (at least) three types of countable non-standard models of arithmetic, depending on the primitive operations:
- successor only → $\mathbb{N}$ followed by a copy of $\mathbb{Z}$ (due to Dedekind, see here or here)
- successor + addition → $\mathbb{N}$ followed by a discretely-ordered infinite sequence of copies of $\mathbb{Z}$
- 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)?
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.