4.3. Non-standard models of Arithmetic

Generalities; non-standard numbers

Since the set theoretical induction axiom needed to determine the isomorphism class of ℕ depends on ℘(ℕ), the relativity of the powerset of infinite sets leaves the possibility for first-order theories to admit non-isomorphic models of arithmetic. Beyond cases of first-order arithmetic using arithmetically defined classes as the only subsets, let us consider any consistent first-order theory T containing bare arithmetic (such as the case of set theory when looked at from the outside as a first-order theory): it has a notion N of "natural number" with a constant 0, a function symbol S, and axioms making N a model of bare arithmetic (in any model of T), thus a bijective {0,S}-algebra.

A number in N is called standard if it belongs to the minimal subalgebra N0 = Min{0,S}N, isomorphic to ℕ by the unique {0,S}-morphism (embedding, nSNn(0N)) from ℕ to N. So, it represents an element of ℕ, which may be called a meta-number.
A model N of arithmetic is called standard if it is a minimal {0,S}-algebra, which can be equivalently written in 3 ways:

We shall abbreviate some works of first-order logic by set theoretical notations as follows :

Existence of non-standard models

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), as any contradiction of T' would only use finitely many axioms, but any model of T can satisfy any finite list of axioms of T' by interpreting k as a different number. Thus, if T is consistent then T' also has a model, where N is non-standard.

But, since any consistent theory that includes arithmetic has non-standard models of it, no theory (regardless its additional notions, symbols and axioms), can ever force its model of arithmetic to be standard, i.e. require induction to apply to the full range of all «existing» subsets of N, beyond those represented in the model, whose exhaustivity remains uncontrollable. While a candidate "standardness" predicate may be added, there can still be models where the true standardness (N0) differs from it, being a mere meta-set beyond all classes of that theory.

As the truth undefinability theorem will show, the set N of "numbers" in any model constructed as described in the proof of the completeness theorem, cannot be elementarily equivalent to ℕ, thus must be non-standard. Skolem's paradox still holds in two ways:

Properties of non-standard models of Arithmetic

Non-standard models have common properties with standard ones, as they satisfy all formulas provable by induction. In details the range of diversity of these models depends on the chosen theory of arithmetic, as the 3 versions we mentioned are not equivalent. As each of bare arithmetic and Presburger arithmetic is a decidable theory, all models fall into only one class of elementary equivalence (all models have the same internally expressible properties) regardless their isomorphism class.

Non-standard models of bare arithmetic

The only "addition" definable from S beyond standard numbers is the meta-operation x + n = Sn(x), that is a sequence of functions with argument the number xN, indexed by the meta-number n∈ℕ which forms the defining term. The consequences of the axiom scheme of induction in bare arithmetic can be summed up as As the restriction of S to the meta-set N\N0 of non-standard numbers of any model is a permutation, N\N0 is a -set. The last formula obliges its orbits to be free, i.e. copies of ℤ as a ℤ-set. Conversely, the disjoint union of ℕ with any family of copies of ℤ, forms a model of bare arithmetic.
Applying both ways the definition of the order from the partial meta-addition, leads to two ordering results with non-standard numbers: Models of arithmetic with order, are formed as models of bare arithmetic with any choice of a total order on the partition of non-standard numbers in ℤ-orbits. Thus, bare arithmetic cannot suffice to define the order. But arithmetic with order cannot suffice either to define addition, as its non-standard models may either admit no or many corresponding interpretations of addition.

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 class of numbers has a smallest element (which the meta-set of non-standard numbers hasn't).

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∈ℕ : nx = x+...+x (with n occurrences of x)
Beyond commutativity, associativity and the seen properties of the order, the last independent consequence of the axiom scheme of induction constraining non-standard models, is the possibility of Euclidean division by any nonzero standard number (generalizing the results on parity) :

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

thanks to ∀d∈ℕ*, ∀qN, d⋅(q+1) = dq+d which is a scheme of theorems in Presburger arithmetic.
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:ddqx< d⋅(q+1) ⇔ ∃ r<d, x = dq + 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 as that of subalgebra generated by a subset for the "algebra" (not exactly an algebra, but...) with language completed, like in the proof of the completeness theorem, by additional operation symbols reflecting all existence properties deduced from the axiom scheme of induction:

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
(ak):d +b
where a,d ∈ℕ* and b∈ℤ (the cases where a,d are relative primes suffice).
The predicate of divisibility of xN by a d∈ℕ*, is defined as the case when the rest cancels: d|x ⇔ (∃qN, x = dq)

The possible shapes of these models with respect to k (classes of isomorphisms preserving k, described using it), are classified by the sequence (rd)d∈ℕ* of rests of the division of k by all standard numbers d. The possible sequences are those which satisfy not only rd<d but also the compatibility formulas : n,d ∈ℕ*, ∃h, rdn = dh + rd (where in fact h<n). The simplest one is where all rd are 0, i.e. where k is divisible by every standard number (the distinguishing property of this isomorphism class of models with 1 generator, "there exists a number divisible by every standard number", is inexpressible in Presburger arithmetic).

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:
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. Non-standard models of Arithmetic
4.4. How theories develop
4.5. Second-order logic
4.6. Well-foundedness and ordinals
4.7. Undecidability of the axiom of choice
4.8. Second-order arithmetic
4.9. The Incompleteness Theorem