4.9. 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:

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 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: 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 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: 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:

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:

On the definition of finiteness

Any definition of finiteness for a set E involves a universal quantifier in some powerset. The reason can be understood considering that for any model N of arithmetic and any nN, the finiteness of the set of elements lower than n is equivalent to the standardness of n, which involves a universal quantifier in ℘(N).

However, this definition only a priori qualifies a particular case : the existence of a model of arithmetic in which a set can be so inserted is questionable, especially if the axiom of infinity is not assumed. Our original definition was using ℘(℘(E)). One may consider this use of the powerset as excessive, and look for a more moderate one. It seems that ℘(E) does not suffice, but EE suffices. Namely, it can be used to express the finiteness of E as the existence of a Σ-term structure, or the existence of a permutation of E having E as a cycle. This still involves a universal quantifier in ℘(E) (which is definable from EE), hidden in the claim for a Σ-structure to be a Σ-term structure, or the claim for a given permutation to admit E as a cycle.

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