# 3.11. 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 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 :

u0=a
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)n∈ℕ 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)),
In this view, associativity appears as (a+b)+n = Sn(Sb(a)) = Sb+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 = (xy)+y
which can be summed up as xy = (Sy)x(0). Then generally, ∀fEE, f xy = (f y)x.
x∈ℕ, x⋅0 = 0 is deduced by induction.
Right distributivity ∀x,y,z∈ℕ, (x+y)⋅z = xz + yz comes by induction on y, or as (Sz)x+y = (Sz)y০(Sz)x.
Left distributivity ∀x,y,z∈ℕ, x⋅(y+z) = xy + xz comes by induction on x using commutativity of +. In particular this gives ∀x,y∈ℕ, xSy = (xy)+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,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
• the set ℤ is defined as ℕ ∪ -ℕ, where elements of ℕ (natural numbers) are called positive, and -ℕ= {-n|n∈ℕ} 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 (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
• f -0 = IdE = f 0
• n∈ℕ, f -n = ff -Sn, equivalently f -1f -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. Initial and final objects
3.9. Algebraic terms
3.10. Term algebras
3.11. Integers and recursion
3.12. Arithmetic with addition
4. Model Theory