## 4.7. Non-standard models of Arithmetic

### Standard and non-standard numbers

Since the induction axiom needed to determine the isomorphism class of ℕ depends on ℘(ℕ), the relativity of ℘ allows a diversity of non-isomorphic models of arithmetic respectively defined by the diverse models of any consistent first-order theory T which contains arithmetic. Many theories may be picked in the role of T, such as a set theory seen as a first-order theory, thus involving other notions than numbers (to define more sets of numbers than arithmetically defined classes). All we shall assume here is that 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:

• It satisfies the full induction axiom (in terms of powerset);
• It is isomorphic to ℕ (also called the standard model of arithmetic);
• All its elements are standard.
We shall abbreviate some works of first-order logic by set theoretical notations as follows :
• Each meta-number n∈ℕ will be confused with the ground term "Sn(0)" and its value as a standard number;
• The quantifier "∀n∈ℕ" at the root of a formula, means to declare a schema of one formula per value of n in ℕ;
• For each n∈ℕ, the quantifier ∀x<n (resp. ∃x<n) can equivalently be read using x as an object (∀x, x<n ⇒), or as a string of conjunctions (resp. disjunctions) of n copies of the sub-formula with each value of x as a meta-number lower than n.

### 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
• A constant symbol k with range N (which may need the axiom kN);
• The schema of axioms nk for each n∈ℕ, making the number k non-standard.
If T is consistent then T' is also consistent (and cannot prove more), as any finite list of axioms of T' can be satisfied in any model of T (by interpreting k as a different number). Thus, T' also has a model, which is a model of T where N is non-standard.

This means that no consistent extension of arithmetic can ever force its model of arithmetic to be standard, i.e. require induction to apply to the full powerset of N, which it cannot ensure to exhaust by its classes. Candidate "standardness" predicates may be introduced but still cannot be forced to coincide with the true standardness (N0), which may stay a meta-set beyond all classes.

Any model of arithmetic obtained as described in the proof of the completeness theorem from any consistent extension of arithmetic, will necessarily be non-standard, as it cannot even be elementarily equivalent to ℕ according to the truth undefinability theorem. Skolem's paradox still holds in two ways:
• the meta-countable set P interpreting "℘(ℕ)", whose elements serve as subsets of N, still cannot exhaust ℘(N) which is also meta-uncountable (on the meta level, bijections between sets N and ℕ induce bijections between their powersets, which preserve uncountability);
• the image of P projected to ℘(ℕ) by taking preimages by the embedding from ℕ to N, does not fill ℘(ℕ) either.
Non-standard models behave much like standard ones, as they satisfy all consequences of induction. Their precise range of diversity depends on the chosen theory of arithmetic.

### Non-standard models of bare arithmetic

The only "addition" definable from S, is the meta-operation adding any n∈ℕ to any xN as x + n = Sn(x), that is the meta-sequence of functions (Sn)n∈ℕ each defined in the theory by a unary S-term n. The consequences of the induction schema in bare arithmetic can be summed up as
• The bijectivity of N as a {0,S}-algebra, which implies the bijectivity of S on the set of non-standard numbers
• The schema of formulas ∀n∈ℕ*, ∀xN, x + nx which is a weak version of (F).
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 this ℤ-set to be free. Conversely, the disjoint union of ℕ with any free ℤ-set, forms a model of bare arithmetic.
Applying both ways the definition of the order from the partial meta-operation of addition, gives two ordering results with non-standard numbers:
• Each ℤ-orbit of non-standard numbers has its own total order.
• Each non-standard number is greater than each standard number, thus may be called «infinitely big».
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 to define addition either, 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 schema 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 schema 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 schema of induction:

• The subtraction of a number by a lower number (or the absolute value of subtraction), which was implicit in the definition of the order and the proof that it is total;
• The sequence of functions (xx:d) of Euclidean division by each d∈ℕ*.
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 (but 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:
• k/k' may be infinitely large or infinitely small;
• It may be close to an irrational number
• But the cases when it is close to a rational number a/b for standard numbers a, b, are reducible to other cases:
• If the difference between bk and ak' is standard then the model is actually generated by only one element (any non-standard element is a generator).
• If this difference is non-standard then, replacing one generator by this difference, reduces this model to the first case.

Set theory and foundations of mathematics
1. First foundations of mathematics
2. Set theory (continued)
3. Algebra 1
4. Arithmetic and first-order foundations
4.1. Algebraic terms
4.2. Term algebras
4.3. Integers and recursion
4.4. Presburger Arithmetic
4.5. Finiteness and countability
4.6. The Completeness Theorem
4.7. Non-standard models of Arithmetic
4.8. Developing theories : definitions
4.9. Constructions
5. Second-order foundations
6. Foundations of Geometry