4.4. Integers and recursion
The set ℕ
Ideally, Arithmetic is the concept of the system ℕ of natural
numbers. In effect, an arithmetic is any theory aiming
to describe it. There are diverse such theories, depending on the
choices of a logical framework, a language and a set of axioms. The
ideal framework for arithmetic would be second-order logic. Then, it
has multiple possible reductions into the framework of first-order
logic, needed to provide concepts of formal provability (but which
will remain incomplete).
Let us start with the set theoretical arithmetic, most
precise arithmetic preserving its ideal meaning by the natural insertion
of second-order logic into set theory, interpreting second-order
quantifiers by the powerset symbol (leaving the extent of formal
provability open and up to the choice of additional axioms for set
theory). This is a set theoretical definition of "the standard ℕ",
or rather its isomorphism
class relative to the given universe.
There are actually two main (kinds of) versions of it, depending on
the strength of the set theory involved. Let us start with the
easier one involving a stronger set theory:
Definition. The set ℕ of natural numbers is a
(fixed choice of) 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, which essentially means to recognize the class
of natural numbers as a set.
The other version of set theoretical arithmetic aims to work
without this axiom, by defining the class of "finite sets", and
letting natural numbers measure the cardinals (numbers of
elements) of finite sets, which will be defined in 4.6.
Let us formalize this definition 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
By previous results, our definition of ℕ naturally gives to each n∈ℕ
a role of 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 {S}-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 made of n iterates of the function symbol f,
applied to the 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
When natural numbers are conceived as cardinals of finite sets,
addition and multiplication in ℕ can be defined in the familiar way,
which directly gives their basic properties from the corresponding canonical bijections.
But let us here develop these operations independently from the
above definition of ℕ.
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