Non-standard model of arithmetic


Non-standard model of 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. The existence of such models is due to Thoralf Skolem (1934).


Contents

Existence

There are several methods that can be used to prove the existence of non-standard models of arithmetic.

From the compactness theorem

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 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 which 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 ZFC 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 non-standard 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.

The Gödel sentence for Peano arithmetic says, in essence, "There is no coded proof of 0=1 from the axioms of Peano arithmetic". In a model where the Gödel sentence is false, there is such a coded proof (although the code is a nonstandard number). Because Peano arithmetic proves there is a coded proof of 0 \not = 1, and because Peano arithmetic is able to formalize the usual properties of the provability predicate, a nonstandard model in which the Gödel sentence fails will have a coded proof of every sentence in the language of arithmetic. This does not, however, mean that Peano arithmetic is inconsistent; it only shows that formalized provability within a model of PA may differ from actual provability.

From an ultraproduct

Another method for constructing a non-standard 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 which is a member of a fixed non-principal ultrafilter. The resulting ring is a non-standard model of arithmetic. It can be identified with the hypernatural numbers.

Structure of countable non-standard 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," each of order type ω* + ω, the order type of the integers. These blocks are in turn densely ordered with the order type of the rationals.

Although the order type of the countable nonstandard models is known, the arithmetical operations are much more complicated. Tennenbaum's theorem shows that there is no countable nonstandard model of Peano arithmetic in which either the addition or multiplication operation is computable. This result, first obtained by Stanley Tennenbaum in 1959, places a severe limitation on the ability to concretely describe the arithmetical operations of a countable nonstandard model.

References

  • Boolos, G., and Jeffrey, R. 1974. Computability and Logic, Cambridge University Press. ISBN 0-521-38923-2
  • Skolem, Th. (1934) Über die Nicht-charakterisierbarkeit der Zahlenreihe mittels endlich oder abzählbar unendlich vieler Aussagen mit ausschliesslich Zahlenvariablen. Fundam. Math. 23, 150–161.

Wikimedia Foundation. 2010.

Look at other dictionaries:

  • Non-standard model — See also Interpretation (logic) In model theory, a discipline within mathematical logic, a non standard model is a model of a theory that is not isomorphic to the intended model (or standard model). If the intended model is infinite and the… …   Wikipedia

  • Non-standard analysis — Abraham Robinson Gottfried Wilhelm Leibniz argued tha …   Wikipedia

  • 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, hellip;}. The… …   Wikipedia

  • Arithmétique non standard — En logique mathématique, un modèle non standard de l arithmétique est un modèle du premier ordre utilisant les axiomes de Peano qui contient les nombres non standards. Le modèle standard de l arithmétique contient l ensemble des nombres naturels… …   Wikipédia en Français

  • Constructive non-standard analysis — In mathematics, constructive nonstandard analysis is a version of Abraham Robinson s non standard analysis, developed by Moerdijk (1995), Palmgren (1998), Ruokolainen (2004). Ruokolainen wrote: The possibility of constructivization of nonstandard …   Wikipedia

  • Non-classical logic — Non classical logics (and sometimes alternative logics) is the name given to formal systems which differ in a significant way from standard logical systems such as propositional and predicate logic. There are several ways in which this is done,… …   Wikipedia

  • Model theory — This article is about the mathematical discipline. For the informal notion in other parts of mathematics and science, see Mathematical model. In mathematics, model theory is the study of (classes of) mathematical structures (e.g. groups, fields,… …   Wikipedia

  • Non-monotonic logic — A non monotonic logic is a formal logic whose consequence relation is not monotonic. Most studied formal logics have a monotonic consequence relation, meaning that adding a formula to a theory never produces a reduction of its set of consequences …   Wikipedia

  • Model selection — is the task of selecting a statistical model from a set of candidate models, given data. In the simplest cases, a pre existing set of data is considered. However, the task can also involve the design of experiments such that the data collected is …   Wikipedia

  • Arithmetic mean — In mathematics and statistics, the arithmetic mean, often referred to as simply the mean or average when the context is clear, is a method to derive the central tendency of a sample space. The term arithmetic mean is preferred in mathematics and… …   Wikipedia


Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”

We are using cookies for the best presentation of our site. Continuing to use this site, you agree with this.