Non-standard model of arithmetic: Difference between revisions

Content deleted Content added

Inline

Latest revision as of 21:48, 27 December 2023

In mathematical logic, a non-standard model of arithmetic is a model of first-order Peano arithmetic that contains non-standard 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 non-standard model is one that has additional elements outside this initial segment. The construction of such models is due to Thoralf Skolem (1934).

Non-standard models of arithmetic exist only for the first-order formulation of the Peano axioms; for the original second-order formulation, there is, up to isomorphism, only one model: the natural numbers themselves.^[1]

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

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 neither 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 non-standard 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 and any infinite cardinality there is a model of arithmetic with G true and of that cardinality.

Arithmetic unsoundness for models with ~G true

Assuming that arithmetic is consistent, arithmetic with ~G is also consistent. However, since ~G states 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 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} }$ . Choose an ultrafilter on $\mathbb {N}$ , then identify two sequences whenever they have equal values on positions that form a member of the ultrafilter (this requires that they agree on infinitely many terms, but the condition is stronger than this as ultrafilters resemble axiom-of-choice-like maximal extensions of the Fréchet filter). The resulting semiring is a non-standard model of arithmetic. It can be identified with the hypernatural numbers.^[2]

Structure of countable non-standard 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 non-standard models of arithmetic. One way to define such a model is to use Henkin semantics.

Any countable non-standard 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 non-standard 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 blocks of non-standard 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.^[3]^[4]^[5]

So, the order type of the countable non-standard 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 a nonstandard (non-finite) element u is in the model, then so is m ⋅ u for any m in the initial segment N, yet u² is larger than m ⋅ u for any standard finite m.

Also one can define "square roots" such as the least v such that v² > 2 ⋅ u. These cannot be within a standard finite number of any rational multiple of u. By analogous methods to non-standard analysis one can also use PA to define close approximations to irrational multiples of a non-standard number u such as the least v with v > $π$ ⋅ u (these can be defined in PA using non-standard finite rational approximations of $π$ even though $π$ itself cannot be). Once more, v − (m/n) ⋅ (u/n) has to be larger than any standard finite number for any standard finite m, n. ^{[citation needed]}

This shows that the arithmetical structure of a countable non-standard 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 non-standard 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 computable on the codes. This result was first obtained by Stanley Tennenbaum in 1959.

References

Citations

^ Hans Hermes (1973). Introduction to Mathematical Logic. Hochschultext. London: Springer. ISBN 3540058192. ISSN 1431-4657. Here: Ch. VI.3
^ Goldblatt, Robert (1998), "Ultrapower Construction of the Hyperreals", Lectures on the Hyperreals, New York: Springer, pp. 23–33, doi:10.1007/978-1-4612-0615-6_3
^ Andrey Bovykin and Richard Kaye Order-types of models of Peano arithmetic: a short survey June 14, 2001
^ Andrey Bovykin On order-types 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
^ Fred Landman LINEAR ORDERS, DISCRETE, DENSE, AND CONTINUOUS – includes proof that Q is the only countable dense linear order.

Sources

Boolos, George, and Jeffrey, Richard 1974. Computability and Logic, Cambridge University Press. ISBN 0-521-38923-2.
Skolem, Thoralf (1934). "Über die Nicht-charakterisierbarkeit der Zahlenreihe mittels endlich oder abzählbar unendlich vieler Aussagen mit ausschließlich Zahlenvariablen" (PDF). Fundamenta Mathematicae (in German). 23 (1): 150–161. doi:10.4064/fm-23-1-150-161.

@@ Line 1: / Line 1: @@
+{{Short description|Model of (first-order) Peano arithmetic that contains non-standard numbers}}
-{{Refimprove}}
+{{Use dmy dates|date=February 2015}}
+{{Refimprove|date=July 2012}}
+In [[mathematical logic]], a '''non-standard model of arithmetic''' is a model of [[Peano axioms#Peano arithmetic as first-order theory|first-order Peano arithmetic]] that contains non-standard 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 non-standard model is one that has additional elements outside this initial segment.  The construction of such models is due to [[Thoralf Skolem]] (1934).
+Non-standard models of arithmetic exist only for the first-order formulation of the [[Peano axioms]]; for the original second-order formulation, there is, up to isomorphism, only one model: the [[natural numbers]] themselves.<ref>{{cite book | issn=1431-4657 | isbn=3540058192 | author=Hans Hermes | title=Introduction to Mathematical Logic | location=London | publisher=Springer | series=Hochschultext | volume= | year=1973 }} Here: Ch. VI.3</ref>
-In [[mathematical logic]], a '''nonstandard model of arithmetic''' is a model of (first-order) [[Peano axioms|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).
 == Existence ==
@@ Line 11: / Line 13: @@
 === 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'' &gt; ''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.
+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'' &gt; ''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.
+Using more complex methods, it is possible to build non-standard 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 non-standard.
 === 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 neither provable nor disprovable in Peano arithmetic. By the [[Gödel's completeness theorem|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 non-standard 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'' and any infinite [[cardinality]] there is a model of arithmetic with ''G'' true and of that cardinality.
+====Arithmetic unsoundness for models with ~''G'' true====
+Assuming that arithmetic is consistent, arithmetic with ~''G'' is also consistent. However, since ~''G'' states that arithmetic is inconsistent, the result will not be [[ω-consistent]] (because ~''G'' is false and this violates ω-consistency).
-[[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 [[Gödel's completeness theorem|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.
+=== From an ultraproduct ===
-Using Gödel's original "Gödel numbering" system, one can, for any first-order statement, come up with a corresponding new statement asserting various numeric relationships between ordinary natural numbers - effectively creating an imitation of PA within PA itself. One can use this system to encode very complex metamathematical propositions, such as the notion of a sequence of statements being a "valid proof" of a theorem from the PA axioms, or the notion of one sequence of statements being a proof of another, final statement, or of a valid proof existing of a certain statement at all. These statements can also be encoded as statements asserting the existence of certain equality and prime factorization relationships on the natural numbers. <ref>See translation of Gödel's original paper here: [http://researcher.ibm.com/files/us-hirzel/canon00-goedel.pdf]. It can be seen from the definitions of proofFor, isProofFigure, immConseq, imp and item that the ultimate encoding of the "provable" proposition asserts the existence of a number satisfying a series of equality, prime factorization, and other numeric relationships.</ref> The "G" sentence is formed from the initial proposition that "no sequence of statements exists which is a proof of G." When translated using Gödel's numbering system, this effectively becomes a statement postulating that no natural number exists which satisifies a certain set of these numeric relationships.
+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, <math>\mathbb{N}^{\mathbb{N}}</math>. Choose an [[Ultrafilter#Ultrafilter_on_the_power_set_of_a_set|ultrafilter]] on <math>\mathbb{N}</math>, then identify two sequences whenever they have equal values on positions that form a member of the ultrafilter (this requires that they agree on infinitely many terms, but the condition is stronger than this as ultrafilters resemble axiom-of-choice-like maximal extensions of the Fréchet filter). The resulting [[semiring]] is a non-standard model of arithmetic.  It can be identified with the [[hypernatural]] numbers.<ref>{{citation
-It can correspondingly be shown that no standard number satisfies the numeric conditions that correspond to the ''G''-proof-encoding numeric property in question. However, one can construct a model in which the Gödel sentence is false, thus asserting there is indeed a necessarily nonstandard "number" which is defined as simply satisfying the abstract numeric relationships in question, despite that this number loses the interpretation of encoding an actual proof of something. In these models, although such a number is defined as existing, it simply satisfies these numeric relationships without in any way correlating to an actual proof of ''G''.
+ | last = Goldblatt | first = Robert|authorlink = Robert Goldblatt
+ | contribution = Ultrapower Construction of the Hyperreals
+ | doi = 10.1007/978-1-4612-0615-6_3
+ | pages = 23–33
+ | publisher = Springer | location = New York
+ | title = Lectures on the Hyperreals
+ | year = 1998}}</ref>
+== Structure of countable non-standard models ==
-The same applies to Gödel's second incompleteness theorem, which asserts that PA is undecided on whether there may exist numbers which "encode a proof" of statements which would conflict with the PA axioms, such as 1=0.<ref name="Grandy1979">{{cite book|author=Richard E. Grandy|title=Advanced Logic for Applications|url=http://books.google.com/books?id=ItgJhsGE-RAC&pg=PA72|accessdate=9 July 2012|date=1 June 1979|publisher=Springer|isbn=978-90-277-1034-5|pages=72–}}</ref> There are necessarily nonstandard models of PA in which such numbers do exist - however, as with ''G'', these numbers are simply defined as satisfying the set of numeric relationships corresponding to the Gödel encoding of the metamathematical propositions in question, without having any bearing on whether the actual metamathematical propositions are true.
+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 non-standard models of arithmetic. One way to define such a model is to use [[Second-order logic#Semantics|Henkin semantics]].
-It is noteworthy that the existence of the above models doesn't imply that they're inconsistent: while statements such as 0=1 which are provably false in PA are false in every nonstandard model, the above models show that particular systems of Gödel numbering may map these false statements onto propositions which nonstandard numbers satisfy, rather than which no numbers of any kind satisfy.{{dubious}} The above formal systems are sometimes called ω-inconsistent, which should be noted is not the same as formal inconsistency: a theory being ω-inconsistent simply means that it's not satisfied by the standard model of arithmetic (and hence that only non-standard models of it exist).
+Any [[countable]] non-standard model of arithmetic has [[order type]] {{nowrap|ω + (ω* + ω) &sdot; η}}, 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 non-standard 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 {{nowrap|ω* + ω}}, 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 blocks of non-standard numbers have to be [[Dense_order|dense]] and linearly ordered without endpoints, and [[Total order#Examples|the order type of the rationals is the only countable dense linear order without endpoints]].<ref>''Andrey Bovykin and Richard Kaye'' [http://web.mat.bham.ac.uk/R.W.Kaye/papers/survey6.pdf Order-types of models of Peano arithmetic: a short survey] June 14, 2001</ref><ref>''Andrey Bovykin'' [http://logic.pdmi.ras.ru/~andrey/phd.pdf On order-types 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</ref><ref>[[Fred Landman]] [http://www.tau.ac.il/~landman/Online_Class_Notes_file/Boolean/1%20%20Linear%20orders,%20discrete,%20dense%20and%20continuous.pdf LINEAR ORDERS, DISCRETE, DENSE, AND CONTINUOUS] – includes proof that '''Q''' is the only countable dense linear order.</ref>
-It's also notable that while PA + ~G is a concrete example of a theory with only nonstandard models of it, that this not the most common or useful way to generate non-standard models of PA. Other axioms are instead often used to assert the existence of a non-standard number in the theory and so force its models to be non standard. Note also that there exist non-standard models for PA + G, of all cardinalities, as well, but the difference is that PA + ~G has only nonstandard models whereas PA + G is supported by the standard model as well.
+So, the order type of the countable non-standard models is known. However, the arithmetical operations are much more complicated.
-=== From an ultraproduct ===
+It is easy to see that the arithmetical structure differs from {{nowrap|ω + (ω* + ω) &sdot; η}}. For instance if a nonstandard (non-finite) element ''u'' is in the model, then so is {{nowrap|''m'' &sdot; ''u''}} for any ''m'' in the initial segment '''N''', yet ''u''<sup>2</sup> is larger than {{nowrap|''m'' &sdot; ''u''}} for any standard finite ''m''.
-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, <math>\mathbb{N}^{\mathbb{N}}</math>.  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.
+Also one can define "square roots" such as the least ''v'' such that {{nowrap|''v''<sup>2</sup> > 2 &sdot; ''u''}}.  These cannot be within a standard finite number of any rational multiple of ''u''. By analogous methods to [[non-standard analysis]] one can also use PA to define close approximations to irrational multiples of a non-standard number ''u'' such as the least ''v'' with {{nowrap|''v'' > {{pi}} &sdot; ''u''}} (these can be defined in PA using non-standard finite [[Approximations of π|rational approximations of {{pi}}]] even though {{pi}} itself cannot be). Once more, {{nowrap|''v'' − (''m''/''n'') &sdot; (''u''/''n'')}} has to be larger than any standard finite number for any standard finite ''m'', ''n''.  {{Citation needed|date=September 2012}}   <!-- Something like this has to be said here otherwise reader will get the wrong impression that it is arithmetically the same – however would be good to have a reference – the way I describe it here could be considered original research, so need to find a citation that explains this clearly -->
-== Structure of countable non-standard models ==
+This shows that the arithmetical structure of a countable non-standard 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 non-standard 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 [[recursion theory|computable]] on the codes. This result was first obtained by [[Stanley Tennenbaum]] in 1959.
-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 ω*&nbsp;+&nbsp;ω, the order type of the integers. These blocks are in turn densely ordered with the order type of the rationals.
+== References ==
-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 [[recursion theory|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.
+=== Citations ===
+{{reflist}}
-==References==
+=== Sources ===
+{{refbegin}}
-* Boolos, G., and Jeffrey, R. 1974. ''Computability and Logic'', Cambridge University Press. ISBN 0-521-38923-2
+* [[Boolos, George]], and [[Jeffrey, Richard]] 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&ndash;161.
+* {{cite journal|url = http://matwbn.icm.edu.pl/ksiazki/fm/fm23/fm23115.pdf  |last = Skolem |first = Thoralf|title = Über die Nicht-charakterisierbarkeit der Zahlenreihe mittels endlich oder abzählbar unendlich vieler Aussagen mit ausschließlich Zahlenvariablen |language = de |journal=[[Fundamenta Mathematicae]] |volume=23 |number=1 |pages = 150–161 |year =1934|doi = 10.4064/fm-23-1-150-161 }}
+{{refend}}
-==Citations==
+==See also==
+*[[Non-Euclidean geometry]] &mdash; about non-standard models in geometry
-{{reflist}}
+{{Mathematical logic}}
 [[Category:Arithmetic]]
 [[Category:Formal theories of arithmetic]]
+[[Category:Mathematical logic]]
 [[Category:Model theory]]
-[[Category:Non-standard analysis]]
-[[es:Aritmética no estándar]]
-[[fr:Arithmétique non standard]]