4.4. 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. Somehow, the main framework for arithmetic
is secondorder logic, but this leads to other versions depending on how secondorder
logic itself comes down to other frameworks.
Let us start with the set theoretical arithmetic, most precise arithmetic
expressible in a strong enough set theory, interpreting secondorder quantifiers
by the powerset symbol. Namely, that is the set theoretical
definition of "the standard ℕ", or rather of its isomorphism class, relative to the
given universe (it amounts
to defining the class of "finite sets", which are measurable by their number of elements,
as we shall define in 4.5).
Definition. The set ℕ of natural numbers is a unary term {S}algebra
where S is a function symbol called the successor ; also expressible as a ground
term {0,S}algebra where 0 (zero) is a constant symbol.
The existence of such a system is our first expression of the axiom of infinity. Let us formalize
it by inserting arithmetic
into set theory, in the form of 3 constant symbols ℕ, 0, S with the following axioms :

0 ∈ ℕ ∧ S : ℕ → ℕ 
: ℕ is a {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=ℕ 
: 0 generates ℕ (induction axiom). 
More constant symbols can be defined from there:
1 = S0
2 = S1 = SS0
and so on.
This completes our axioms of set theory up to the strength
of Mc Lane set theory,
which essentially forms (with the axiom of choice)
the most commonly used foundational theory for mathematics.
It will imply the existence
of term algebras with any language.
This definition of ℕ may be criticized as circular, for involving concepts of algebra
we initially introduced using ℕ as set of possible arities of symbols. But
these concepts may be rewritten up to this point without this use, by restriction
to the use of symbols with small arities (0, 1, 2).
Recursively defined sequences
Each n∈ℕ represents a function
symbol S^{n} defined by a unary Sterm and interpreted
in each Salgebra (E,f) as a function f^{ n} ∈
E^{E}.
A sequence of elements of a set E, is a family u : ℕ → E.
It is called recursive when it is a morphism for a given
Salgebra structure on E, i.e. defined by choices of
a∈E and f∈E^{E} :
u ∈ Mor_{{0,S}}(ℕ, (E,(a,f)))
⇔ (∀n∈ℕ, u_{n} = f^{ n}(a))
⇔
(u_{0} = a ∧ ∀n∈ℕ, u_{Sn} =
f(u_{n})).
Intuitively, each f^{ n}(a) abbreviates
the term with n occurrences of the function symbol f, and variable a :
f^{ 0}(a) = a
f^{ 1}(a) = f(a)
f^{ 2}(a) = f(f(a)) 
The sequence (f^{ n}) is itself 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 recursive sequence h : ℕ → E^{X}
defined by h_{0} = g ∧
∀n∈ℕ, h_{Sn} = f⚬h_{n},
is h_{n} = f^{ n}⚬g.
Addition
The basic properties of addition and multiplication in ℕ become obvious when
seeing natural numbers as measures ("cardinals") of finite sets, as will be defined in 4.6. But let us take here as an
exercise to prove them independently.
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 the 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)
n+1 = S(n+0) = Sn
The action axiom ∀f∈ E^{E}, ∀n,p∈ℕ,
f^{ n+p} = f^{ p}⚬f^{
n} is deducible like for any term algebra:
(f^{ n+0}=f^{ n} ∧ ∀p∈ℕ,
f^{ n+Sp} = f^{ S(n+p)
} = f⚬f^{ n+p})
∴
∀a∈E, (p↦f^{
n+p}(a))∈Mor(ℕ,(E,f^{ n}(a),f)).
It gives associativity : (a+b)+n =
S^{n}(S^{b}(a)) =
S^{b}^{+}^{n}(a) =
a+(b+n), which will be used implicitly, omitting parenthesis.
Multiplication
Let us define multiplication in ℕ as y⋅x = (S^{x})^{y}(0)
(this choice of sides fits common language, unlike the usual one from the literature,
until the distinction disappears by the proof of commutativity). In recursive formulation,
∀x∈ℕ, 0⋅x = 0
∀x,y∈ℕ, (Sy)⋅x = (y⋅x)+x
the latter coming as (S^{x})^{Sy}(0) = S^{x}((S^{x})^{y}(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 for eggs 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
4. Arithmetic and firstorder foundations
5. Secondorder foundations
6. Foundations of Geometry