3.9. Integers and recursion
The set ℕ
An arithmetic is any theory describing the system ℕ of natural numbers.
There are diverse such theories, depending on the choice of a logical framework,
then of a language and axioms. First is the set theoretical one,
which is the most precise as it determines the isomorphism class of ℕ in
the given universe :
Definition. ℕ is a ground
term algebra with two symbols: a constant
symbol 0 called zero, and a unary symbol S called the successor.
The essential uniqueness of such systems removes any uncertainty attached
to fixing a choice of ℕ among them, at least once any irrelevant questions are made
inexpressible by seeing ℕ as a set of pure elements.
The existence of a ground term {0,S}algebra is our first expression 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 will imply the existence
of term algebras with any language.
The above use of algebraic concepts in the definition of ℕ may make it look circular, as
our study of algebras used natural
numbers as arities of operation symbols. But these definitions may also be written
without reference to numbers when used symbols have small arities only
(for arithmetic, arities are first just 0 and 1, then later 2).
Namely, the most convenient expression of the axiom of infinity consists in inserting arithmetic into
set theory, by first inserting the language of {0,S}algebra in the form of 3
constant symbols: ℕ (as a set) and the images of both algebraic symbols 0 and S,
with axioms 0∈ℕ and S:ℕ→ℕ; then making this a ground term algebra by the
following 3 axioms :
(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. 
More constant symbols can be defined from there:
1=S0, 2=S1=SS0, 3=S2=SSS0, ...
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)),
In this view, associativity appears as (a+b)+n =
S^{n}(S^{b}(a)) =
S^{b}^{+}^{n}(a) =
a+(b+n). From now on, use of associativity will be implicit, omitting parenthesis.
Multiplication
By the concept of cardinals of finite
sets (counting their elements)
that will be defined in 4.1., multiplication in ℕ
may be defined as the cardinal of a product, making obvious its
basic properties, including commutativity.
Without this, multiplication can be defined by the following recursion,
which needs to treat sides differently until commutativity is deduced.
Let us choose the side that fits common language, though it is opposite
(transpose) to the usual one from the literature on the axioms of arithmetic:
∀x∈ℕ, 0⋅x = 0
∀x,y∈ℕ, (Sx)⋅y = (x⋅y)+y
which can be summed up as x⋅y =
(S^{y})^{x}(0). Then generally, ∀f∈E^{E}, f^{ x⋅y}
= (f^{ y})^{x}.
∀x∈ℕ, x⋅0 = 0 is deduced by induction.
Right distributivity ∀x,y,z∈ℕ, (x+y)⋅z =
x⋅z + y⋅z comes by induction on y, or as
(S^{z})^{x+y} =
(S^{z})^{y}০(S^{z})^{x}.
Left distributivity ∀x,y,z∈ℕ, x⋅(y+z) =
x⋅y + x⋅z comes by induction on x using commutativity of +. In particular this gives ∀x,y∈ℕ, x⋅Sy = (x⋅y)+x, so that the transpose of multiplication, satisfying the same recursive definition, coincides with it : multiplication is commutative.
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