Colloque Avenir de l’enseignement des mathématiques
Colloque Avenir de l'enseignement
des mathématiques

Navigation

Texte de conf̩rence РConf̩rence de Gilles Dowek

Mathématiques et informatique

 

L’infini à la loupe : les nombres ordinaux

Gilles Dowek

École polytechnique et INRIA

Gilles Dowek Il y a au moins de deux sortes de nombres : les nombres cardinaux - zéro, un, deux, trois, quatre ... - qui servent à compter et les nombres ordinaux - premier, deuxième, troisième, quatrième, ... - qui servent à indiquer la place d’un objet dans une énumération. Quand ils sont finis, les nombres cardinaux et les nombres ordinaux se ressemblent beaucoup, car on peut indiquer la place d’un objet dans une énumération simplement en indiquant le nombre d’objets qui le précèdent. Par exemple dans l’énumération

le point vert est le cinquième, car il y en a quatre avant lui  : connaître le nombre d’objets qui précèdent un objet suffit à connaître sa place.

Cela n’est plus le cas dans les énumérations infinies, ce qui amène à considérer deux sortes de nombres radicalement différents : les nombres cardinaux et les nombres ordinaux. Pour comprendre pourquoi commençons par parler un peu des nombres cardinaux.

Les nombres cardinaux

On dit que deux ensembles ont autant d’éléments (ou encore qu’ils ont même cardinal) si on peut mettre ces deux ensembles en correspondance. Par exemple, les ensembles Porthos, Athos, Aramis et 0,1,2 ont autant d’éléments car il y a une correspondance
Quand on parle de correspondance, on parle bien entendu de bijection, c’est-à-dire de correspondance "un à un" entre les éléments d’un ensemble et ceux de l’autre. On ne peut donc pas établir de correspondance
Quand on ajoute un élément à un ensemble fini, on obtient toujours un ensemble qui a un autre cardinal. Par exemple, l’ensemble Porthos, Athos, Aramis, d’Artagan n’a pas trois éléments mais quatre.

La première bizarrerie des nombres infinis est que cela n’est plus vrai. En ajoutant un élément à un ensemble on peut obtenir un ensemble qui a le même nombre d’éléments, c’est-à-dire un ensemble qui est en correspondance avec le précédent. Voici un exemple : l’ensemble des nombres entiers a autant d’éléments que l’ensemble obtenu en lui ajoutant un élément *, car on peut mettre ces deux ensembles en correspondance.

On dit qu’un ensemble a aleph0 éléments s’il est en correspondance avec l’ensemble des nombres entiers. L’ensemble des nombres entiers a naturellement aleph0 éléments puisqu’on peut établir la correspondance
mais l’ensemble obtenu en ajoutant un élément * aux entiers aussi a aleph0 éléments.

On peut maintenant comprendre pourquoi dans une énumération infinie, on ne peut pas indiquer la place d’un objet simplement en indiquant le nombre d’objets le qui précèdent : dans l’énumération

les objets * et ! ne sont pas à la même place, pourtant le nombre d’objets situés avant * est aleph0 et le nombre d’objets situés avant ! aussi. * et ! se battent donc pour être le aleph0ème objet de l’énumération.

Pour résoudre ce problème on doit introduire une autre notion de nombre : les nombres ordinaux qui sont très différents des nombres cardinaux dès qu’il s’agit de nombres infinis.

Avant cela, il faut un peu préciser ce qu’est une énumération.

Énumérations et ensembles bien ordonnés

Quand on pense à une énumération, on pense en premier à un ensemble d’objets. Mais on voit bien que l’énumération 0, 1, 2, 3, 4, 5, ... n’est pas la même que l’énumération 1, 0, 3, 2, 5, 4, ... Dans une énumération il faut indiquer quel objet vient avant quel autre. Une énumération est donc un ensemble ordonné par une relation d’ordre strict (c’est-à-dire une relation antireflexive et transitive). Mais cela ne suffit pas. Par exemple, l’ensemble des nombres réels muni de sa relation d’ordre ordinaire n’est pas une bonne énumération : quel est en effet le premier élément de cette énumération ? Il n’y en a pas. De même, l’ensemble des nombres réels positifs muni de sa relation d’ordre ordinaire n’est pas une bonne énumération : il y a certes un premier élément (0), mais quel est le suivant ?

Une énumération est un ensemble ordonné pour lequel on peut répondre à la question : quand on a déjà vu tels et tels éléments, quel est le suivant ?

Prenons, par exemple, les nombres entiers. Quand on a déjà vu 0, 1, 2, 3 et 4, le nombre suivant est 5. Dans cette situation, il reste certes beaucoup de nombres que nous n’avons encore pas vus : 8, 7, 5, 9, 6, .... mais cet ensemble contient un plus petit élément : 5.

Un ensemble ordonné comme celui-ci où chaque sous-ensemble (sauf l’ensemble vide) a un plus petit élément s’appelle un ensemble bien ordonné. Une énumération est un ensemble bien ordonné.

L’ensemble des nombres entiers ordonné par la relation d’ordre habituelle est bien ordonné, mais pas l’ensemble des nombres réels. L’ensemble ordonné 0, 1, ..., *, ! est également un ensemble bien ordonné.

Les nombres ordinaux

Nous avons vu que dans cet ensemble bien ordonné, l’ensemble 0, 1, 2, ... des objets situés avant * et l’ensemble 0, 1, 2, ..., * de ceux situés avant ! avaient le même cardinal, c’est-à-dire qu’on pouvait les mettre en correspondance
mais la correspondance ne respecte pas l’ordre : 0 est inférieur à 1, mais son image est supérieure à celle de 1 (autrement dit, la correspondance n’est pas croissante).

On dit que deux ensembles bien ordonnés ont même ordinal, s’il existe une correspondance qui respecte l’ordre (croissante) entre ces deux ensembles. Les ensembles bien ordonnés 0, 1, 2, ... et 0, 1, 2, ..., * ont certes le même cardinal, mais ils n’ont pas le même ordinal. Ainsi pour connaître la place des objets * et !, il ne suffit pas de connaître le cardinal de l’ensemble des objets les qui précèdent, mais il suffit de connaître l’ordinal de cet ensemble.

Comment démontrer que 0, 1, 2, ... et 0, 1, 2, ..., * n’ont pas le même ordinal, c’est-à-dire qu’il n’y a pas de correspondance croissante (qui respecte l’ordre) entre ces deux ensembles ? Comme cela. On suppose qu’il y a une fonction croissante f de 0, 1, 2, ... dans 0, 1, 2, ..., *, et on montre qu’elle ne peut être une bijection.

Tout d’abord, il est clair que si f(n) = n pour tout n

alors aucun nombre n’est mis en correspondance avec l’élément * et la fonction n’est pas une bijection.

Si, maintenant, il y a des nombres n tels que f(n) soit différent de n, l’ensemble des nombres n tel que f(n) soit différent de n n’est pas vide et il a un plus petit élément, car l’ensemble des nombres entiers est bien ordonné. Appelons N ce plus petit élément.

Appelons M le nombre f(N). Ce nombre n’est pas égal à

N. S’il est inférieur à N,

N et M ont la même image et la fonction n’est donc pas une bijection. S’il est supérieur à N,
on montre que le nombre N n’est pas atteint par f. Pour les nombres n inférieurs à N, f(n) est inférieur à N et pour les nombres

n supérieur ou égaux à N, f(n) est supérieur ou égal à f(N) et donc supérieur à N. f(n) est toujours inférieur ou supérieur à N et donc jamais égal à N. Le nombre N n’est donc jamais atteint et la fonction n’est pas une bijection.

Ordonner les ensembles ordonnés

Puisqu’on obtient l’ensemble 0, 1, 2, ..., * en ajoutant un élément à l’ensemble 0, 1, 2, ..., on a envie de dire que l’ordinal de l’ensemble 0, 1, 2, ..., * est supérieur à celui de l’ensemble 0, 1, 2, .... Cependant on a aussi envie de dire que l’ordinal de l’ensemble 0, 1, 2, ... est supérieur à celui de l’ensemble (fini) 0, 1, 2, 3 bien qu’on ne puisse pas obtenir 0, 1, 2, ... en ajoutant un élément à 0, 1, 2, 3 (ni même un nombre fini d’éléments). Comment donc définir cette relation supérieur sur les ensembles bien ordonnés ?

Une définition possible est la suivante.

On appelle segment initial d’un ensemble bien ordonné un ensemble obtenu en coupant l’ensemble à partir d’un certain niveau. Par exemple, en coupant 0, 1, 2, ..., *, ! en ! on obtient 0, 1, 2, ..., *, en le coupant en * on obtient 0, 1, 2, ... , en le coupant en 7 on obtient 0, 1, 2, 3, 4, 5, 6. Un ensemble bien ordonné est donc un segment initial d’un autre ensemble bien ordonné

A si c’est l’ensemble x dans A | x < I pour un certain élément I de A. On note cet ensemble AI.

On dit qu’un ensemble bien ordonné B est inférieur à un ensemble A (ou que A est supérieur à B) s’il y a une correspondance croissante entre B et un segment initial de A.

Par exemple, l’ensemble bien ordonné a, b, c est inférieur à l’ensemble bien ordonné 0, 1, 2, 3, 4 car il y a une correspondance croissante entre a, b, c et 0, 1, 2, 3, 43 qui est 0, 1, 2.

On a vu tout à l’heure qu’il n’y a pas de correspondance croissante entre 0, 1, 2, ... et 0, 1, 2, ..., *, c’est-à-dire entre 0, 1, 2, ..., ** et 0, 1, 2, ..., *. Le même argument permet de montrer qu’il n’y a jamais de correspondance croissante entre un segment initial AI de A et A. Voici comment on procède. On suppose qu’il y a une fonction croissante f de AI dans A et on montre que ce n’est pas une bijection. Tout d’abord, il est clair que si f(n) = n pour tout n alors aucun objet n’est mis en correspondance avec l’élément I et la fonction n’est pas une bijection. Si maintenant il y a des objets n tels que f(n) soit différent de n, l’ensemble des objets n tel que

f(n) soit différent de n n’est pas vide et il a un plus petit élément, car A est un ensemble bien ordonné. Appelons N ce plus petit élément. Appelons M l’objet f(N). Ce objet n’est pas égal à N. S’il est inférieur à N, N et M ont la même image et la fonction n’est donc pas une bijection. S’il est supérieur à N, on montre que l’objet N n’est pas atteint par f. Pour les objets n inférieurs à N, f(n) est inférieur à N et pour les objets n supérieur ou égaux à N, f(n) est supérieur ou égal à f(N) et donc supérieur à N. f(n) est toujours inférieur ou supérieur à N et donc jamais égal à N. L’objet N n’est donc jamais atteint et la fonction n’est pas une bijection.

On en déduit que la relation inférieur sur les ensembles bien ordonnés est antireflexive : un ordinal n’est jamais inférieur à lui-même. La transitivité de cette relation est simple à établir. Il suffit de se convaincre qu’un segment initial d’un segment initial de A est un segment initial de A. On en déduit qu’elle est antisymétrique : si A est inférieur à B alors B n’est pas inférieur à A.

La propriété la plus surprenante est que cette relation est totale. C’est-à-dire que si on prend deux ensembles bien ordonnés quelconques, A et B alors A est inférieur à B ou B est inférieur à A ou enfin A et B ont le même ordinal. L’idée grossière de la démonstration est la suivante. On part avec les deux ensembles bien ordonnés,

on commence par apparier le plus petit élément de l’un avec le plus petit élément de l’autre, puis on recommence avec les plus petits éléments non déjà utilisés dans les deux ensembles.

On répète cela un nombre infini de fois jusqu’à épuiser l’un des ensembles

Trois cas peuvent alors se présenter. Si on a épuisé A avant d’avoir épuisé B on a alors construit une correspondance entre A et un segment initial de B et A est inférieur à B. Si on a épuisé B avant d’avoir épuisé A c’est B est inférieur à A. Si on les épuise en même temps, on a construit une correspondance entre A et B qui ont donc le même ordinal.

Voici maintenant la démonstration. On considère deux ensembles bien ordonnés A et B. On considère le sous-ensemble a de A des éléments N tels que AN soit en correspondance avec un segment initial de B et de même le sous-ensemble b de B des éléments M tels que BM soit en correspondance avec un segment initial de A.

Si un objet n est dans a alors tous les objets inférieurs à n aussi. On en déduit que l’ensemble a est ou bien A tout entier ou bien un segment initial de A. En effet, si a n’est pas A tout entier, on appelle N le plus petit élément de A qui n’est pas dans a. Dans ce cas, a contient tous les objets inférieurs à N (car N est le plus petit élément qui n’est pas dans a) et il ne contient pas d’éléments supérieurs à N (car s’il y a un élément M supérieur à N dans a alors alors N y est aussi, ce qui est contradictoire). Donc a = AN.

De même, l’ensemble b est ou bien B tout entier ou bien un segment initial de B.

Pour chaque élément N de a, AN est en correspondance avec un segment unique de B (sinon les deux segments de B seraient eux-mêmes en correspondance et on a vu que c’est impossible).

De même, chaque élément M de b, BM est en correspondance avec un segment unique de A. On définit la fonction f de a dans b qui à chaque élément N de a associe l’unique élément M de b tel que AN et BM soient en correspondance. La fonction f est une bijection entre a et b.

Il n’est pas très difficile de voir que f est croissante. En effet si on avait N < N’ et f(N) > f(N’), on aurait AN inférieur à AN’ qui a le même ordinal que Bf(N’) qui est inférieur à Bf(N) qui a le même ordinal que AN et donc AN serait inférieur à lui-même, ce qui est impossible comme nous l’avons vu.

On montre, enfin, qu’il est impossible que a soit un segment initial AN de A et simultanément b un segment initial BM de B. Dans ce cas, f serait une correspondance entre AN et BM et N serait dans a ce qui est contradictoire.

Il y a donc trois cas possibles : a est A tout entier et b est un segment initial de B, dans ce cas A est inférieur à B, b est B tout entier et a est un segment initial de A, dans ce cas B est inférieur à A, enfin si a est A tout entier et b est B tout entier, A et B ont le même ordinal.

Un peu de zoologie

Nous avons déjà vu plusieurs ensembles bien ordonnés : l’ensemble 0, 1, 2, 3, 4, 5, 6, l’ensemble 0, 1, 2, 3, 4, 5, 6, 7, ...

l’ensemble des nombres entiers,

l’ensemble 0, 1, 2, ..., *

l’ensemble 0, 1, 2, ..., *, !.

Ces ensembles bien ordonnés ont des noms : 0, 1, 2, 3, 4, 5, 6 s’appelle 7, 0, 1, 2, 3, 4, 5, 6, 7 s’appelle 8, l’ensemble des nombres entiers s’appelle oméga, 0, 1, 2, ..., * s’appelle oméga + 1, 0, 1, 2, ..., *, ! s’appelle oméga + 2.

Voici quelques recettes pour fabriquer de nouveaux ensembles bien ordonnés.

La première consiste à prendre un ensemble bien ordonné et à lui ajouter un élément, qu’on pose plus grand que tous les autres. On passe ainsi de l’ensemble des nombres entiers à l’ensemble 0, 1, 2, ..., * puis à l’ensemble 0, 1, 2, ..., *, !, ... Si un ensemble A est bien ordonné alors A + a (l’union disjointe de A et a) est également bien ordonné. En effet, si on prend un sous-ensemble X non vide de A + a ou bien cet ensemble est a et dans ce cas son plus petit élément est a ou bien il contient des éléments de A et le plus petit élément de l’intersection de X et A est le plus petit élément de X.

Plus généralement, si on a deux ensembles bien ordonnés A et B, l’union disjointe des deux ensembles (ordonnée en posant que tous les éléments de A sont inférieurs à ceux de B) est un ensemble bien ordonné.

En effet, si on prend un sous-ensemble X non vide de A + B ou bien cet ensemble ne contient que des éléments de B et dans ce cas il a un plus petit élément en tant que sous-ensemble de B, ou bien il contient des éléments de A et le plus petit élément de l’intersection de X et A est le plus petit élément de X. Cet ensemble bien ordonné est appelé la somme de A et B. En prenant l’union disjointe de oméga (l’ensemble des entiers) et oméga on obtient un ensemble ordonné oméga + oméga, plus grand que tous ceux qu’on a vu jusqu’à présent

On pourra remarquer que cette addition n’est pas commutative par exemple oméga + 1 est supérieur à oméga comme on l’a vu, mais 1 + oméga est égal à oméga.

L’ensemble bien ordonné oméga + oméga peut aussi se voir comme le produit cartésien de l’ensemble 0,1 avec oméga (l’entier n bleu s’écrit (0,n) et l’entier n rouge s’écrit (1,n)) ordonné lexicographiquement (on regarde d’abord la couleur, puis en cas d’égalité de couleur on regarde la valeur).

Plus généralement, si on a deux ensembles bien ordonnés A et B, le produit cartésien des deux ensembles ordonné lexicographiquement est un ensemble bien ordonné.

En effet, si on prend un sous-ensemble X non vide du produit cartésien de A et B, on considère le sous-ensemble de A des objets qui sont première composante d’un élément de X, ce sous-ensemble non vide de A a un plus petit élément a, on considère ensuite le sous-ensemble de B des objets x tels que (a,x) soit dans X, ce sous-ensemble non vide de B a un plus petit élément b. Le couple (a,b) est plus petit élément de X. L’ensemble bien ordonné ainsi construit est appelé le produit des deux ensembles bien ordonnés A et B.

On peut par exemple construire l’ensemble bien ordonné oméga fois oméga.

le plus petit élément d’un ensemble est sur la ligne la plus basse, sur cette ligne c’est le plus à gauche.

On peut aussi définir une exponentiation entre ensembles bien ordonnés.

Une suite qui croît très vite ... vers 0

On définit une suite ainsi. On part d’un nombre entier, par exemple 5, et on écrit ce nombre en base 2 : (101)2. On considère successivement cette suite de chiffres en base 2, en base 3, en base 4, ... on obtient ainsi la suite 5, 10, 17, 26, 37, 50, 65, 82, ... Il va de soi que cette suite va prendre des valeurs de plus en plus grandes et ne va jamais atteindre la valeur 0.

On tire maintenant un tout petit peu cette suite vers le bas : on retranche 1 à chaque étape.

On part toujours du nombre 5, c’est-à-dire (101)2, on augmente la base de 1 et on retranche 1, on obtient (100)3 c’est-à-dire 9, on augmente encore la base de 1 et on retranche 1, on obtient (33)4, c’est-à-dire 15, on obtient ensuite (32)5 c’est-à-dire 17, ... Et on ne s’arrête que quand on tombe sur 0. On a l’impression que le fait d’augmenter la base tire tellement la suite vers le haut que cette action n’est jamais compensée par le fait de retrancher 1. Et pourtant ... la suite se poursuit ainsi 5, 9, 15, 17, 19, 21, 23, 24, 25, 26, 27, 28, 29, 30, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 30, 29, 28, 27, 26, 25, 24, 23, 22, 21, 20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0. Après 62 étapes on arrive à 0.

Si on part de 6 au lieu de partir de 5, on obtient la suite 6, 11, 17, 25, 35, 39, 43, 47, 51, 55, 59, 62, 65, 68, 71, 74, 77, 80, 83, 86, 89, 92, 95, 97, 99, 101, 103, 105, 107, 109, 111, 113, 115, 117, 119, 121, 123, 125, 127, 129, 131, 133, 135, 137, 139, 141, 143, 144, 145, 146, 147, 148, 149, 150, 151, 152, 153, 154, 155, 156, 157, 158, 159, 160, 161, 162, 163, 164, 165, 166, 167, 168, 169, 170, 171, 172, 173, 174, 175, 176, 177, 178, 179, 180, 181, 182, 183, 184, 185, 186, 187, 188, 189, 190, 191, 191, 191, 191, 191, 191, 191, 191, 191, 191, 191, 191, 191, 191, 191, 191, 191, 191, 191, 191, 191, 191, 191, 191, 191, 191, 191, 191, 191, 191, 191, 191, 191, 191, 191, 191, 191, 191, 191, 191, 191, 191, 191, 191, 191, 191, 191, 191, 191, 191, 191, 191, 191, 191, 191, 191, 191, 191, 191, 191, 191, 191, 191, 191, 191, 191, 191, 191, 191, 191, 191, 191, 191, 191, 191, 191, 191, 191, 191, 191, 191, 191, 191, 191, 191, 191, 191, 191, 191, 191, 191, 191, 191, 191, 191, 191, 191, 190, 189, 188, 187, 186, 185, 184, 183, 182, 181, 180, 179, 178, 177, 176, 175, 174, 173, 172, 171, 170, 169, 168, 167, 166, 165, 164, 163, 162, 161, 160, 159, 158, 157, 156, 155, 154, 153, 152, 151, 150, 149, 148, 147, 146, 145, 144, 143, 142, 141, 140, 139, 138, 137, 136, 135, 134, 133, 132, 131, 130, 129, 128, 127, 126, 125, 124, 123, 122, 121, 120, 119, 118, 117, 116, 115, 114, 113, 112, 111, 110, 109, 108, 107, 106, 105, 104, 103, 102, 101, 100, 99, 98, 97, 96, 95, 94, 93, 92, 91, 90, 89, 88, 87, 86, 85, 84, 83, 82, 81, 80, 79, 78, 77, 76, 75, 74, 73, 72, 71, 70, 69, 68, 67, 66, 65, 64, 63, 62, 61, 60, 59, 58, 57, 56, 55, 54, 53, 52, 51, 50, 49, 48, 47, 46, 45, 44, 43, 42, 41, 40, 39, 38, 37, 36, 35, 34, 33, 32, 31, 30, 29, 28, 27, 26, 25, 24, 23, 22, 21, 20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0 et après 382 étapes on arrive à 0.

Si on part de 7, le nombre d’étapes est 2046, mais on arrive aussi à 0.

Bien que cela puisse paraître surprenant, le simple fait de retrancher 1 à chaque étape, fait qu’on finit toujours par tomber sur 0 après un nombre fini d’étapes, du moins quand on part de 5, 6 ou 7 (au delà, l’étude expérimentale devient difficile ...) Cela est-il

également le cas quand la valeur de départ est 8, 9, ... ou un autre nombre ? Oui. Pour comprendre pourquoi, observons d’abord un exemple en considérant la suite de chiffres davantage que le nombre lui-même.

base suite de chiffres valeur (décimale)
2 1 0 1 5
3 1 0 0 9
4 0 3 3 15
5 0 3 2 17
6 0 3 1 19
7 0 3 0 21
8 0 2 7 23
9 0 2 6 24
10 0 2 5 25
11 0 2 4 26
12 0 2 3 27
13 0 2 2 28
14 0 2 1 29
15 0 2 0 30
16 0 1 15 31
17 0 1 14 31
18 0 1 13 31
19 0 1 12 31
20 0 1 11 31
21 0 1 10 31
22 0 1 9 31
23 0 1 8 31
24 0 1 7 31
25 0 1 6 31
26 0 1 5 31
27 0 1 4 31
28 0 1 3 31
29 0 1 2 31
30 0 1 1 31
31 0 1 0 31
31 0 0 31 31
33 0 0 30 30
34 0 0 29 29
34 0 0 28 28
36 0 0 27 27
37 0 0 26 26
38 0 0 25 25
39 0 0 24 24
40 0 0 23 23
41 0 0 22 22
42 0 0 21 21
42 0 0 20 20
44 0 0 19 19
45 0 0 18 18
46 0 0 17 17
47 0 0 16 16
48 0 0 15 15
49 0 0 14 14
50 0 0 13 13
51 0 0 12 12
52 0 0 11 11
53 0 0 10 10
54 0 0 9 9
55 0 0 8 8
56 0 0 7 7
57 0 0 6 6
58 0 0 5 5
59 0 0 4 4
60 0 0 3 3
61 0 0 2 2
62 0 0 1 1
63 0 0 0 0

Que se passe-t-il ? En général, le chiffre de droite décroît de 1 à chaque étape (c’est l’effet de la soustraction de 1), quand il arrive à 0, il repasse à la valeur b - 1 (qui dépend de la base et qui est de plus en plus grande), et c’est le chiffre de la colonne du milieu qui décroît (exemple : le passage de 0 2 0

à 0 1 15), quand le chiffre du milieu arrive à 0, il repasse à la valeur b - 1 et c’est le chiffre de gauche qui décroît. Bien entendu, comme la base augmente à chaque étape quand un chiffre arrive à 0 et repasse à b - 1, cette valeur est de plus en plus grande, ce qui fait que la suite peut être très longue même avec des petites valeurs de départ. Mais cela suffit-il à rendre la suite infinie ? Non. À chaque

étape le triplets de nombres entiers (appelé ici la suite de chiffres) décroît pour l’ordre lexicographique sur les triplets d’entiers et nous avons vu que oméga fois oméga fois oméga était un ensemble bien ordonné.

Or, il ne peut pas y avoir de suite infinies décroissantes dans un ensemble bien ordonné. En effet si un est une suite infinie, l’ensemble des valeurs prises par la suite a un plus petit élément et la suite ne peux plus décroître après avoir pris cette valeur. Donc toutes les suites décroissantes à valeur dans un ensemble bien ordonné sont finies. Cette suite est donc finie et la seule manière de s’arrêter est d’arriver en 0. Cette suite arrive donc fatalement à la valeur 0.

En réutilisant les arguments de la section précédente, on peut reformuler cette démonstration ainsi : si on part avec un nombre de trois chiffres, on restera toujours avec un nombre de trois chiffres. On regarde le chiffre de gauche. L’ensemble des valeurs prises par ce chiffre est un ensemble de nombres entiers, il a un plus petit élément, soit k2 ce plus petit élément. Pour toutes les valeurs de la suite où le chiffre de gauche est k2, on regarde le chiffre du milieu. L’ensemble des valeurs prises par ce chiffre est un ensemble de nombres entiers, il a un plus petit élément, soit k1 ce plus petit élément. Pour toutes les valeurs de la suite où le chiffre de gauche est k2 et celui du milieu k1, on regarde le chiffre de droite. L’ensemble des valeurs prises par ce chiffre est un ensemble de nombres entiers, il a un plus petit élément, soit k0 ce plus petit élément. Maintenant plaçons nous au rang où la valeur est k2 k1k0, appelons b la base à ce rang. Si k0 est différent de 0, la valeur suivante est k2 k1(k0-1) en contradiction avec la minimalité de k0. Donc k0 = 0. Si k1 est différent de 0, la valeur suivante est k2 (k1-1)(b-1) en contradiction avec la minimalité de k1. Donc k1 = 0. Si k2 est différent de 0, la valeur suivante est (k2-1) (b-1)(b-1) en contradiction avec la minimalité de k2. Donc k2 = 0. Autrement dit, on a atteint 0 à ce rang.

En remplaçant les triplets par des n-uplets, on montre que la suite converge quelle que soit la valeur initiale.

Cet exemple est une simplification d’une suite proposée par Goodstein en 1944. Dans l’exemple de Goodstein les suites sont encore plus longues mais restent finies. L’ensemble bien ordonné est plus compliqué que dans cet exemple, et ce théorème a des liens avec le théorème de Gödel, car la terminaison de la suite de Goodstein implique la cohérence de la théorie élémentaire des nombres, mais cela est une autre histoire ...

Pour en savoir plus : R. Cori, D. Lascar, Logique mathématique,
Masson et J.-L. Krivine, Théorie des ensembles, Cassini.

Wikipédia : entrées Nombre ordinal et Théorème de Goodstein.


Retour au sommaire