3.8. Integers and recursion

The set ℕ

Any theory that aims to describe the system ℕ of natural numbers is called an Arithmetic. In details, there are several such formal theories, depending on the language (list of basic structures), and the logical framework (affecting the expressibility of axioms).

Our first "definition" of ℕ will characterize it in a set theoretical framework. This way of starting to formalize ℕ now may look circular, as we already used natural numbers as arities of operation symbols of algebras, of which arithmetic is a particular case. But this case only uses operation symbols with arity 0, 1 or 2, for which previous definitions might as well be specially rewritten without any general reference to numbers.

Definition. The set ℕ of natural numbers is a ground term algebra with a language of two symbols: one constant symbol 0 ("zero"), and one unary symbol S.

The interpretation of S there is called the successor, understood as adding one unit (Sn=n+1).

This concept of ground term algebra can be expanded as the following 3 axioms on this {0,S}-algebra :
n∈ℕ, Sn ≠ 0
(H0), i.e. 0 ∉ Im S
n,p∈ℕ, Sn = Sp n = p (Inj), i.e. S is injective
A⊂ℕ, (0∈A ∧ ∀nA,SnA) ⇒ A=ℕ (Ind) : induction axiom (ℕ is a minimal (0,S)-algebra).

We can define 1=S0, 2=SS0...

This insertion of arithmetic into set theory, adding to set theory the constant symbol ℕ with some basic structure symbols interpreted in this ℕ, is the natural way to complete set theory (as we progressively introduced from the beginning to 2.5, + eventually the axiom of choice), to form the standard foundation of mathematics as practiced by most mathematicians. There is no uncertainty in choosing ℕ in the class of ground term {0,S}-algebras, since, as an initial {0,S}-algebra, it is essentially unique. The existence of ℕ is a form of the axiom of infinity, which implies the existence of term algebras of any language, as will be explained later.

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 in E as a and f. 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))
In another curried view of this map from E×EE×ℕ to E we can re-interpret 0 as a variable instead of a constant symbol. Then each number n becomes a term Sn with n occurrences of the function symbol S and one variable, 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, f1=f and f 2 = ff.
More generally, for any functions fEE, gEX, the sequence of functions recursively defined by (h0=g) and (∀n∈ℕ, hSn = fhn) is hn=f ng.


The operation of addition in ℕ can be defined as n+p = Sp(n), i.e. by the recursive definition

n + 0 = n
p∈ℕ, n+S(p) = S(n+p).

n+1 = n+S0 = S(n+0) = Sn
As ∀aE ,∀fEE, (pf n+p(a))∈Mor(ℕ,(E,fn(a),f)), i.e. fn+0=fn and ∀p∈ℕ, fn+Sp = fS(n+p) = ffn+p we have

n,p∈ℕ , f n+p = f pf n.

As a particular case of monoid of unary terms, (ℕ, 0 +) is a monoid, and recursive sequences are its actions. So, addition is associative: (a+b)+n = Sn(Sb(a)) = Sb+n(a) = a+(b+n).
It is also commutative as it is generated by 1 which commutes with itself.


Multiplication in ℕ can be defined as xy = (Sx)y(0), so that

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

More generally, for any aE and fEE, we have fxy(a) = (fx)y(a).

Inversed recursion and relative integers

By induction using the commutativity of addition,

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 order reversal, as (f n)-1 has the more direct recursive definition

(f Sn)-1 = (fn)-1f.

The set of (relative) integers ℤ is defined as the {0,S}-algebra made of Proposition. ℤ is a commutative group, and for any permutation f of a set E, there exists a unique nf 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 from that of {S}-algebras (E,f) where f is a permutation, by sending 0 to all possible elements. Therefore, ℤ is a monoid acting by nf 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.∎

A more general form of recursion

Some useful sequences need recursive definitions where the term defining uSn uses not only un but also n itself. Somehow it would work all the same, but trying to directly adapt to this case the proof we gave would require to define some special generalizations of previous concepts, and specify their resulting properties. To simplify, let us proceed another way, similar to the argument in Halmos's Naive Set Theory, but generalized.
For any algebraic language L, let us introduce a general concept of "recursive condition" for functions u : EF, where, instead of a draft, E is first assumed to be an L-algebra (then a ground term algebra to conclude).
The version we saw was formalized by giving the term in the recursive definition as an L-algebra structure on F, φF: LFF, then expressing the request for u to satisfy this condition as u∈Mor(E,F), namely

∀(s,x)∈LE, u(sE(x)) = φF(s,ux).

Let us generalize this as u(sE(x)) = φ(s,x,ux) which by the canonical bijection Dom φ ≡ ∐sL Ens ×Fns ≡ ∐sL (E×F)ns = L⋆(E×F) can be written using h : L⋆(E×F) → F such that ∀(s,x,y)∈ Dom φ, φ(s,x,y) = h(s,x×y), as

u(sE(x)) = h(s,x×(ux)).

As ∀uFE, x×(ux) = (IdE×u)০x, this becomes the second component of the formula IdE×u ∈ Mor(E, E×F) when giving E×F the structure φE×F = (φE০πLh.
The first component (φE০πL) we give to φE×F, makes π∈ Mor(E×F, E) and makes tautological the first component of the formula IdE×u ∈ Mor(E, E×F), namely
IdE(sE(x)) = φE(s,x) = (φE০πL)(s,x×(ux)).
It is then possible to conclude by re-using the previous result of existence of interpretations:
If E is a closed term L-algebra then ∃!f ∈ Mor(E, E×F), which is of the form IdE×u because π০f ∈ Mor(E, E) ∴ π০f = IdE.
But one can do without it, based on the following property of this L-algebra E×F:

uFE, IdE×u ∈ MorL(E, E×F) ⇔ Gr u ∈ SubL(E×F)

Indeed the defining formulas of both sides coincide. To see it otherwise, This reduces the issue to the search of subalgebras of E×F which are graphs of functions from E to F.
Now if E is a ground term L-algebra then M = MinL(E×F) is one of them because π|M∈ MorL(M, E) from a surjective algebra to a ground term algebra must be bijective.
Any other subalgebra of E×F must include M, thus to stay functional it must equal M. ∎
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. Categories
3.7. Algebraic terms and term algebras
3.8. Integers and recursion
3.9. Arithmetic with addition
4. Model Theory