David Madore's WebLog: Nombres ordinaux : une (longue) introduction

Le principe d'induction transfinie

Les ordinaux sont une sorte d'échelle, disais-je dans l'introduction. Cela a deux aspects : chaque ordinal est une échelle (on a vu ci-dessus les dessins des échelles ω et ω²), et chaque ordinal est aussi le nom d'un barreau dans toutes les échelles plus longues : voyez comme le nom ω m'a servi à la fois à désigner l'échelle des entiers naturels et aussi un barreau particulier (le premier qui suit tous les entiers naturels) de l'échelle ω² ; l'échelle ω s'obtient en ne considérant de l'échelle ω² que les échelons strictement avant celui étiqueté ω ; l'échelle ω2, que je n'ai pas dessinée spécialement mais qui ressemble à deux copies de ω mises bout à bout, s'obtient en prenant tous les barreaux de ω² strictement avant le barreau lui-même nommé ω2, et ainsi de suite. Voici donc une règle du jeu qui sera très importante : chaque ordinal porte en lui, et est défini par, tous les ordinaux qui le précèdent (je m'excuse auprès des matheux pour qui une formulation tellement vague provoque des grincements de dents, mais j'essaie d'introduire les idées progressivement). Certains diront même qu'un ordinal est l'ensemble des ordinaux qui le précèdent : c'est la définition standard (due à von Neumann), c'est une façon très élégante de les construire dans le cadre de la théorie des ensembles, mais ce n'est pas du tout nécessaire. Ce qui est sûr, c'est qu'à chaque fois qu'on a fabriqué les ordinaux jusqu'à un certain point, ce certain point constitue lui-même un ordinal, qui s'inscrit à la fin de tout ce qu'on a fabriqué. Et c'est par ce procédé (itéré de façon infinie jusqu'à un niveau vertigineux d'infini) que tous les ordinaux sont fabriqués (en un sens, les ordinaux sont ce procédé).

La façon dont les mathématiques formalisent cette idée que tous les ordinaux sont fabriqués de par ce procédé est le principe suivant, qui s'appelle principe d'induction transfinie, et qui est un peu délicat à saisir[#5]. L'idée générale est que pour démontrer une propriété sur les ordinaux on peut supposer, à chaque étape α, qu'elle est déjà vérifiée par les ordinaux strictement inférieurs à α. Formellement, le principe d'induction transfinie se dit ainsi :

Si une propriété est telle que :

lorsque tous les ordinaux strictement inférieurs à α possèdent la propriété, (alors) α la possède,

alors tous les ordinaux possèdent cette propriété.

(De façon plus concise et plus cryptique : une propriété qui est satisfaite par tout ordinal pour lequel elle est satisfaite par tout ordinal strictement plus petit que lui, est satisfaite par tous les ordinaux.)

Pourquoi ? D'abord, 0 possède la propriété puisque tous les ordinaux strictement plus petits que lui (il n'y en a pas !) la possèdent. Puis 1 possède la propriété puisque tous les ordinaux plus petis que lui (c'est-à-dire 0) la possèdent (on vient de le voir). Puis 2 la possède puisque 0 et 1 la possèdent. Puis 3 parce que 0, 1 et 2 la possèdent. Et ainsi de suite pour tous les entiers naturels. Mais dès lors que tous les entiers naturels possèdent la propriété, ω la possède aussi. Donc ω+1 aussi. Et ainsi de suite. (Et ce et ainsi de suite renferme précisément la construction de tous les ordinaux.)

On ne peut pas décroître indéfiniment

Techniquement, je suis en train de redire la même chose, mais comme je m'adresse au non-mathématicien pour qui toutes les subtilités de l'induction transfinie ne sont pas forcément devenues apparentes à une seule lecture, mieux vaut dire ça clairement.

Choisissez un entier naturel. Maintenant, choisissez-en un autre, strictement plus petit. Puis un autre, strictement plus petit. Et encore. Et encore… Peut-on continuer ce petit jeu indéfiniment ? Non : tôt ou tard, on finit par tomber sur 0, et on ne peut plus continuer (il n'y a pas d'entier naturel strictement plus petit que zéro). Le nombre d'étapes peut être arbitrairement grand, mais il est toujours fini.

Mais si on part d'un ordinal quelconque ? Comme les ordinaux peuvent être infinis, on se dit peut-être qu'en partant d'un ordinal assez grand, on pourra continuer indéfiniment. Pourtant, ce n'est pas le cas : un processus qui diminue strictement un ordinal termine toujours en un nombre fini d'étapes (ou, mathématiquement parlant : il n'existe pas de suite infinie strictement décroissante d'ordinaux). On comprend un peu ce qui se passe si on part de l'ordinal ω : dès qu'on va le décroître, on va forcément tomber sur un entier naturel (rappelez-vous qu'il n'existe pas de ω−1 : les ordinaux plus petits que ω sont juste les entiers naturels), et on est ramené au cas des entiers naturels. Si on part de ω+1 ou plus généralement ω+k avec k un entier naturel, on tombera en un nombre fini d'étapes sur ω et on vient de traiter ce cas ; si on part de ω2, l'étape suivante sera justement un ω+k (ou tout de suite un entier naturel). Bref, on voit l'idée.

Ce phénomène, selon lequel on ne peut décroître indéfiniment un ordinal, reflète de nouveau l'idée que les ordinaux sont construits à partir d'ordinaux plus petits et « expliqués » par eux : il s'agit typiquement de quelque chose qu'on peut prouver par le principe d'induction transfini esquissé ci-dessus (et en fait il lui est équivalent). Pourquoi ? Supposons que je veuille montrer qu'en partant d'un ordinal α je ne peux pas décroître indéfiniment ; le principe d'induction transfinie me permet, pour démontrer cela, de supposer que je le sais déjà pour tout ordinal strictement inférieur à α : or, pour décroître α, je vais justement le remplacer à la première étape par un tel ordinal, et je sais alors (par hypothèse d'induction) que le processus termine. Aussi étonnant que cela puisse paraître, ceci constitue bien une démonstration !

Ce fait que les ordinaux ne peuvent pas décroître indéfiniment n'est pas du tout anecdotique : il est au cœur même de leur rôle en mathématiques. Parce qu'à l'inverse, on peut dire qu'à tout processus qui termine toujours en un nombre fini d'étapes est naturellement associé un ordinal, qui mesure la longueur de cette terminaison (si elle se fait toujours en au plus n étapes, alors l'ordinal est au plus l'entier naturel n ; l'ordinal ω, lui, indique que le processus peut prendre un nombre d'étapes a priori arbitrairement grand, mais que dès la première étape on saura borner le nombre d'étapes restantes ; l'ordinal ω+1 indique que c'est à la deuxième étape qu'on saura borner le nombre d'étapes restantes, etc.). [Ajout : voir une entrée ultérieure à ce sujet.]

C'est l'ordre qui est important

J'ai représenté plus haut les ordinaux ω et ω² par des petits dessins formés de bâtonnets verticaux. Dans quelle mesure ces dessins reflètent-ils vraiment les ordinaux en question ? La hauteur que j'ai donnée aux bâtonnets est uniquement utile pour aider à bien visualiser l'arrangement, et n'a aucune espèce de signification, seul compte leur arrangement sur l'axe gauche-droite. Et même sur cet axe, l'emplacement précis d'un bâtonnet n'a aucun sens, la seule chose qui compte est l'ordre des bâtonnets (l'ordre étant tel, comme je viens de l'expliquer, qu'on ne puisse pas indéfiniment passer d'un bâtonnet à un bâtonnet plus à gauche). Dès que vous avez une infinité de bâtonnets organisés comme sur la première figure (c'est-à-dire qu'il y en a un le plus à gauche, que chacun en a un suivant immédiatement à droite, et que tous les bâtonnets s'atteignent en parcourant un nombre fini à partir de celui qui est le plus à gauche), on peut dire qu'on a affaire à l'ordinal ω quel que soit son déguisement.

Par exemple, si vous partez de ω et que vous ajoutez un bâtonnet à gauche de (i.e., avant) celui qui était le plus à gauche, vous n'avez rien changé à l'affaire : vous avez simplement décalé tous les numéros (votre nouveau bâtonnet devient le nouveau 0, l'ancien 0 devient le 1, l'ancien 1 devient le 2, et ainsi de suite), et l'ordinal est toujours ω. C'est sur la base de ce fait qu'on pourra dire que 1+ω = ω. En revanche, si vous ajoutez un nouveau bâtonnet à droite de (i.e., après) tous ceux qui existaient, vous avez un nouvel ordinal, ω+1.

Quand on a ordonné des objets (de façon que deux quelconques soient toujours comparables : il y en a un plus petit et un plus grand) et qu'on a la propriété qu'il n'existe aucun moyen de passer indéfiniment d'un de ces objets à un autre strictement plus petit (on ne peut pas décroître indéfiniment), on dit qu'on a affaire à un ensemble bien-ordonné (ou à un bon ordre) sur ces objets. Les ordinaux servent à mesurer à la fois les ensembles bien-ordonnés et à étiqueter les objets qu'ils contiennent : tout ensemble bien-ordonné correspond de façon bien définie à un unique ordinal α, au sens où il y a une unique manière d'étiqueter les objets par des ordinaux strictement plus petits que α de façon que les étiquettes soient dans l'ordre qu'on a imposé sur les objets. Ceci permet donc de dire que les ensembles bien-ordonnés et les ordinaux sont essentiellement la même chose. Mes petits bâtonnets étant bien-ordonnés, ils définissent bien des ordinaux et, de nouveau, seul l'ordre importe. Ceci ne signifie pas que n'importe quel ordinal puisse être ainsi représenté, mais j'y reviendrai. Pour l'instant, reprenons un peu le jeu là où je l'avais laissé.

Addition et multiplication

Reprenons. J'ai expliqué qu'un ordinal est défini par une sorte d'« échelle » sur laquelle il n'est pas possible de décroître indéfiniment (un ensemble bien-ordonné). Pour définir des opérations sur les ordinaux, une manière de faire consiste donc à utiliser ces ensembles bien-ordonnés :

• l'ordinal α+β est l'ordinal associé à une copie de α suivie d'une copie de β, dans cet ordre ;
• l'ordinal α×β (ou α·β, ou simplement α⁢β ou αβ si aucune confusion n'en résulte) est l'ordinal obtenu en remplaçant chaque barreau de l'échelle β par une copie de l'échelle α.

Ces opérations ne sont pas commutatives (α+β n'est pas toujours égal à β+α, et de même pour le produit) : c'est surprenant quand on pense aux entiers naturels, mais c'est finalement assez évident quand on se rappelle que tout tourne autour de structures ordonnées, donc il est logique que la droite et la gauche ne soient pas interchangeables. Voici quelques exemples :

• L'ordinal 1+ω est égal à ω : en effet, ajouter un barreau à gauche de l'échelle ω ne fait que renuméroter tous les barreaux ultérieurs, mais ne change rien à la structure. On a donc 1+ω = ω.
• En revanche, ω+1 est obtenu en ajoutant un nouveau barreau après ω et c'est un ordinal différent (ω n'avait pas de dernier élément, ω+1 en a un).
• De même, on a ω+ω² = ω² alors que ω²+ω est un ordinal différent. (De façon générale, on peut montrer que si α>β, alors ω^β+ω^α = ω^α.)
• S'agissant du produit, 2ω est égal à ω : en effet, si on dédouble chaque barreau de l'échelle ω, on ne change rien à la structure (l'ancien barreau 1 devient numéroté 2, l'ancien 2 devient 4, l'ancien 3 devient 6 et ainsi de suite, mais on a toujours un barreau par entier naturel, dans cet ordre), donc 2ω=ω.
• En revanche, ω2 = ω+ω (obtenu en mettant deux copies de ω bout à bout) est un ordinal différent, et strictement supérieur à ω.
• On a déjà signalé que ω×ω^ω=ω^ω ; en revanche, ω^ω×ω (obtenant en mettant bout à bout ω copies de ω^ω) est un ordinal strictement plus grand, qu'on notera ω^ω+1.

Bien que la commutativité soit en défaut, il y a certaines propriétés sur les opérations sur les ordinaux qui rappellent celles des entiers naturels :

• Associativité de l'addition : α+(β+γ) = (α+β)+γ.
• On a 0+α = α = α+0 quel que soit α.
• Distributivité d'un côté : α(β+γ) = αβ+αγ (en revanche, dans l'autre sens, ça ne marche pas en général : (α+β)γ peut être différent de αγ+βγ).
• Associativité de la multiplication : α·(β·γ) = (α·β)·γ.
• On a 0·α = 0 = α·0 et 1·α = α = α·1 quel que soit α.

J'ai aussi envie d'énoncer les règles suivantes, mais qui vont nécessiter d'expliquer en quoi consiste l'exponentiation :

• α^(β+γ) = α^β·α^γ
• α^(βγ) = (α^β)^γ

Comment définir, donc, cette opération ‘^’ ? Il est possible de donner une définition semblable à celle que j'ai faite pour l'addition et la multiplication, mais elle est plus compliquée[#7], donc il vaut mieux utiliser une approche par induction. Pour cela, il faut que je parle d'ordinaux successeurs et d'ordinaux limites.

Ordinaux successeurs et ordinaux limites, définitions par induction

Une définition par induction consiste à définir quelque chose sur les ordinaux en supposant cette chose déjà définie sur tous les ordinaux plus petits. On est souvent amené à distinguer trois cas :

• l'ordinal 0, qui est unique (c'est le seul qui n'ait aucun ordinal strictement plus petit),
• les ordinaux qui ont un prédécesseur α, c'est-à-dire qu'ils sont de la forme α+1 (par exemple 1=0+1, 42=41+1, ou encore ω+1 ou ω³+1729=(ω³+1728)+1), ou, ce qui revient au même, les ordinaux correspondant à des échelles ayant un plus grand barreau (qui est justement celui numéroté par le prédécesseur) : on les appelle les ordinaux successeurs,
• et tous les autres ordinaux, qu'on appelle ordinaux limites (par exemple, ω, ou encore ω2, ou ω², ou ω^ω).

Les ordinaux limites sont effectivement des limites en un certain sens topologique, sur lequel je ne vais pas insister : par exemple, ω est bien la limite (dans les ordinaux) des entiers naturels, ou encore des entiers pairs, ou des entiers impairs, ou des puissances de 2, ou des nombres premiers, ou de n'importe quelle suite qui tend vers l'infini au sens de l'analyse (si on sait ce que ça signifie), et en particulier de n'importe quelle suite strictement croissante.

Ceci permet de fournir une définition différente de l'addition, en distinguant les trois cas, et dont je ne chercherai pas à démontrer qu'elle est équivalente à celle que j'ai déjà proposée :

• α+0 = α
• Pour le cas d'un ordinal successeur (β+1), on a α+(β+1) = (α+β)+1
• Si δ est un ordinal limite, alors α+δ est la limite des α+γ pour tout γ<δ (c'est-à-dire, concrètement, le plus petit ordinal supérieur à tous les α+γ pour γ<δ) ; on dit que l'addition est continue à droite.

(Les deux premières parties de cette définition sont des cas particuliers de règles déjà énoncées, mais la troisième est nouvelle.) Ceci permet de se convaincre une nouvelle fois que 1+ω n'est autre que ω : d'après la troisième règle, comme ω est un ordinal limite, 1+ω est la limite des 1+n pour n parcourant les entiers naturels, c'est-à-dire la limite de 1,2,3,4…, qui est ω tout autant que la limite de 0,1,2,3,4…

Pour la multiplication, on a :

• α·0 = 0
• Pour le cas d'un ordinal successeur (β+1), on a α·(β+1) = α·β+α
• Si δ est un ordinal limite, alors α·δ est la limite des α·γ pour tout γ<δ (c'est-à-dire, concrètement, le plus petit ordinal supérieur à tous les α·γ pour γ<δ) ; on dit que la multiplication est continue à droite.

Ici on voit que 2ω vaut ω car la limite de la suite 0,2,4,6,8,… des nombres pairs est ω.

Un peu plus difficile : que vaut (ω+1)×(ω+1) ? D'après la deuxième règle, c'est (ω+1)×ω + (ω+1). Or d'après la troisième règle, (ω+1)×ω est la limite de (ω+1), (ω+1)2, (ω+1)3, etc. Mais (ω+1)2 = (ω+1)+(ω+1) = ω+(1+ω)+1 = ω+ω+1 = ω2+1, et de façon générale, pour tout entier naturel n, on a (ω+1)·n = ω·n+1 (car tous les +1 se font annuler par le +ω qui suit, sauf le dernier). La limite des ω·n+1 est ω² (car c'est le plus petit ordinal qui dépasse ω+1, ω2+1, ω3+1, etc. : regardez sur un des dessins précédents si vous n'êtes pas convaincu). Ceci montre que (ω+1)×ω=ω², et du coup (ω+1)×(ω+1)=ω²+ω+1. On peut confirmer ce résultat en prenant ω+1 et en remplaçant chacun de ses barreaux par une copie de ω+1 tout entier.

À présent, on peut définir l'exponentiation :

• α⁰ = 1
• Pour le cas d'un ordinal successeur (β+1), on a α^(β+1) = (α^β)·α
• Si δ est un ordinal limite, alors α^δ est la limite des α^γ pour tout γ<δ (c'est-à-dire, concrètement, le plus petit ordinal supérieur à tous les α^γ pour γ<δ) ; on dit que l'exponentiation est continue en l'exposant.

On peut par exemple ainsi se persuader que 2^ω vaut ω, car c'est la limite de la suite 1,2,4,8,16…, qui vaut ω comme la limite de n'importe quelle suite strictement croissante d'entiers naturels. En revanche, ω² est bien ω×ω, et il est strictement supérieur à ω. Et ω^ω est bien l'ordinal limite de 1, ω, ω², ω³, etc.

Exercice : Que valent (ω+1)^ω et (ω+1)^(ω+1) ? Réponse : Le premier est la limite des (ω+1)ⁿ=ωⁿ+⋯+ω²+ω+1, c'est-à-dire simplement ω^ω. Le second vaut donc ω^ω×(ω+1)=ω^ω+1+ω^ω.

Une esquisse d'approche de ε₀

Pour l'instant, nous avons poussé le petit jeu de la fabrication des ordinaux jusqu'à ω^ω, qui est la limite de ω, ω², ω³, etc. Si on met ω copies de ω^ω bout à bout, on obtient l'ordinal ω^ω×ω=ω^ω+1. Si on met ω copies de cet ordinal-là bout à bout, on obtient ω^ω+2. En répétant ce procédé, on obtient successivement ω^ω+3, ω^ω+4, etc., dont la limite est ω^ω2. Ce dernier peut aussi se voir comme (ω^ω)², par exemple obtenu en remplaçant chacun des échelons de l'échelle ω^ω par une copie de ω^ω tout entière. Il ne faut pas confondre ω^ω2=(ω^ω)² avec ω^ω2 (c'est-à-dire ω^ω×2), qui est beaucoup plus petit et simplement la somme de deux copies de ω^ω. En répétant l'opération, on tombe sur ω^ω3 puis ω^ω4 et ainsi de suite, dont la limite vaut ω^ω², lequel s'écrit encore (ω^ω)^ω. Le passage de ω^ω à ω^ω² peut être répété pour donner ω^ω³=(ω^ω²)^ω et ainsi de suite. La limite de ces choses-là vaut ω^ωω.

Je peux d'ores et déjà annoncer que la limite de ω, ω^ω, ω^ωω, ω^ωωω, etc., porte un nom tout à fait différent (parce qu'il n'y a aucune manière de l'atteindre avec les opérations déjà introduites), c'est l'ordinal ε₀. Mais cette description ne fait pas vraiment justice à ε₀, car elle masque le fait que chaque ω qu'on empile dans la tour d'exponentielles introduit, en fait, un niveau de complexité tout à fait considérable par rapport au précédent : quand on parlait de ω^ω, il fallait bien distinguer l'échelon ω2 de l'échelon ω² ; quand on parle de ω^ωω, il faut distinguer ω^ω2 de ω^ω2 et ω^ω², et ainsi de suite.

Je ne peux malheureusement pas faire un petit dessin de ε₀ avec des bâtonnets comme je l'ai fait pour les tout petits ordinaux déjà représentés ainsi. Enfin, techniquement, je peux, et je l'ai déjà fait [Ajout : voir une entrée ultérieure à ce sujet], mais cette représentation n'a aucun intérêt parce qu'on n'y voit rien du tout. Pour vraiment comprendre ε₀, il faut introduire un outil qui permet d'écrire les ordinaux de façon un peu standardisée, et de calculer les opérations dessus.

La forme normale de Cantor

La forme normale de Cantor est une façon d'écrire les ordinaux de façon un peu systématique, et c'est ce que nous avons utilisé sans le dire jusqu'à présent. L'écriture ω¹⁷²⁹+ω⁴²18+ω²666+13, par exemple, est une forme normale de Cantor (alors que (ω+1)³ n'en est pas une : son écriture en forme normale de Cantor est ω³+ω²+ω+1). Il s'agit de quelque chose d'assez semblable à l'écriture des entiers naturels en « base b », par exemple l'écriture décimale (base 10) à laquelle nous sommes habitués, sauf qu'ici b vaudrait ω : au lieu d'avoir des unités, des dizaines, des centaines, des milliers, etc., chacun étant en un nombre <10 (c'est-à-dire entre 0 et 9), on a des unités, des ω-aines, des ω²-aines, etc., chacun étant en un nombre <ω, c'est-à-dire un entier naturel quelconque. Et le etc. que je viens d'écrire est transfini : il y a des ω^ω-aines, si l'on veut, et des ω^ω²+7-aines.

Bref, on dit qu'un ordinal est écrit en forme normale de Cantor lorsqu'il est écrit comme une somme de puissances de ω portant des exposants strictement décroissants de la gauche vers la droite (de la somme), chacune de ces puissances étant multipliée par un entier naturel non nul. Autrement dit, sous la forme ω^γ_r·n_r + ⋯ + ω^γ₁·n₁, où γ_r>⋯>γ₁ sont des ordinaux (les exposants des puissances de ω intervenant) et n₁,…,n_r des entiers naturels non nuls (les coefficients indiquant le nombre de ω^γ_i-aines). On peut permettre d'ajouter des termes avec n_i=0, sachant que ces termes sont à ignorer purement et simplement (néanmoins, il est généralement utile de réserver le terme de forme normale de Cantor, au sens strict, au cas où tous les n_i sont non nuls). Tout ordinal admet une unique écriture sous forme normale de Cantor (mais cette affirmation cache un peu de poussière sous le tapis, à savoir la façon dont on représente les γ_i : on peut demander qu'ils soient eux-mêmes sous forme normale de Cantor, mais le processus ne termine pas nécessairement, et notamment l'ordinal ε₀=ω^ε₀ va poser des difficultés dans ce cas).

On a déjà expliqué comment comparer deux ordinaux écrits sous forme normale de Cantor : on utilise l'ordre lexicographique, c'est-à-dire qu'on commence par comparer le terme le plus fort (celui le plus à gauche dans la forme normale), et s'ils sont égaux on passe au terme suivant, et ainsi de suite (si tous les termes sont égaux, les deux ordinaux sont évidemment égaux, sinon il y a un terme qui diffère et c'est le premier qui diffère qui emporte la comparaison, tous les autres étant négligeables).

La forme normale de Cantor permet de rendre systématique le calcul des additions et des multiplications. Pour l'addition, le fait essentiel, à part l'associativité de l'addition, est que si γ<γ′, alors ω^γ·n + ω^γ′·n′ = ω^γ′·n′ (autrement dit, une puissance de ω absorbe sur la gauche toute puissance plus petite de ω), et évidemment ω^γ·n + ω^γ·n′ = ω^γ·(n+n′) : l'addition se calcule alors très simplement, en plaçant bout à bout les deux formes normales de Cantor à ajouter et en effaçant purement et simplement tous les termes qui ne sont pas dans l'ordre correct.

Exercice : Que vaut la somme de ω^ω²·18+ω^ω2·2000+ω^ω·666+ω³·7+299792458 et de ω^ω2·11+ω^ω+1+ω·12+8 ? Et que vaut la somme dans l'autre sens ? Réponse : C'est ω^ω²·18+ω^ω2·2011+ω^ω+1+ω·12+8. Et dans l'autre sens, c'est exactement le premier (le plus grand) des deux nombres (tous les termes du plus petit sont avalés par le ω^ω²·18).

Pour la multiplication, le fait essentiel, à part les associativités et la distributivité du bon côté, est que dès que ω^γ_r·n_r+⋯+ω^γ₁·n₁ est un ordinal non-nul écrit sous forme normale de Cantor, son produit par ω^γ′ par la droite vaut tout simplement ω^(γ_r+γ′) dès que γ′>0, et son produit par n′>0 par la droite vaut ω^γ_r·n_rn′+⋯+ω^γ₁·n₁ (seul le coefficient le plus haut est multiplié par n′, les autres sont inchangés).

Exercice : En reprenant l'exemple des ordinaux ω^ω²·18+ω^ω2·2000+ω^ω·666+ω³·7+299792458 et ω^ω2·11+ω^ω+1+ω·12+8, que vaut cette fois leur produit ? Et que vaut leur produit dans l'autre sens ? Réponse : Dans le sens dans lequel ils sont proposés, le produit vaut ω^ω²+ω2·11+ω^ω²+ω+1+ω^ω²+1·12+ω^ω²·144+ω^ω2·2000+ω^ω·666+ω³·7+299792458 (le 144 s'obtient comme 18×8). Dans l'autre sens, le produit vaut ω^ω²·18+ω^ω4·2000+ω^ω3·666+ω^ω2+3·7+ω^ω2·3297717038+ω^ω+1+ω·12+8 (le 3297717038 s'obtient comme 11×299792458).

On peut aussi donner des formules pour l'exponentiation, mais elles sont un petit peu fastidieuses à écrire proprement[#8].

En tout état de cause, la forme normale de Cantor permet de décrire, comparer et manipuler de façon systématique les ordinaux strictement inférieurs à ε₀ : il suffit de les écrire en forme normale de Cantor, d'écrire les exposants de ω de cette forme eux-mêmes sous forme normale de Cantor, et ainsi de suite récursivement — pour les ordinaux inférieurs à ε₀, ce processus termine bien, et fournit une écriture complètement normalisée. Par exemple : ω^{ωω7·6+ω+42·1729+ω9+88}·3 + ω^ωω·5 + 65537 désigne un ordinal strictement inférieur à ε₀. En vertu du principe que comprendre un ordinal, c'est comprendre tous les ordinaux qui le précèdent et la façon dont ils s'ordonnent, on peut dire qu'on a maintenant compris ε₀.

Quelques pas de plus

La forme normale de Cantor ne cesse pas d'être valable au-delà de ε₀ : elle devient seulement moins utile. Le problème est que ε₀=ω^ε₀, si bien que la forme normale de Cantor de ε₀ est ω^ε₀, mais si on veut mettre l'exposant lui-même en forme normale de Cantor, on doit écrire ω^ωε₀, et on n'en finit pas. On peut simplement faire une exception d'écriture, et décider que pour le nombre ε₀, on écrira simplement ε₀ (en revanche, ε₀², par exemple, s'écrira ω^ε₀2, et ε₀^ω s'écrira ω^ωε₀+1, et ε₀^ε₀ s'écrira ω^ωε₀2). Ceci fournit une écriture standardisée, permettant la comparaison et les opérations arithmétiques jusqu'à la limite de la suite ε₀, ε₀^ε₀=ω^ωε₀2, ε₀^ε₀ε₀=ω^ωωε₀2, etc. Cet ordinal s'appelle ε₁, et peut se voir comme le deuxième ordinal vérifiant l'équation α=ω^α (le premier étant ε₀). On peut définir de même ε₂, ε₃, etc. Leur limite est ε_ω, qui a le bon goût de vérifier toujours ε_ω=ω^ε_ω (donc c'est la ω-ième solution de α=ω^α). Plus généralement, on peut définir ε_γ pour tout ordinal γ : ceci fournit assez naturellement une description, ou un système de notation, jusqu'à l'ordinal ε_εε⋱ qui est le plus petit ordinal vérifiant l'équation α=ε_α. On peut lui donner le nom ζ₀, mais à ce stade-là il commence à falloir inventer des systèmes un peu plus puissants (voire beaucoup plus puissants).

À quoi joue-t-on ?

Il y a quelque chose de grisant dans ce petit jeu de fabriquer des ordinaux de plus en plus grands (j'y reviendrai peut-être dans une entrée ultérieure). Et il y a quelque chose de terrifiant à se rendre compte qu'on n'effleure même pas la surface de ce que sont les ordinaux : qu'à chaque fois qu'on met en place un système pour les décrire ou les comprendre ou en faire quoi que ce soit, les ordinaux ont un ordinal plus grand à proposer. Mais ce petit jeu a-t-il un intérêt ?

Les petits ordinaux que j'ai construits ci-dessus, et les autres au-delà pour lesquels il existe aussi des systèmes de notations, de plus en plus compliqués, du même genre (c'est-à-dire permettant de déterminer, nommer et comparer les ordinaux plus petits), s'appellent les ordinaux constructifs (ou récursifs). Certains portent un nom particulier, et il existe une activité de recherche mathématique consistant notamment à décrire de tels ordinaux, toujours plus grands : aux ordinaux constructifs appartiennent, par exemple, l'ordinal de Feferman-Schütte, les petit[#9] et grand ordinaux de Veblen, l'ordinal de Bachmann-Howard, l'ordinal de Takeuti-Feferman-Buchholz, les écrasements de grands cardinaux, et bien d'autres (le logicien Michael Rathjen a publié plusieurs articles extrêmement techniques tels que celui-ci dont le but est, pourrait-on dire, de décrire un ordinal constructible incroyablement grand, celui qui mesure la force de la Π¹₂-compréhension). J'avais déjà évoqué ces problématiques sur ce blog. L'intérêt de cette activité de savoir compter aussi loin que possible est que ces ordinaux, en même temps qu'ils sont fabriqués, mesurent la force de certaines théories logiques : décrire ces ordinaux permet de savoir ce que la théorie en question permettra, ou ne permettra pas, de prouver (de façon très très simplifiée, l'ordinal de preuve d'une théorie logique est le plus petit ordinal dont cette théorie ne permet pas de prouver qu'il s'agit, justement, d'un ordinal — c'est-à-dire qu'il est bien-ordonné ; s'agissant de l'arithmétique de Peano, l'ordinal de preuve en est ε₀, et c'est ce qui conduit à des résultats assez naturels qui ne peuvent pas être démontrés dans cette théorie).

Mais les ordinaux constructifs, ceux qu'on peut décrire par un système de notations algorithmique, ne sont que les plus petits des ordinaux. Selon le principe général que à chaque fois qu'on a fabriqué les ordinaux jusqu'à un certain point, on en ajoute un nouveau à la fin, lorsqu'on considère tous les ordinaux constructifs, il y a quelque chose de plus grand qui vient après : ce quelque chose s'appelle l'ordinal de Church-Kleene (noté ω₁^CK), et il représente en quelque sorte le plus petit ordinal qu'on n'a aucune chance d'arriver à comprendre complètement (où on est qui que ce soit de limité par la thèse de Church-Turing, donc selon toute vraisemblance nous, humains, au moins dans cette vie-ci). Le fait qu'on ne puisse pas comprendre complètement l'ordinal de Church-Kleene ne cependant signifie pas pour autant qu'on ne puisse rien dire d'intelligent dessus : cela signifie seulement qu'il est désespéré de chercher à en décrire totalement les ordinaux qui mènent jusqu'à lui.

Ajout : voir cette entrée ultérieure pour plus de précisions sur cette partie.

L'ordinal de Church-Kleene, qui marque la fin de la théorie des ordinaux constructibles, en ouvre une nouvelle, celle de la récursion supérieure. Plutôt que de jouer à décrire explicitement des ordinaux pour mesurer les théories dont ces ordinaux mesurent la force, la récursion supérieure étudie des modèles de calcul strictement plus puissants que la machine de Turing, et il se trouve que certains ordinaux, appelés admissibles, fournissent des modèles de calculs assez naturels qui enrichissent la machine de Turing. (Ces machines peuvent, par exemple, être présentés comme des ordinateurs qui mènent des calculs sur les ordinaux. Pour en savoir plus, voyez ces notes rapides que j'avais gribouillées il y a un moment ou bien le livre de Peter Hinman, Recursion-Theoretic Hierarchies, disponible gratuitement au bout du lien précédent.)

La théorie de la récursion supérieure a elle-aussi une fin, c'est l'ordinal noté ω₁^L et appelé le ω₁ constructible (il y a un malheureux choix de vocabulaire dans le fait que l'ordinal de Church-Kleene s'appelle parfois le ω₁ constructif et qu'on a là le ω₁^L constructible). Ce n'est pas le plus grand ordinal admissible (il existe des ordinaux admissibles arbitrairement grands) mais c'est, en un certain sens, le plus grand qui soit intéressant.

Mais tous ces ordinaux, c'est-à-dire au moins tous ceux inférieurs à ω₁^L, et peut-être ω₁^L lui-même (c'est une question indécidable, même si la réponse « naturelle » est oui) sont des ordinaux dénombrables, c'est-à-dire qu'ils n'ont en fait pas plus d'éléments qu'il n'y a d'entiers naturels : ils sont juste ordonnés différemment. Théoriquement, tous ces ordinaux pourraient être représentés par des figures comme j'en ai faites avec des petit bâtonnets (on n'y comprendrait absolument rien, et s'agissant d'ordinaux à partir de celui de Church-Kleene, il serait même impossible pour des raisons théoriques d'y comprendre quoi que ce soit, mais en principe on pourrait). À partir de ω₁, on change complètement de domaine, on a maintenant affaire à des ordinaux non dénombrables.

Ordinaux indénombrables

L'ordinal ω₁ est le plus petit qui ne soit pas dénombrable. C'est-à-dire qu'il s'agit de l'ordinal défini par toutes les façons d'ordonner les entiers naturels de manière à former un bon ordre (un bon ordre, je rappelle, signifie qu'il n'y a pas moyen de décroître indéfiniment). Comme la limite de n'importe quelle suite (suite signifiant implicitement, indicée par les entiers naturels) d'ordinaux dénombrables est encore un ordinal dénombrable, ω₁ ne peut pas être atteint par une suite. C'est une propriété extrêmement forte et très peu intuitive, qui fait de ω₁ un objet assez monstrueux :

Toute suite d'éléments de ω₁ est bornée.

Cela signifie que si vous prenez un ordinal dénombrable (=strictement plus petit que ω₁), aussi grand que vous voulez, α₀, puis un autre, α₁, encore beaucoup plus grand, puis encore un autre, α₂, et ainsi de suite, la limite des α_i sera toujours strictement plus petite que ω₁, vous n'aurez pas réussi à atteindre ce dernier — aucune suite ne peut l'atteindre, il faut vraiment quelque chose de nouveau, parce qu'on a affaire à un infini vraiment plus grand que les entiers naturels. L'ordinal ε₀ peut sembler grand, mais il est la limite de la suite ω, ω^ω, ω^ωω, ω^ωωω… ; même l'ordinal de Church-Kleene peut se laisser approcher par une suite (c'est juste que cette suite sera nécessairement non calculable). L'ordinal ω₁, lui, ne se laisse simplement pas atteindre par ce genre de procédé. En termes encore plus imagés, si vous essayez d'énumérer des éléments de ω₁, même si vous disposez de toute l'éternité et que vous pouvez passer aussi vite que vous voulez d'un élément à un élément plus grand, aussi grand que vous voulez, y compris quitte à accélérer infiniment (comme le font mes petits dessins de bâtonnets pour faire tenir une infinité de bâtons dans un espace fini), il y aura toujours des éléments de ω₁ si grands que vous ne les aurez pas atteints.

Et pourtant, ω₁, comme son indice le laisse soupçonner, n'est que la première étape au-delà du dénombrable. L'ordinal ω₂ est tout aussi inatteignable par ω₁ que ω₁ l'est par ω, et l'ordinal ω₃ par ω₂, et ainsi de suite. (En revanche, l'ordinal ω_ω, défini comme la limite des ω_i avec i parcourant les entiers naturels, a beau être plus grand que tous, il est atteignable par ω puisque c'est, par définition, la limite d'une suite. Comme quoi la taille et la cofinalité sont des choses un peu plus compliquées qu'il n'y semble à première vue.) Mais tout ce qu'on peut construire de la forme ω_ω, ω_ωω et la limite de tout ça, n'a aucune chance d'atteindre le premier cardinal inaccessible, qui est le plus petit ordinal qu'on ne peut pas atteindre avec les opérations de la théorie des ensembles (et pour cette raison, il est impossible de prouver dans la théorie des ensembles que cet ordinal existe effectivement, même si moralement il n'a aucune raison de ne pas exister). Et les cardinaux inaccessibles ne sont eux-mêmes que les plus petits des grands cardinaux !