Les nombres ordinaux

Pour compter jusqu'à l'infini... Plusieurs fois

[Illustration des ordinaux]

En hommage à Chuck Norris (1940-2026)

Chuck Norris n'est pas mort...
Il a pris congé du monde des vivants, pour une retraite bien méritée !

L'infini n'est pas unique... Il est multiple.

Dans le monde des entiers naturels, il y a équivalence entre compte et positionnement. Ajouter un premier élément à un ensemble initialement vide, puis un deuxième, etc. jusqu'à un dixième élément vous donnera un ensemble... De dix éléments. Mais avec l'infini, ce schéma ne fonctionne plus.

Il peut s'avérer alors nécessaire de construire de nouveaux objets permettant de distinguer les différents ensembles infinis auxquels on a ajouté des éléments supplémentaires, bien plus finement que de simplement dire « c'est toujours l'infini ».

C'est ici qu'interviennent les ordinaux, qui permettent - tout comme Chuck Norris - de continuer à compter au-delà de l'infini...

Les formules sur cette page sont écrites à l'aide de jqMath - un guide est disponible sur mon site.

Ensembles bien ordonnés

C'est le mathématicien allemand Georg Cantor (1845-1918) qui a rencontré le premier cette problématique de hiérachisation des ensembles infinis. En vrai qui d'autre aurait pu, lorsque l'on parle de l'infini ? Par la suite, John von Neumann (1903-1957) formalisera la notion de « bon ordre » permettant de poser un cadre théorique à ce qu'avait conceptualisé Cantor, mais sans que cela ne provoque de paradoxes.

On appelle ordinal un ensemble $α$ strictement bien ordonné pour l'appartenance, c'est à dire qu'il vérifie :

Pour tout $x∈α$, on a $x⊂α$ et $x∉x$
Pour tous $x,y,z∈α$, si $x∈y$ et $y∈z$ alors $x∈z$
Pour tout $z⊂α$ non vide, alors $z$ possède un plus petit élément : il existe un $x∈z$ tel que pour tout $y∈z$, alors $x∈y$ ou $x=y$.

En quelque sorte, un ordinal est un ensemble « poupée russe » : une imbrication parfaite avec des sous-ensembles qui partagent les mêmes propriétés que le tout, de la même façon que les cinq poupées les plus petites d'un ensemble de sept sont déjà en elles-même un jouet à part entière.

[Poupées russes]

L'inclusion $⊂$ dans un ordinal α est une relation d'ordre classique, c'est à dire réflexive, antisymétrique et transitive. L'ensemble $(α,⊂)$ est même totalement ordonné car dans un bon ordre, deux éléments sont toujours comparables : $\{x,y\}$ a un plus petit élément.

Le plus petit ordinal est l'ensemble vide $∅$, ordonné par son unique relation : $(∅,∅)$.

Les ordinaux permettent de définir rigoureusement les entiers naturels :

Le nombre « zéro » est défini comme étant l'ensemble vide : $0=∅$.
L'entier $1$ est défini par $0∪\{0\}=\{∅\}$, soit l'ensemble contenant pour seul élément l'ensemble vide $∅$
$2$ est défini par $1∪\{1\}=\{0,1\}=\{∅, \{∅\}\}$
$3=2∪\{2\}=\{0,1,2\}$
...

Plus formellement, on définit l'application $S$ « successeur » par $S\text " : "n↦n∪\{n\}$ et on note $S(n)=n+1$. Tout entier $n$ autre que $0$ a forcément un « prédécesseur » : le seul entier dont $n$ est le successeur. Il existe donc aussi une application $P$ réciproque de $S$ vérifiant $P(S(n))=S(P(n))=n$. On note cette fois $P(n)=n-1$. Ici, ce ne sont encore que des conventions d'écriture. Mais ces deux notions permettent ensuite de définir l'addition dans les entiers naturels et par suite la soustraction, ce qui donne un réel sens à « $-1$ » puis plus tard à d'autres écritures telles que $P=S^{-1}$.

L'entier $n$ est donc l'ensemble qui contient $0$, puis $1$, puis $2$, ... A la manière d'un jeu de $n$ poupées russes.

$$n=\{0,1,2,...,n-1\}\text " ou encore "0⊂1⊂2⊂...⊂n-1$$
Ah oui, rendez-vous compte que l'on ne vous avait jamais défini les nombres en cours de mathématiques à l'école ! Avouez que c'est quand même assez balo... Précisément, il y a en fait équivalence parfaite entre tous les ordinaux finis et les entiers naturels, et c'est grâce à cela que l'on peut se servir des nombres pour compter les objets d'un ensemble.

Par suite, on est amené assez logiquement à s'intéresser à la clôture de l'application $S$, c'est-à-dire la classe de tous les ordinaux finis.

A partir de là, il est nécessaire d'introduire un axiome pour admettre que cette classe est un ensemble. Sans entrer dans les détails, sachez qu'on ne peut pas systématiquement considérer qu'une propriété mathématique (telle que « être un ordinal ») définit un ensemble car cela peut mener à des inconsistances.

Ici ce n'est pas le cas, et on peut obtenir ainsi le premier ordinal transfini (dans le sens de « non fini »). On le note $ω$, et il a la particularité de n'avoir aucun prédécesseur dans le bon ordre qu'il représente, au contraire d'un ordinal fini non vide $n$, qui lui en a toujours un.

Le prédicat dans la théorie des ensembles dite « ZF », postulant que $ω$ peut être considéré comme faisant partie de cette même théorie, s'appelle justement axiome de l'infini.

$$ω=\{0,1,2,3,...\}$$
Il constitue la « poupée russe finale » de tous les entiers naturels ! Accessoirement $ω$ est aussi le plus petit ensemble infini.

Factuellement, $ω$ est l'ensemble $ℕ$ - et même plus précisément, $ω=(ℕ,≤)$, l'ensemble des entiers naturels muni de son ordre usuel, qui se trouve être un bon ordre. Néanmoins en théorie des ordinaux on conserve la dénomination $ω$ - ces ensembles étant traditionnellement notés avec des lettres grecques.

Car on ne va évidemment pas s'arrêter là...

Une construction d'infinis en gigogne

Puisque $ω$ est un ensemble, on peut également utiliser les autres axiomes de ZF afin de construire de nouveaux objets, qui seront aussi des ensembles. Ainsi, l'axiome de la paire permet d'obtenir l'ensemble $\{ω\}$ et l'axiome de la réunion celui que l'on va noter $ω+1$ :

$$ω+1=ω∪\{ω\}$$
Vous l'avez compris, on peut de la même manière définir de nombreux successeurs $ω+2$, $ω+3,...,ω+n$ de $ω$.

L'ensemble $ω$ est aussi appelé premier ordinal limite, rappelant qu'il n'a pas de précédesseur, au contraire de $ω+1$ et suivants. Avec ce qu'on appelle le « schéma d'axiomes de remplacement » de la théorie ZF on peut obtenir le prochain ordinal limite, l'ensemble de tous les $ω+n$. On peut le noter $ω+ω$ ou $ω2$ - oui ici le chiffre $2$ suit la lettre $ω$, et ce n'est pas non plus un indice - ne vous inquétez pas, c'est expliqué dans la partie suivante.

Vous le voyez arriver, on poursuit de même jusqu'à arriver à un $ω3$, puis à un $ωn$... Et enfin jusqu'à l'ordinal limite $ωω$ qu'on peut noter lui de manière plus habituelle $ω^2$.

Mais à quoi diable cela ressemble-t-il en pratique ? Eh bien on peut par exemple s'intéresser à l'ensemble $ℕ^{2}$ que l'on munit d'une relation d'ordre $≺$ qui range les couples d'entiers naturels en comparant le premier entier, puis le second. C'est-à-dire que :

$$(0,0)≺(0,1)≺...≺(0,n)≺...≺(1,0)≺(1,1)≺...≺(2,0)≺...≺(n,0)≺...$$
L'élément $(1,0)$ n'a aucun prédécesseur et il se place après une infinité d'entiers. Il est suivi par $(1,1)$ puis $(1,2)$, etc. On voit alors que $(1,0)$ « s'associe » à $ω$, puis $(1,1)$ à $ω+1$, $(n,0)$ à $ωn$ et ainsi de suite. On dit alors que l'ensemble ordonné $(ℕ^{2},≺)$ est un bon ordre de type $ω^2$.

Plus généralement - et c'est là que ça devient intéressant - pour tout ensemble bien ordonné $(E,≤)$, fini ou infini, il existe toujours un ordinal $α$ qui lui « correspond » parfaitement. En termes mathématiques précis et rigoureux : il existe un isomorphisme d'ordres (une application bijective croissante) entre $(E,≤)$ et $(α,⊂)$.

Egalement, deux ordinaux α et β construits différemment mais liés par un tel isomorphisme peuvent-être considérés comme étant égaux et on écrira que $α=β$, même s'il ne contiennent pas des éléments identiques, à proprement parler. Pour les puristes, je précise que dans la théorie de von Neumann, les ordinaux sont des classes d'isomorphie entre ensembles bien ordonnés, et que c'est donc tout à fait légitime d'écrire cela.

C'est à partir de ce moment-là qu'on peut réellement parler de compter au-delà de l'infini.

On peut bien sûr poursuivre après $ω^2$ pour obtenir $ω^3$ puis $ω^n$ et enfin $ω^ω$, ce qui est illustré par l'image d'illustration de cette page, celle à gauche du grand Chuck. Cela correspond plus ou moins à compter une infinité d'une infinité de fois... Jusqu'à l'infini !!

Si vous voulez un exemple concret d'ordre de type $ω^ω$, vous pouvez considérer l'ensemble des suites d'entiers $(u_n)_{n∈ℕ}$ à support fini, c'est à dire ne comportant qu'un nombre fini d'éléments non nuls, ordonné par une relation similaire à ≺ ci-dessus, où on considère une suite comme un « $∞$-uplet » d'entiers de la forme $(u_0,u_1,...,u_n,...)$ que l'on range suivant $u_0$, puis $u_1$, etc.

Opérations sur les ordinaux

Ces notations ne sont-elles que de simples conventions d'écriture ou bien y a-t-il vraiment une « arithmétique ordinale » ?

La réponse est oui, et il est possible de donner un sens à des expressions telles que :

$$ω^ω+ω^65+ω7+15534$$
Les définitions sont un petit peu techniques, il faut avoir l'habitude des opérations sur les ensembles.

Pour l'addition de deux ordinaux quelconques $α$ et $β$ :

$α+0≝α$
$α+(β+1)≝(α+β)+1$
si $β$ est un ordinal limite, alors $α+β≝⋃↙{λ∈β}(α+λ)$

De manière symétrique, pour la multiplication :

$α0≝0$ ; (l'ensemble vide $∅$)
$α(β+1)≝αβ+α$
si $β$ est un ordinal limite, alors $αβ≝⋃↙{λ∈β}(αλ)$

Et enfin pour l'exponentiation (puissance) :

$α^0≝1$ ; c'est à dire $\{∅\}$
$α^{β+1}≝α^βα$
si $β$ est un ordinal limite, alors $α^β≝⋃↙{λ∈β}(α^λ)$

Attention, il y a quelques surprises ! Par exemple $1+ω$ est un ensemble constitué d'un élément (notons-le $x$) que l'on a fait suivre de tous les entiers dans une chaîne d'inclusion, suivant le (Ⅲ) de la définition de l'addition ci-dessus. L'ordre dans $1+ω$ ressemble donc à :

$$x⊂0⊂1⊂2⊂3⊂...$$
C'est un simple décalage, et on peut construire une bijection croissante $f$ entre $ω$ et $1+ω$ avec $f\text " ":(0↦x\text" ; "n↦n-1, n≥1)$ - de sorte qu'en fait $1+ω=ω$. Cette addition n'est pas commutative. La multiplication ne l'est pas non plus, et $2ω=ω$. Ceci explique la notation $ω2$ utilisée plus haut. Par contre on peut démontrer que cette addition et cette multiplication sont associatives. Cela justifie l'écriture sans parenthèses donnée en exemple tout au début de cette partie.

L'exponentiation possède des propriétés encore plus étranges. Si on a bien $α^βα^γ=α^{β+γ}$, on n'a généralement pas égalité entre $(αβ)^γ$ et $α^γβ^γ$. Par contre on a bien $(α^β)^γ=α^{βγ}$. Attention à l'ordre dans cette dernière égalité, rappellez-vous que $βγ≠γβ$ dans le cas général ! Et de fait, si on applique le (Ⅲ) de la définition de cette puissance, on peut remarquer assez facilement que $2^ω=ω$ ; l'ordinal $2^ω$ correspond en effet à simplement lister toutes les puissances finies de $2$ dans l'ordre croissant.

$$2^ω=\{1,2,4,8,16,32,...\}$$
A partir du moment où on dispose d'opérations - certes aux propriétés singulières - c'est tout comme si on avait créé de nouveaux nombres, et de fait on rencontre fréquemment la dénomination nombre ordinal ou nombre transfini.

Il est possible de définir des suites (une liste ordonnée de termes) non plus simplement sur $ℕ$ mais sur un ordinal, par exemple $(u_α)_{α∈ω^2}$ ; les termes de la suite sont alors $u_0,u_1,...,u_ω,u_{ω+1},...,u_{ω2},...$

Il y a même alors moyen d'effectuer des raisonnements par « récurrence transfinie » en étendant une hypothèse de récurrence à n'importe quel ordinal dénombrable.

Où ces opérations nous mènent-t-elles ensuite ?

Après $ω^ω$ vu précédemment, nous allons retrouver $ω^{ω^ω}$, puis des ordinaux de la forme $ω^{ω^{ω^{^{·^{·^{·^{ω}}}}}}}$ qui vont vous rappeler la fameuse tétration des opérateurs de Knuth ! Bon il ne sera pas utile d'utiliser cette notation ici, car $\text " ↑"^{n}$ correspond toujours à une puissance du nombre de gauche, si vous vous souvenez. On peut directement considérer l'ordinal limite qui contient tous ceux que l'on peut obtenir avec des opérations arithmétiques (sommes, produits et puissances) utilisant ω, et que l'on note $ε_0$.

Mais on peut ensuite recommencer à partir de là, et obtenir $ε_0^{ε_0}$ puis $ε_0^{ε_0^{ε_0}}$ jusqu'à $ε_1=ε_0^{ε_0^{ε_0^{^{·^{·^{·}}}}}}$. Ah oui ça devient dingo, mais ce n'est pas fini... Pourquoi s'arrêter ? Viennent ensuite $ε_2$, puis $ε_3$,... Puis $ε_ω$. Ou comment compter d'énormes ensembles infinis en s'appuyant sur d'autres ensembles infinis ! Cela aboutit bien sûr à $ε_{ω^ω}$ puis $ε_{ω^{ω^ω}}$ et $ε_{ε_0}$. Est-ce que ça devient n'importe quoi ? Mathématiquement non mais philosophiquement parlant, totalement.

Et ensuite cela continue, mais dans les indices : $ε_{ε_{ε_0}}$, $ε_{ε_{ε_{·_{·_{·_{ε_0}}}}}}$, ... Ces nombres epsilon, dont la caractéristique est d'être les solutions de l'équation (d'inconnue $α$) : $α=ω^α$, constituent eux-mêmes une sorte de « limite de limites » car l'ordinal qui les contient tous, noté généralement $\Ω$ majuscule, est le premier ordinal non dénombrable.

Celui-ci permet d'affirmer qu'un bon ordre existe sur $ℝ$, sans avoir besoin de l'axiome du choix pour cela. Ce n'est évidemment pas l'ordre usuel ici...

Au-delà, il n'est donc plus vraiment possible de « compter » ! La théorie permettant de construire de nouveaux ensembles se complexifie alors quelque peu... Restons donc dans le domaine du raisonnable et voyons une autre application des ordinaux, qui fera un écho sympathique à une page précédemment publiée sur cette rubrique !

Hiérarchie de croissance rapide

Si vous aviez aimé les chaînes de Conway, alors vous allez adorer ce qui suit !

Il est possible d'aller encore plus loin pour désigner les grands entiers naturels, en s'appuyant sur des fonctions extrêmement croissantes indexées par les ordinaux, ce qu'on appelle une hiérarchie de croissance rapide. Il en existe en effet plusieurs, définies de manières différentes par ceux qui les ont introduites, mais l'idée de base reste la même.

Celle qu'on va détailler ici est la plus connue, la hiérarchie de Wainer. Il s'agit d'une suite de fonctions $(f_α)_{α∈ε_0}$ construites par itérations successives.

D'autres définitions utilisent aussi parfois la même notation avec un « $f$ » assez ambigü, mais sans précisions supplémentaires, quand on lit « hiérachie de croissance rapide » c'est généralement de la hiérarchie de Wainer dont il est question.

Dans ce qui suit, les fonctions sont définies de $ℕ$ vers $ℕ$, et on note $f^{[n]}$ l'itérée de $f$ d'ordre $n$, c'est à dire $f^{[n]}=f∘f∘...∘f$ ($n$ fois) - ceci afin de ne pas confondre avec l'exponentiation d'entiers !

On débute avec la toute simple $f_0\text " ":n↦n+1$. La fonction suivante $f_1$ est alors construite en itérant $f_0$ autant de fois que son argument, c'est à dire que $∀n∈ℕ,f_1(n)=f_0^{[n]}(n)$, ce qui donne $f_1(n)=n+n=2n$.

En poursuivant ainsi, on obtient successivement :

$f_2(n)=f_1^{[n]}(n)=2^nn$

$f_3(n)=f_2^{[n]}(n)$, déjà supérieur à $2\text " ↑↑ "n$ (tétration) dès que $n≥2$

$f_{p+1}(n)=f_p^{[n]}(n)>2\text " ↑"^{p}\text " "n$, avec l'opérateur de Knuth d'ordre $p$

A partir de là, on passe à la limite de manière un peu particulière « par la diagonale », où on considère la fonction $f_ω$ définie par $n↦f_n(n)$. Attention ici, le nombre $n$ est bien présent deux fois, signifiant que l'on « change » la fonction à chaque nouvelle valeur de l'argument : $f_ω(3)=f_3(3)=f_2(f_2(f_2(3)))$, $f_ω(4)=f_4(4)=f_3(f_3(f_3(f_3((4)))))$, etc. On a alors $f_ω(n)≥2\text " ↑"^{n-1}\text " "n$, l'ordre de l'opérateur de Knuth est ici variable. De fait, $f_ω$ croît plus vite que toutes les $f_p$ et finira toujours par les majorer.

Comme vous l'imaginez, on utilise maintenant les nombres transfinis pour continuer de compter :

$f_{ω+1}(n)=f_ω^{[n]}(n)>2→n→(n-1)→2$, avec la notation des chaînes de Conway

$f_{ω+p}(n)>2→n→(n-1)→(p-1)$, pour $p≥2$

On peut alors de nouveau considérer le prochain ordinal limite en changeant les fonctions en même temps que l'argument, et obtenir $f_{ω2}$ définie par $n↦f_{ω+n}(n)$. Petite précision au passage, pour n'importe quel ordinal $α∈ε_0$, on a toujours $f_α(1)=2$. C'est parfaitement similaire au $2\text " ↑"^{n}\text " "2=2$ des opérateurs de Knuth. Donc dans la suite, on suppose que $n≥2$. Cela donne alors :

$f_{ω2+p}(n)>n→n→n→p$

$f_{ω3}(n)>n→n→n→n$

$f_{ωp}(n)>n→n→...→n→n$, chaîne de longueur $p+1$

$f_{ω^2}(n)>n→n→...→n→n$, chaîne de $n+1$ éléments dont la longueur change avec l'arguement $n$

A partir de là, la notation de Conway ne permet plus d'écrire ces nombres. Il est pourtant possible de poursuivre ainsi par sauts sucessifs entre les différents ordinaux limites appartenant à $ε_0$. Par exemple on aura $f_{ω^ω}$ définie par $n↦f_{ω^n}(n)$ puis $f_{ω^ω^ω}\text " : "n↦f_{ω^ω^n}(n)$, etc.

Et que se passe-t-il quand on arrive à $ε_0$ ? – Détails un peu plus techniques...

On peut bien sûr poursuivre avec les $ω^{ω^{ω^{^{·^{·^{·^{ω}}}}}}}$, ce qu'on pourrait noter de manière assez audacieuse $ω\text " ↑↑ "p$. Dès lors on est tenté de définir $f_{ε_0}\text " : "n↦f_{ω\text " ↑↑ "n}(n)$, et de fait, cette $f_{ε_0}$ est parfois incluse dans la hiérarchie de Wainer.

Mais si l'on cherche à aller au-delà, on va se retrouver avec un problème dès $ε_0^{ε_0}={ε_0}^ω^{ω^{ω^{^{·^{·^{·}}}}}}$ et à fortiori avec $ε_1=ε_0^{ε_0^{ε_0^{^{·^{·^{·}}}}}}$ et les suivants, car tous ces ensembles sont des « tours infinies de puissances ω » qui vérifient leur équation caractéristique : $ε_0=ω^{ε_0}$, $ε_1=ω^{ε_1}$, ... Et finalement on aurait $f_{ε_1}=f_{ε_0}$ par seule définition via l'exponentiation des ordinaux. C'est pour des raisons analogues qu'étendre la notation de Knuth n'a pas vraiment de sens non plus.

Dès lors, il faut trouver comment décrire beaucoup plus rigoureusement et finement les ordinaux limites, par exemple avec des séquences ressemblant à :

$$ω^ω\text " "~\text " "[1,ω,ω^2,ω^3,...]$$
Attention ici il ne s'agit pas du contenu de l'ensemble $ω^ω$, qui comprend bien sûr tous les entiers naturels, pas seulement $1$. On peut y voir plutôt une certaine similarité avec l'expression d'un vecteur dans une base en algèbre linéaire. Et cela se fait au moyen de suites de fonctions $(φ_{β})$ elles-mêmes indexée sur les ordinaux, qui explicitent ces séquences et permettent de construire des hiérarchies plus étendues.

Si une telle hiérachie est notée $(g_α)_{α∈\Ω}$, il se peut alors que dans celle-ci, $g_ω=f_ω$, $g_{ω^ω}=f_{ω^ω}$ mais que $g_{ε_0}≠f_{ε_0}$ telle que définie ci-dessus. Raison pour laquelle certains auteurs préfèrent limiter la hiérarchie de Wainer aux ordinaux strictement inclus dans $ε_0$, sachant qu'à partir de $ε_0$ il faudra de toute façon utiliser autre chose.

Quelques exemples pour finir, histoire de voir à quel point on est dans la démesure !

$f_2(2)=8$
$f_3(2)=2048$
$f_4(2)>10\text " ↑↑ "2049$

$f_2(3)=24$
$f_3(3)>10^{121\text " "210\text " "694$
$f_4(3)>10\text " ↑↑ "10^{10^115}$

Enfin on peut montrer l'encadrement suivant :

$$f_{ω+1}(63)<G<f_{ω+1}(64)$$
Où $G$ désigne le nombre de Graham.

Les Mathématiques sur TheRaphit.com
- Les autres pages ajoutées depuis 2025 dans la rubrique -

$[Compteur]$
Nombre de visiteurs
depuis le 10 janvier 2000.

[Accueil Mathématiques (1997)]

TheRaphit's Web Site - La dernière homepage du Web

[(Tout)² Evangelion] [Webzine : La Revue] [Manga Pink Zone]

Mathématiques