L’arithmétique naturelle est la science des nombres entiers naturels : elle repose sur l’addition, la multiplication, l’ordre naturel et la divisibilité. Or, toutes ces opérations et relations se définissent à partir de la seule fonction successeur, dont les propriétés sont rassemblées dans les trois axiomes de l’arithmétique de Peano, qui additionnés à la théorie des ensembles, permettent ainsi de reconstituer toute la mathématique classique.

1.Fonction successeur et théorème de récurrence

1.1.Reconstruire la mathématique naturelle grâce à trois axiomes non logiques

Dans Qu’est-ce qu’un nombre entier naturel ?, nous avons évoqué comment il est possible de donner une description axiomatique de l’ensemble $\mathbb N$ des nombres entiers naturels, bien que la notion en elle-même soit un concept primitif qu’on ne peut définir (à moins de le réduire à celui d’ordinal fini). Quoiqu’il en soit, c’est bien l’approche axiomatique qui nous intéresse en mathématique, lorsque l’on veut construire de manière scientifique l’arithmétique élémentaire à partir de la théorie des ensembles. Or, c’est à partir de cette théorie des entiers naturels que l’on reconstitue de manière rigoureuse tous les ensembles naturels de nombres (rationnels, réels, complexes…), ainsi que tous les objets naturels de la mathématique classique (fonctions de l’analyse, figures géométriques, espaces euclidiens…) à partir de celle-ci. Rappelons ici les axiomes de Peano, qui permettent à eux seuls, sur fond des axiomes logiques de la théorie des ensembles, de refonder entièrement et rigoureusement toute la mathématique (on rappelle que le successeur d’un entier naturel $n$ est l’entier naturel suivant, c’est-à-dire $n+1$) :

1. Le nombre entier naturel \(0\) n’est le successeur d’aucun nombre
2. Si deux entiers naturels \(m\) et \(n\) ont le même successeur, alors \(m=n\)
3. Si $S$ est un sous-ensemble de \(\mathbb N\) tel que \(0\in S\) et tel que \(n+1\in S\) dès que \(n\in S\), alors \(S\) est l’ensemble \(\mathbb N\) tout entier (principe de récurrence).

1.2.Le choix de l’opération « successeur »

Ces trois axiomes sont quelque peu étranges : pourquoi avoir choisi cette fonction successeur $s:\mathbb N\to \mathbb N$ qui associe à un entier naturel $n$ l’entier naturel suivant $n+1$, afin de décrire l’ensemble des entiers naturels ? Celui-ci nous est connu dans l’intuition par l’usage que nous faisons de ces nombres : pour compter des ensembles d’objets, pour comparer les quantités obtenues ou encore les additionner et multiplier. Ainsi, pour décrire les opérations et relations arithmétiques fondamentales, nous devons décrire avec l’ensemble $\mathbb N$ une « structure mathématique » qui les prend en considération. Celle-ci doit faire apparaître l’ordre naturel $<$ (ou $\leq$), l’addition $+$ et la multiplication $\times$… mais aussi l’opération « entier naturel suivant », qui apparaît naturellement dans l’activité de comptage ou numération. C’est cette opération, parmi les autres, qui a été choisie par Peano comme « fonction successeur » pour décrire intégralement l’ensemble des entiers naturels, sans doute parce que $+$, $\times$ et $<$ s’y ramènent, et parce qu’elle admet la description axiomatique la plus simple. Ainsi, à partir des trois petits axiomes de Peano (et de la théorie des ensembles…), on peut reconstituer toutes les opérations et relations naturelles de l’ensemble $\mathbb N$, ainsi que toutes les fonctions « calculables » en un sens raisonnable, et qu’on appelle fonctions récursives, à la base de l’informatique théorique.

1.3.Le théorème de récurrence

Cette reconstitution des opérations et relations élémentaires de l’arithmétique naturelle à partir des axiomes de Peano repose sur un « outil » conceptuel fondamental qui dérive de ces axiomes, le théorème de récurrence. Celui-ci énonce essentiellement que, pour définir une suite d’objets dans un ensemble $E$ (c’est-à-dire une fonction $u:\mathbb N\to E$, ou encore une liste d’objets de $E$ indexée par les entiers naturels), il suffit de disposer de deux informations distinctes :

1. Un élément fixé $a$ de l’ensemble $E$ (le « premier terme » de la suite)
2. Une fonction de $E$ dans $E$ (un « processus de transformation » de l’ensemble $E$).

Intuitivement, étant donnés un tel objet $a$ et une telle fonction $f$, on peut en effet décrire intégralement la « suite » qui commence par $a$ et dont le procédé de formation est $f$ : il s’agit de la liste infinie $a,f(a),f(f(a)),\ldots$. Dans ce procédé, on applique d’abord à $a$, puis successivement à chaque résultat obtenu, la fonction $f$ afin de le transformer en l’élément suivant de la liste, à l’infini.

Exemple 1
i) Avec $E=\mathbb N$, $a=0$ et $f=s$, on obtient la suite $0,1,2,\ldots$ de tous les entiers naturels.
ii) Avec $E=\mathbb R$, $a=1$ et $f:\mathbb R\to \mathbb R$ la multiplication par un nombre réel $x$, on obtient les puissances successives de $x$, soit $1=x^0,x=x^1,x^2,x^3,\ldots$.

On comprend intuitivement pourquoi un tel procédé est étroitement lié à la fonction successeur : dans la suite générée $(a,f(a),f(f(a)),f(f(f(a))),\ldots)$, le terme d’indice $s(n)$ est obtenu par application de $f$ au terme d’indice $n$. L’énoncé rigoureux du théorème, dont la démonstration repose sur les axiomes de Peano, est le suivant :

Théorème 1 [Théorème de récurrence]
Si $E$ est un ensemble, $a$ un élément de $E$ et $f:E\to E$ une application, alors il existe une unique suite $u:\mathbb N\to E$ d’éléments de $E$ telle que :
i) $u(0)=a$
ii) $u(n+1)=f(u(n))$ pour tout entier naturel $n$.

Les suites obtenues à partir de l’application du théorème de récurrence sont dites définies par récurrence.

2.Des axiomes de Peano à la structure arithmétique naturelle

2.1.Du successeur à l’addition

Tandis que les axiomes de Peano définissent en quelque sorte le nombre $0$ et la fonction successeur, dans la notation « $n+1$ » du successeur $s(n)$ de l’entier naturel $n$ les symboles $+$ et $1$ ne sont pour l’instant que des conventions d’écriture. En effet, pour parler de l’addition, et même du nombre $1$, dans ce contexte, il faudrait soit les avoir définis de manière axiomatique, ce que nous n’avons pas fait, soit les définir à partir des propriétés du successeur : c’est ce que nous allons faire, afin de montrer la puissance des axiomes de Peano. La définition de l’addition se fait par exemple « élément par élément » , en utilisant le théorème de récurrence : pour chaque entier naturel $n$ fixé, on définit l’expression $n+m$ pour tous les entiers naturel $m$, par récurrence sur $m$. On définit l’expression $n+0$ comme valant $n$, et en supposant que la valeur de $n+m$ est définie, on définit $n+(m+1)$ comme le successeur de $n+m$, c’est-à-dire $s(n+m)$ (ce que nous aurions noté auparavant $(n+m)+1$, mais cette fois-ci la notation est ambiguë !). Ainsi, pour tout entier naturel $n$ l’expression $n+m$ est définie pour chaque entier $m$, si bien qu’on a défini une addition $+$, opération de $\mathbb N\times\mathbb N$ dans $\mathbb N$. Le nombre $1$ est alors défini comme le successeur de $0$, (soit $1:=s(0)$), et pour tout entier naturel $n$ l’expression $n+1$ désigne maintenant la somme de $n$ et de $1$, c’est-à-dire par définition le successeur de $n+0$, soit le successeur de $n$ : la notation $n+1$ pour le successeur de $n$ se trouve ainsi justifiée par la définition de l’addition ! On peut démontrer, en utilisant le principe de récurrence, les propriétés naturelles de l’addition à partir de sa définition :

Proposition 1
Si $n,m,p$ sont des entiers naturels, alors on a :
i) $n+m=m+n$ (l’addition est dite commutative)
ii) $n+(m+p)=(n+m)+p$ (l’addition est dite associative).

Remarque 1
La définition par récurrence sur $m$ de l’expression $n+m$, pour $n$ fixé, applique le théorème de récurrence de la manière suivante : l’ensemble $E$ est $\mathbb N$, l’objet $a$ choisi comme premier élément est $n$, et la fonction $f:E\to E$ choisie comme « processus » est le successeur $s:\mathbb N\to \mathbb N$. La suite générée avec ces données est alors : $n,s(n)=n+1,s(s(n))=n+2,s(s(s(n)))=n+3,\ldots$ : c’est bien l’addition des entiers successifs à $n$.

2.2.Ordre naturel et multiplication