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 ∧ ∀nA,SnA) ⇒ 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 uE such that u ∈ Mor(ℕ,(E,a,f)), where (E,a,f) is the {0,S}-algebra E interpreting 0 as aE and S as fEE :

n∈ℕ, uSn = f(un).

As un 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))
Re-interpreting the constant 0 as a variable, makes ℕ a unary term {S}-algebra, where each number n is a unary term Sn with n occurrences of S, interpreted in each {S}-algebra (E,f) as the function f nEE, recursively defined by

f 0 = IdE
n∈ℕ, f Sn = ff n

In particular, f 1=f and f 2 = ff.
Generally for any fEE, gEX, the sequence (hn) in EX recursively defined by (h0=g) and (∀n∈ℕ, hSn = fhn) is hn=f ng.


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 = Sp(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 pf n is deduced from
(fn+0=fn ∧ ∀p∈ℕ, fn+Sp = fS(n+p) = ffn+p) ∴ ∀aE, ∀fEE, (pf n+p(a))∈Mor(ℕ,(E,fn(a),f)),
from which associativity comes as (a+b)+n = Sn(Sb(a)) = Sb+n(a) = a+(b+n).


Multiplication in ℕ can be defined as xy = (Sx)y(0), or recursively as

x∈ℕ, x⋅0 = 0
x,y∈ℕ, x⋅(Sy) = (xy)+x

Then generally, ∀fEE, f xy = (f x)y.

Inversed recursion and relative integers

By induction using commutativity (n+1 = 1+n),

f,gEE, gf = IdE ⇒ ∀n∈ℕ, gnf n = IdE.

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 = (fn)-1f.

The system of (relative) integers ℤ is defined as the {0,S}-algebra where 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 (EE, IdE, f), or an action of ℤ on E interpreting 1 as f.

Proof: the {0,S}-morphism condition requires on ℕ the same nf n as above; on -ℕ, it recursively defines f -n = (f -1)n, namely

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 commutative because it is generated by {-1, 1}, which commute: (-1)+1=0=1+(-1).
It is a group: (-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