Natural arithmetic is the science of natural numbers: it is based on addition, multiplication, natural order and divisibility. Now, all these operations and relations are defined on the basis of the single successor function, whose properties are brought together in the three axioms of Peano’s arithmetic, which, together with set theory, make it possible to recreate the whole of classical mathematics.

1.Successor function and recursion theorem

1.1.Reconstructing natural mathematics using three non-logical axioms

In What is a natural number ? we discussed how it is possible to give an axiomatic description of the set of natural numbers, even though the notion itself is a primitive concept that cannot be defined (unless we reduce it to that of a finite ordinal). Be that as it may, it is the axiomatic approach that interests us in mathematics, when we want to construct elementary arithmetic scientifically on the basis of set theory.It is on the basis of this theory of the natural integers that we can rigorously reconstitute all the natural sets of numbers (rational, real, complex, etc.), as well as all the natural objects of classical mathematics (analytical functions, geometric figures, Euclidean spaces, etc.). Let’s recall Peano’s axioms, which in themselves, against the background of the logical axioms of set theory, make it possible to completely and rigorously refound the whole of mathematics:

1. The natural number \(0\) is not the successor of any number
2. If two natural numbers \(m) and \(n) have the same successor, then \(m=n\)
3. If $S$ is a subset of \(\mathbb N\) such that \(0\in S\) and such that \(n+1\in S\) whenever \(n\in S\), then \(S\) is the whole set \(\mathbb N\) (induction principle).

1.2.The choice of the “successor” operation

These three axioms are somewhat odd: why have we chosen this successor function $s:\mathbb N\to \mathbb N$ which associates with a natural number $n$ the next natural number $n+1$, in order to describe the set of natural numbers? We know this intuitively through the use we make of these numbers: to count sets of objects, to compare the quantities obtained or to add and multiply them. So, in order to describe the fundamental arithmetical operations and relations, we need to use the set $\mathbb N$ to describe a “mathematical structure” that takes them into account. This must include the natural order $<$ (or $\leq$), addition $+$ and multiplication $\times$… but also the “next natural number” operation, which appears naturally in the counting or numeration activity. It is this operation, among the others, that Peano chose as the “successor function” to describe the whole set of natural numbers, no doubt because $+$, $\times$ and $<$ can be reduced to it, and because it admits the simplest axiomatic description. So, from Peano’s three little axioms (and from set theory…), we can reconstruct all the natural operations and relations of the set $\mathbb N$, as well as all the functions that are ” computable ” in a reasonable sense, and that we call recursive functions, lying at the heart of theoretical computer science.

1.3.The recursion theorem

This reconstruction of the elementary operations and relations of natural arithmetic from Peano’s axioms is based on a fundamental conceptual “tool” derived from this axiom, the recursion theorem (at leats two theorems have this name). Essentially, this theorem states that, in order to define a sequence of objects in a set $E$ (i.e. a function $u:\mathbb N\to E$, or a list of objects indexed by the natural numbers), all we need is two distinct pieces of information:

1. A fixed element $a$ of the set $E$ (the “first term” of the sequence)
2. A function of $E$ in $E$ (a “transformation process” of the set $E$).

Intuitively, given such an object $a$ and such a function $f$, we can fully describe the “sequence” that starts with $a$ and whose formation process is $f$: this is the infinite list $a,f(a),f(f(a)),\ldots$. In this procedure, we first apply function $f$ to $a$, then successively to each result obtained, in order to transform it into the next element of the list, ad infinitum.

Example 1
i) With $E=\mathbb N$, $a=0$ and $f=s$, we obtain the sequence $0,1,2,\ldots$ of all the natural numbers.
ii) With $E=\mathbb R$, $a=1$ and $f:\mathbb R\to \mathbb R$ multiplication by a real number $x$, we obtain the successive powers of $x$, i.e. $1=x^0,x=x^1,x^2,x^3,\ldots$.

It’s easy to see why such a procedure is closely linked to the successor function: in the generated sequence $(a,f(a),f(f(a)),f(f(a))),\ldots)$, the term of index $s(n)$ is obtained by applying $f$ to the term of index $n$. The rigorous statement of the theorem, whose proof is based on Peano’s axioms, is as follows:

Theorem 1 [Recursion theorem]
If $E$ is a set, $a$ an element of $E$ and $f:E\to E$ an application, then there exists a unique sequence $u:\mathbb N\to E$ of elements of $E$ such that:
i) $u(0)=a$
ii) $u(n+1)=f(u(n))$ for all natural numbers $n$.

Sequences obtained by applying the recursion theorem are said to be “defined by induction”.

2.From Peano’s axioms to the natural arithmetic structure

2.1.From successor to addition

While Peano’s axioms somehow define the number $0$ and the successor function, in the notation “$n+1$” of the successor $s(n)$ of the natural number $n$ the symbols $+$ and $1$ are for the moment only written conventions. Indeed, to talk about addition, and even the number $1$, in this context, we would either have to define them axiomatically, which we have not done, or define them on the basis of the properties of the successor: this is what we are going to do, in order to illustrate the power of Peano’s axioms. For example, addition is defined “element by element”, using the recursion theorem 1: for each fixed natural number $n$, we define the expression $n+m$ for all natural numbers $m$, by induction on $m$. We define the expression $n+0$ as being equal to $n$, and assuming that the value of $n+m$ is defined, we define $n+(m+1)$ as the successor of $n+m$, i.e. $s(n+m)$ (which we would previously have noted as $(n+m)+1$, but this time the notation is ambiguous!). Thus, for any natural number $n$, the expression $n+m$ is defined for each natural number $m$, so that we have defined an addition $+$, an operation from $\mathbb N$ into $\mathbb N$. The number $1$ is then defined as the successor of $0$, (i.e. $1:=s(0)$), and for any natural number $n$ the expression $n+1$ now denotes the sum of $n$ and $1$, i.e. by definition the successor of $n+0$, i.e. the successor of $n$: the notation $n+1$ for the successor of $n$ is thus justified by the definition of addition! Using the induction principle, we can demonstrate the natural properties of addition from its definition:

Proposition 1
If $n,m,p$ are natural numbers, then we have :
i) $n+m=m+n$ (addition is said to be commutative)
ii) $n+(m+p)=(n+m)+p$ (addition is said to be associative).

Remark 1
The definition by induction on $m$ of the expression $n+m$, for fixed $n$, applies the recursion theorem in the following way: the set $E$ is $\mathbb N$, the object $a$ chosen as first element is $n$, and the function $f:E\to E$ chosen as “process” is the successor $s:\mathbb N\to \mathbb N$. The sequence generated with these data is then: $n,s(n)=n+1,s(s(n))=n+2,s(s(s(n)))=n+3,\ldots$: it is indeed the addition of the successive integers to $n$.

2.2.Natural order and multiplication

Natural order over the natural numbers can be defined directly from addition: intuition suggests that if $n,m$ are two natural numbers, then we have $n\leq m$ ($n$ smaller than (or equal to) $m$) if and only if “we must add a certain quantity $p$ to $n$ to get $m$”, in other words if “there exists $p\in\mathbb N$ such that $m=n+p$”.

Multiplication is also defined on the basis of addition, but here we must again use the recursion theorem to define the expression $n\times m$ for any natural number $m$, with $n$ fixed as for addition:

• define $n\times 0=0$
• assuming that $n\times m$ is defined, we define $n\times (m+1)$ as $(n\times m)+n$.

Here, the recursion theorem applies with $E=\mathbb N$, $a=0$, and the function $f:\mathbb N\to \mathbb N$ which associates with a natural number $k$ the natural number $k+n$ (defined from addition): the sequence generated is in fact $0,n,2n,3n,\ldots$, i.e. the list of multiples of $n$. As with addition, we have thus defined a multiplication $\times :\mathbb N^2\to \mathbb N$, and we demonstrate its elementary properties by induction:

Proposition 2
If $n,m,p$ are natural numbers, then :
i) $n\times 1=n$
ii) $n\times m=m\times n$ (multiplication is commutative)
iii) $n\times (m\times p)=(n\times m)\times p$ (multiplication is associative)
iv) $n\times (m+p)=(n\times m)+(n\times p)$ (multiplication is said to be distributive over addition).

We then define the divisibility relation based on multiplication, in a perfectly analogous way to the definition of natural order based on addition: we say that a natural number $n$ divides another natural number $m$, if the latter “is a multiple of $n$”, in other words if “there exists $p\in\mathbb N$ such that $m=n\times p$”.

2.3.Peano arithmetic and recursion theory

Addition and multiplication, natural order and divisibility, are the fundamental “arithmetical” operations and relations: from their definitions and properties – and therefore, ultimately, from Peano’s three axioms! – we can demonstrate all the elementary results of natural arithmetic (for example, the existence of an infinite number of primes). These are special cases of the so-called recursive functions and relations, mentioned in a previous section, which are all the functions and relations, in infinite number, that essentially have an “algorithmic” description. The generic construction of these functions and relations is based on a principle analogous to the recursion theorem, but more general in scope, called the recursion principle, a simplified version of which is as follows:

Theorem 2 [Recursion principle]
If $f:\mathbb N\to \mathbb N$ and $g:\mathbb N^3\to \mathbb N$ are two functions, then there exists a unique function $h:\mathbb N^2\to \mathbb N$ such that :
i) For any natural number $n$, we have $h(n,0)=f(n)$
ii) For all natural numbers $n,m$, we have $h(n,m+1)=g(n,m,h(n,m))$.

According to this principle, the function $h: \mathbb N^2\to \mathbb N$ is “constructed” by a sophisticated form of recursion from the auxiliary functions $f$ and $g$, the function $f$ giving all the values of $h$ for pairs of the form $(n,0)$ and the function $g$ “recursively” giving the value of $h$ for $(n,m+1)$ from the previous value $h(n,m)$ and the data $n$ and $m$.

Example 2
i) By choosing for $f$ the identical function $n\mapsto n$, and for $g$ the function $(m,n,p)\mapsto s(p)$ (the successor of $p$), the function $h$ implicitly defined is none other than addition.
ii) By choosing for $f$ the constant function of value $0$, and for $g$ the function $(m,n,p)\mapsto m+p$, the function $h$ constructed is multiplication.
iii) By analogy, by choosing for $f$ the constant function of value $1$ and for $g$ the function $(m,n,p)\mapsto m\times p$, we obtain as function $h$ the “exponentiation” function, which associates with a pair $(m,n)$ of natural numbers the integer $m^n$.

Example 2 illustrates that we can define addition and multiplication “simultaneously” using two functions, whereas the previously accepted definitions require a different inductive definition for each natural number. Now, the recursion principle can be demonstrated as a generalisation of the recursion theorem 1, starting from Peano’s axioms alone: here we are not leaving the framework that these determine, even if they are not sufficient to demonstrate all true arithmetic theorems, which is the subject of Gödel’s first incompleteness theorem; but that’s another story.