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 N_{0} = Min_{{0,S}}N,
isomorphic to ℕ by the unique {0,S}-morphism
(embedding,
n↦S_{N}^{n}(0_{N}))
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
"S^{n}(0)" and its value as a standard number;
- The quantifier "∀n∈ℕ" written as root of a formula, abbreviates the
declaration of a scheme
of formulas, one for each value of n;
- 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 n conjunctions (resp. disjunctions)
of copies of the sub-formula with the different values 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 k∈N);
- The scheme of axioms n ≠ k for each
n∈ℕ, making the number k non-standard.
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 (N_{0})
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:
- the meta-countable set P interpreting "℘(ℕ)", whose elements serve as
subsets of the interpretation N of "ℕ", still cannot exhaust the "true"
℘(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 restricting "∈" to N_{0}
(= preimage by n↦S_{N}^{n}(0_{N})),
does not fill ℘(ℕ) either.
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 = S^{n}(x), that is a sequence of functions with
argument the number x∈N, 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
- The bijectivity of N as a {0,S}-algebra, which
implies the bijectivity of S on the set of non-standard numbers
- The scheme of formulas
∀n∈ℕ*, ∀x∈N,
x + n ≠ x which is a weak version of (F).
As the restriction of S to the meta-set N\N_{0}
of non-standard numbers of any model is a permutation, N\N_{0}
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:
- 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 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
x∈N by a standard number n∈ℕ : n⋅x =
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∈ℕ*, ∀x∈N, ∃q∈N,
∃r<d,
x = d⋅q + r
thanks to ∀d∈ℕ*, ∀q∈N, d⋅(q+1) =
d⋅q+d which is a scheme of theorems in Presburger arithmetic.
Moreover this (q,r) is unique; q = x:d∈N
is called the quotient and r is called the rest of the division of an
x∈N by a d∈ℕ*, so that
∀q∈N,
q=x:d ⇔ d⋅q ≤ x< d⋅(q+1) ⇔ ∃
r<d, x = d⋅q + 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:
- 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 (x↦ x: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 k∈N), the set of non-standard elements is the set of
all values of expressions of the form (a⋅k):d +b
where a,d ∈ℕ* and b∈ℤ (the cases where a,d
are relative primes suffice).
The predicate of divisibility of x∈N by a d∈ℕ*, is defined as the
case when the rest cancels:
d|x ⇔ (∃q∈N, x = d⋅q)
The possible shapes of these models with respect to k (classes of isomorphisms
preserving k, described using it), are classified by the sequence
(r_{d})_{d∈ℕ*} of rests of the division of k by all
standard numbers d. The possible sequences are those which satisfy not only
r_{d}<d but also the compatibility formulas :
∀n,d ∈ℕ*, ∃h,
r_{d⋅n} = d⋅h + r_{d}
(where in fact h<n). The simplest one is where all r_{d}
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:
- 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 b⋅k and a⋅k'
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. 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