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 second-order logic, but this leads to other versions depending on how second-order logic itself comes down to other frameworks.
Let us start with the set theoretical arithmetic, most precise arithmetic expressed in the framework of a strong enough set theory, interpreting second-order quantifiers by the powerset symbol. This defines "the standard ℕ", or rather 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.6).

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 ∧ ∀nA, SnA) ⇒ 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 re-written 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 Sn defined by a unary S-term and interpreted in each S-algebra (E,f) as a function f nEE.

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 S-algebra structure on E, i.e. defined by choices of aE and fEE :

u ∈ Mor{0,S}(ℕ, (E,(a,f))) ⇔ (∀n∈ℕ, un = f n(a))
⇔ (u0 = a ∧ ∀n∈ℕ, uSn = f(un)).

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 = IdE ∧ ∀n∈ℕ, f Sn = ff n.
In particular, f 1 = f and f 2 = ff.
Generally for any fEE, gEX, the recursive sequence h : ℕ → EX defined by h0 = g ∧ ∀n∈ℕ, hSn = fhn, is hn = f ng.


The basic properties of addition and multiplication in ℕ can be seen as obvious consequences of the role of natural numbers as measures ("cardinals") of finite sets, which will be defined in 4.6. But let us prove them independently here as an exercise.
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 = Sp(n), or recursively as

n + 0 = n
p∈ℕ, n+S(p) = S(n+p)
n+1 = S(n+0) = Sn

The action axiom ∀fEE, ∀n,p∈ℕ, f n+p = f pf n is deducible like for any term algebra:
(f n+0 = f n ∧ ∀p∈ℕ, f n+Sp = f S(n+p) = ff n+p) ∴ ∀aE, (pf n+p(a)) ∈ Mor(ℕ,(E, f n(a),f)).
The associativity of + (coming as a property of monoids) will be used implicitly, omitting parenthesis.

Inversed recursion and integers

Let -ℕ = {-n | n∈ℕ} (where -n is read "minus n") a copy of ℕ, structured as a partial {0,S}-algebra where 0-ℕ = -0 and S-ℕ is the copy of S-1. As a relational system, it works like ℕ with S transposed. Thus, it has a unique {0,S}-morphism to any {0,S}-system E where 0E is a singleton and SE is both injective and surjective. In particular this holds for {0,S}-algebras (E,(a,f)) where f = SE ∈ 𝔖E, forming the negative recursion

(f n(a))n∈-ℕ ∈ Mor{0,S}(-ℕ, (E,(a,f)))
n∈ℕ, f -n = (f -1)n

giving back the notation f -1 for the inverse of f as a particular case.
Let us define the system of integers as ℤ = ℕ ∪ -ℕ assuming ℕ ⋂ -ℕ = {0} = {-0}, with the union of structures from ℕ and -ℕ. It is easy to see that S ∈ 𝔖, and that ℤ is a {0,S}-algebra and the coproduct of ℕ and -ℕ in the category of partial {0,S}-algebras.
Thus, (ℤ,0) is an egg in the category of {S}-algebras (E,f) where f ∈ 𝔖E. This defines a monoid structure (0,+) on ℤ, extending the one on ℕ, and acting on each such (E,f) by the unique (f n)n∈ℤ ∈ Mor{0,S}(ℤ, (EE, IdE, ⚬(f)). It is also the unique morphism of monoid from ℤ to EE sending 1 to f.
  1. + is commutative.
  2. n∈ℕ, (-n)+n = 0 = n+(-n), thus ∀f ∈ 𝔖E, {f n | n∈ℤ} ⊂ 𝔖E.
Proof of 1. : ℤ is generated by {-1, 1}, while (-1) + 1 = 1 + (-1) = 0 because f ∈ 𝔖Ef -1f = ff -1 = IdE.

Proof of 2. : from ∀n∈ℕ, n+1 = 1+n comes

fEE, f Sn = ff n = f nf
f,gEE, gf = IdE ⇒ ∀n∈ℕ, gnf n = IdE
f∈𝔖E, ∀n∈ℕ, f n∈𝔖E ∧ (f n)-1 = f -n

Each result can also be deduced from the other:
1.⇒2. : by symmetry between ℕ and -ℕ, (-n)+n ∈ ℕ ⇔ n+(-n) ∈ -ℕ.
2.⇒1. from the commutativity of + and a previous result.

Following the French terminology, the subsets ℕ and -ℕ of ℤ will be respectively called the sets of positive and negative integers.


The following definition and properties of multiplication in ℕ also hold in ℤ (where it is an extension of the one in ℕ).
Let us define it as np = (Sp)n(0) (this choice of sides fits common language, unlike the usual one from the literature, until the proof of commutativity removes the distinction). Recursively, the latter coming as (Sx)Sy(0) = Sx((Sx)y(0)).
Then generally, ∀fEE, f np = (f p)n. Proof : n∈ℕ, n⋅0 = 0 (easy to check 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 ∀x,y∈ℕ, xSy = (xy)+x. As the transpose of ⋅ fits the recursive definition of ⋅, both are equal : multiplication is commutative.

An elegant approach to multiplication is to see (ℕ, 1, ⋅) as the monoid End{0, +} ℕ. It will be developed later.

Set theory and foundations of mathematics
1. First foundations of mathematics
2. Set theory
3. Algebra 1
4. Arithmetic and first-order foundations
4.1. Algebraic terms
4.2. Quotient systems
4.3. Term algebras
4.4. Integers and recursion
4.5. Presburger Arithmetic
4.6. Finiteness and countability (draft)
4.7. The Completeness Theorem
4.8. More recursion tools
4.9. Non-standard models of Arithmetic
4.10. Developing theories : definitions
4.11. Constructions
4.A. The Berry paradox
5. Second-order foundations
6. Foundations of Geometry