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

In Peano Arithmetic, the induction axiom states that there is no proper subset of the natural numbers that contains 0 and is closed under the successor function. This is intended to rule out the possibility of extra natural numbers beyond the familiar ones. It doesn't accomplish that goal; there remains the possibility that other natural numbers exist and the familiar ones do not form a set. In Internal Set Theory (IST), which is an extension of ZFC that is consistent relative to ZFC, there is a distinction between standard and nonstandard sets, and it can be shown that

(1) 0 is standard;

(2) if $n \in \mathbb{N}$ is standard, then so is its successor;

(3) $\mathbb{N}$ has nonstandard elements.

The induction axiom is not violated because the standard natural numbers do not form a set.

Is there a way to axiomatize set theory so that no such nonstandard natural numbers can exist?

(Note: this question is not about nonstandard models of arithmetic. In IST, $\mathbb{N}$ is a standard set, and within a given model of IST, all models of second-order Peano arithmetic are isomorphic to $\mathbb{N}$.)

share|improve this question
1  
The intention of the induction axiom is not so much what you say but more to allow one to prove (standard) statements quantified over all natural numbers, and it does accomplish that goal. –  Lee Mosher Jul 2 '12 at 18:51
    
I just ran across the following article, with the charming title "INEXPRESSIBLE LONGING FOR THE INTENDED MODEL", which provides a rich historical backdrop to various attempts in answering this very question and variants: glli.uni.opole.pl/publications/L_006_en.pdf –  Ali Enayat Jul 7 '12 at 2:08
add comment

2 Answers 2

up vote 17 down vote accepted

As long as you axiomatize set theory in first-order logic, the answer to your question is no. The axioms would be consistent with each finite subset of the following set of sentences involving a new constant symbol $c$: "$c$ is a natural number" and "$c\neq n$" for each (standard name of a) natural number $n$. By compactness, there would be a model of the axioms plus all of these sentences, and in that model $c$ would denote a nonstandard natural number.

On the other hand, if you're willing to go beyond first-order logic, then the answer to your question is yes. For example, in second-order logic, you can express the induction axiom as a single sentence and be confident that "set" really means arbitrary set (not "internal set" or anything like that). In other words, once you're sure that "set" has its intended meaning, the induction principle guarantees that "natural number" also has its intended meaning. (To me, this doesn't look very helpful, since the intended meaning of "set" seems more complicated than the intended meaning of "natural number".)

For another example, if you're willing to use infinitary logic, then you can formulate the axiom "every natural number is equal to 0 or to 1 or to 2 or to 3, or ..."

share|improve this answer
1  
Also, the upwards Löwenheim–Skolem theorem states that, in first order theories of the natural numbers, there are always models with (uncountably many) nonstandard numbers. The proof of that can be done in just the same way as in the first paragraph of this answer. –  George Lowther Jul 2 '12 at 18:23
add comment

By Gödel's incompleteness theorem, there can't be any such axiom in a first-order, recursively enumerable theory.

You can axiomatize $\mathbb N$ by adding an infinitary rule of inference, the Hilbert $\omega$-rule:

$$P(0)\wedge P(1) \wedge P(2) \wedge \cdots \over \forall n P(n)$$

to PA for each arithmetic predicate P. This says, if predicate P holds for each of the natural numbers (0,1,2...) then you can deduce the formula $\forall n P(n)$. The resulting system is called ω-logic.

Obviously this is something of a "cheat" since you no longer have an effective theory. As one example (maybe there are better ones) of how it can be used, Michael Rathjen's article "The Art of Ordinal Analysis" describes using the $\omega$-rule to analyze stronger and stronger arithmetic theories, and is pretty interesting.

share|improve this answer
2  
The $\omega$-rule does not prohibit nonstandard models. If you add it to PA, you obtain the first-order theory of all statements in the language of arithmetic true in $\mathbb N$. In general, if you add it to a first-order theory, you obtain another first-order theory, since $\omega$-logic does not change the set of formulas. Thus, the result will still have nonstandard models by Andreas’ argument. $\omega$-logic is complete wrt $\omega$-models, and there are no nonstandard $\omega$-models, but this is not any deep property of the theory, but a matter of the definition: ... –  Emil Jeřábek Jul 3 '12 at 11:21
1  
... Basically, you first declare that you will only study standard models, and then of course, it should come as no surprise that all such models are standard. –  Emil Jeřábek Jul 3 '12 at 11:22
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.