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)).
The formula (u0 = a ∧ ∀n∈ℕ, uSn
= f(un)) is called the recursive definition of u.
Indeed, it determines a unique u since ℕ is an initial {0,S}-algebra,
or equivalently (ℕ,0) is an egg for {S}-algebras.
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 from the operations of
sum and product between sets (2.6),
which directly gives their basic properties from the corresponding canonical bijections.
But let us here develop these operations only based on the
above definition of ℕ.
Since (ℕ, 0) is an egg for {S}-algebras, it forms a monoid
(ℕ, 0, +), acting on any {S}-algebra (X,f) as
ℕ×X ∋ (n,x) ↦ f n(x)
It is conventionally defined by recursion as
n + 0 = n
∀p∈ℕ, n+S(p) = S(n+p)
∴ n+1 = S(n+0) = Sn
thus basically acting on the right : n+p
= Sp(n).
The associativity of + will be used implicitly, omitting parenthesis.
As any unary
term {S}-algebra, the monoid (ℕ, 0, +) has a basis, that is
{1}, i.e. (ℕ,1) is an egg in the category of monoids.
It is commutative
as it is generated by the singleton {1} (which commutes with
itself). Thus the sides in the use of + won't matter, and
f Sn = f⚬f n = f n⚬f.
Inversed recursion and integers
If f∈EE is injective, resp. surjective, then so is
f n for each n∈ℕ (the proof is easy by induction).
Precisely, ∀f∈𝔖E, ∀n∈ℕ, fn∈𝔖E
∧ (f n)-1 = (f -1)n
More generally,
∀f,g∈ EE, g⚬f = IdE
⇒ ∀n∈ℕ, gn⚬f n = IdE
Proof by induction using the commutativity of + :
g0⚬f0 = IdE⚬IdE = IdE
gn⚬f n = IdE ⇒
gSn⚬f Sn
=g⚬gn⚬f n⚬f
=g⚬f = IdE ∎
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 whose transpose is algebraic, i.e. 0E is a
singleton and SE is both
injective and surjective.
This negative recursion will be mainly used with {0,S}-algebras
(E,(a,f)) where f ∈ 𝔖E :
(f n(a))n∈-ℕ
∈ Mor{0,S}(-ℕ, (E,(a,f)))
∀n∈ℕ, f -n = (f -1)n
This gives back the notation f -1 for the inverse of
f as the particular case n=1.
Let us define the system of integers as ℤ = ℕ ∪ -ℕ with the convention
ℕ ⋂ -ℕ = {0} = {-0}, and with structure the union of those from ℕ and -ℕ. It
is easy to see that Sℤ ∈ 𝔖ℤ, so that
ℤ is a {0,S}-algebra. Obviously, it is the coproduct
of ℕ and -ℕ in the category of partial {0,S}-algebras; and thus also
in any smaller category that contains it (with a sub-class of systems
and the same morphism between them), such as the category of {0,S}-algebras,
but more interestingly that of those {0,S}-algebras where S acts as
a permutation.
Indeed the systems in this latter class satisfy the existence and uniqueness of both
recursion and negative recursion. By virtue of the concept of coproduct, this implies
that (ℤ,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.
ℤ is a group where inverses are given by negation:
∀n∈ℕ, (-n)+n = 0 = n+(-n)
Precisely, (ℤ,1) is an egg in the category of groups, and also that of permutation groups:
∀f ∈ 𝔖E, {f n |
n∈ℤ} ⊂ 𝔖E.
Moreover, +ℤ is commutative.
Indeed, ℤ is generated by {-1, 1}, which commute: (-1) + 1 = 1 + (-1) =
0.
It can also be deduced from the commutativity of +ℕ and a previous result.
Multiplication
Let us introduce multiplication as a general concept in category theory,
from which the multiplication operations in ℕ and ℤ will come as particular cases.
Let L = {0,+} the language of monoids, and (F,1) an egg
in a concrete category where objects are L-algebras and
Mor ⊂ MorL.
Then multiplication is defined as the
natural right action ⋅ on every object E, of the monoid
(F,1,⋅) isomorphic to End F
like E is a copy of Mor(F,E):
∀x∈E, {⋅⃗(x)} =
{f∈ Mor(F,E) | f(1)=x}
The ⊂ logical side of this equality, followed by the use of
Mor ⊂ MorL, expands as
∀x∈E, x⋅0 = 0 (right zero)
∀x∈E, x⋅1 = x
∀x∈E, ∀y,z∈F, x⋅(y+z)
= x⋅y + x⋅z (left distributivity)
This may be (not so usefully) completed by the formula Mor(F,E) =
Im ⋅⃗ to form a definition of ⋅ from Mor(F,E).
But, this action (x⋅n for x∈E, n∈F)
may be denoted differently depending on the name for
the L-structure of E : if that structure is conceived as a kind of
multiplication then the action rather takes an exponential notation xn.
Our first example is the egg (ℕ,1) of the category of transformation monoids
where +E
is defined as the transpose of composition :
the unique morphism of ℕ into a
transformation monoid E ⊂ XX which sends 1 to f,
is the recursive sequence (fn)n∈ℕ.
The above axioms are denoted there
∀f∈E, f 0 = IdX ∧
f 1 = f
∀f∈E, ∀n,p∈ℕ,
f n+p = f p⚬f n
The proof of the latter is expressible in this case as follows:
for each fixed n, the sequence
(fn+p)p∈ℕ fits the above recursive definition of
(f p⚬f n)p∈ℕ. Namely
fn+0 = f n
∧ ∀p∈ℕ, f n+Sp = f
S(n+p) = f⚬f n+p
∴ ∀a∈E, (p ↦ f n+p(a))
∈ Mor{0,S}(ℕ,(E, f n(a),f)) ∎
The remaining axiom of the action of ⋅ is written there
∀f∈EE, f n⋅p
= (f n)p.
This category also satisfies the left zero axiom, but outside the egg
it neither fits right distributivity, nor the commutativity of +.
As another example, the category of algebras made of a commutative monoid
(resp. commutative group) with another constant symbol (not subject to any axiom),
has an egg whose monoid structure (0,+) is that of ℕ×ℕ (resp. ℤ×ℤ). Its +
is everywhere commutative, but left zero and right distributivity fail even in the egg.
So, to justify those remaining properties of multiplication, some other condition
is needed. Let us now focus on those we have for ℕ and ℤ. Another solution with wider
scope will be given later in terms of clones.
If Mor(F,E) = MorL(F,E) then
∀f∈ MorL(F,E), ⋅⃗(f(1)) = f.
So if moreover E is a commutative monoid then
Im ⋅⃖ ⊂ EndLE, namely
- ∀x∈F, 0⋅x = 0 (left zero)
- ∀x,y∈E,z∈F, (x+y)⋅z
= x⋅z + y⋅z (right distributivity)
- Therefore if E=F then ⋅ is commutative.
Proof:- uses 0+0 = 0 in E.
- ⋅⃗(x+y) = (F ∋ z ↦ x⋅z + y⋅z) because
- x⋅0 + y⋅0 = 0
-
x⋅1 + y⋅1 = x+y
-
x⋅(z+t) + y⋅(z+t) =
x⋅z+x⋅t + y⋅z+y⋅t =
(x⋅z+y⋅z) + (x⋅t+y⋅t)
- The formulas which defined ⋅ also hold for its transpose, thus both coincide. ∎
Conversely, if distributivity holds and +E is associative and cancellative,
then it is also commutative.
Proof : ∀x,y∈E, x + y+x + y
= (x+y)⋅1 + (x+y)⋅1
= (x+y)⋅(1+1)
=
x⋅(1+1) + y⋅(1+1) = x + x+y + y ∎
Note : if E = F then another proof is possible with a somehow weaker cancellativity assumption:
x⋅y + y+x +1
= (x+1)⋅(y+1) = x⋅y + x+y +1
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