David Madore's WebLog: Petit guide bordélique de quelques ordinaux intéressants

Remarques générales (sur ce qui rend les ordinaux intéressants)

Les ordinaux « intéressants » vont généralement de pair avec les propriétés qu'on peut définir sur les ordinaux. En effet, de façon générale, les ordinaux qui sont intéressants sont de la forme le plus petit ordinal qui a la propriété <machin>, et c'est ça qui les rend intéressants. (Par exemple, ω est le plus petit ordinal infini ou le plus petit ordinal limite ; ω₁^CK est le plus petit ordinal non calculable ; et ω₁ est le plus petit ordinal indénombrable.) La propriété <machin> peut être de diverses sortes : parfois elle vaut pour tous les ordinaux à partir d'un certain point (par exemple, tous les ordinaux ≥ω sont infinis) ; parfois seulement pour certains (seulement certains ordinaux — ω, ω·2, ω·3…, ω², etc. — à partir de ω sont limites), auquel cas, le deuxième ordinal la vérifiant peut être aussi intéressant, surtout si le premier était ω, qui est souvent un cas un peu spécial. Souvent, une limite d'ordinaux ayant tous la propriété <machin> a encore cette propriété (on dit alors que la propriété est fermée), parfois non ; dans les deux cas, être limite d'ordinaux <machin> (plus petits) définit une nouvelle propriété. (Par exemple, les ordinaux limites sont les multiples ω·α non nuls de ω et le plus petit est ω, les limites d'ordinaux limites sont les multiples ω²·α de ω² et ω² peut être considéré comme intéressant car il est le premier ordinal limite d'ordinaux limites.) Mais bon, l'intérêt de ces propriétés « dérivées » décroît quand même bien vite.

Il est souvent, mais pas systématiquement, le cas que chaque ordinal intéressant est « incomparablement plus grand » que tous les précédents. Pour commencer, si on a un ordinal intéressant, α, qui est le premier ayant la propriété <machin>, « souvent », tous les ordinaux intéressants plus grands vont aussi avoir la propriété <machin> (même si ce n'est pas le cas de tous les ordinaux). Par exemple, on peut considérer que tous les ordinaux infinis intéressants sont des ordinaux limites : on s'intéresse peut-être à l'entier 1729 mais personne ne s'intéresse à l'ordinal ω+1729, désolé pour lui, dès lors qu'on commence à regarder des ordinaux limites, on ne regarde plus que des ordinaux limites, et ceci vaut pour beaucoup des propriétés qui suivent. En fait, c'est encore pire que ça : « souvent », à partir du moment où on s'est intéressé à α qui est le premier ayant la propriété <machin>, non seulement tous les ordinaux β suivants auront la propriété <machin>, mais ils seront même le β-ième ordinal ayant la propriété <machin> (c'est-à-dire qu'il y a autant d'ordinaux machin jusqu'à β que d'ordinaux tout court — donc si on veut, la propriété <machin> ne rend pas du tout β plus petit).

Le genre de propriétés qui rend un ordinal intéressant, c'est souvent d'être « stable » ou « inatteignable » par certaines constructions ou opérations, ce qui veut dire que l'ordinal en question ne pourra pas être atteint en appliquant ces constructions ou opérations à des ordinaux plus petits. Le cas le plus simple est celui de la fonction successeur (qui à un ordinal γ associe γ+1) : un ordinal α pourrait être appelé « successeur-clos » lorsque le successeur d'un ordinal <α est encore <α, c'est-à-dire, lorsque α ne peut pas être atteint en prenant un successeur d'un ordinal plus petit ; en fait, cela revient exactement à être (zéro ou bien) un ordinal limite, c'est-à-dire un multiple ω·α de ω. Un peu moins trivial : les ordinaux α « clos par addition » sont ceux tels que si γ<α et γ′<α alors γ+γ′<α, autrement dit, on ne peut pas atteindre α en ajoutant des ordinaux plus petits que lui (en nombre fini) ; il n'est pas difficile de se convaincre que les ordinaux clos par addition sont exactement les puissances ω^α de ω. De même, les ordinaux clos par addition et multiplication sont exactement les doubles puissances de ω, autrement dit les ω^ωα. Quant à ceux qui sont clos par addition, multiplication et exponentiation, ce sont les ε_α (ceci peut servir de définition, si on veut). Et généralement parlant, tout ordinal intéressant ≥ε₀ va être clos par tout ça, donc va être un ε_α, et même va être le α-ième tel ordinal, c'est-à-dire vérifier α=ε_α.

Trois ou quatre grands domaines

J'ai déjà dit ça plusieurs fois : il est raisonnable, pour s'y retrouver, de diviser mes ordinaux en quatre régions, par ordre de taille :

0. les entiers naturels (i.e., les ordinaux <ω),
1. les (autres) ordinaux calculables (=constructifs, =récursifs) (i.e., les ordinaux <ω₁^CK),
2. les (autres) ordinaux dénombrables [peut-être : dans l'univers constructible] (i.e., les ordinaux <ω₁ [ou peut-être <ω₁^L, ignorons ça pour l'instant]),
3. les ordinaux indénombrables (qui ne sont intéressants que s'ils sont des cardinaux).

Autrement dit, je découpe en trois points : ω, puis ω₁^CK, et enfin ω₁ [ou peut-être plutôt ω₁^L mais les non experts peuvent ignorer cette subtilité]. Selon la manière dont un ordinal se situe par rapport à ces trois points, je le classe dans une de ces quatre régions. On peut donc coniserer que ω, ω₁^CK et ω₁ sont particulièrement intéressants ; mais c'est surtout parce qu'ils marquent la limite entre des régions différentes des mathématiques :

0. les entiers naturels intéressent les mathématiciens non logiciens/ensemblistes,
1. les ordinaux calculables (=constructifs, =récursifs) infinis intéressent essentiellement les logiciens qui font de la théorie de la démonstration, parce qu'ils servent surtout à mesurer/calibrer la force de certaines théories logiques (par exemple, ε₀ mesure en un certain sens la force de l'arithmétique de Peano),
2. les grands ordinaux dénombrables intéressent la calculabilité supérieure (ou la structure fine de l'univers constructible), le genre de choses que j'ai évoquées dans l'entrée précédente,
3. les grands cardinaux intéressent les théoriciens des ensembles.

Même si ce n'est pas nécessaire pour comprendre un peu mieux comment ces domaines s'agencent, il est utile que je rappelle ce que j'ai déjà évoqué à plusieurs reprises : le fait que des ordinaux de chacun de ces quatre domaines puisse servir à en fabriquer des domaines plus petits :

• (1→0) Donné un ordinal calculable (plus des machins appelées « séquences fondamentales » qui viennent généralement avec sa construction), il existe des machins appelées « fonctions de la hiérarchie à croissance rapide » et « fonctions de la hiérarchie à croissance lente » (qui coïncident essentiellement si on va assez loin), c'est-à-dire des fonctions ℕ→ℕ qui croissent très vite, et qui peuvent servir à fabriquer des entiers naturels phénoménalement grands, et qui sont, en fait, la seule manière (connue ?) de fabriquer des entiers phénoménalement grands « explicites ».
• (2→1 ou 3→1) La manière dont on sait fabriquer de très grands ordinaux calculables consiste à utiliser (2) des ordinaux dénombrables « récursivement très grands », ou, en pratique, (3) des grands cardinaux qui sont plus faciles à manier (mais dont on sait qu'en principe ils sont seulement des faire-valoir pour des ordinaux dénombrables récursivement très grands), par un mécanisme qu'on appelle « écrasement ». Très grossièrement parlant, le but est généralement d'analyser une théorie logique, dont l'ordinal dans le domaine (1) va mesurer la force arithmétique tandis que l'ordinal dans le domaine (2) va mesurer la force ensembliste.
• (2→0 ou 3→0) Si le but est juste de faire de la gogologie, on peut aussi directement définir de grands entiers naturels par des constructions de type « castor affairé généralisé » en passant directement d'un ordinal « récursivement très grands » à un entier naturel. Ces entiers seront encore (beaucoup beaucoup !) plus grands que ceux obtenus en passant par l'étape intermédiaire (1), mais ils sont moins explicites et mathématiquement moins intéressants.
• (3→2) Beaucoup de propriétés d'ordinaux « récursivement très grands » sont fabriquées selon l'analogue de propriétés de grands cardinaux qui vivent dans le domaine (3).

(Aucune de ces flèches n'est rigoureusement définie : la flèche 3→2 est, que je sache, une simple analogie, la flèche 2→1 est bien définie mais seulement au cas par cas, c'est-à-dire jusqu'à un ordinal <truc> et devient techniquement de plus en plus difficile à définir à mesure qu'on monte, et la flèche 1→0 est définie rigoureusement seulement à condition d'avoir des données supplémentaires accompagnant l'ordinal calculable, à savoir des séquences fondamentales, qui viennent normalement avec la flèche 2→1, et bien sûr elle ne donne pas un entier naturel mais une fonction ℕ→ℕ qu'on peut ensuite évaluer, disons, en 1 000 000 000 si on veut, mais c'est complètement arbitraire.)

Le but de ces remarques est surtout d'expliquer pourquoi on retrouve des mots comme « Mahlo » à plusieurs niveaux, ce qui peut être source de confusion (le plus petit cardinal Mahlo — s'il existe ! — vit dans le domaine (3) et est gigantesquement plus grand que le plus petit ordinal récursivement Mahlo qui vit dans le domaine (2), qui est lui-même gigantesquement plus grand que l'écrasement qu'on peut définir et qui vit dans le domaine (1), et qui peut encore, si on trouve ça amusant, servir à définir des entiers naturels monstrueusement grands, c'est-à-dire des habitants du domaine (0)).

Je peux diviser encore un petit peu chaque domaine (1)–(3), mais les points de coupure deviennent moins évidents : voici un plan possible (où il y a plein de termes qu'il faudrait que je définisse, mais c'est juste pour donner une petite idée de la situation) :

1. dans le domaine des ordinaux calculables j'ai tendance à trouver que l'ordinal de Bachmann-Howard fournit un point de coupure naturel, i.e. :
   • les ordinaux calculables définissables « par le bas » (par les fonctions de Veblen, qui sont encore vaguement « prédicatives ») : ω, ε₀, φ(ω,0), l'ordinal de Feferman-Schütte, le petit ordinal de Veblen, le grand ordinal de Veblen ;
   • les ordinaux calculables définissables « par le haut » (par des fonctions d'écrasement 2→1, c'est-à-dire des méthodes « imprédicatives ») : l'ordinal de Bachmann-Howard et les écrasements de toutes sortes de grands cardinaux ;
   • et je pourrais ajouter : tout ce qu'il y a à partir de l'ordinal de preuve de l'arithmétique du second ordre (ou peut-être seulement la Π¹₂-compréhension), parce qu'on ne sait pas du tout les rendre explicites à l'heure actuelle (les ordinaux de ce genre sont juste définis par la théorie qu'ils calibrent, par exemple l'ordinal de preuve de ZFC, s'il existe) ;
2. dans le domaine des grands ordinaux dénombrables, c'est un peu plus confus, je vais avoir tendance à faire plusieurs coupures :
   • les grands ordinaux récursifs jusqu'au premier nonprojectible exclu, qui sont en gros ceux qu'on sait écraser pour l'instant (c'est-à-dire fabriquer une fonction 2→1) : par exemple, l'ordinal de Church-Kleene, le premier récursivement inaccessible, le premier récursivement Mahlo, le premier récursivement faiblement compact (= Π₃-réfléchissant) ;
   • les grands ordinaux récursifs jusqu'à l'ordinal de l'analyse ramifiée exclu, qui sont ceux qu'on peut définir au niveau de l'arithmétique du second ordre (bon, il n'y a pas grand-chose d'intéressant ici) ;
   • les grands ordinaux récursifs jusqu'au premier ordinal stable exclu, qui restent nommables en théorie des ensembles (par exemple, le plus petit ordinal ρ tel que L_ρ définisse un modèle de ZFC) ;
   • et le reste, qui est plus ou moins terra incognita ;
3. enfin, pour ce qui est des grands cardinaux, il y a une séparation naturelle très forte donnée par la compatibilité avec l'univers constructible de Gödel :
   • les cardinaux qui ne sont pas grands (dont ZFC démontre l'existence), comme ω₁=ℵ₁ ;
   • les « petits » grands cardinaux, compatibles avec la constructibilité : cardinaux inaccessibles, Mahlo, faiblement compacts, totalement indescriptibles, ineffables, ω-Erdős, etc. ;
   • les « grands » grands cardinaux : mesurables, supercompacts, gigantesques (voire : incompatibles avec l'axiome du choix : cardinaux Reinhardt) — mais là, de plus en plus, ça devient problématique de les comparer parce que ce qui importe n'est pas leur « taille » mais leur « force » (logique).

Qu'est-ce qu'un ordinal calculable ?

Je laisse de côté les entiers naturels sur lesquels je n'ai rien d'intéressant à dire : disons juste que 0 est un ordinal remarquable parce que c'est le seul qui ne soit ni limite ni successeur, et que 1, en tant que premier ordinal successeur, est aussi remarquable, et du point de vue des ordinaux on peut considérer que ce sont les seuls entiers naturels intéressants (d'où il découle que 2 est un ordinal intéressant puisque c'est le premier ordinal inintéressant, ha, ha, ha).

Un ordinal calculable, dit aussi indifféremment constructif ou récursif, est un ordinal α qu'on peut réaliser informatiquement : c'est-à-dire qu'on peut écrire un programme (pour un ordinateur ordinaire idéalisé, i.e., une machine de Turing) qui est capable de « manipuler » les ordinaux <α (ce qui importe est de pouvoir les comparer, mais sans changer la notion d'ordinal calculable on peut aussi demander que le programme soit capable de calculer les opérations, disons, d'addition, multiplication et puissance). Autrement dit, on peut représenter les ordinaux <α par une donnée informatique (forcément finie, et qu'on peut coder par un entier naturel si on veut) de manière qu'il soit algorithmiquement faisable de tester les représentations valables et de comparer les ordinaux représentés (et, si on veut, faire des opérations diverses dessus). Ce système informatique s'appelle un système de notations ordinales (sous-entendu : calculable) de taille α, et un ordinal calculable est donc un ordinal admettant un système de notations ordinales.

Pour être tout à fait précis, un ordinal α — forcément dénombrable — est dit calculable lorsqu'il existe une partie de ℕ (qu'on appellera les représentations d'ordinaux) qui soit calculable (i.e., le programme est capable de décider, à coup sûr en temps fini, si un élément proposé appartient à cette partie, i.e., est une représentation valable) et une relation d'ordre sur cette partie qui soit également calculable et qui soit une relation de bon ordre d'ordinal α. C'est la donnée de cette partie et de cette relation d'ordre (toutes deux calculables) qui s'appelle un système de notations ordinales.

Par exemple, ω est calculable parce que les entiers naturels sont manipulables informatiquement. De façon moins triviale, ω² est calculable parce qu'on peut utiliser informatiquement un couple (m,n) d'entiers naturels pour représenter ω·m+n, et que la comparaison se fait par l'ordre lexicographique (ω·m+n < ω·m′+n′ si et seulement si m<m′ ou bien [m=m′ et n<n′]). En fait, ε₀ est calculable parce qu'on peut utiliser la forme normale de Cantor itérée (= écriture en « base ω » dont les exposants sont eux-mêmes notés en « base ω » et ainsi de suite) pour représenter et manipuler les ordinaux <ε₀.

Il est à peu près trivial qu'un ordinal plus petit qu'un ordinal calculable est lui-même calculable, et comme il n'est certainement pas possible que tous les ordinaux soient calculables, ni même tous les ordinaux dénombrables (parce qu'il y a ℵ₁ ordinaux dénombrables, presque par définition de ℵ₁, et ℵ₀ programmes possibles pouvant représenter un ordinal calculable), il existe un plus petit ordinal non calculable, tout ordinal strictement plus petit est calculable et tout ordinal à partir de lui ne l'est pas. Ce plus petit ordinal non calculable s'appelle l'ordinal de Church-Kleene et est noté ω₁^CK.

L'idée générale est que, si tout ordinal <ω₁^CK est calculable, plus il est grand plus la représentation est difficile à trouver, et surtout, plus il est difficile de se convaincre qu'elle est « correcte ». En fait, il existe un système « universel » qui représente tous les ordinaux <ω₁^CK, appelé le 𝓞 de Kleene, mais (forcément !) il lui manque quelque chose pour être un système de notations ordinales : en fait, c'est que, si on peut comparer deux éléments du système universel en question, en revanche, on ne peut savoir ce qui est un élément valable ou un « faux », et on ne peut pas le savoir dans un sens très fort (même une machine hyperarithmétique ne peut pas — alors qu'elles sont beaucoup plus puissantes que les machines de Turing). Le problème est donc de déterminer, au sein de ce système universel, quels sont les « vrais » ordinaux.

Le lien avec la force logique de théories

Considérons d'une part une théorie mathématique T permettant de démontrer certains énoncés arithmétiques (je renvoie au tout début de cette entrée pour un rappel de ce que signifie arithmétique ici, mais disons juste que c'est un énoncé portant sur les entiers naturels — par opposition, disons, aux ensembles), et d'autre part un système de notations ordinales représentant [les ordinaux plus petits qu']un certain ordinal calculable α, c'est-à-dire, codant les ordinaux <α comme des entiers naturels. Je rappelle qu'une propriété importante des ordinaux est l'induction transfinie : si dès que tous les ordinaux <β ont une certaine propriété P alors β l'a aussi, alors tous les ordinaux ont cette propriété P ; cela revient essentiellement à dire que tout ensemble non vide d'ordinaux a un plus petit élément, ou que toute suite strictement décroissante d'ordinaux est finie (i.e., termine en temps fini). A priori, l'induction transfinie est une propriété ensembliste, mais dès lors qu'on a un système de notations ordinales représentant [les ordinaux plus petits que] α, cela devient quelque chose de plus arithmétique : il s'agit de dire que dès toutes les notations plus petites [au sens de l'ordinal dénoté] que β ont une certaine propriété P alors β l'a aussi, alors toutes les notations ont cette propriété P. Dans ces conditions, on peut se demander si la théorie T démontre ou non cette affirmation (de récurrence transfinie sur le système de notations), i.e., si elle est assez puissante pour cela.

Bon, il y a toutes sortes de subtilités que je veux passer sous silence : par exemple, la notion de propriété P fait que l'affirmation n'est pas tout à fait arithmétique (elle est analytique Π¹₁, c'est-à-dire qu'elle a une unique quantification universelle sur les propriétés P des entiers naturels devant un énoncé arithmétique), mais il y a toutes sortes de moyens de faire comme si (par exemple, se limiter à des propriétés P d'une certaine complexité arithmétique). Qu'on me permette donc un peu d'imprécision et de dire que, grosso modo, l'ordinal de preuve (proof-theoretic ordinal, je ne sais pas dire ça en français alors j'improvise) de la théorie T est la borne supérieure des ordinaux α tels que la théorie T prouve l'induction transfinie pour un certain système de notations pour α.

De façon plus imagée, l'ordinal de preuve de T est le plus petit ordinal α tel que T ne soit pas assez forte pour « comprendre » α au sens de démontrer qu'un certain système de notations ordinales pour α se comporte bien (vérifie l'induction transfinie, i.e., définit bien un ordinal).

(Comme je disais, il y a en fait toutes sortes de subtilités, donc toutes sortes d'ordinaux qu'on peut associer à une théorie. Il se trouve que, dans la pratique, pour les théories T auxquelles on s'intéresse, ces ordinaux coïncident.)

L'exemple le plus célèbre est l'arithmétique de Peano [du premier ordre], PA, dont l'ordinal de preuve est ε₀ : on peut définir, dans l'arithmétique de Peano, la notation pour les ordinaux <ε₀ par forme normale de Cantor itérée, on peut y prouver qu'elle constitue un ordre total, mais montrer que c'est un bon ordre, c'est-à-dire montrer l'induction transfinie, n'est pas possible dans ce système. En fait, ce n'est pas possible parce que l'induction transfinie sur ε₀ permet de démontrer la consistance de PA, et Gödel interdit que PA puisse faire ça : c'est ce résultat, dû à Gentzen en 1936, qui a lancé la théorie de la démonstration et de l'analyse ordinale (c'est-à-dire de l'utilisation d'ordinaux pour mesurer la force de systèmes logiques). Intuitivement, si on veut bien croire que ε₀ est un ordinal, alors on croit que PA est consistant.

(Le résultat de Gentzen a été mis sous forme un peu ludique sous la forme du jeu de l'hydre de Kirby-Paris : croire que ε₀ existe signifie en gros croire que le jeu termine toujours en temps fini.)

L'analyse ordinale d'une théorie T consiste essentiellement à :

• trouver un ordinal (calculable !) α et un système (calculable !) de notations ordinales « explicite » représentant [les ordinaux plus petits que] α,
• tel que T prouve l'induction transfinie jusqu'à n'importe quelle notation (β<α) dans le système, mais pas pour α lui-même,
• et si possible de sorte que (au-dessus d'une théorie T₀ très faible) les conséquences arithmétiques de T soient les mêmes que les conséquences arithmétiques de pour tout β<α [dans le système de notations ordinales décrit], l'induction transfinie vaut jusqu'à β.

Cette troisième partie nous dit que l'ordinal α mesure précisément la force arithmétique de la théorie T : non seulement cette dernière prouve l'induction transfinie jusqu'à tout β<α mais pas α, mais en plus, a contrario, si on suppose l'induction transfinie jusqu'à tout β<α alors on obtient tout ce que T démontre comme énoncés arithmétiques. C'est assez remarquable, mais il s'avère que c'est possible en pratique : on ne sait pas vraiment pourquoi, mais les théories mathématiques s'ordonnent bien par leurs conséquences arithmétiques.

(Enfin, de nouveau, j'ai glissé de la poussière sous le tapis. Si vous voulez un survey écrit par quelqu'un qui s'y connaît vraiment et pas quelqu'un comme moi qui fait mal semblant, voyez le papier The Realm of Ordinal Analysis de Michael Rathjen.)

Les théories T concernées peuvent être de plusieurs sortes : cela peut être des théories des ensembles faibles (c'est-à-dire des choses plus faibles que ZFC, dont un exemple typique est la théorie des ensembles de Kripke-Platek) ou des sous-ensembles de l'arithmétique de Peano du second ordre PA² (qui permet, en gros, de parler d'entiers naturels et de propriétés/ensembles d'entiers naturels, y compris de quantifier sur ces derniers) ; cela peut aussi être, quitte à être plus précis dans la définition de l'ordinal de preuve, des choses plus constructives, comme des extensions de la théorie des types de Martin-Löf ou des théories des ensembles en logiquie intuitionniste (voyez par exemple ici pour un survol).

Mais mon but n'est pas de parler de la théorie de la démonstration, juste d'expliquer comment elle se retrouve liée avec les grands ordinaux calculables : l'idée à retenir est donc que

• la théorie de la démonstration est à la fois demandeuse et productrice de grands ordinaux calculables, comme ordinaux de preuves de théories naturelles,
• pour des théories « suffisamment faibles » (comme l'arithmétique de Peano du premier ordre ou la théorie des ensembles de Kripke-Platek enrichie de divers axiomes d'infinis), on a une analyse ordinale, c'est-à-dire qu'on dispose d'une description vraiment explicite de l'ordinal de preuve en question (comme « écrasement » d'un grand cardinal / grand ordinal dénombrable) et cette description éclaire la théorie analysée en même temps que l'ordinal lui-même,
• tandis que pour des théories trop fortes (comme l'arithmétique de Peano du second ordre ou a fortiori ZFC), l'ordinal de preuve reste quelque chose de complètement abstrait.

Petits ordinaux calculables et fonctions de Veblen

Pour les ordinaux jusqu'à ε₀, on a une notation tout à fait explicite par la forme normale de Cantor itérée (je rappelle que la forme normale de Cantor est juste l'écriture en base ω de l'ordinal, et itérée signifie qu'on recommence avec les exposants de l'écriture, et ainsi de suite, et sur les ordinaux <ε₀ le processus termine, c'est quasiment la définition de ε₀ qui est le plus petit ordinal ε tel que ε=ω^ε ; voir ici pour des explications plus détaillées). Si on veut voir ça comme un type informatique, on va dire qu'une « notation <ε₀ » est quelque chose de la forme ω^γ_r·n_r + ⋯ + ω^γ₁·n₁, où γ_r>⋯>γ₁ sont des « notations <ε₀ » (préalablement définies) et n₁,…,n_r des entiers naturels non nuls (et la somme vide est autorisée et supposée désigner l'ordinal 0) ; la comparaison des notations se définit alors, de façon récursive assez simple (commencer par comparer le plus grand exposant, puis son coefficient, et continuer ainsi lexicographiquement) : c'est assez simple à programmer, c'est d'ailleurs un bon exercice pour voir si on a compris le schmilblick, en tout cas, ε₀ est bien un ordinal calculable. Cet ordinal ε₀ mesure précisément la force de l'arithmétique de Peano du premier ordre.

Si on veut noter les ordinaux jusqu'à ε₁ (la solution suivante de ε=ω^ε), on peut utiliser l'écriture en forme normale de Cantor itérée à la seule exception du fait que ε₀ se note par un symbole spécial (i.e., une « notation <ε₁ » est soit le symbole spécial ε₀ soit quelque chose défini par forme normale de Cantor dont les exposants sont des notations <ε₁ et différentes du seul symbole spécial ε₀) : ça reste facile de programmer les comparaisons (on applique le même algorithme que pour les notations <ε₀, à ceci près que si on doit comparer ε₀ à une notation écrite sous forme normale de Cantor, on remplace ε₀ par ω^ε₀ et on recommence). Le même procédé fonctionne encore pour les ordinaux jusqu'à ε₂ (on ajoute un symbole spécial ε₁, et la règle spéciale que ε₀<ε₁) ou un nombre fini quelconque de ε, c'est-à-dire jusqu'à ε_ω.

Mais du coup, il n'y a pas de raison de s'arrêter là. Définissons un type informatique « notation <ζ₀ » comme suit : une « notation <ζ₀ » est soit une forme normale de Cantor ω^γ_r·n_r + ⋯ + ω^γ₁·n₁, où γ_r>⋯>γ₁ sont des notations <ζ₀ (préalablement définies) et qui ne sont pas un ε_ι et n₁,…,n_r des entiers naturels non nuls (et la somme vide est autorisée et supposée désigner l'ordinal 0), soit un symbole ε_ι où ι est une notation <ζ₀ (préalablement définie) ; et la comparaison entre deux notations <ζ₀ se fait (récursivement) soit en comparant les indices ι si elles sont toutes deux de la forme ε_ι, soit en les comparant selon la règle lexicographique sur les formes normales de Cantor (quitte à réécrire ε_ι comme ω^ε_ι pour transformer un ε_ι en forme normale de Cantor). C'est un tout petit peu fastidieux à cause de cette double écriture ε_ι et ω^ε_ι (il faut choisir la première pour normaliser et éventuellement convertir à l'autre pour comparer), mais il n'y a vraiment aucune difficulté informatique. Si vous voulez voir du vrai code, voyez ce que j'avais fait ici et regardez le source JavaScript, qui est censé être vaguement lisible, il suit exactement ce que je viens de décrire.

La notation ζ₀ est pourrie, bien sûr, et personne ne l'utilise. Écrivons plutôt : φ(0,γ) pour ω^γ, puis φ(1,γ) pour ε_γ, et φ(2,0) pour l'ordinal ζ₀ décrit par le système de notations du paragraphe précédent, qui est le plus petit ordinal ζ vérifiant ε_ζ=ζ. Vous devinez bien sûr comment ça continue : je peux introduire une notation spéciale pour l'ordinal φ(2,0)=ζ₀ (sachant qu'on n'a pas le droit d'écrire ε_ζ₀ puisque c'est ζ₀, ni ω^ζ₀ puisque c'est aussi ζ₀), ce qui me permet de monter jusqu'au point fixe suivant φ(2,1)=ζ₁ de la fonction ε ; en étendant ça à un mécanisme systématique pour les φ(2,ι)=ζ_ι comme j'ai fait pour les ε, cela permet de monter jusqu'à un ordinal qu'on a envie de noter φ(3,0) pour ne pas avoir à chercher la lettre de l'alphabet grec suivant ζ. En suivant ce procédé de nouveau, on construit des notations pour les ordinaux φ(k,0), où φ(k+1,ι) est le ι-ième point fixe de la fonction γ↦φ(k,γ). Si vous avez compris le principe, félicitations, vous avez compris l'ordinal φ(ω,0) obtenu en mettant ensemble toutes ces notations : cet ordinal est assez important puisque c'est le plus petit après ω qui soit « primitivement récursivement clos ». (Il y a certainement des théories logiques assez naturelles ayant φ(ω,0) comme ordinal de preuve, mais je n'y connais pas assez pour essayer d'en décrire.)

La fonction φ que je définis au fur et à mesure s'appelle la fonction de Veblen. Définir φ(ω,ι) est un tout petit peu plus compliqué, parce qu'il n'y a pas un niveau précédent dont on peut simplement reprendre les points fixes : ce qu'on va dire est que φ(ω,ι) est le ι-ième point fixe commun à toutes les fonctions γ↦φ(k,γ) pour k<ω, et plus généralement, on définit φ(μ,ι) comme le ι-ième point fixe commun à toutes les fonctions γ↦φ(ν,γ) pour ν<μ. L'ensemble de tous les ordinaux qu'on peut écrire avec cette fonction (de deux variables !) s'appelle l'ordinal de Feferman-Schütte Γ₀ ; il est tout à fait possible d'utiliser φ(μ,ι) pour donner un système de notations ordinales explicite pour les ordinaux <Γ₀, mais cela devient un petit peu plus compliqué : si on se rappelle que précédemment on devait choisir des écritures normalisées (interdire d'écrire ω^ε_ι parce que c'est ε_ι, ou interdire d'écrire φ(ℓ,φ(k,γ)) si ℓ<k parce que c'est φ(k,γ)), ici on veut interdire d'écrire φ(ν,φ(μ,γ)) si ν<μ parce que c'est φ(μ,γ), mais le fait de pouvoir tester ν<μ demande déjà de disposer des notations, bref, on a une définition encore plus récursive à faire, dont je crois que la clé est l'affirmation suivante :

φ(μ,γ)<φ(μ′,γ′) a lieu si et seulement si l'une des affirmations suivantes vaut :

• μ=μ′ et γ<γ′,
• ou bien μ<μ′ et γ<φ(μ′,γ′),
• ou bien μ>μ′ et φ(μ,γ)<γ′.

(Ou, ce qui revient au même, pour comparer φ(μ,γ) et φ(μ′,γ′), on commence par trouver le minimum μ₀ de μ et μ′, puis on réécrit chacun des deux comme φ(μ₀,qqch) en se rappelant que φ(μ,γ)=φ(μ₀,φ(μ,γ)) lorsque μ₀<μ, et il n'y a alors qu'à appliquer le premier cas, qui est trivial.)

Certains ont émis l'opinion que l'ordinal Γ₀ est extrêmement important parce qu'il définit la limite de la prédicativité (très très très grossièrement, la prédicativité est la capacité à définir quelque chose à partir de choses plus petites). C'est quelque chose qui ne me convainc pas du tout. Mais il est indéniable que Γ₀ est l'ordinal de preuve d'une théorie relativement importante.

La notation Γ₀ est pourrie, bien sûr, et malheureusement des gens l'utilisent quand même. Écrivons plutôt φ(1,0,0) pour Γ₀ et plus généralement φ(1,0,ι) (ou Γ_ι) pour le ι-ième point fixe de toutes les fonctions γ↦φ(γ,0). Attention !, car si on a φ(Γ₀,0)=Γ₀, en revanche, φ(Γ₀,1) est strictement supérieur car la fonction φ(Γ₀,—) est strictement croissante (mais φ(Γ₀,1) est quand même inférieur à Γ₁ puisque Γ₁=φ(Γ₁,0)=φ(Γ₀,φ(Γ₁,0))>φ(Γ₀,1)). Plus généralement, convenons que φ(0,…,0,truc)=φ(truc) et que pour tout μ>0 on définit φ(machin,μ,0,…,0,ι) comme le ι-ième point fixe commun à toutes les fonctions γ↦φ(machin,ν,γ,0,…,0) pour ν<μ (ici, truc et machin sont des suites finies quelconques d'ordinaux, et dans la deuxième partie, la suite 0,…,0 a la même longueur des deux côtés). Ainsi, φ(1,1,ι) est le ι-ième point fixe de γ↦φ(1,0,γ) et φ(2,0,ι) est le ι-ième point fixe de γ↦φ(1,γ,0). (L'ordinal φ(1,0,0,0) s'appelle parfois ordinal d'Ackermann, mais il n'a aucun intérêt particulier, c'est juste une sorte d'erreur historique.)

Il s'agit là des fonctions de Veblen d'un nombre fini de variables. Le plus petit ordinal δ stable par toutes ces fonctions (au sens où : si tous les arguments — en nombre fini — d'une fonction φ sont tous strictement inférieurs à δ, alors le résultat est encore strictement inférieur à δ), qui est la limite de φ(1,0), φ(1,0,0), φ(1,0,0,0), etc., s'appelle petit ordinal de Veblen. Il présente un intérêt, notamment en lien avec le théorème de Kruskal sur les arbres (grosso modo, et modulo plein d'erreurs et approximations possibles de ma part, le petit ordinal de Veblen mesure la force d'une théorie pouvant prouver le théorème en question ; pour une affirmation moins vague, voir les références données ici). On peut utiliser les fonctions de Veblen d'un nombre fini de variables pour définir un système de notations ordinales pour le petit ordinal de Veblen un peu comme je l'ai esquissé pour l'ordinal de Feferman-Schütte : je ne crois pas qu'il y ait de difficulté majeure, même s'il y a sans doute des petits trucs pénibles (regarder la manière dont j'ai comparé φ(Γ₀,1) à Γ₀ et Γ₁ ci-dessus pour se faire une idée).

On se doute bien que je ne vais pas en rester là. La définition des fonctions de Veblen s'étend à un nombre transfini de variables : plus exactement, c'est-à-dire qu'on peut définir φ sur n'importe quelle fonction des ordinaux vers les ordinaux dont seulement un nombre fini de valeurs sont non nulles (la fonction correspondant à l'association d'une valeur à un emplacement). Par exemple, φ(k↦1), ce qui signifie φ appliqué à un 1 au k-ième emplacement et des 0 partout ailleurs vaut ce qu'on a appelé précédemment φ(1,0,…,0) où le 1 est à l'emplacement k compté à partir de la fin (le dernier emplacement étant numéroté 0), tandis que φ(1,1,0) s'écrirait φ(2↦1, 1↦1). L'ordinal φ(ω↦1) sera le petit ordinal de Veblen. La définition est que φ(machin, τ↦μ, 0↦ι), où τ est au premier emplacement >0 à porter une valeur non nulle, est le ι-ième point fixe commun à toutes les fonctions γ ↦ φ(machin, τ↦ν, ρ↦γ) pour ν<μ et ρ<τ : c'est un peu compliqué à dire, mais c'est assez naturel, et je crois que ça ne change essentiellement rien à la difficulté d'écrire un système de notations ordinales. Pour comparer ξ:=φ(τ↦γ_τ) à ξ′:=φ(τ↦γ′_τ), on commence par trouver le plus grand τ₀ tel que γ_τ₀ et γ′_τ₀ diffèrent : si γ′_τ₀ est le plus grand, on réécrit φ(τ↦γ′_τ) en remplaçant la valeur à l'emplacement τ₀ par γ_τ₀, et en mettant ξ′ lui-même à l'emplacement τ₀ suivant où γ_τ₁ n'est pas nul. Je ne rentre pas dans les détails, mais il n'y a pas de difficulté majeure.

L'ordinal qu'on peut atteindre avec ce système, c'est-à-dire le plus petit ordinal δ stable par toutes ces fonctions (au sens où : si toutes les valeurs non nulles — en nombre fini —, et tous les emplacements où elles se trouvent, d'une fonction φ sont tous strictement inférieurs à δ, alors le résultat est encore strictement inférieur à δ), qui est la limite de φ(ω↦1), φ(φ(ω↦1)↦1), φ(φ(φ(ω↦1)↦1)↦1), etc., s'appelle grand ordinal de Veblen.

Pour construire des ordinaux substantiellement plus grands que ça, il faut changer d'approche (et selon mon avis, c'est là qu'on perd la « prédicativité »).

L'idée générale des fonctions d'écrasement

Je commence par présenter un peu les choses de façon très informelle, par expliquer ce qu'on cherche à faire en introduisant une fonction d'écrasement ψ, et comment elle peut aider à noter de grands ordinaux.

Il faut que j'avertisse qu'il y a toutes sortes de variantes possibles sur les fonctions d'écrasement : celle que j'évoque ici diffère de façon peu importante de celle que j'ai introduite dans l'article Wikipédia que j'ai écrit sur le sujet, mais il y a des différences plus importantes dans la manière dont les choses sont faites dans les vraies fonctions d'écrasement servant dans la littérature mathématique (en gros, il y a le choix entre rendre la fonction croissante ou ce que j'ai tendance à appeler « décoincée », et si je trouve la version monotone plus facile à comprendre en première approche, la version décoincée marche mieux quand on veut aller loin).

On a vu que les points fixes, les énumérations et les itérations de points fixes jouent un rôle important dans la fabrication d'ordinaux (moralement, parce qu'un point fixe signifie qu'un procédé qu'on croit avoir trouvé pour fabriquer des ordinaux plus grands cesse d'en produire, il n'arrive pas à dépasser un certain point). On part typiquement de la fonction (qu'on pourra noter φ(α), ou ψ(α) au moins pour les petits α) valant α↦ω^α, et on considère ses points fixes, les solutions de l'équation ω^δ=δ : on a vu qu'on pouvait les noter ε_α, mais ce n'est pas du tout systématique ; on a aussi vu avec les fonctions de Veblen qu'on pouvait les noter φ(1,α), mais même cette notation-là atteint ses limites. Imaginons une notation de la forme ψ(Ω) pour ε₀, où Ω est pour l'instant un symbole magique voulant dire « point fixe » ; on pourra noter ψ(Ω+1) pour la puissance de ω suivante (c'est-à-dire ε₀·ω = ω^ε₀+1), et plus généralement ψ(Ω+α) = ε₀·ω^α = ω^ε₀+α (au moins pour les petits α), puis, quand on arrive à ε₁, qui est un nouveau point fixe de α↦ω^α, sortir la notation ψ(Ω·2) (« deuxième point fixe » : pour l'instant, Ω est toujours un symbole magique). De façon générale, on notera ψ(Ω·(1+α))=ε_α (au moins pour des petits α) ; le petit décalage de 1 n'est pas bien grave. Quand cette fonction arrive elle-même à un point fixe, on peut écrire ψ(Ω²), c'est ce qui a précédemment été noté φ(2,0) ou ζ₀. De même, ψ(Ω^ω) correspondra à φ(ω,0), et plus généralement ψ(Ω^α) à φ(α,0) (pour des petits α), le α-ième niveau de point fixe, ou la α-ième lettre de l'alphabet grec transfini après ε₀ et ζ₀. L'ordinal de Feferman-Schütte, lui, que ci-dessus j'ai noté Γ₀, ou φ(1,0,0) avec les fonctions de Veblen de plusieurs variables, sera ψ(Ω^Ω), où cette fois le Ω en exposant signifie qu'on cherche un point fixe de la fonction ψ(Ω^α).

Bref, le type de notation que je cherche à introduire est le suivant : on introduit une certaine fonction ψ dont l'argument peut faire intervenir un symbole magique Ω, et ce symbole veut dire quelque chose comme faire un point fixe de la fonction ψ où le dernier symbole Ω est remplacé par une variable ; bref, Ω est une sorte d'« opérateur de point fixe » qui généralise de façon systématique ce qu'on essayait de faire dans les fonctions de Veblen. (Je rappelle que pour l'instant je ne décris les choses que de façon très informelle.) L'avantage est que si on autorise une notation semblable à la forme normale de Cantor itérée mais en base Ω au lieu de ω, on fabrique vite des points fixes très compliqués : le petit ordinal de Veblen est ψ(Ω^Ωω) (de façon générale, φ(α↦1) s'écrira ψ(Ω^Ωα), au moins pour des petits α) et le grand est ψ(Ω^ΩΩ), mais il n'y a cette fois-ci aucun obstacle qui interdise d'empiler les Ω (chacun correspondant à tout un niveau de complexité dans le jeu d'itérations de points fixes !) et de fabriquer ψ(Ω^ΩΩΩ) et ainsi de suite jusqu'à une limite qui s'appelle l'ordinal de Bachmann-Howard, ψ(ε_Ω+1).

Pour essayer de rendre ce système un peu rigoureux, il faut commencer par donner un sens à Ω : on pourrait se contenter de dire que c'est un symbole, mais manifestement on veut pouvoir faire des opérations dessus, donc pour éviter de tout faire de façon ad hoc, il faut bien que ce soit un ordinal. Quel ordinal ? Ce qui importe essentiellement est qu'il soit beaucoup plus grand (et, en fait, beaucoup plus stable) que tous les ordinaux qu'on va fabriquer avec le procédé qu'on est en train de construire : par exemple, ψ(Ω+ψ(Ω)) désigne (ε₀)² et est beaucoup plus petit que ψ(Ω·2), ce qui suggère que Ω doit être largement plus gros que ψ(Ω), i.e., notre fonction ψ a plutôt tendance à « écraser » les ordinaux.

Bref, l'idée de notre approche est la suivante : on commence à définir une fonction modeste (dans l'exemple que j'ai choisi, ψ(α) vaut ω^α au début), et dès que cette fonction commence à ne plus rien produire d'intéressant parce qu'elle bute contre un point fixe, on fait appel à un ordinal Ω supposé largement plus grand que tout ce qu'on risque de fabriquer. Il y a, bien sûr, plein d'ordinaux qu'on a raté entre temps, mais ce n'est pas grave, on ne cherche pas à étudier Ω, on l'introduit juste pour décoincer les notations quand elles sont coincées : la valeur ψ(Ω) est donc « l'ordinal sur lequel les notations ψ(α) sont restées coincées » (et la fonction ψ sera non définie entre ψ(Ω) inclus et exclu Ω — c'est-à-dire sur toutes les valeurs qu'on a omises — ou bien constante de valeur ψ(Ω) si on préfère).

C'est cette idée bizarre de faire appel à des ordinaux encore plus grands pour définir des ordinaux plus modestes qui explique le nom général de fonction d'écrasement (ordinal collapsing function).

Une définition de l'ordinal de Bachmann-Howard

Pour définir les choses rigoureusement, on considère normalement que Ω désigne le premier ordinal indénombrable ω₁=ℵ₁ (parce qu'il est garanti qu'on ne fabriquera que des choses dénombrables, donc il est forcément supérieur à toute valeur de la fonction ψ). En fait, on peut se contenter de bien moins, à savoir le premier ordinal non-calculable ω₁^CK. La définition avec le premier indénombrable est moins technique, mais celle avec le premier ordinal non-récursif est plus économique du point de vue logique. Au niveau où je me place, de toute façon, ces subtilités sont sans importance : ce qui importe est que Ω est très très grand, et qu'entre autres ω^Ω=Ω et encore bien plus (notamment Ω est stable par toutes les fonctions de Veblen).

Comment définir ψ rigoureusement ? Il y a toutes sortes de variations, mais voici une définition qui produit les valeurs que j'ai annoncées :

Pour définir ψ(α) en supposant (par induction) ψ(β) connu pour tout β<α : on définit ψ(α) comme le plus petit ordinal qui ne peut pas être atteint à partir de 0 au moyen des opérations d'addition, d'application de ψ|_α (c'est-à-dire ψ limité aux valeurs <α) et de la fonction (γ,ξ)↦Ω^γ·ξ pour γ>0.

Ajout (2021-12-02) : la phrase ci-dessus n'est pas parfaitement claire (même si je détaille un peu plus ci-dessous sur des exemples), donc soulignons que les ordinaux atteints dans cette phrase sont ceux qui sont construits à partir de 0 en appliquant (un nombre fini de fois) les opérations d'addition, de ψ|_α (si elle est définie, c'est-à-dire si son argument est <α) et de (γ,ξ)↦Ω^γ·ξ (où γ>0) ; autrement dit, ψ(α) est défini comme le plus petit ordinal n'appartenant pas à la clôture C(α) de 0 sous les opérations qu'on vient de dire. Pour être encore plus explicite, pour avoir le droit d'appliquer ψ à un ordinal β dans cette définition, l'ordinal β doit être à la fois déjà construit (par les opérations dont on prend la clôture) et aussi <α (pour que ψ|_α(β) ait un sens).

Essayons d'expliquer ce que ça signifie.

D'abord je veux calculer ψ(0) : ma définition me dit que c'est le plus petit ordinal qui ne peut pas être atteint à partir de 0 par des additions, la fonction ψ restreinte à l'ensemble vide et la fonction (γ,ξ)↦Ω^γ·ξ restreinte aux couples (γ,ξ) avec γ>0 : il n'y a pas à chercher beaucoup pour se rendre compte qu'on ne peut pas quitter 0 avec ces opérations, donc le plus petit ordinal qui n'est pas atteignable est 1, si bien que ψ(0)=1. Ensuite on cherche à calculer ψ(1) : cette fois-ci, on a le droit d'appliquer ψ(0)=1 et les additions, donc on peut produire tous les entiers naturels ; on peut aussi appliquer la fonction (γ,ξ)↦Ω^γ·ξ aux entiers naturels, donc produire Ω, Ω², Ω³, et aussi les sommes de ces choses-là, donc par exemple Ω²+Ω·42, ou encore plusieurs exponentiations de base Ω, donc par exemple Ω^Ω, etc. — mais tout ceci ne nous concerne pas vraiment, ce qui importe est le plus petit ordinal qu'on n'atteint pas, et c'est ω, donc ψ(1)=ω. Pour calculer ψ(2), de même, on a le droit à 1 et ω, aux additions, et à la fonction (γ,ξ)↦Ω^γ·ξ, donc et on se convainc rapidement qu'on peut essentiellement produire les ω·p+q avec p et q entiers, plus plein de choses impliquant Ω mais qui ne nous concernent pas pour l'instant, et le minimum inatteignable est ω². Le même type de raisonnement montre que ψ(α)=ω^α pour toutes les petites valeurs de α. Jusqu'à quand continue-t-il à être valable ? Il l'est, essentiellement, tant qu'on peut approcher α par des valeurs plus petites en appliquant α↦ω^α un nombre fini de fois, autrement dit, tant que α<ε₀.

En revanche, à partir de ε₀, la valeur de ψ cesse de grandir (au moins pour la fonction telle que je l'ai définie ci-dessus : d'autres variantes donneraient une fonction qui n'est plus définie, ou encore des choses différentes) : en effet, ε₀ n'est pas atteignable à partir de 0 au moyen des opérations d'addition, d'application de ψ|_ε₀:α↦ω^α (et de la fonction (γ,ξ)↦Ω^γ·ξ qui, à ce stade-là, continue à ne servir à rien). La fonction est « coincée ». Ceci est vrai jusqu'à ψ(Ω)=ε₀. Mais là, il se produit quelque chose d'un peu miraculeux, qui justifie l'intérêt de notre construction, c'est que ψ(Ω+1) se « débloque » : en effet, parmi les ordinaux qu'on peut fabriquer à partir de 0 en appliquant les opérations d'addition, d'application de ψ|_Ω et de la fonction (γ,ξ)↦Ω^γ·ξ, il y a, cette fois, ε₀, puisque c'est, justement, ψ(Ω) (et que Ω lui-même s'obtient comme Ω¹·1, et 1 comme ψ(0)), et du coup tous les multiples entiers de ε₀, et le premier ordinal qu'on ne peut pas atteindre est, maintenant, ε₀·ω=ω^ε₀+1. Plus généralement, on a ψ(Ω+α) = ε₀·ω^α = ω^ε₀+α tant que α<ε₁, où la fonction ψ se retrouve de nouveau coincée : on a ψ(Ω·2)=ε₁, mais pour la même raison que précédemment, la valeur suivante la « débloque » et ψ(Ω·2+1)=ε₁·ω. On a ainsi ψ(Ω·(1+α))=ε_α pour tout α<ζ₀, après quoi la fonction est de nouveau bloquée, et on a ψ(Ω²)=ζ₀=φ(2,0).

Je ne vais pas refaire l'explication pour chaque valeur que j'ai déjà annoncée plus haut, mais l'idée générale est qu'à chaque fois que la fonction ψ se retrouve coincée parce qu'elle bute contre un point fixe, cette valeur peut être écrite comme l'image d'une expression faisant intervenir Ω, et ce fait permet de « débloquer » la fonction ψ. C'est ce qui explique que Ω se comporte comme un symbole signifiant point fixe. À titre d'exemple :

• ψ(Ω) est la limite de 0, ψ(0), ψ(ψ(0)), ψ(ψ(ψ(0))), etc.
• ψ(Ω·2) est la limite de ψ(Ω), ψ(Ω+ψ(Ω)), ψ(Ω+ψ(Ω+ψ(Ω))), etc.
• ψ(Ω²) est la limite de ψ(Ω), ψ(Ω·ψ(Ω)), ψ(Ω·ψ(Ω·ψ(Ω))), etc.
• ψ(Ω^Ω) est la limite de ψ(Ω), ψ(Ω^ψ(Ω)), ψ(Ω^ψ(Ωψ(Ω))), etc.

Il est aussi important de souligner que Ω devient en quelque sort « de plus en plus grand » à chaque fois qu'on fait appel à lui, puisqu'il tient lieu de « quelque chose de bien plus grand que tout ce qu'on a construit jusqu'ici » : par exemple, ψ(Ω) se contente d'être supérieur à tous les ψ(α) seulement pour les α qu'on peut fabriquer à partir de 0 en itérant l'addition et la fonction ψ, donc pour α<ψ(Ω)=ε₀ ; en revanche, déjà ψ(Ω·2) doit dépasser ψ(Ω+α) à la fois pour ces α-là, mais aussi pour les α comme ψ(Ω) qui ont été fabriqués à l'étape précédente. Donc chaque appel à Ω est plus riche et plus complexe que le précédent !

Jusqu'où peut-on aller comme ça ? On voit aisément que ce qui nous limite est l'empilement des puissances de Ω : si on considère la limite de 1, Ω, Ω^Ω, Ω^ΩΩ, Ω^ΩΩΩ, etc. — qui vaut ε_Ω+1 (puisque ε_Ω=Ω et que Ω^Ωα=ω^Ωα dès que α est infini), la fonction ψ se retrouve bloquée à la limite de ψ(1), ψ(Ω), ψ(Ω^Ω), ψ(Ω^ΩΩ), etc., et il n'y a plus rien pour la débloquer : cette limite, comme je l'ai dit, s'appelle l'ordinal de Bachmann-Howard, ψ(ε_Ω+1), et c'est la puissance de la fonction d'écrasement que j'ai définie.

Mais la fonction d'écrasement ψ ne fait pas que définir l'ordinal de Bachmann-Howard, elle permet de le comprendre, c'est-à-dire, de le construire : elle définit un système de notations pour les ordinaux plus petits que lui, qui permet de les désigner et de les comparer. À la limite, on pourra oublier complètement la définition de la fonction ψ et traiter les notations ordinales qu'elle définit comme la définition de l'ordinal de Bachmann-Howard.

Pour définir ce système de notations, on commence par définir les arguments « non bloqués » de la fonction ψ, qui sont les arguments α pour lesquels ψ(α+1)>ψ(α), ou, de façon équivalente, tels que α soit le plus grand argument possible pour lequel ψ prenne la valeur en question. Par exemple, Ω est un argument non bloquée de ψ, alors que ε₀, ou n'importe quel ordinal entre ε₀ inclus et Ω exclu, est un argument bloqué, puisque la fonction ψ n'augmente pas entre ε₀ et Ω comme je l'ai expliqué. Ainsi, toute valeur prise par ψ est prise en un et un seul argument non bloqué (à savoir le plus grand pour lequel ψ prend cette valeur).

On définit alors la forme normale (pour ψ) d'un ordinal : c'est essentiellement la façon de l'écrire — si c'est possible — au moyen de la fonction ψ (ainsi que des additions et la fonction ξ↦Ω^ξ) de sorte que tous les arguments de toutes les fonctions ψ soient non-bloqués ; de façon un peu plus précise, pour obtenir la forme normale d'un ordinal, on l'écrit en base Ω itérée, et chacun des morceaux (qui sont alors <Ω, c'est-à-dire dénombrables) comme somme de valeurs de ψ en des arguments non bloqués, qui sont eux-mêmes écrits sous forme normale. Cette forme normale est unique quand elle existe, et elle existe pour tout ordinal inférieur à l'ordinal de Bachmann-Howard, ainsi que pour certains ordinaux indénombrables (à savoir ceux dont les morceaux de l'écriture en base Ω itérée sont plus petits que l'ordinal de Bachmann-Howard : c'est ce qui sert comme arguments dans les fonctions φ). Concrètement, la manière dont on teste si une expression est une forme normale est de vérifier qu'il s'agit d'une écriture en base Ω itérée dont les morceaux sont des sommes décroissantes de valeurs de ψ appliquées à des formes normales (récursivement) et que chaque argument de ψ est supérieur à tous les arguments de toutes les fonctions ψ qui apparaissent à l'intérieur : par exemple, ψ(ψ(Ω)) ou ψ(ψ(Ω)+1) ou ou ψ(ψ(Ω)·2) ne sont pas des formes normales parce que l'argument (Ω) de la fonction ψ intérieure est supérieur à l'argument (que ce soit ψ(Ω) ou ψ(Ω)+1 ou ψ(Ω)·2). En revanche, les expressions suivantes sont des formes normales d'ordinaux plus petits que l'ordinal de Bachmann-Howard, et écrits dans l'ordre : 1 (que techniquement il faudrait écrire ψ(0), mais admettons que « 1 » est un racourci de langage), 42 (que techniquement il faudrait écrire 1+1+1+⋯+1), ψ(1) (qui n'est autre que ω), ψ(1)+ψ(0), ψ(1)·18 (que techniquement il faudrait écrire ψ(1)+⋯+ψ(1)), ψ(2) (qui vaut ω²), ψ(ψ(1)) (qui vaut ω^ω), ψ(ψ(ψ(1))) (qui vaut ω^ωω), ψ(Ω) (qui vaut ε₀), ψ(Ω+1) (qui vaut ε₀·ω), ψ(Ω+ψ(Ω)) (qui vaut ε₀²), ψ(Ω·2) (qui vaut ε₁), ψ(Ω·ψ(Ω)) (soit ε_ε₀), ψ(Ω²) (qui vaut ζ₀), ψ(Ω^ψ(Ω)) (qui vaut φ(φ(1,0),0)), ψ(Ω^Ω) (qui vaut Γ₀), ou encore ψ(Ω^Ωψ(ΩΩ)) ou ψ(Ω^{ΩΩ·ψ(ΩΩ)}+Ω^Ω²+Ω^ψ(Ω³)).

Comment comparer deux ordinaux écrits sous forme normale ? C'est trivial : ils sont écrits en base Ω itérée, donc il suffit de comparer lexicographiquement celles-ci, ce qui nous ramène à comparer des sommes décroissantes de valeurs de fonctions ψ, qui sont elles-mêmes comparées lexicographiquement, et enfin on est ramené à comparer des valeurs de fonctions ψ, ce qui se fait en comparant leurs arguments (puisque la fonction ψ est croissante, et même strictement croissante sur les arguments non bloqués). C'est-à-dire concrètement que la seule règle à retenir est que Ω est supérieur à toute valeur de la fonction ψ. À titre d'exemple, ψ(Ω^Ω) est supérieur à ψ(Ω^ψ(Ωψ(Ω))) — en effet, pour les comparer, il s'agit de comparer Ω^Ω et Ω^ψ(Ωψ(Ω)), ce qui revient à comparer Ω et ψ(Ω^ψ(Ω)), et bien sûr Ω est le plus grand. On notera que la vérification de la forme normale utilise elle-même la comparaison (pour vérifier que les arguments des ψ « extérieurs » sont supérieurs à ceux des ψ « intérieurs »).

Quelques idées sur des écrasements plus sophistiqués

L'ordinal de Bachmann-Howard (ψ(ε_Ω+1) ci-dessus) mesure la puissance d'une certaine théorie appelée théorie des ensembles de Kripke-Platek (avec axiome de l'infini). Je ne vais pas définir exactement cette théorie, mais disons qu'elle a un rapport avec les ordinaux admissibles (une notion que je définis dans mon entrée sur la programmation transfinie), dont le plus petit (après ω) est l'ordinal de Church-Kleene ω₁^CK à partir duquel les ordinaux cessent d'être calculables (pour que les choses soient bien claires : ω₁^CK est donc beaucoup plus grand que l'ordinal de Bachmann-Howard ou que tous les ordinaux définis dans cette partie !). Il existe un rapport entre l'ordinal de Bachmann-Howard et celui de Church-Kleene, qui peut se présenter de deux manières :

• L'ordinal de Church-Kleene permet de définir une fonction d'écrasement grâce à laquelle on définit celui (plus petit !) de Bachmann-Howard : en effet, dans la définition que j'ai donnée, j'utilisais pour Ω le premier ordinal indénombrable ω₁, mais en fait, ω₁^CK suffit si on est beaucoup plus soigneux dans les définitions (il suffit car ce qui importe de Ω est qu'il soit toujours beaucoup plus grand que tout ce qu'on peut construire, et c'est le cas de ω₁^CK car on ne construit que des ordinaux calculables).
• L'ordinal de Church-Kleene est l'ordinal de Bachmann-Howard sont tous les deux « le plus petit ordinal qui soit hors de portée de la théorie des ensembles de Kripke-Platek », mais dans un sens différent : l'ordinal de Church-Kleene est le plus petit dont KP ne prouve pas l'existence en tant qu'ordinal ensembliste (l'affirmation ω₁^CK existe, i.e., il existe un ordinal admissible >ω, n'est pas démontrable dans KP un peu de la manière dont l'existence d'un cardinal inaccessible est indémontrable dans ZFC : en gros, la raison est que cet ordinal « suffit » pour constituer la classe de tous les ordinaux d'un modèle de KP), tandis que l'ordinal de Bachmann-Howard est le plus petit sur lequel KP ne prouve pas l'induction transfinie lorsqu'il est réalisé comme un ordinal calculable (par un système de notations ordinales explicites, à savoir celui que j'ai esquissé plus haut ; accessoirement, on peut aussi en déduire un petit jeu d'hydre comme on pouvait le faire pour ε₀, qui est une sorte de traduction ludique du système de notations).

Ce phénomène est général : très grossièrement parlant (vraiment très très très grossièrement), et dans les cas usuels (pas fait exprès pour le contraire) l'ordinal de preuve d'une théorie des ensembles « façon Kripke-Platek » est décrit par un système de notations construit autour d'une fonction d'écrasement basée sur le plus petit ordinal dont cette théorie des ensembles ne prouve pas l'existence. Seulement, plus cet ordinal est gros (et du coup, son écrasé aussi), plus la fonction d'écrasement est complexe à définir et à décrire et le système de notations ordinales aussi (ce qui est inévitable vu qu'aucun système de notations ordinales ne peut les englober toutes, plus on veut aller loin plus il faut le payer).

Dans tous les cas (en tout cas ceux qu'on sait décrire à l'heure actuelle !), les ordinaux écrasés sont des ordinaux dénombrables « récursivement grands », ceux que j'ai appelés du domaine (2) dans mon introduction, mais, en fait, la description est beaucoup plus simple avec des cardinaux du domaine (3) (comme ω₁ à la place de ω₁^CK) ; c'est un peu gênant parce que ça veut dire qu'on fait appel à des théories dépassant ZFC (par exemple, l'existence d'un cardinal inaccessible, ou Mahlo, ou faiblement compact voire plus, choses dont ZFC ne prouve pas l'existence, à la place d'un ordinal récursivement inaccessible, ou récursivement Mahlo, ou récursivement faiblement compact, choses dont ZFC prouve l'existence) pour décrire des théories plus faibles que ZFC ; mais cela diminue considérablement la technicité de la description du système de notations (qui reste assez colossale quand on va au-delà du faiblement compact).

Regardons un peu à quoi ressemblent des écrasements divers et variés qui ont été décrits. Je ne peux évidemment que faire une description extrêmement grossière de l'idée générale de ce qui se passe, je ne compte pas rentrer dans le moindre détail, juste faire entendre la musique (du coup, j'utilise certains termes techniques sans les définir, tant mieux pour les lecteurs qui savent ce qu'ils veulent dire, mais si ce n'est pas le cas, c'est que ce n'est pas terriblement important pour se faire une idée) : mais mon propos n'est pas tellement de définir les ordinaux en question que de donner un minuscule aperçu de la manière dont la complication s'accumule.

✱ La première étape évidente pour aller au-delà de l'ordinal de Bachmann-Howard consiste à ajouter un nouveau Ω₂ qui soit encore plus grand que tout ce qu'on peut fabriquer avec Ω, et qui va donc permettre de dépasser ε_Ω+1=Ω^ΩΩ⋰. Pour ça, on peut utiliser ω₂ (le plus petit cardinal >ω₁) ou, si on est plus courageux, ω₂^CK (notation peu standard mais logique pour le plus petit ordinal admissible >ω₁^CK). Je ne vais pas décrire exactement la fonction d'écrasement ou le système de notations qui en résulte, mais l'idée est qu'on a deux fonctions d'écrasement, l'une qui utilise Ω₂ pour donner des noms à certains ordinaux à partir de Ω₁=Ω un peu comme la manière dont on a utilisé Ω pour donner des noms à certains ordinaux dénombrables, et l'autre qui utilise ces noms à son tour pour donner des noms à certains ordinaux dénombrables. Pour dire les choses autrement : Ω a servi comme une sorte d'opérateur de point fixe pour construire toutes sortes de notations de points fixes imbriqués, généralisant monstrueusement les fonctions de Veblen, qui permet, par des puissances de Ω, de monter jusqu'à l'ordinal de Bachmann-Howard ; maintenant, Ω₂ sert à son tour comme une sorte d'opérateur de point fixe pour fabriquer des constructions en Ω beaucoup plus grandes que ce qu'on peut atteindre avec des puissances, et du coup démultiplie le pouvoir de Ω de fabriquer des ordinaux dénombrables (on a deux fonctions d'écrasement définies ensemble : l'une, disons ψ ou ψ_Ω, qui fabrique des ordinaux <Ω et l'autre, disons ψ₁ ou ψ_Ω₁, qui fabrique des ordinaux ≥Ω mais <Ω₂). On obtient un ordinal qui sera noté quelque chose comme ψ(ε_Ω₂+1) et qui est grosso modo à l'ordinal de Bachmann-Howard ψ(ε_Ω+1) (qui dans ce contexte devient ψ(Ω₂)) ce que ce dernier est à ε₀. Cet ordinal ψ(ε_Ω₂+1) mesure la force de la théorie des ensembles de Kripke-Platek enrichie de l'axiome ω₁^CK existe.

Pour mieux comprendre le rapport entre ε₀, l'ordinal de Bachmann-Howard ψ(ε_Ω+1) et le nouvel ordinal ψ(ε_Ω₂+1) dont je parle ci-dessus, il est peut-être intéressant que je digresse pour dire quelques mots des hiérarchies de fonctions à croissance lente et à croissance rapide. Je préfère réserver leur description précise à une (éventuelle) prochaine entrée, mais disons grosso modo la chose suivante : donné un ordinal α calculable (muni de données supplémentaires appelées « séquences fondamentales » que je vais abusivement ignorer), on peut fabriquer deux fonctions ℕ→ℕ (pouvant servir à construire de grands entiers naturels), l'une appelée la fonction f=f_α de la hiérarchie à croissance rapide, l'autre g=g_α de la hiérarchie à croissance lente (il y en a encore d'autres, et il y a des variations dans la construction, mais c'est en gros ce qui est important). La hiérarchie à croissance lente correspond intuitivement et très grossièrement à substituer l'argument de la fonction à la place de ω dans l'ordinal α (par exemple, si α=ω^ω, alors g(n) va être quelque chose comme n↑n = nⁿ, et si α=ε₀ alors g(n) va être quelque chose comme une tour de n empilement de puissances, parfois notée n↑↑n) ; la hiérarchie à croissance rapide, elle, correspond à itérer à chaque fois la fonction du niveau précédent : donc déjà f_k est en gros la k-ième tranche de la fonction d'Ackermann (le niveau 3 de la hiérarchie à croissance rapide est déjà en gros le même que le niveau ε₀ de la hiérarchie à croissance lente), et aux ordinaux limites on diagonalise, donc par exemple f_ω est en gros la diagonale de la fonction d'Ackermann (qui n'est déjà plus primitive récursive), f_ω+1(n) correspond à itérer n fois f_ω, et ainsi de suite. La hiérarchie à croissance rapide est donc beaucoup plus efficace que celle à croissance lente. Pourtant, « les ordinaux gagnent toujours » : le niveau ε₀ de la hiérarchie à croissance rapide est comparable au niveau de la hiérarchie à croissance lente donné par l'ordinal de Bachmann-Howard, et ce niveau-là de la hiérarchie à croissance rapide est comparable au niveau de la hiérarchie à croissance lente donné par l'ordinal ψ(ε_Ω₂+1) dont il est question au paragraphe précédent, « et ainsi de suite » : chaque nouveau Ω ajouté va donner à la hiérarchie à croissante lente une vitesse de croissance comparable au niveau précédent de celle à croissance rapide.

✱ Il est tentant (comme je le suggère au paragraphe précédent) d'ajouter Ω₃ après Ω₂, puis Ω₄ après Ω₃, « et ainsi de suite » : chaque nouveau Ω ajouté fabrique un ordinal qui est, grossièrement parlant, au précédent comme l'ordinal de Bachmann-Howard est à ε₀. Ou en fait beaucoup plus : chaque nouveau Ω ajouté démultiplie le pouvoir du précédent de fabriquer des points fixes, qui servent eux-mêmes à démultiplier, et ainsi de suite. Pour construire la fonction ψ, il faut interpréter ces Ω_i comme des cardinaux ω_i=ℵ_i, ou, si on veut être plus économique au prix de plus de complexité technique, comme des ordinaux « admissibles » ω_i^CK. La limite ψ(Ω_ω) des ordinaux écrasés ψ(ε_Ωi+1) est, si on a lu le paragraphe précédent, le premier ordinal où les hiérachies à croissance lente et rapide se rattrapent (c'est-à-dire que les fonctions f et g associées à cet ordinal sont comparables l'une à l'autre) ; cet ordinal mesure la force d'un système logique appelé Π¹₁-compréhension (le sous-système de l'arithmétique du second ordre où on a le droit de définir un ensemble d'entiers naturels par une propriété qui porte uniquement, en tête, des quantificateurs universels, sur les parties d'entiers naturels). L'ordinal obtenu en ajoutant juste un niveau de Ω après, ψ(ε_Ωω+1), est lui aussi important (c'est la force logique de la Π¹₁-compréhension plus « bar-induction », si j'ai bien retenu — je ne retrouve plus mes références à ce sujet).

✱ Bien sûr, au stade où j'en suis, on se doute bien que je ne vais pas m'arrêter là ! Pour disposer de plein de Ω, on va mettre la fonction γ↦Ω_γ elle-même dans le système de notations. Mais pour rendre ce système vraiment puissant, on veut aussi pouvoir créer des points fixes là-dessus : c'est-à-dire pouvoir disposer d'un ordinal tel que γ=Ω_γ (un point fixe de la fonction Ω), et un ordinal γ qui est le γ-ième point fixe de la fonction Ω, et ainsi de suite, un peu comme on a construit l'ordinal de Bachmann-Howard en créant plein de points fixes à partir de γ↦ω^γ sauf que cette fois-ci ce sont des niveaux de Ω tout entiers qu'on est en train de créer. La façon de s'en sortir est de faire appel à quelque chose de beaucoup plus grand que tout ce qu'on pourra fabriquer avec Ω, et ce « quelque chose » est, par exemple (si on a interprété Ω_γ comme le γ-ième cardinal ω_γ=ℵ_γ), un cardinal inaccessible I (de mon domaine (3) des ordinaux). Peu importe ce qu'est exactement un cardinal inaccessible : ce qui importe est qu'il soit plus grand que tout ce qu'on peut fabriquer en empilant les Ω, et c'est exactement ce qu'est un cardinal inaccessible ; mais si on a été soigneux et qu'on a interprété les Ω_γ comme des « ordinaux admissibles » (ω_γ^CK de mon domaine (2) des ordinaux), alors I a « simplement » besoin d'être ce qu'on appelle « récursivement inaccessible ».

Toujours est-il qu'on fabrique ainsi un ordinal (calculable ! on est toujours dans le domaine (1) !) qu'on peut noter ψ(ε_I+1) (peu importent les détails de la fonction d'écrasement ψ, je cherche juste à donner une idée), qui bien que construit à partir d'un cardinal inaccessible I (ou au moins un ordinal récursivement inaccessible) est, pour sa part, tout à fait dénombrable, calculable et explicite ; mais pour vérifier que cet ordinal « a bien un sens », c'est-à-dire qu'il vérifie l'induction transfinie, il commence à falloir utiliser des théories un peu puissantes pour donner un sens à toutes les définitions : en l'occurrence, ψ(ε_I+1) mesure la force de la théorie des ensembles de Kripke-Platek enrichie d'un axiome qui dit « la classe des ordinaux est récursivement inaccessible » (ce qui signifie : tout ordinal est majoré par un ordinal admissible).

✱ On peut bien sûr ensuite ajouter un deuxième inaccessible, puis un troisième, et ainsi de suite. Mais pour faire les choses de façon plus systématique, ce qu'on va faire est faire appel à un cardinal « Mahlo » (ou, comme précédemment, un ordinal récursivement Mahlo, quitte à plonger dans beaucoup plus de technicité) M, qui sert à fabriquer des cardinaux inaccessibles/réguliers ou des ordinaux admissibles ad lib. avec une nouvelle fonction d'écrasement : en gros, on aura peut-être une fonction θ « d'écrasement à valeurs dans les cardinaux réguliers (ou ordinaux admissibles) » où θ(1)=Ω et θ(2)=Ω₂ et ainsi de suite, mais ensuite θ(M) est le premier inaccessible (le premier cardinal régulier / ordinal admissible tel que γ=Ω_γ) et θ(M2) est le suivant, et ainsi de suite, et θ(M²) est le premier hyperinaccessible (le premier γ qui soit le γ-ième cardinal inaccessible), et θ(M³) est le premier hyperhyperinaccessible, et θ(M^M) est le premier γ dont le degré d'inaccessibilité soit égal à γ lui-même, et ainsi de suite. Et pour chacun des cardinaux (ou ordinaux admissibles) π produits par cette fonction θ on a une fonction d'écrasement ψ_π vers les ordinaux <π : je passe plein plein plein de détails, mais l'idée générale est que ce cardinal Mahlo permet de fabriquer toutes sortes d'inaccessibles (qui eux-mêmes fonctionnent comme je l'ai esquissé ci-dessus). On obtient ainsi un ordinal (calculable !) ψ_Ω(ε_M+1) qui mesure la force de la théorie des ensembles de Kripke-Platek enrichie d'un axiome qui dit « la classe des ordinaux est récursivement Mahlo ».

✱ Pour aller encore plus loin, on fait appel à un cardinal « faiblement compact » K, une notion de grand cardinal (domaine (3)) dont l'analogue récursif (domaine (2)) s'appelle « Π₃-réfléchissant », quelque chose que je ne compte pas définir, mais à ce niveau-là, le système de fonctions d'écrasement devient encore plus complexe. Au niveau de l'écrasement d'un cardinal récursivement Mahlo (:= Π₂-réfléchissant sur les admissibles, c'est-à-dire Π₂-réfléchissant sur les Π₂-réfléchissants), que j'avais évoqué ci-dessus, il y avait deux « niveaux » de fonctions d'écrasement : θ qui sert à fabriquer des cardinaux réguliers / ordinaux admissibles π<M, et toutes sortes de fonctions ψ_π qui fabriquent des ordinaux <π. Maintenant qu'on veut jouer avec K, les choses se compliquent encore : on a une hiérarchie par niveau de « Mahloïtude », avec au niveau 0 tous les ordinaux <K, au niveau 1 les cardinaux réguliers ou ordinaux admissibles, au niveau 2 les cardinaux Mahlo ou ordinaux récursivement Mahlo, et au niveau γ+1 les cardinaux réguliers dans lesquels ceux du niveau γ sont clos-cofinaux (ou quelque chose d'analogue côté récursif : les ordinaux Π₂-réfléchissant sur ceux de niveau γ) ; on a une fonction d'écrasement qui produit le plus petit élément de chaque niveau de Mahloïtude, mais surtout, on a en a une autre ψ^ξ_π de trois variables qui prend un niveau de Mahloïtude ξ, un π dans lequel écraser (qui est lui-même d'un certain niveau de Mahloïtude >ξ), et un ordinal à écraser, et qui produit un écrasement <π de niveau de Mahloïtude ξ (qui peut donc servir pour de nouveaux écrasements si ξ>0). Bref, là où au paragraphe précédent on avait juste le niveau 0 (la fonction ψ) et une ébauche de niveau 1 (la fonction θ), on a maintenant toute une hiérarchie de niveaux, et K peut servir à diagonaliser sur la hiérarchie elle-même (produire le plus petit cardinal dont le niveau de Mahloïtude est égal à lui-même, etc.).

L'ordinal ψ⁰_Ω(ε_K+1) décrit par tout ce fatras mesure la force d'une théorie qui est la théorie des ensembles de Kripke-Platek enrichie d'un axiome de Π₃-réflexion.

Tout ça est déjà bien compliqué. Chronologiquement, cette analyse date de 1994 (Michael Rathjen, Proof theory of reflection, Ann. Pure Appl. Logic 68 (1994), 181–224 ; disponible ici mais avec malheureusement plein de fautes typographiques pénibles). C'est l'ordinal calculable le plus grand que j'ai l'impression de bien comprendre, au sens où je crois pouvoir coder sur un ordinateur un système de notations ordinales jusqu'à ce ψ⁰_Ω(ε_K+1) (ce n'est pas un exploit : l'article de Rathjen donne en gros tous les algorithmes nécessaires).

Mais au-delà de ça, il arrive des complications bien plus importantes : pour écraser un ordinal « Π₄-réfléchissant », on doit commencer à gérer des ordinaux dont la description est vraiment plus complexe que l'écrasement de quelque chose (par exemple des ordinaux Π₂-réfléchissant sur les Π₃-réfléchissants) : les fonctions d'écrasement prennent en argument non pas juste un ordinal vers lequel écraser et un simple niveau de Mahloïtude, mais des données beaucoup plus riches que sont des « configurations de réflexion » ou des « instances de réflexion » (on n'écrase pas juste vers un ordinal de niveau de Mahloïtude ξ et inférieur à π mais vers un ordinal ayant certaines propriétés de réflexion qui conduisent elles-mêmes à d'autres fonctions d'écrasement), et le système de notation devient incroyablement plus subtil et défini par un nombre assez impressionnant de récursions imbriquées. Au moins les ordinaux « Π₅-réfléchissants » ou plus n'apportent-ils pas plus de complexité substantielle par rapport aux Π₄-réfléchissants, mais il y a encore quelques subtilités si on veut inclure tous les niveaux d'un coup, voire, des niveaux indicés par le système d'ordinaux qu'on est en train de définir. C'est en gros à ce point-là que travaille la thèse de Jan-Carl Stegert (Ordinal proof theory of Kripke-Platek set theory augmented by strong reflection principles (2010), disponible ici en PDF), qui introduit des systèmes de notations ordinales dont la seule définition s'étend sur un bon nombre de pages (notamment p. 13–30 pour le système principal, p. 68–70 pour une version simplifiée, p. 66–67 pour une version encore plus simplifiée équivalente à l'écrasement d'un cardinal Mahlo / ordinal Π₃-réfléchissant, et p. 100–113 pour un système encore plus riche). De ce que je sais, c'est le système de notations ordinales explicite le plus grand qui ait été introduit et rigoureusement analysé dans la littérature mathématique.

Il est cependant possible qu'on connaisse des systèmes de notations ordinales encore plus grands. Un certain Dmytro Taranovsky prétend avoir développé des systèmes de notations qui dépassent l'ordinal de preuve de l'arithmétique du second ordre et monte peut-être jusqu'à l'ordinal de preuve de ZFC. Il ne prétend pas avoir de preuve de ces affirmations, mais, même comme ça, j'avoue que je suis assez sceptique : pas tellement parce que l'auteur n'a ni fait de thèse de maths ni jamais rien publié formellement (je n'aime vraiment pas invoquer ce genre de critères, et en l'occurrence il ne vaut vraiment pas grand-chose parce qu'il est clair que l'auteur est au même passablement compétent dans ce qu'il écrit), mais surtout parce que je trouve très suspect de ne pas voir apparaître dans son système la complexité des hiérarchies d'écrasement qu'on voit dans celui de Stegert, et la facilité avec laquelle il prétend monter dans la hiérarchie preuve-théorique est quand même un peu incroyable. Mais je ne suis pas non plus complètement convaincu qu'il ait tort (au pif, je dirais que son système est bien-fondé, mais n'a pas la puissance qu'il croit qu'il a). De façon plus sérieuse, Toshiyasu Arai (新井(あらい)敏康(としやす)) a écrit tout un tas d'articles, dont beaucoup sont publiés, sur l'analyse ordinale de théories assez fortes : celui-ci, par exemple, construit un système de notations équivalent à un de ceux de Stegert et qui se prétend plus simple (je ne suis pas complètement convaincu par cette dernière partie, mais bon, je n'ai fait que survoler) ; je crois avoir vu de sa part quelque chose qui se prétendait encore plus fort, mais je ne retrouve plus de quoi il peut s'agir. Il y a aussi les patterns of resemblance de Timothy Carlson qui peuvent servir à définir des systèmes de notations ordinales, je crois comprendre que leur portée pourrait être très grande, mais je ne comprends pas ce qu'on sait exactement à leur sujet.

Ajout (2023-07-24) : On me signale cet article qui vient d'être posté sur arXiv et qui représente le travail de mathématiciens amateurs (« goglologistes ») pour développer et prouver la fondation d'un système de notations ordinales (Bashicu Matrix System) très puissant, dont il resterait alors à comparer la force aux autres évoqués ci-dessus.

Comment on peut tricher pour décrire de grands ordinaux de preuve

J'ai essayé de faire passer ci-dessus l'idée qu'on essaye de définir de grands ordinaux calculables pour mesurer la force de théories (qui se situent typiquement quelque part entre l'arithmétique de Peano du premier ordre PA et la théorie des ensembles ZFC) et qu'on ne sait pas monter trop haut dans cette hiérarchie (on n'atteint pas l'arithmétique de Peano du second ordre, et on est très loin de ZFC). Ces analyses ordinales permettent de mieux comprendre les théories, de réduire la question de leur correction arithmétique ou de leur consistance à la croyance en l'existence de certains ordinaux (grossièrement parlant, croire que ε₀ existe « revient au même » que croire que PA est consistante, et la même chose vaut pour ces analyses ordinales plus grandes).

Néanmoins, tout ceci présuppose que le système de notations soit raisonnablement « explicite », quelque chose qu'il n'est pas possible de formaliser. Si on ne fait pas une hypothèse de ce genre, il est tout à fait possible de décrire l'ordinal de preuve de ZFC (ou d'essentiellement ce qu'on voudra) de façon essentiellement triviale et qui n'apporte en gros aucune information sur ZFC :

Une notation ordinale est un triplet (p,e,x) où p est une preuve dans ZFC qu'une certaine machine de Turing e calcule un bon-ordre sur ℕ, et x est un entier naturel. On compare (p,e,x) à (p′,e′,x′) par l'ordre lexicographique sur les deux premières coordonnées (enfin, la première suffit, la seconde est déterminée par elle), ou, si elles sont égales, en comparant x et x′ par l'ordre défini par e.

Ce qui précède est bien une relation calculable : on peut tout à fait programmer une machine de Turing pour comparer des triplets (p,e,x) à (p′,e′,x′) dans l'ordre que je viens de dire, ce n'est pas spécialement difficile (il faut juste programmer un vérificateur de preuves dans ZFC). Sous des hypothèses plus fortes que ZFC, c'est un bon ordre sur les entiers naturels, et c'est alors presque tautologiquement un ordinal de preuve de ZFC. Comme il y a des variations sur la définition d'un ordinal de preuve, je dis un ordinal de preuve, et il peut y avoir des variations sur la construction, par exemple on peut mettre des bornes de complexité sur e ou diagonaliser autrement, ou imposer des contraintes sur la preuve de bon-ordre, mais en tout état de cause, il est clair que ZFC ne prouve pas que la relation ci-dessus est un bon-ordre alors qu'il prouve que c'est un bon ordre jusqu'à n'importe quel (p,e,x) donné, et l'extension de ZFC par l'ajout d'un cardinal inaccessible va prouver que ce qui précède est bien un bon ordre. (Voir ce vieux fil sur sci.math.research ou celui-ci sur MathOverflow pour des constructions essentiellement équivalentes.)

La construction ci-dessus n'a aucun intérêt (c'est essentiellement la même idée que ce que j'avais raconté ici pour calculer un grand entier naturel), mais elle illustre le fait qu'on ne peut pas vraiment formaliser ce qu'on fait en théorie de la démonstration (on veut décrire explicitement des ordinaux de preuve, mais ce que décrire explicitement signifie n'est pas si clair que ça), et il est délicat d'expliquer qu'on ne connaît pas l'ordinal de preuve de ZFC. Néanmoins, il est clair que cet ordinal est très difficile à « comprendre » parce que cela signifierait, d'une certaine manière, être capable de décrire tous les ordinaux que ZFC peut fabriquer (et de façon, on l'espère, plus explicite que ce qui précède).