En mathématiques, et plus particulièrement en théorie des ensembles, il existe de nombreuses méthodes de description des ordinaux dénombrables. Les plus petits (jusqu'à ε0) peuvent être exprimés (de façon utile et non circulaire) à l'aide de leur forme normale de Cantor. Au-delà, on parle de grands ordinaux dénombrables ; de nombreux grands ordinaux (le plus souvent en rapport avec la théorie de la démonstration) possèdent des notations ordinales calculables. Cependant, il n'est pas possible en général de décider si une notation ordinale potentielle en est effectivement une, pour des raisons analogues à celles rendant insoluble le problème de l'arrêt.
Comme il ne peut exister qu'un nombre dénombrable de notations, l'ensemble des ordinaux qui en admettent une se termine bien avant le premier ordinal non dénombrable ω1 ; la borne supérieure de cet ensemble s'appelle l'ordinal ω1 de Church–Kleene, noté ω1CK (cet ordinal est dénombrable, et ne doit pas être confondu avec ω1). Les ordinaux inférieurs à ω1CK sont les ordinaux récursifs. Il est possible de définir des ordinaux supérieurs, mais ils ne possèderont pas de notations.
L'étude des ordinaux dénombrables non récursifs est délicate, la difficulté principale venant de ce qu'on ne sait pas, en général, comparer deux grands ordinaux définis par des méthodes différentes, et parfois même, qu'on ne sait pas démontrer qu'un ordre donné est un bon ordre.
Généralités sur les ordinaux récursifs Les ordinaux récursifs (ou calculables) sont les ordinaux dénombrables qu'on peut représenter par une fonction calculable. On peut en donner plusieurs définitions rigoureuses équivalentes ; la plus simple consiste à dire qu'un ordinal est récursif s'il est le type d'ordre d'un bon ordre calculable sur les entiers, c'est-à-dire qu'il existe une machine de Turing qui, ayant pour entrée deux entiers, décide lequel est le plus petit pour cet ordre. Notations ordinales 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).
Relations avec des théories arithmétiques 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'à ε0 : bien que l'ordinal ε0 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'à ε0 permet de démontrer la cohérence des axiomes de Peano (c'est le ), 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 ε0 mesure la 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', 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.
Ordinaux récursifs particuliers Définitions prédicatives et hiérarchie de Veblen
L'ordinal ε0 est le plus petit ordinal satisfaisant l'équation ; c'est la limite de la suite 0, 1, , , , etc. L'ordinal suivant satisfaisant cette équation est appelé ε1 : c'est la limite de la suite etc.
Plus généralement, le -ème ordinal tel que est appelé . On pourrait définir comme le plus petit ordinal tel que (c'est-à-dire la limite de la suite 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 par récurrence transfinie en posant et est alors le -ème point fixe de (c'est-à-dire le -ème ordinal tel que ; ainsi, par exemple, ), et si est un ordinal limite, on appelle le -ème point fixe commun de tous les pour tous les . Cette famille de fonctions est connue sous le nom de hiérarchie de Veblen ; est appelée la -ème fonction de Veblen.
On a le bon ordre : si et seulement si ( et ) ou ( et ) ou ( et ).
L'ordinal de Feferman–Schütte et les ordinaux supérieurs Le plus petit ordinal tel que s'appelle l'ordinal de Feferman-Schütte, et se note généralement . 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 . 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 (le premier de ceux-ci est l'), 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 On trouvera une description constructive du petit ordinal de Veblen, sous forme d'un bon ordre explicite entre arbres finis, dans cet article de H. R. Jervell , et une illustration plus complète de cette correspondance entre arbres et ordinaux dans ce document dû à David Madore..
Ordinaux imprédicatifs 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ù Ω = ω1 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 à α Plus rigoureusement, on définit par récurrence transfinie sur α ordinal et n entier des ensembles , union des pour tous les n entiers, et ψ(α) le plus petit ordinal non dans , en posant et .. 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 Nik Weaver, « »..
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 , , , etc., qui est donc ; c'est l'. 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.
Ordinaux récursifs dont on ne peut prouver la récursivité