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,
n↦SNn(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 k∈N);
- The schema of axioms n ≠ k 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 x∈N 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∈ℕ*, ∀x∈N,
x + n ≠ x 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
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 schema 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 schema 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 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 (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
(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,
rd⋅n = d⋅h + 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 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.
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
n∈N, 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
5. Second-order foundations
6. Foundations of Geometry