3.9. Non-standard models of Arithmetic

Generalities; non-standard numbers

As announced in 3.6, first-order formalizations of arithmetic are weaker than the first introduced set theoretical one with its induction axiom involving the powerset. This also goes for first-order theories larger than arithmetic, with other notions than "numbers", including set theory itself when looked at from the outside as a first-order theory.

Anyway, the system N interpreting "natural numbers" in any model of a theory that includes bare arithmetic, is a model of bare arithmetic, thus a bijective {0,S}-algebra.
The unique f∈Mor{0,S}(ℕ,N), denoted nSNn(0N), is injective with image the minimal subalgebra N0 = Min{0,S}N called the set of standard numbers in N, which can be seen as identified with ℕ by this morphism.

A model N of arithmetic is called standard if it is a minimal {0,S}-algebra, which can be equivalently written in 3 other ways:

Following the terminology of 1.7., N0 is only a meta-set, not representable by any object of the considered theory if N is non-standard. Elements of ℕ would also be called meta-numbers. This embedding of ℕ into N, provides another view on Skolem's paradox : the countable set of subsets of N interpreting "℘(ℕ)" not only cannot fill ℘(N), but by restricting "∈" to N0, they do not either fill the copy ℘(N0) of ℘(ℕ).

Existence of non-standard models

Let T be any consistent first-order theory containing arithmetic, having a notion N of "natural number" with a constant 0, a function symbol S, and axioms making N a bijective (0,S)-algebra in any model. The non-standardness of N is expressible by axioms on an additional structure, forming an extended theory T'. One way is to add This preserves consistency from T to T' (thus cannot increase provability), because any finite list of these axioms is satisfied by any model of T interpreting k as an Sn(0) outside that list. Thus, T' has a model, where N is non-standard.

But the standardness of a model of arithmetic cannot be expressed by any axioms even with any additional structures, since we just saw that any consistent theory of arithmetic has non-standard models. Therefore, no schema of first-order axioms can ever force the axiom of induction to apply to the full range of all «existing» subsets of N beyond those represented in the model. In particular, the property of «being a standard number» in a model of a theory, remains able, in some models of any consistent theory, to escape any given definition or representation by an object (such as "a set" in a first-order interpretation of set theory).

Properties of non-standard models of Arithmetic

The 3 versions of first-order arithmetic we mentioned differ on what shapes of non-standard models they allow. Non-standard models have common properties with standard ones, as they satisfy all formulas provable by induction. Those of bare arithmetic and Presburger arithmetic even satisfy all the same (ground) formulas, as all formulas in these theories are decidable from axioms.
Below is a brief review of these properties, abbreviating some works of first-order logic by set theoretical notations as follows :

Non-standard models of bare arithmetic

The only "addition" definable from S beyond standard numbers is the meta-operation of addition x+n = Sn(x) between the number xN and the standard number n∈ℕ (this is only an infinite list of functions, each separately defined in bare arithmetic). The consequences of the axiom schema of induction in bare arithmetic can be summed up as In every model, the set of non-standard numbers is naturally partitioned into copies of the set ℤ of integers. Conversely, any disjoint union of one copy of the standard ℕ and an arbitrary set of copies of ℤ, forms a model of bare arithmetic (a rigourous approach to such systems will be presented later).
The definition of the order in Presburger arithmetic can be applied in 2 ways to our partial meta-operation of addition, leading to 2 ordering results involving non-standard numbers: Models of arithmetic with order satisfying the needed properties, are determined as models of bare arithmetic with an arbitrary choice of a total order on the partition of non-standard numbers in ℤ-slices. Thus, bare arithmetic cannot suffice to define the order. But as such models may have no or several possible corresponding operations of addition, arithmetic with order cannot define addition either.

Non-standard models of Presburger Arithmetic

Such models satisfy all theorems of Presburger Arithmetic. In particular they have a well-defined total order, by which any non-standard number is greater than any standard number, and any non-empty definable set of numbers has a smallest element (while the set of non-standard numbers has no smallest element but is not definable).

Here are some more details only for the sake of illustration, which may be skipped.

There is also a meta-operation (sequence of functions) of multiplication of an xN by a standard number n∈ℕ : xn = x+...+x (with n occurrences of x)
The last separate consequence of the axiom schema of induction constraining the form of non-standard models, is the possibility of Euclidean division by a nonzero standard number:

d∈ℕ*, ∀xN, ∃qN, ∃r<d, x = qd + r

thanks to the formula (q+1)⋅d = qd+d which can be deduced by induction on d from the commutativity and associativity of +.
Moreover this (q,r) is unique; q = x:dN is called the quotient and r is called the rest of the division of an xN by a d∈ℕ*, so that

qN, q=x:dqdx<(q+1)⋅d ⇔ ∃ r<d, x = qd + r.

The concept of model of Preburger arithmetic generated by a set (of non-standard numbers, since standard ones have no generating effect), is defined by applying the concept of subalgebra generated by a subset to the "algebra" (not exactly an algebra, but...) with language completed, like in the proof of the completeness theorem, by operation symbols which reflect all existence properties deduced from the axiom schema of induction. These operations are:

They can be conceived either in the abstract (by evaluating relations arbitrarily, like in the proof of the completeness theorem) or as a subset of a given model (interpreting expressions there).
In particular, in any model of Preburger arithmetic generated by a single element (non-standard kN), the set of non-standard elements is the set of all values of expressions of the form
(ka):d +b
where a,d ∈ℕ* and b∈ℤ (the cases where a,d are relative primes suffice).
The predicate d|x of divisibility of x by d∈ℕ*, is defined as the case when the rest cancels: ∃qN, x = qd

The possible shapes of these models, as described by formulas using k, are classified by the sequence (rd)d∈ℕ* of rests of the division of k by all standard numbers d. The possibilities for this sequence satisfy not only rd<d but also a schema of formulas of pairwise compatibility : d|rndrd, i.e.

n,d ∈ℕ*, ∃h, rnd = hd + rd

(in fact h<n). Among such possible shapes of models, the simplest one is where all rd are 0, i.e. where k is divisible by every standard number. All non-standard numbers in this model can be written as (ka)/d + b for some a,d∈ℕ* and some b∈ℤ, where / is the exact division.

Anyway, Presburger Arithmetic is a decidable theory in the sense that all its ground formulas are decidable, determined as logical consequences of the axioms. This means it cannot distinguish the isomorphism classes of its models but sees them all as having the same internally expressible properties. For example, "there exists a number divisible by every standard number" would distinguish the latter model from most others, but cannot be expressed by any first-order formula with language 0,1,+.

The non-standard models generated by 2 non-standard numbers k,k' can be split into the following classification depending on what may be intuitively described as the (standard) real number which k/k' is infinitely close to:

Non-standard models of full first-order arithmetic

The ability of full arithmetic to express recursion has a counterpart : its complexity escapes itself any kind of clear recursive description comparable to that we just gave for non-standard models of the weaker forms of arithmetic. Namely, Tennenbaum's theorem forbids arithmetic from having any countable non-standard model where either addition or multiplication is computable, though arithmetically definable models can be produced by Gödel's encoding methods applied to the proof of the completeness theorem .

Back to homepage : Set theory and foundations of mathematics
1. First foundations of mathematics
2. Set theory (continued)
3. Algebra 1
4. Model Theory
4.1. Finiteness and countability
4.2. The Completeness Theorem
4.3. Infinity and the axiom of choice
4.4. Non-standard models of Arithmetic
4.5. How theories develop
4.6. The Incompleteness Theorem