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 ∧ ∀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 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 n ∈
EE.
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
a∈E and f∈EE :
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 = f ⚬ f n.
In particular, f 1 = f and f 2 = f⚬f.
Generally for any f∈EE,
g∈EX, the recursive sequence h : ℕ → EX
defined by h0 = g ∧
∀n∈ℕ, hSn = f⚬hn,
is hn = f n⚬g.
Addition
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 ∀f∈EE, ∀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))
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.
Moreover,
- +ℤ is commutative.
- ∀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 ∈ 𝔖E
⇒ f -1 ⚬ f = f ⚬ f -1 = IdE.
Proof of 2. : from ∀n∈ℕ, n+1 = 1+n comes
∀f∈EE, f Sn =
f⚬f n = f n⚬f
∀f,g∈
EE, g⚬f = IdE
⇒ ∀n∈ℕ, gn⚬f 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.
Multiplication
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 n⋅p = (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,
∀x∈ℕ, 0⋅x = 0
∀x,y∈ℕ, (Sy)⋅x = (y⋅x)+x
the latter coming as (Sx)Sy(0) =
Sx((Sx)y(0)).
Then generally, ∀f∈EE, f n⋅p
= (f p)n. Proof :
(n⋅p)n∈ℕ ∈ Mor ((ℕ,S),(ℕ,Sp))
(fm)m∈ℕ ∈ Mor ((ℕ,Sp),(EE,f p)) by properties of actions.
(f n⋅p)n∈ℕ ∈ Mor((ℕ,S),(EE,f p))
(f 0⋅p)n∈ℕ = IdE
(f n⋅p)n∈ℕ fits the definition of
((f p)n)n∈ℕ
∎
∀n∈ℕ, n⋅0 = 0 (easy to check by induction).
Right distributivity ∀x,y,z∈ℕ, (x+y)⋅z =
x⋅z + y⋅z comes by induction on y, or as
(Sz)x+y =
(Sz)y⚬(Sz)x.
Left distributivity ∀x,y,z∈ℕ, x⋅(y+z) =
x⋅y + x⋅z comes by induction on x using commutativity of +.
In particular ∀x,y∈ℕ, x⋅Sy = (x⋅y)+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
5. Second-order foundations
6. Foundations of Geometry