In mathematical logic, a nonstandard model of arithmetic is a model of (firstorder) Peano arithmetic that contains nonstandard numbers. The term standard model of arithmetic refers to the 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. The construction of such models is due to Thoralf Skolem (1934).
Contents

Existence 1

From the compactness theorem 1.1

From the incompleteness theorems 1.2

Arithmetic unsoundness for models with ~G true 1.2.1

From an ultraproduct 1.3

Structure of countable nonstandard models 2

References 3

Citations 4
Existence
There are several methods that can be used to prove the existence of nonstandard models of arithmetic.
From the compactness theorem
The existence of nonstandard models of arithmetic can be demonstrated by an application of the compactness theorem. To do this, a set of axioms P* 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 P together with another infinite set of axioms: for each numeral n, the axiom x > n is included. Any finite subset of these axioms is satisfied by a model that is the standard model of arithmetic plus the constant x interpreted as some number larger than any numeral mentioned in the finite subset of P*. Thus by the compactness theorem there is a model satisfying all the axioms P*. Since any model of P* is a model of P (since a model of a set of axioms is obviously also a model of any subset of that set of axioms), we have that our extended model is also a model of the Peano axioms. The element of this model corresponding to x cannot be a standard number, because as indicated it is larger than any 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. It can be proved in Zermelo–Fraenkel set theory that Goodstein's theorem holds in the standard model, so a model where Goodstein's theorem fails must be nonstandard.
From the incompleteness theorems
Gödel's incompleteness theorems also imply the existence of nonstandard models of arithmetic. The incompleteness theorems show that a particular sentence G, the Gödel sentence of Peano arithmetic, is not provable nor disprovable in Peano arithmetic. By the completeness theorem, this means that G is false in some model of Peano arithmetic. However, G is true in the standard model of arithmetic, and therefore any model in which G is false must be a nonstandard model. Thus satisfying ~G is a sufficient condition for a model to be nonstandard. It is not a necessary condition, however; for any Gödel sentence G, there are models of arithmetic with G true of all cardinalities.
Arithmetic unsoundness for models with ~G true
Assuming that arithmetic is consistent, arithmetic with ~G is also consistent. However since ~G means that arithmetic is inconsistent, the result will not be ωconsistent (because ~G is false and this violates ωconsistency).
From an ultraproduct
Another method for constructing a nonstandard model of arithmetic is via an ultraproduct. A typical construction uses the set of all sequences of natural numbers, \mathbb{N}^{\mathbb{N}}. Identify two sequences if they agree for a set of indices that is a member of a fixed nonprincipal ultrafilter. The resulting semiring is a nonstandard model of arithmetic. It can be identified with the hypernatural numbers.
Structure of countable nonstandard models
The ultraproduct models are uncountable. One way to see this is to construct an injection of the infinite product of N into the Ultraproduct. However, by the Löwenheim–Skolem theorem there must exist countable nonstandard models of arithmetic. One way to define such a model is to use Henkin semantics.
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," each of order type ω* + ω, the order type of the integers. These blocks are in turn densely ordered with the order type of the rationals. The result follows fairly easily because it is easy to see that the nonstandard numbers have to be dense and linearly ordered without endpoints, and the order type of the rationals is the only countable dense linear order without endpoints.^{[1]}^{[2]}^{[3]}
So, the order type of the countable nonstandard models is known. However, the arithmetical operations are much more complicated.
It is easy to see that the arithmetical structure differs from ω + (ω* + ω) · η. For instance if u is in the model, then so is m*u for any m, n in the initial segment N, yet u^{2} is larger than m*u for any standard finite m.
Also you can define "square roots" such as the least v such that v^{2} > 2*u. It is easy to see that these can't be within a standard finite number of any rational multiple of u. By analogous methods to Nonstandard analysis you can also use PA to define close approximations to irrational multiples of a nonstandard number u such as the least v with v > π*u (these can be defined in PA using nonstandard finite rational approximations of π even though pi itself can't be). Once more, v  (m/n)*u/n has to be larger than any standard finite number for any standard finite m,n.
This shows that the arithmetical structure of a countable nonstandard model is more complex than the structure of the rationals. There is more to it than that though.
Tennenbaum's theorem shows that for any countable nonstandard model of Peano arithmetic there is no way to code the elements of the model as (standard) natural numbers such that either the addition or multiplication operation of the model is a computable on the codes. This result was first obtained by Stanley Tennenbaum in 1959.
References

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

Skolem, Th. (1934) Über die Nichtcharakterisierbarkeit der Zahlenreihe mittels endlich oder abzählbar unendlich vieler Aussagen mit ausschliesslich Zahlenvariablen. Fundam. Math. 23, 150–161.
Citations

^ Andrey Bovykin and Richard Kaye Ordertypes of models of Peano arithmetic: a short survey June 14, 2001

^ Andrey Bovykin On ordertypes of models of arithmetic thesis submitted to the University of Birmingham for the degree of Ph. D. in the Faculty of Science 13 April 2000

^  LINEAR ORDERS, DISCRETE, DENSE, AND CONTINUOUS  includes proof that Q is the only countable dense linear order.
This article was sourced from Creative Commons AttributionShareAlike License; additional terms may apply. World Heritage Encyclopedia content is assembled from numerous content providers, Open Access Publishing, and in compliance with The Fair Access to Science and Technology Research Act (FASTR), Wikimedia Foundation, Inc., Public Library of Science, The Encyclopedia of Life, Open Book Publishers (OBP), PubMed, U.S. National Library of Medicine, National Center for Biotechnology Information, U.S. National Library of Medicine, National Institutes of Health (NIH), U.S. Department of Health & Human Services, and USA.gov, which sources content from all federal, state, local, tribal, and territorial government publication portals (.gov, .mil, .edu). Funding for USA.gov and content contributors is made possible from the U.S. Congress, EGovernment Act of 2002.
Crowd sourced content that is contributed to World Heritage Encyclopedia is peer reviewed and edited by our editorial staff to ensure quality scholarly research articles.
By using this site, you agree to the Terms of Use and Privacy Policy. World Heritage Encyclopedia™ is a registered trademark of the World Public Library Association, a nonprofit organization.