Non-standard arithmetic

In mathematical logic, a nonstandard model of arithmetic is a model of (first-order) Peano arithmetic that contains nonstandard numbers. The standard model of arithmetic consists of the set of standard natural numbers {0, 1, 2, …}. The elements of any model of Peano arithmetic are linearly ordered and possess an initial segment isomorphic to the standard natural numbers. A nonstandard model is one that has additional elements outside this initial segment.

Existence

The existence of non-standard models of arithmetic can be demonstrated by an application of the compactness theorem. To do this, a set of axioms is defined in a language including the language of Peano arithmetic together with a new constant symbol "x". The axioms consist of the axioms of Peano arithmetic together with another infinite set of axioms: for each standard natural number "n", the axiom "x" > "n" is included. Any finite subset of these axioms is satisfied by the standard model of arithmetic, and thus by the compactness theorem there is a model satisfying all the axioms. The element of this model corresponding to "x" cannot be a standard number.

Using more complex methods, it is possible to build nonstandard models that possess more complicated properties. For example, there are models of Peano arithmetic in which Goodstein's theorem fails; because it can be proved in ZFC that Goodstein's theorem holds in the standard model, a model where Goodstein's theorem fails must be nonstandard.

Countable models

Any countable nonstandard model of arithmetic has order type ω + (ω* + ω) · η, where ω is the order type of the standard natural numbers, ω* is the dual order (an infinite decreasing sequence) and η is the order type of the rational numbers. In other words, a countable nonstandard model begins with an infinite increasing sequence (the standard elements of the model). This is followed by a collection of "blocks" of order type ω + ω*, the order type of the integers. These blocks are densely ordered with the order type of the rationals.

A result of Stanley Tennenbaum shows that there is no countable nonstandard model of Peano arithmetic in which either the addition or multiplication operation is computable. This places a severe limitation on the ability to constructively describe the structure of a countable nonstandard model.

References

Boolos, G., and Jeffrey, R. 1974. Computability and Logic. Cambridge: Cambridge University Press.