Grand ordinal dénombrable

Une autre définition des ordinaux récursifs utilise les notations ordinales de Kleene. Schématiquement, une notation ordinale est soit le nom zéro (représentant l'ordinal 0), soit le successeur d'une notation ordinale (représentant le successeur de l'ordinal que cette notation décrit), soit une fonction calculable (ou la machine de Turing correspondante) qui produit en sortie une suite croissante de notations ordinales, l'ordinal décrit par cette suite étant la limite des ordinaux décrits par chaque notation. On définit un ordre (partiel) sur les notations tel que le successeur de o soit plus grand que o et que la limite soit plus grande que chaque terme de la suite. Cet ordre est calculable, mais l'ensemble O des notations ordinales n'est pas récursif, car il est impossible de décider si une machine de Turing donnée produit effectivement une suite infinie de notations (c'est une variante du problème de l'arrêt). Un ordinal récursif est alors un ordinal décrit par une notation ordinale.

Tout ordinal plus petit qu'un ordinal récursif est lui-même récursif, aussi l'ensemble des ordinaux récursifs est un ordinal dénombrable, l'ordinal de Church-Kleene. Bien qu'il soit tentant de négliger les notations ordinales, et de ne parler que des ordinaux récursifs eux-mêmes, cela peut créer de graves difficultés : même le plus petit ordinal infini, ω, possède de nombreuses notations, et il n'est pas toujours possible de montrer qu'elles sont équivalentes à la plus simple d'entre elles (la limite du programme énumérant les entiers dans l'ordre usuel).

Il existe une importante relation entre les ordinaux récursifs et certains systèmes formels (contenant l'arithmétique, c'est-à-dire un sous-ensemble suffisant des axiomes de Peano).

En effet, certains ordinaux récursifs sont si grands que bien qu'ils correspondent à une certaine notation ordinale o, un système formel donné peut ne pas être assez puissant pour démontrer que o est effectivement une notation ordinale : le système ne permet pas la récurrence transfinie jusqu'à o.

Ainsi, les axiomes de Peano (ou, pour être plus précis, la théorie du premier ordre qui leur est associée) ne permettent pas la récurrence transfinie jusqu'à ε₀ : bien que l'ordinal ε₀ puisse être aisément décrit dans l'arithmétique du premier ordre, les axiomes de Peano ne sont pas assez puissants pour montrer que c'est effectivement un ordinal ; en fait, la récurrence transfinie jusqu'à ε₀ permet de démontrer la cohérence des axiomes de Peano (c'est le théorème de cohérence de l'arithmétique de Gentzen (en)), ce qui montre que ce raisonnement ne saurait être formalisé dans l'arithmétique du premier ordre, d'après le théorème d'incomplétude de Gödel (ce résultat est à la base des théorèmes d'indécidabilité, dus à Kirby et Paris, concernant les suites de Goodstein). On dit que ε₀ mesure la force démonstrative (en) des axiomes de Peano.

On peut mesurer ainsi des systèmes bien plus puissants. Ainsi, la force démonstrative de la théorie des ensembles de Kripke-Platek est l'ordinal de Bachmann-Howard (en), et en fait, ajouter simplement aux axiomes de Peano des axiomes affirmant que tous les ordinaux inférieurs à l'ordinal de Bachmann-Howard sont effectivement bien ordonnés est suffisant pour obtenir toutes les conséquences arithmétiques de la théorie des ensembles de Kripke-Platek.

L'ordinal ε₀ est le plus petit ordinal satisfaisant l'équation ${\displaystyle \omega ^{\alpha }=\alpha }$ ; c'est la limite de la suite 0, 1, ${\displaystyle \omega }$, ${\displaystyle \omega ^{\omega }}$, ${\displaystyle \omega ^{\omega ^{\omega }}}$, etc. L'ordinal suivant satisfaisant cette équation est appelé ε₁ : c'est la limite de la suite ${\displaystyle \varepsilon _{0}+1,}$ ${\displaystyle \omega ^{\varepsilon _{0}+1}=\varepsilon _{0}\cdot \omega ,}$ ${\displaystyle \omega ^{\omega ^{\varepsilon _{0}+1}}=(\varepsilon _{0})^{\omega },}$ etc.

Plus généralement, le ${\displaystyle \iota }$-ème ordinal tel que ${\displaystyle \omega ^{\alpha }=\alpha }$ est appelé ${\displaystyle \varepsilon _{\iota }}$. On pourrait définir ${\displaystyle \zeta _{0}}$ comme le plus petit ordinal tel que ${\displaystyle \varepsilon _{\alpha }=\alpha }$ (c'est-à-dire la limite de la suite 0, ${\displaystyle \varepsilon _{0}}$, ${\displaystyle \varepsilon _{\varepsilon _{0}}}$, etc.), mais comme l'alphabet grec n'a pas un nombre infini de lettres, une notation plus robuste s'impose : on définit les ordinaux ${\displaystyle \varphi _{\gamma }(\beta )}$ par récurrence transfinie en posant ${\displaystyle \varphi _{0}(\beta )=\omega ^{\beta }}$ et ${\displaystyle \varphi _{\gamma +1}(\beta )}$ est alors le ${\displaystyle \beta }$-ème point fixe de ${\displaystyle \varphi _{\gamma }}$ (c'est-à-dire le ${\displaystyle \beta }$-ème ordinal tel que ${\displaystyle \varphi _{\gamma }(\alpha )=\alpha }$ ; ainsi, par exemple, ${\displaystyle \varphi _{1}(\beta )=\varepsilon _{\beta }}$), et si ${\displaystyle \delta }$ est un ordinal limite, on appelle ${\displaystyle \varphi _{\delta }(\alpha )}$ le ${\displaystyle \alpha }$-ème point fixe commun de tous les ${\displaystyle \varphi _{\gamma }}$ pour tous les ${\displaystyle \gamma <\delta }$. Cette famille de fonctions est connue sous le nom de hiérarchie de Veblen ; ${\displaystyle \varphi _{\gamma }}$ est appelée la ${\displaystyle \gamma }$-ème fonction de Veblen.

On a le bon ordre : ${\displaystyle \varphi _{\alpha }(\beta )<\varphi _{\gamma }(\delta )}$ si et seulement si (${\displaystyle \alpha =\gamma }$ et ${\displaystyle \beta <\delta }$) ou (${\displaystyle \alpha <\gamma }$ et ${\displaystyle \beta <\varphi _{\gamma }(\delta )}$) ou (${\displaystyle \alpha >\gamma }$ et ${\displaystyle \varphi _{\alpha }(\beta )<\delta }$).

Le plus petit ordinal tel que ${\displaystyle \varphi _{\alpha }(0)=\alpha }$ s'appelle l'ordinal de Feferman-Schütte, et se note généralement ${\displaystyle \Gamma _{0}}$. On peut le décrire comme l'ensemble de tous les ordinaux qui peuvent s'écrire à l'aide d'expressions finies, utilisant uniquement 0, la hiérarchie de Veblen, et l'addition. L'ordinal de Feferman-Schütte est important parce que, en un sens assez difficile à rendre précis, c'est le plus petit ordinal qui ne peut être décrit prédicativement à l'aide des ordinaux plus petits. Il mesure la force de systèmes tels que celui de la récurrence transfinie arithmétique (en). Plus généralement, Γ_α est le α-ème ordinal qui ne peut être obtenu à partir des ordinaux précédents et de la hiérarchie de Veblen.

Il est bien sûr possible de décrire des ordinaux au-delà de l'ordinal de Feferman-Schütte. Ainsi, on peut continuer à énumérer des points fixes par des schémas de plus en plus complexes : ceux de ${\displaystyle \alpha \mapsto \Gamma _{\alpha }}$ (le premier de ceux-ci est l'ordinal d'Ackermann (en)), puis les points fixes de cette fonction-là, et ainsi de suite, puis le premier ordinal α tel que α est obtenu après α étapes de ce procédé, puis continuer à « diagonaliser » par des méthodes analogues. Ceci amène finalement à la définition des ordinaux de Veblen (en)[1].

Pour aller bien au-delà de l'ordinal de Feferman-Schütte, et même des ordinaux de Veblen, il est nécessaire d'introduire de nouvelles méthodes. Il n'existe malheureusement encore aucune standardisation de ces méthodes : chaque auteur s'étant intéressé à cette question semble avoir inventé son propre système de notation, et il est souvent difficile d'établir une correspondance entre ces différents systèmes. La première de ces notations fut introduite par Bachmann en 1950 (d'une manière assez artificielle), et diverses extensions et variations en furent décrites par Buchholz, Takeuti (les diagrammes ordinaux), Feferman (les systèmes θ), Aczel, Bridge, Schütte et Pohlers. Cependant, la plupart de ces systèmes de notations utilisent la même idée fondamentale consistant à construire de nouveaux ordinaux dénombrables à l'aide de certains ordinaux non dénombrables. Voici l'une de ces constructions (décrite avec beaucoup plus de détails dans l'article fonction d'effondrement ordinale) :

• ψ(α) est défini comme le plus petit ordinal ne pouvant être construit à l'aide de 0, 1, ω et Ω (où Ω = ω₁ est le premier ordinal non dénombrable), de l'addition, de la multiplication et de l'exponentiation, et de ψ appliqué à des ordinaux déjà construits, et inférieurs à α[2].

Le rôle de Ω est d'empêcher la fonction ψ de rester « bloquée » au plus petit ordinal σ tel que ε_σ = σ : de fait, ψ(α) = σ pour tous les ordinaux α tels que σ ≤ α ≤ Ω (ce n'est pas tout à fait clair au vu de la définition ci-dessus, mais, bien que ψ(σ) = σ, on ne peut utiliser σ dans le calcul de ψ(σ+1), car il n'est pas encore « construit »). Mais inclure Ω permet de dépasser ce point: ψ(Ω+1) est supérieur à σ. Dans ce contexte, la propriété essentielle de Ω est d'être plus grand que tout ordinal construit par ψ. Cette définition est imprédicative, parce qu'elle utilise l'ordinal non dénombrable Ω, ce qui, en un certain sens, revient déjà à utiliser tous les ordinaux dénombrables qu'on est en train de construire. De même, l'opérateur « plus petit point fixe » utilisé dans la hiérarchie de Veblen peut être considéré comme non prédicatif[3].

La construction précédente finit, à son tour, par rester définitivement bloquée : on ne peut dépasser l'ordinal limite de la suite ${\displaystyle \psi (\Omega )}$, ${\displaystyle \psi (\Omega ^{\Omega })}$, ${\displaystyle \psi (\Omega ^{\Omega ^{\Omega }})}$, etc., qui est donc ${\displaystyle \psi (\varepsilon _{\Omega +1})}$ ; c'est l'ordinal de Bachmann-Howard (en). Pour construire des ordinaux plus grands, il est possible, et de plusieurs manières, d'adjoindre à la définition de la fonction ψ de nouveaux ordinaux non dénombrables, ou de nouvelles méthodes de construction d'ordinaux ; certaines de ces constructions sont détaillées dans l'article fonction d'effondrement ordinale.

L'ordinal de Bachmann-Howard, ψ(ε_Ω+1), joue un rôle important, parce qu'il décrit la force démonstrative de la théorie des ensembles de Kripke-Platek. De fait, l'importance de ces grands ordinaux, et l'intérêt de les décrire précisément, vient de leur relation avec certains systèmes formels ; cependant, des systèmes aussi puissants que l'arithmétique du second ordre, sans même parler de la théorie des ensembles de Zermelo-Fraenkel, semblent hors de portée pour le moment.

Si l'on ne réclame pas de description véritablement explicite, il est possible de définir des ordinaux récursifs encore beaucoup plus grands, en les caractérisant comme les ordinaux mesurant la force démonstrative de diverses théories puissantes ; on peut en gros voir ces ordinaux comme les plus petits que ces théories ne peuvent démontrer être bien ordonnés. En prenant des théories de plus en plus fortes, comme l'arithmétique du second ordre, la théorie des ensembles de Zermelo, ou ZFC augmentée d'un des axiomes de grand cardinal, on peut atteindre des ordinaux extrêmement grands. Mais, à proprement parler, il n'est pas clair qu'on ait encore affaire à des ordinaux : par construction, ceci n'est démontrable qu'à l'aide d'une théorie encore plus puissante ; dans le dernier cas mentionné, il n'est nullement évident qu'on puisse en construire une qui soit admise[4] par la majorité des mathématiciens.

L'ensemble des ordinaux récursifs est lui-même un ordinal, le plus petit qui ne puisse être décrit de manière récursive (autrement dit, ce n'est le type d'ordre d'aucun bon ordre sur les entiers reconnaissable par machine de Turing). Cet ordinal est dénombrable ; on l'appelle l’ordinal de Church–Kleene, et on le note ${\displaystyle \omega _{1}^{\mathrm {CK} }}$. Ainsi, aucun ordinal à partir de ${\displaystyle \omega _{1}^{\mathrm {CK} }}$ ne peut être réellement « décrit », mais seulement, dans le meilleur des cas, défini comme ayant telle ou telle propriété caractéristique. ${\displaystyle \omega _{1}^{\mathrm {CK} }}$ étant dénombrable, il est évidemment bien plus petit que le premier ordinal non dénombrable, ${\displaystyle \omega _{1}}$. Cependant, comme la notation le suggère, il se comporte à certains égards comme ${\displaystyle \omega _{1}}$ (ainsi, par exemple, toute suite récursive croissante d'ordinaux inférieurs à ${\displaystyle \omega _{1}^{\mathrm {CK} }}$ est stationnaire).

L'ordinal de Church-Kleene est lui aussi lié à KP, la théorie des ensembles de Kripke-Platek, mais en un sens différent : là où l'ordinal de Bachmann-Howard (décrit précédemment) était le plus petit ordinal pour lequel KP ne démontre pas la validité de la récurrence transfinie, l'ordinal de Church-Kleene est le plus petit α tel que la construction de l'univers de Gödel, L, jusqu'à l'étape α, fournit un modèle ${\displaystyle L_{\alpha }}$ de KP. Les ordinaux ayant cette propriété sont dits admissibles ; ainsi ${\displaystyle \omega _{1}^{\mathrm {CK} }}$ est le plus petit ordinal admissible.

Un théorème de Gerald Sacks montre que les ordinaux admissibles dénombrables sont exactement ceux correspondants à la construction de l'ordinal de Church-Kleene, mais en autorisant des machines de Turing avec oracles. On note parfois ${\displaystyle \omega _{\alpha }^{\mathrm {CK} }}$ le ${\displaystyle \alpha }$-ème ordinal qui soit admissible ou limite d'ordinaux admissibles.

Un ordinal ${\displaystyle \alpha }$ qui est à la fois admissible et limite d'ordinaux admissibles, ce qui revient à dire que ${\displaystyle \alpha }$ est le ${\displaystyle \alpha }$-ème ordinal admissible, est dit récursivement inaccessible. Il existe une théorie des grands ordinaux de ce type qui est tout à fait analogue à celle des premiers grands cardinaux. Ainsi, on peut définir des ordinaux récursivement Mahlo (voir cardinal Mahlo (en)) : ce sont les ${\displaystyle \alpha }$ tel que tout sous-ensemble non borné de ${\displaystyle \alpha }$, ${\displaystyle \alpha }$-récursivement fermé contienne un ordinal admissible. Mais les ordinaux définis de cette manière peuvent encore parfaitement être dénombrables, et, alors que l'existence de cardinaux inaccessibles ne peut être démontrée dans ZFC, celle d'ordinaux dénombrables récursivement inaccessibles ou récursivement Mahlo est un théorème de ZFC ; en revanche, ils sont hors de portée de la théorie de Kripke-Platek.

Un ordinal admissible ${\displaystyle \alpha }$ est dit non-projectif s'il n'y a pas d'application injective et ${\displaystyle \alpha }$-récursive envoyant ${\displaystyle \alpha }$ sur un ordinal plus petit (cette définition est automatiquement vérifiée pour les cardinaux réguliers[5], mais nous nous intéressons ici essentiellement au cas des ordinaux dénombrables). La non-projectivité est une condition bien plus forte que les précédentes ; elle est équivalente à dire que l'univers de Gödel construit jusqu'à l'étape α, donne un modèle ${\displaystyle L_{\alpha }}$ de KP + l'axiome de séparation pour les propositions de type ${\displaystyle \Sigma _{1}}$.

On peut imaginer des ordinaux encore plus grands, et toujours dénombrables. Ainsi, si ZFC possède un modèle transitif (en) (hypothèse un peu plus forte que la seule hypothèse de cohérence, et impliquée par l'existence d'un cardinal inaccessible), il existe un ${\displaystyle \alpha }$ dénombrable tel que ${\displaystyle L_{\alpha }}$ est un modèle de ZFC. De tels ordinaux sont « au-delà » de ZFC, au sens où ZFC ne peut (par construction) prouver leur existence.

• (en) Wolfram Pohlers, Proof theory, Springer 1989 (ISBN 0-387-51842-8) (hiérarchie de Veblen, et quelques ordinaux imprédicatifs). C'est probablement l'ouvrage le plus lisible sur la question (ou peut-être faudrait-il dire le moins illisible)
• (en) Gaisi Takeuti, Proof theory, 2nd edition 1987 (ISBN 0-444-10492-5) (diagrammes ordinaux)
• (en) Kurt Schütte, Proof theory, Springer 1977 (ISBN 0-387-07911-4) (hiérarchie de Veblen, et quelques ordinaux imprédicatifs)
• (en) Craig Smorynski, The varieties of arboreal experience Math. Intelligencer 4 (1982), no. 4, 182-189; (contient une description informelle de la hiérarchie de Veblen)
• (en) Hartley Rogers, Jr. (en), Theory of Recursive Functions and Effective Computability McGraw-Hill (1967) (ISBN 0-262-68052-1) (description des ordinaux récursifs et de l'ordinal de Church–Kleene)
• (en) Larry W. Miller, Normal Functions and Constructive Ordinal Notations, The Journal of Symbolic Logic, volume 41, n°2, juin 1976, pages 439 à 459
• (en) Hilbert Levitz, Transfinite Ordinals and Their Notations: For The Uninitiated, article introductif (8 pages, en PostScript)
• (en) Herman Ruge Jervell, Truth and provability [PDF], texte en ligne en cours d'écriture.

• (en) Jon Barwise, Admissible Sets and Structures : an Approach to Definability Theory, Berlin/Heidelberg/New York, Springer-Verlag, 1976, 394 p. (ISBN 3-540-07451-1)
• (en) Peter G. Hinman, Recursion-theoretic hierarchies, Springer-Verlag, 1978

• (en) Michael Rathjen, "The realm of ordinal analysis." dans S. Cooper et J. Truss (éds.): Sets and Proofs. (Cambridge University Press, 1999) 219-279. En ligne : (fichier Postscript).