Non-standard Model of Arithmetic - Structure of Countable Non-standard Models

Structure of Countable Non-standard Models

The ultraproduct models are uncountable (since they are based on an infinite product of Z, so infinite sequences of numbers). 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 non-standard numbers have to be dense and linearly ordered without endpoints, and the rationals are the only countable dense linear order without endpoints.

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 u is in the model, then so is m*u for any m, n in the initial segment N, yet u2 is larger than m*u for any standard finite m.

Also you can define "square roots" such as the least v such that v2 > 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 Non-standard analysis you 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 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 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 there is no countable non-standard 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 non-standard model.