Non-standard model of arithmetic: Difference between revisions
→Countable models: clarify |
|||
| Line 9: | Line 9: | ||
== Countable models == |
== 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. |
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. |
||
A [[Tennenbaum's theorem|result]] of Stanley Tennenbaum shows that there is no countable nonstandard model of Peano arithmetic in which either the addition or multiplication operation is [[recursion theory|computable]]. This places a severe limitation on the ability to constructively describe the structure of a countable nonstandard model. |
A [[Tennenbaum's theorem|result]] of Stanley Tennenbaum shows that there is no countable nonstandard model of Peano arithmetic in which either the addition or multiplication operation is [[recursion theory|computable]]. This places a severe limitation on the ability to constructively describe the structure of a countable nonstandard model. |
||
== Galaxy of a hypernatural number == |
== Galaxy of a hypernatural number == |
||
Revision as of 03:42, 9 August 2009
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 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 standard natural number 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 some largest number (named by 'x'), and 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, indeed as indicated it is a "largest" 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" each of order type ω* + ω, the order type of the integers. These blocks are in turn 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.
Galaxy of a hypernatural number
The galaxy of a hypernatural number is the set of hypernaturals to whose distance from it is a natural number :
References
Boolos, G., and Jeffrey, R. 1974. Computability and Logic. Cambridge: Cambridge University Press.