3.9. Integers and recursion
The set ℕ
Any theory aiming to describe the system ℕ of natural numbers is called an Arithmetic.
There are several of them, depending on the logical framework and the choice of
language. Let us start with the set theoretical arithmetic, which is the most precise
as it determines ℕ up to isomorphism, i.e. it is a definition of an isomorphism class of systems in
a given universe.
The use of algebra in this formalization may make it look circular, as our study of
algebras used natural numbers as
arities of operation symbols. But arithmetic only uses operation symbols with arity
0, 1 or 2, for which previous definitions might be as well written without reference to numbers.
Definition. ℕ is a ground term algebra with
two symbols: a constant symbol 0 ("zero"), and a unary symbol S.
This S is called the successor. Its meaning is to add one
unit (Sn=n+1) as will be seen below.
This definition can be explicited as the following list of 3 axioms on this
{0,S}algebra :
(H0) 
∀n∈ℕ, Sn ≠ 0

: 0 ∉ Im S 
(Inj) 
∀n,p∈ℕ, Sn =
Sp ⇒ n = p 
: S is injective 
(Ind) 
∀A⊂ℕ, (0∈A ∧ ∀n∈A,Sn∈A)
⇒ A=ℕ 
(induction) : ℕ is minimal. 
We can define 1=S0, 2=SS0...
The existence of a ground term {0,S}algebra is an equivalent form of the
axiom of infinity, which
completes the set theory we progressively introduced from the beginning to the powerset (with optionally the
axiom of choice), to form what is
essentially the standard foundation of mathematics as practiced by most mathematicians.
It is most conveniently expressed by an insertion of arithmetic into set theory,
in the form of the constant symbols of the set ℕ, its element 0 and its
transformation S, and the above axioms (from which more symbols such as
+ and ⋅ can then be defined). It will
be seen to imply the existence of term algebras of any language.
Fixing ℕ in its class does not cause any uncertainty thanks to the essential uniqueness
of initial {0,S}algebras.
Recursively defined sequences
A sequence of elements of a set E, is a function from ℕ to E
(a family of elements of E indexed by ℕ).
In particular, a recursive sequence in E is a sequence defined as the
only u∈E^{ℕ} such that u ∈ Mor(ℕ,(E,a,f)),
where (E,a,f) is the {0,S}algebra E
interpreting 0 as a∈E and S as f∈E^{E} :
u_{0}=a
∀n∈ℕ, u_{Sn} = f(u_{n}).
As u_{n} also depends on a and f, let us write it as
f^{ n}(a). This notation is motivated as follows.
As an element of a ground term {0,S}algebra, each number n represents a
term with symbols 0 and S respectively interpreted as a and f in E.
So, f^{ n}(a) abbreviates
the term with shape n using symbols a and f:
f^{ 0}(a) = a
f^{ 1}(a) = f(a)
f^{ 2}(a) = f(f(a)) 
Reinterpreting the constant 0 as a variable, makes ℕ a unary term
{S}algebra, where each number n is a unary term S^{n} with n
occurrences of S, interpreted in each {S}algebra (E,f)
as the function f^{ n}∈ E^{E}, recursively defined by
f^{ 0} = Id_{E}
∀n∈ℕ, f^{ Sn} = f০f^{ n}
In particular, f^{ 1}=f and f^{ 2} = f০f.
Generally for any f∈E^{E},
g∈E^{X}, the sequence (h_{n})_{n∈ℕ} in
E^{X} recursively defined by (h_{0}=g) and
(∀n∈ℕ, h_{Sn} = f০h_{n})
is h_{n}=f^{ n}০g.
Addition
Like any unary term algebra, ℕ forms a monoid (ℕ, 0, +),
whose actions are the sequences (f^{ n}) for any transformation f.
It is commutative as it is generated by a singleton, {1} (which commutes with itself). Thus the side won't
matter, but conventions basically present it as acting on the right, defining addition as
n+p = S^{p}(n), or recursively as
n + 0 = n
∀p∈ℕ, n+S(p) = S(n+p).
Thus, n+1 = S(n+0) = Sn.
Like in the general case, the action formula ∀n,p∈ℕ, f^{ n+p} = f^{
p}০f^{ n} is deduced from
(f^{n+0}=f^{n} ∧ ∀p∈ℕ,
f^{n+Sp} = f^{S(n+p)
} = f০f^{n+p})
∴
∀a∈E, ∀f∈ E^{E}, (p↦f^{
n+p}(a))∈Mor(ℕ,(E,f^{n}(a),f)),
from which associativity comes as (a+b)+n =
S^{n}(S^{b}(a)) =
S^{b}^{+}^{n}(a) =
a+(b+n).
Multiplication
Multiplication in ℕ can be defined as x⋅y =
(S^{x})^{y}(0), or recursively as
∀x∈ℕ, x⋅0 = 0
∀x,y∈ℕ, x⋅(Sy) = (x⋅y)+x
Then generally, ∀f∈E^{E}, f^{ x⋅y}
= (f^{ x})^{y}.
Inversed recursion and relative integers
By induction using commutativity (n+1 = 1+n), ∀f,g∈
E^{E}, g০f = Id_{E}
⇒ ∀n∈ℕ, g^{n}০f^{ n} = Id_{E}.
Thus if f is a permutation then f^{ n} is also a permutation, with inverse
(f^{ n})^{1} = (f^{ 1})^{n}.
Commutativity was just here to show that composing n times is insensitive to sides reversal,
as (f^{ n})^{1} has the more direct recursive definition
(f^{ Sn})^{1} =
(f^{n})^{1}০f.
The system of (relative) integers ℤ is defined as the {0,S}algebra where
 the set ℤ is defined as ℕ ∪ ℕ, where elements of ℕ (natural numbers) are
called positive, and ℕ= {nn∈ℕ} is a copy of ℕ
called the set of negative integers (where n is the opposite of n),
only intersecting ℕ at 0 = 0.
 S_{ℤ} is the permutation extending S_{ℕ} by
∀n∈ℕ, S(Sn)= n, thus letting Gr S_{ℤ} be
the union of Gr S_{ℕ} with its transposed copy in ℕ.
Proposition. ℤ is a commutative group, and for any permutation f of a set E,
there exists a unique (f^{ n})_{n∈ℤ} which is,
equivalently, a {0,S}morphism from ℤ to (E^{E}, Id_{E},
f), or an action of ℤ on E interpreting 1 as f.
Proof: the {0,S}morphism condition requires on ℕ the same n ↦
f^{ n} as above; on ℕ, it recursively defines f^{ n} =
(f^{ 1})^{n}, namely
 f^{ 0} = Id_{E} = f^{ 0}
 ∀n∈ℕ, f^{ n} = f০f^{ Sn},
equivalently f^{ 1}০f^{ n} = f^{ Sn}
This makes (ℤ,0,S) an initial object in the category of {0,S}algebras
(E,a,f) where f is a permutation. This category is derived as described with categories of acts
from that of
{S}algebras (E,f) where f is a permutation.
Therefore, ℤ is a monoid acting by (f^{ n})_{n∈ℤ} on every set E
with a permutation f.
This monoid is a commutative group because it is generated by {1, 1}, which commute and are the
inverse of each other : (1)+1=0=1+(1).
The formula of its inverse, (n)+n = 0 = n+(n) can be deduced either
from symmetry ((n)+n∈ℕ ⇔ n+(n)∈ℕ) and commutativity, or from the
above result.
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. Algebras
3.3. Special morphisms
3.4. Monoids
3.5. Actions of monoids
3.6. Invertibility and groups
3.7. Categories
3.8. Algebraic terms and term algebras
3.9. Integers and recursion
3.10. Arithmetic with addition
4. Model Theory