Anyway, the system *N* interpreting "natural numbers" in any model
of a theory that includes bare arithmetic, is a model of bare arithmetic, thus a bijective
{0,*S*}-algebra.

The unique *f*∈Mor_{{0,S}}(ℕ,*N*),
denoted *n*↦*S _{N}^{n}*(0

A model *N* of arithmetic is called *standard* if it
is a minimal {0,*S*}-algebra, which can be equivalently written in 3 other
ways:

- It satisfies the full induction axiom (in terms of powerset);
- It is isomorphic to ℕ (also called
*the standard model of arithmetic*) and thus has all the same proprerties; - All its elements are standard.

- A constant symbol
*k*with range*N*(which may need the axiom*k*∈*N*); - The schema of axioms
*S*(0)≠^{n}*k*for each*n*∈ℕ, making the number*k*non-standard.

But the standardness of a model of arithmetic cannot be expressed
by any axioms even with any additional structures, since we just saw that any
consistent theory of arithmetic has non-standard models.
Therefore, no schema of first-order axioms can ever force the axiom of induction
to apply to the full range of all «existing» subsets of *N* beyond
those represented in the model. In particular, the property of «being a standard
number» in a model of a theory, remains able, in some models of any consistent
theory, to escape any given definition or representation by an object (such
as "a set" in a first-order interpretation of set theory).

Below is a brief review of these properties, abbreviating some works of first-order logic by set theoretical notations as follows :

- As root, ∀
*x*∈ℕ introduces a schema of formulas, one for each value of the meta-number*x*=*S*(0);^{x} - 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*x*.

- 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*,*S*(^{n}*x*) ≠*x*which is a version of (F).

The definition of the order in Presburger arithmetic can be applied in 2 ways to our partial meta-operation of addition, leading to 2 ordering results involving non-standard numbers:

- Each ℤ-slice of non-standard numbers has its own total order.
- Each non-standard number is greater than each standard number. Non-standard numbers may be called «infinitely big».

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 anThe last separate consequence of the axiom schema of induction constraining the form of non-standard models, is the possibility of Euclidean division by a nonzero standard number:

∀*d*∈ℕ*, ∀*x*∈*N*,
∃*q*∈*N*, ∃*r*<*d*, *x* = *q*⋅*d* + *r*

Moreover this (

∀*q*∈*N*,
*q*=*x*:*d* ⇔ *q*⋅*d*≤*x*<(*q*+1)⋅*d* ⇔ ∃
*r*<*d*, *x* = *q*⋅*d* + *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 by
applying the concept of subalgebra
generated by a subset to the "algebra" (not exactly an algebra, but...) with language completed, like in the proof of the completeness theorem, by operation symbols
which reflect all existence properties deduced from the axiom schema of induction. These operations are:

- The operation of subtraction of a number by a lower number (or absolute value of subtraction);
- The sequence of functions (
*x*↦*x*:*d*) of Euclidean division by each*d*∈ℕ*.

In particular, in any model of Preburger arithmetic generated by a single element (non-standard

The predicate

The possible shapes of these models, as described by formulas using

∀*n*,*d* ∈ℕ*, ∃*h*, *r*_{n⋅d}
= *h*⋅*d* + *r _{d}*

Anyway, Presburger Arithmetic is a decidable theory in the sense that all its ground formulas are decidable, determined as logical consequences of the axioms. This means it cannot distinguish the isomorphism classes of its models but sees them all as having the same internally expressible properties. For example, "there exists a number divisible by every standard number" would distinguish the latter model from most others, but cannot be expressed by any first-order formula with language 0,1,+.

The non-standard models generated by 2 non-standard numbers

*k*/*k'*may be infinitely large or infinitely small;- It may be an irrational number
- However the cases when it is close to a rational number
*a*/*b*, can be eliminated, differently between cases: - If the difference between
*k*⋅*b*and*k*'⋅*a*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.

Back to homepage : Set theory and foundations of mathematics

1. First foundations of mathematics

2. Set theory (continued)

3. Algebra 1

3.1. Morphisms of relational systems and concrete categories

3.2. Special morphisms

3.3. Algebras

3.4. Algebraic terms and term algebras

3.5. Integers and recursion

3.6. Arithmetic with addition

4.1. Finiteness and countability

4.2. The Completeness Theorem

4.3. Infinity and the axiom of choice

4.4.Non-standard models of Arithmetic

4.5. How theories develop

4.6. The Incompleteness Theorem