De la Récurrence à l’Induction

Vignette écrite par Michèle Artigue et Ferdinando Arzarello.
Un quadrillage fait de carrés étant donné, il est facile de construire des carrés dont tous les sommets sont des nœuds du quadrillage. Mais est-ce possible pour d’autres polygones réguliers, par exemple pour un octogone ? La réponse est : « Non » et on peut le démontrer, pour l’octogone, de la façon suivante (Payan, 1994) :

Oublions momentanément le quadrillage. A chaque octogone régulier (c’est-à-dire un octogone dont tous les côtés et tous les angles sont égaux), on associe un second octogone construit comme indiqué sur la figure 2. Le point $A'$ est l’image du point $A$ par la rotation dans le sens direct de centre $B$ et d’angle $90^{\circ}$ , le point $B'$ est l’image de $B$ par la rotation dans le sens direct de centre $C$ et d’angle $90^{\circ}$ , et ainsi de suite… On peut démontrer qu’on obtient ainsi un second polygone régulier homothétique du premier et de même centre $O$ . Son aire est strictement inférieure à celle de l’octogone initial.

Revenons maintenant aux polygones convexes dont les sommets sont des nœuds d’un quadrillage. On associe à un tel polygone $P$ le nombre $S(P)$ de points du quadrillage que ce polygone contient sans compter ceux du bord. Par exemple, pour le pentagone $P$ de la figure 3, $S(P)$ qui est le nombre de points rouges est égal à $26$ (rappelons qu’il est relié à l’aire du pentagone par la formule de Pick).

Figure 2 : Construction de l’octogone intérieur

Figure 3 : Calcul de S(P)

Supposons maintenant que l’on soit capable de construire un octogone régulier dont les sommets soient des nœuds du quadrillage : $P_1$ . Par la construction décrite précédemment, on peut lui associer un autre octogone régulier $P_2$ dont les sommets sont aussi sur le quadrillage car cette propriété est préservée par rotation d’angle $90^{\circ}$ et de centre un point du quadrillage. De plus, l’entier $S(P_2)$ sera strictement inférieur à l’entier $S(P_1)$ . En itérant le processus, on arrive donc nécessairement à une contradiction.

Nous avons prouvé l’impossibilité en faisant un raisonnement bien connu en arithmétique depuis l’époque de Fermat : un raisonnement par descente infinie. Sur quoi repose ce raisonnement ? Sur l’impossibilité de construire une suite infinie décroissante stricte d’entiers. Cette impossibilité repose sur une propriété de l’ordre sur les entiers : celle d’être un bon ordre, c’est-à-dire un ordre tel que toute partie non vide possède un plus petit élément. En effet, supposons que l’on puisse construire une suite infinie décroissante stricte d’entiers $(u_n )$ . Notons $S$ l’ensemble de ses termes : $S=\{ u_0, u_1, ... , u_n ... \}$ . S a un plus petit élément, notons le $\alpha$ . C’est un terme de la suite, donc il existe un $k$ tel que $\alpha = u_k$ . Mais alors $u_{k+1} < u_k$ et appartient à $S$ , ce qui contredit la définition de $\alpha$ .

Principe de récurrence et bon ordre sur les entiers

Le principe de récurrence, généralement introduit au lycée, découle en fait de la propriété de bon ordre des entiers. Dans l’axiomatique de l’arithmétique proposée par Peano (1908), c’est le troisième axiome et il est énoncé sous la forme suivante :

« Si $S$ est un ensemble qui contient $0$ et si lorsque $a$ appartient à $S$ , le successeur de $a$ appartient à $S$ , alors tous les nombres appartiennent à $S$ ».

On l’énonce plus usuellement dans l’enseignement sous la forme suivante : si une propriété $P$ portant sur des entiers est satisfaite par $0$ et si, dès qu’elle satisfaite par un entier $n$ , elle l’est par son successeur $n+1$ , alors elle est satisfaite par tous les entiers.

Si l’on admet que l’ordre sur les entiers est un bon ordre, alors le principe de récurrence en découle directement. En effet, supposons que la propriété $P$ ne soit pas satisfaite par tous les entiers, et soit $S$ l’ensemble des entiers qui ne la satisfont pas. $S$ est non vide, il a donc un plus petit élément $n_0$ et $n_0$ est non nul puisque $0$ satisfait $P$ . Il a donc un prédécesseur $n_0 -1$ qui n’est pas dans $S$ . Mais alors $n_0 -1$ satisfait $P$ et donc également $n_0$ , ce qui contredit la définition de $n_0$ .

Le principe de récurrence peut aussi être utilisé pour définir des fonctions. C’est ce que l’on fait par exemple quand on définit des suites par récurrence, en se donnant une relation $u_{n+1}=f(u_n)$ où $f$ est une fonction définie sur $\mathbb{N}$ , et un premier terme $u_0$ . C’est ce que l’on appelle aussi une définition par induction.

Récurrence et induction : une première généralisation

Plus généralement, on peut raisonner par induction sur tout ensemble qui est muni d’un bon ordre. Considérons par exemple l’ensemble $\{0,1\} \times \mathbb{N}$ muni de l’ordre lexicographique $(a,b) \leqslant (c,d)$ si $a < c$ ou $a=c$ et $b \leqslant d$ . Cet ordre est un bon ordre. En effet soit $S$ un sous ensemble non vide de $\{0,1\} \times \mathbb{N}$ , nous pouvons distinguer deux cas :

soit tous les éléments de $S$ sont de la forme $(1,b)$ . Alors $\{ b \mid (1,b) \in S \}$ est un sous-ensemble non vide de $\nathbb{N}$ et il a un plus petit élément $b_0$ . Alors $(1,b_0)$ est le plus petit élément de $S$ ;
soit, il existe un élément de $S$ de la forme $(0,b)$ . Alors, montrer que $S$ a un plus petit élément revient à montrer que $\{ b \mid (0,b) \in S \}$ a un plus petit élément, ce qui est nécessairement le cas.

De la même façon, l’ordre lexicographique sur $\mathbb{N}^2$ et plus généralement sur $\mathbb{N}^p$ est un bon ordre. Nous laissons au lecteur le soin d’adapter à ces cas la démonstration ci-dessus. Dans ces ensembles donc, il ne peut exister de suite infinie décroissante stricte et ce, même si pour tout élément de la forme $(a_1, a_2, ... , a_p)$ avec $a_1 \neq 0$ il existe une infinité d’éléments qui lui sont inférieurs, tous ceux de la forme $(b_1, b_2, ..., b_p)$ avec $b_1 < a_1$ .

Dans $\mathbb{N}^p$ donc, le raisonnement par descente infinie que nous avons utilisé dans le premier exemple s’applique. Et dans $\mathbb{N}^p$ , on peut également définir des fonctions par induction. C’est le cas par exemple pour la célèbre fonction de $\mathbb{N}^2$ dans $\mathbb{N}$ introduite par Ackermann en 1932 sur laquelle nous reviendrons dans la suite de cette vignette.

Induction et ordinaux

Dans la théorie des ensembles, cette notion de bon ordre, essentielle au raisonnement mathématique, s’exprime à travers la notion d’ordinal et l’on ne s’y arrête pas à des bons ordres comme ceux mentionnés ci-dessus. Les ordinaux et donc les entiers eux-mêmes qui sont les ordinaux finis y sont définis comme des ensembles bien ordonnés par la relation d’appartenance et transitifs (un ensemble $X$ est transitif si pour tout élément $z$ d’un élément $y$ de $X$ est aussi un élément de $X$ ), mais nous nous contenterons ici d’une vision plus intuitive de ce que sont les ordinaux transfinis introduits par Cantor à la fin du 19e siècle. Le premier ordinal infini est noté $\omega$ et il est la réunion de tous les ordinaux finis. Il représente l’ordre sur les entiers. Il a un successeur $\omega +1$ qui a lui-même pour successeur $\omega +2$ , et ainsi de suite… Le plus petit ordinal plus grand que tous les $\omega +n$ est $\omega + \omega$ noté aussi $\omega . 2$ . Le plus petit ordinal plus grand que tous les $\omega . n$ est $\omega^2$ et l’on continue ainsi.

$0, 1, 2... n... \omega, \omega+1, \omega+2… \omega+n... \omega.2, \omega.2+1, \omega.2+2... \omega.2+n... \omega.3... \omega.n ... \omega^2 ... \omega^3... \omega^\omega ...$

Il y a en fait deux types d’ordinaux, ceux qui sont successeurs d’un ordinal donné comme $\omega +n$ , $\omega ^\omega +n$ , pour $n$ non nul, et ceux qui n’ont pas de prédécesseur mais sont la réunion de tous les ordinaux inférieurs, comme $\omega$ , $\omega ^n$ , $\omega^\omega, ...$ dans la liste ci-dessus. On remarquera que l’ordre lexicographique que nous avons mis sur $\{0,1\} \times \mathbb{N}$ munit cet ensemble d’un ordre qui n’est autre que celui de l’ordinal $\omega+\omega$ . La généralisation de cet ordre à l’ordre lexicographique sur $\mathbb{N} \times \mathbb{N}$ correspond à $\omega^2$ , … Mais il y a bien d’autres ordinaux que ceux que nous avons évoqués ici qui en fait sont tous dénombrables. En théorie des ensembles on peut démontrer, en utilisant l’axiome du choix, que tout ensemble peut être bien ordonné.

On peut définir des fonctions par induction sur les ordinaux. Pour définir une fonction par induction sur un ordinal $\alpha$ , il faut donner sa valeur en $0$ et un procédé qui permet d’obtenir la valeur de $f(\alpha)$ à partir des valeurs de la fonction pour les ordinaux précédents. Notons qu’il est souvent commode de distinguer deux cas pour définir $f(\alpha)$ , selon que $\alpha$ est limite ou successeur. Sur les ordinaux, on peut raisonner par descente infinie et la vignette Goodstein donne un exemple de tel raisonnement.

Retour sur la fonction d’Ackermann et méthode de diagonalisation

Un exemple de fonction définie par induction est la fonction d’Ackermann évoquée plus haut. Notée $A$ , elle est définie comme suit :

Pour tout entier $y$ , $A(0,y) = y+1$
Pour tout entier $x$ , $A(x+1,0) = A(x,1)$
Pour tout couple d’entiers $(x,y)$ , $A(x+1,y+1) = A(x, A(x+1,y))$ .

Sa valeur en un point $(x,y)$ est donc donnée explicitement si $x$ est nul. Lorsque $x$ est non nul, le calcul de $A(x,y)$ utilise des valeurs de la fonction elle-même mais en des points $(c,d)$ tels que $(c,d) < (x,y)$ pour l’ordre lexicographique. Ce calcul fait donc intervenir une suite strictement décroissante de tels points et cette suite est nécessairement finie puisque l’ordre lexicographique est un bon ordre. Elle peut en revanche être très longue. Combien de termes faut-il calculer par exemple pour obtenir $A(3,2)$ ?

Commençons avec un exemple plus simple. Calculons $A(2,2)$ en remplissant progressivement le tableau suivant :

Rendered by QuickLaTeX.com

La première condition $A(0,y)=y+1$ permet de remplir la première colonne. Ensuite, nous avons successivement :

$A(1,0) = A(0,1) = 2$ ; $A(1,1) = A(0,A(1,0)) = A(0, 2) = 3$ ; $A(1,2) = A(0,A(1,1))= A(0,3) = 4$ , et plus généralement on a :

$A(1,n+1)=A(0, A(1,n))=A(0,n+1)=n+2.$

On peut alors calculer :

$A(2,0) = A(1,1) = 3$ ; $A(2,1) = A(1,A(2,0)) = A(1,3) = 5$ et finalement $A(2,2) = A(1, A(2,1)) = A(1,5) = 7$ .

On voit donc que, pour calculer $A(2,2)$ , on utilise toutes les valeurs de la fonction pour les couples de la première colonne jusqu’à $(0,6)$ , de la deuxième jusqu’à $(1,5)$ , et de la troisième jusqu’à $(2,2)$ , soit $15$ valeurs.

Que se passe-t-il quand on veut calculer $A(3,2)$ et quelle est la valeur finalement obtenue pour $A(3,2)$ ? Nous laissons au lecteur le soin de répondre à cette question.

En fixant une des deux variables dans la fonction d’Ackermann, on obtient ce qu’il est convenu d’appeler les fonctions arithmétiques. Ainsi, si on note $A_n$ , la fonction obtenue en fixant la première variable à la valeur $n$ , nous avons vu que $A_0(y)=A(0,y)=y+1$ , donc $A_0$ est la fonction successeur et $A_1(y)=y+2$ . On peut montrer que $A_2(y)=2y+3$ et $A_3(y)=2^{y+3}-3$ . Ensuite, très vite, les expressions se compliquent, faisant intervenir des itérations de puissances et les valeurs de $A(x,y)$ deviennent en fait terriblement grandes en quelques étapes seulement. Par exemple, $A(5,0) = 65 533$ et $A(4,2)$ est un nombre de $19 729$ chiffres.

En fait, on peut démontrer que la fonction $g$ définie par $g(x)=A(x,x)$ est telle que, pour toute fonction récursive primitive, c’est-à-dire toute fonction qui peut être construire à partir de la fonction successeur et des fonctions projections de $\mathbb{N}^p$ dans $\mathbb{N}$ par composition et récurrence, il existe un entier $N$ telle que $g(x) > f(x)$ pour tous les $x$ supérieurs à $N$ . C’est ainsi que l’on prouve qu’il existe des fonctions calculables qui ne sont pas récursives primitives. La fonction d’Ackermann en est justement un exemple. Mais les fonctions usuelles sur les entiers, toutes celles que l’on manipule dans l’enseignement secondaire, sont bien, elles, des fonctions récursives primitives. Les fonctions qui à deux nombres entiers $x$ et $y$ associent leur somme et leur produit sont bien récursives primitives. On peut en effet les définir par récurrence en posant : pour tout $x$ , $x+0=x$ et $x.0=0$ et pour tout $y$ , $x+(y+1)=(x+y)+1$ et $x(y+1)=xy+x$ . On laisse le lecteur en déduire que la fonction qui, au couple d’entiers $(x,y)$ associe $x^y$ est elle aussi récursive primitive, ainsi que toute itération finie de telles exponentielles. Plus généralement, toute fonction qui peut se définir à partir de fonctions récursives primitives par un algorithme faisant intervenir une boucle de la forme « Pour $k$ allant de $1$ à $n$ » est récursive primitive.

La preuve fait appel à un argument de diagonalisation. C’est Georg Cantor qui, en 1874, inventa ce type d’argument pour démontrer que l’ensemble des nombres réels est non dénombrable, c’est-à-dire ne peut pas être mis en bijection avec l’ensemble des entiers. En 1891, il utilisa aussi cette méthode pour montrer que l’ensemble des parties d’un ensemble $X$ a toujours un cardinal strictement supérieur à celui de $X$ . L’invention de cette méthode diagonale a été une étape importante pour le développement de la logique mathématique. Elle est notamment à la base de la preuve de nombreux résultats dont le théorème d’incomplétude de Gödel, et de nombreux théorèmes de théorie de la calculabilité. Le paradoxe de Russell est également basé sur cette idée. On peut, dans l’enseignement secondaire, faire sentir la puissance de ce mode de raisonnement, en l’utilisant pour démontrer que l’intervalle $[0,1[$ n’est pas dénombrable, en s’appuyant sur le fait que tout nombre réel possède un développement décimal unique (à condition de ne pas considérer les développements impropres qui se terminent par une infinité de $9$ ). Supposons que l’intervalle $[0,1[$ soit un ensemble dénombrable et considérons un rangement de ces réels en une suite $(\alpha_n)$ . Le développement décimal illimité propre associé au réel $\alpha_n$ est de la forme : $0$ , $a_1^n a_2^n ...$ , et se termine par une infinité de $0$ si $\alpha_n$ est un nombre décimal. Considérons alors le réel $\alpha$ dont le développement décimal illimité est $0,b_1^n b_2^n ...$ avec $b_k=a_k ^k -1$ si $a_k ^k \neq 0$ et $b_k=a_k ^k +1$ si $a_k ^k = 0$ . Il est alors clair que $0,b_1 ^n b_2 ^n ...$ est le développement décimal illimité propre d’un réel $\beta$ de l’intervalle $[0,1[$ et que le réel $\beta$ n’est égal à aucun des réels de la suite $(\alpha_n)$ . L’intervalle $[0, 1[$ n’est donc pas dénombrable et a fortiori l’ensemble des nombres réels.

Morale

Le raisonnement par récurrence ou induction est présent dans les mathématiques dès l’antiquité. Dans les Eléments d’Euclide, il sert par exemple à prouver l’existence d’une infinité de nombres premiers. Parallèlement, le raisonnement par descente infinie est lui aussi présent dans les mathématiques depuis des siècles et on attache souvent son nom à celui de Fermat qui en a fait un usage répété dans ses travaux de théorie des nombres. Montrer l’équivalence de ces deux modes de raisonnement est en revanche une conquête plus récente, liée au développement de la logique mathématique. L’outil essentiel pour cela est la notion de bon ordre. Cette notion dans laquelle Georg Cantor voyait « un outil fondamental de la pensée » permet non seulement de comprendre l’équivalence entre récurrence et descente infinie mais aussi de raisonner par induction sur des ensembles autres que les seuls entiers et de comprendre notamment comment fonctionnent des récurrences imbriquées (doubles, triples) comme celles à l’œuvre dans la définition de la fonction d’Ackermann.

L’exemple par lequel nous avons débuté cette vignette a été choisi pour montrer que le raisonnement par induction est un outil général en mathématiques, et non pas un outil réservé à la seule théorie des nombres. Il joue un rôle déterminant notamment dans les mathématiques discrètes.

Au-delà de la seule induction, cette vignette a été l’occasion d’évoquer d’autres questions, non indépendantes des premières, et très importantes comme celle de la calculabilité. La mathématisation de la notion intuitive de calculabilité qui a nécessité le codage de différents types d’objets discrets, et l’utilisation des méthodes de diagonalisation a permis d’obtenir des résultats profonds dans différents domaines. Elle est aussi essentielle aux connexions entre mathématiques et informatique.

Références

[1] Calude C., Marcus S., Tevy, I (1979). The first example of a recursive function which is not primitive recursive, Historia Math., vol. 6, n. 4, 380–84.
[2] Cori, R., Lascar D. (). Logique mathématique, tome 2 : Fonctions récursives, théorème de Gödel, théorie des ensembles, théorie des modèles. Paris : Editions Dunod.
[3] Payan C. (1992). Une belle histoire de polygones et de pixels. MATh.en.JEANS” au Palais de la Découverte, pp. 99-106. mathenjeans.free.fr/amej/edition/actes/actespdf/92099106.pdf

Ce post est disponible en: Anglais, Allemand, Arabe, Khmère

De la Récurrence à l’Induction

Leave a Reply Cancel reply

Receive notice of every new vignette.

List of Vignettes

Sites of the Month

Books of the Month

Search

Meta

De la Récurrence à l’Induction

Share this:

Leave a Reply Cancel reply

Receive notice of every new vignette.

List of Vignettes

Sites of the Month

Books of the Month

Search

Meta