Fonction d'effondrement ordinale

En logique mathématique et en théorie des ensembles, une fonction d'effondrement ordinale (en anglais, ordinal collapsing function) est une méthode de définition de notations pour certains grands ordinaux dénombrables, consistant à donner des noms à certains ordinaux beaucoup plus grands que ceux que l'on veut noter, puis à les « effondrer » pour obtenir le système de notations cherché.

Un exemple atteignant l'ordinal de Bachmann-Howard

La construction de la fonction d'effondrement de cet exemple est inspiré de celle de Buchholz, mais se limite à un seul cardinal pour simplifier l'exposé.

Définition

Soit $\Omega$ le plus petit ordinal non dénombrable (généralement noté $\omega _{1}$). On définit une fonction $\psi$ (qui sera non décroissante et continue) envoyant n'importe quel ordinal $\alpha$ vers un ordinal dénombrable $\psi (\alpha )$, par récurrence transfinie sur $\alpha$, de la manière suivante : supposons que $\psi (\beta )$ ait été défini pour tous les $\beta <\alpha$. Soit $C(\alpha )$ l'ensemble des ordinaux engendrés (récursivement) à partir de $0$, $1$, $\omega$ et $\Omega$, de l'addition, la multiplication et l'exponentiation ordinale, et de la fonction $\psi \upharpoonright _{\alpha }$, c'est-à-dire de la restriction de $\psi$ aux ordinaux $\beta <\alpha$ (plus rigoureusement, on pose $C(\alpha )_{0}=\{0,1,\omega ,\Omega \}$ et$C(\alpha )_{n+1}=C(\alpha )_{n}\cup \{\beta _{1}+\beta _{2},\beta _{1}\beta _{2},{\beta _{1}}^{\beta _{2}}:\beta _{1},\beta _{2}\in C(\alpha )_{n}\}\cup \{\psi (\beta ):\beta \in C(\alpha )_{n}\land \beta <\alpha \}$ pour tout $n$ ; $C(\alpha )$ est la réunion de tous les $C(\alpha )_{n}$). $\psi (\alpha )$ est alors défini comme le plus petit ordinal n'appartenant pas à $C(\alpha )$.

Intuitivement, la motivation de cette construction est que les opérations usuelles ne permettant pas d'aller très loin, dès qu'on rencontre un nouvel ordinal (comme limite de ceux déjà construits), plutôt que d'inventer un nouveau nom ad hoc, on le prend parmi des ordinaux bien au-delà de ceux qui nous intéressent (au-delà de $\Omega$, donc) ; on donne ainsi des noms à des ordinaux non dénombrables, et la liste de ces ordinaux étant nécessairement dénombrable, $\psi$ les « effondrera » vers des ordinaux dénombrables.

Calcul de valeurs de 𝜓

Pour montrer comment $\psi$ produit des notations pour de grands ordinaux dénombrables, on va calculer ses premières valeurs.

Début prédicatif

Par construction, $C(0)$ contient les ordinaux $0$, $1$, $2$, $3$, $\omega$, $\omega +1$, $\omega +2$, $\omega 2$, $\omega 3$, $\omega ^{2}$, $\omega ^{3}$, $\omega ^{\omega }$, $\omega ^{\omega ^{\omega }}$ , etc., ainsi que les ordinaux $\Omega$, $\Omega +1$, $\Omega \omega$, $\Omega ^{\Omega }$. Le premier ordinal qu'il ne contient pas est $\varepsilon _{0}$ (la limite de $\omega$, $\omega ^{\omega }$, $\omega ^{\omega ^{\omega }}$, etc., inférieur à $\Omega$ par hypothèse). La borne supérieure de $C(0)$ est $\varepsilon _{\Omega +1}$ (la limite de $\Omega$, $\Omega ^{\Omega }$, $\Omega ^{\Omega ^{\Omega }}$ , etc.), mais cela n'intervient pas dans la suite. Ainsi, $\psi (0)=\varepsilon _{0}$.

De même, $C(1)$ contient les ordinaux qu'on peut former à partir de $0$, $1$, $\omega$, $\Omega$ ainsi à présent que $\varepsilon _{0}$, ce qui permet de construire tous les ordinaux jusqu'à $\varepsilon _{1}$ (mais pas ce dernier) et donc $\psi (1)=\varepsilon _{1}$. Par récurrence transfinie sur $\alpha$, on démontre que $\psi (\alpha )=\varepsilon _{\alpha }$ ; cette démonstration ne fonctionnant que tant que $\alpha <\varepsilon _{\alpha }$. Ainsi :

$\psi (\alpha )=\varepsilon _{\alpha }=\phi _{1}(\alpha )$ pour tous les $\alpha \leq \zeta _{0}$, où $\zeta _{0}=\phi _{2}(0)$ est le plus petit point fixe de $\alpha \mapsto \varepsilon _{\alpha }$ (ici, les $\phi$ sont les fonctions de Veblen définies en partant de $\phi _{1}(\alpha )=\varepsilon _{\alpha }$).

Ainsi $\psi (\zeta _{0})=\zeta _{0}$, mais $\psi (\zeta _{0}+1)$ n'est pas plus grand, puisqu'on ne peut pas construire $\zeta _{0}$ par un nombre fini d'itérations de $\phi _{1}\colon \alpha \mapsto \varepsilon _{\alpha }$ et donc $\zeta _{0}$ n'appartient à aucun ensemble $C(\alpha )$ pour $\alpha \leq \Omega$ ; la fonction $\psi$ est donc longtemps « bloquée » à $\zeta _{0}$ : $\psi (\alpha )=\zeta _{0}$ pour tous les $\alpha$ tels que $\zeta _{0}\leq \alpha \leq \Omega$.

Premières valeurs non prédicatives

On continue à avoir $\psi (\Omega )=\zeta _{0}$. Mais pour le calcul de $\psi (\Omega +1)$, quelque chose a changé : $\Omega$ ayant été (artificiellement) inclus dans tous les $C(\alpha )$, les règles permettent d'utiliser la valeur $\psi (\Omega )=\zeta _{0}$. Ainsi, $C(\Omega +1)$ contient tous les ordinaux qu'on peut construire à partir de $0$, $1$, $\omega$, $\Omega ,$ la fonction $\phi _{1}\colon \alpha \mapsto \varepsilon _{\alpha }$ jusqu'à $\zeta _{0}$ et cette fois également $\zeta _{0}$. Le plus petit ordinal qu'on ne peut construire ainsi est $\varepsilon _{\zeta _{0}+1}$ (le premier $\varepsilon$-ordinal après $\zeta _{0}$).

La définition $\psi (\Omega )=\zeta _{0}$, et les valeurs suivantes de $\psi$ telles que $\psi (\Omega +1)=\varepsilon _{\zeta _{0}+1}$ sont dites imprédicatives parce qu'elles utilisent des ordinaux (ici, $\Omega$) supérieurs à ceux qu'on veut définir (ici, $\zeta _{0}$).

Valeurs de 𝜓 jusqu'à l'ordinal de Feferman-Schütte

Le fait que $\psi (\Omega +\alpha )=\varepsilon _{\zeta _{0}+\alpha }$ reste vrai pour tous les $\alpha \leq \zeta _{1}=\phi _{2}(1)$ (en particulier $\psi (\Omega +\zeta _{0})=\varepsilon _{\zeta _{0}2}$, mais maintenant que $\zeta _{0}$ est construit, rien n'empêche de continuer au delà). cependant, à $\zeta _{1}=\phi _{2}(1)$ (le premier point fixe de $\alpha \mapsto \varepsilon _{\alpha }$ après $\zeta _{0}$), la construction est à nouveau bloquée, car $\zeta _{1}$ ne peut être obtenu à partir de $\zeta _{0}$ (et des ordinaux plus petits) par un nombre fini d'application de la fonction $\varepsilon$. On voit ainsi comme précédemment que $\psi (\Omega 2)=\zeta _{1}$.

Le même raisonnement montre que $\psi (\Omega (1+\alpha ))=\phi _{2}(\alpha )$ pour tous les $\alpha \leq \phi _{3}(0)$ (où $\phi _{2}$ énumère les points fixes de $\phi _{1}\colon \alpha \mapsto \varepsilon _{\alpha }$ et$\phi _{3}(0)$ est le premier point fixe de $\phi _{2}$). On obtient ainsi$\psi (\Omega ^{2})=\phi _{3}(0)$.

On voit de même que $\psi (\Omega ^{\alpha })=\phi _{1+\alpha }(0)$ tant que $\alpha$ est plus petit que le premier point fixe $\Gamma _{0}$ de $\alpha \mapsto \phi _{\alpha }(0)$, lequel est l'ordinal de Feferman-Schütte. Ainsi, $\psi (\Omega ^{\Omega })=\Gamma _{0}.$

Au-delà de l'ordinal de Feferman-Schütte

On a $\psi (\Omega ^{\Omega }+\Omega ^{\alpha })=\phi _{\Gamma _{0}+\alpha }(0)$pour tous les $\alpha \leq \Gamma _{1}$, où $\Gamma _{1}$ est le prochain point fixe de $\alpha \mapsto \phi _{\alpha }(0)$. Utilisant la fonction $\alpha \mapsto \Gamma _{\alpha }$ qui énumère ces points fixes (et qu'on peut également noter $\phi (1,0,\alpha )$ à l'aide des fonctions de Veblen à plusieurs variables), on a $\psi (\Omega ^{\Omega }(1+\alpha ))=\Gamma _{\alpha }$, jusqu'au premier point fixe $\phi (1,1,0)$ de la fonction $\alpha \mapsto \Gamma _{\alpha }$ elle-même, qui sera $\psi (\Omega ^{\Omega +1})$ (et le premier point fixe $\phi (2,0,0)$ des fonctions $\alpha \mapsto \phi (1,\alpha ,0)$ sera $\psi (\Omega ^{\Omega 2})$). Continuant ainsi :

• $\psi (\Omega ^{\Omega ^{2}})$ est l'ordinal d'Ackermann (en) (la limite des ordinaux de la forme $\phi (\alpha ,\beta ,\gamma )$),
• $\psi (\Omega ^{\Omega ^{\omega }})$ est le petit ordinal de Veblen (en) (la limite des ordinaux de la forme $\phi (\ldots )$ avec un nombre fini de variables),
• $\psi (\Omega ^{\Omega ^{\Omega }})$ est le grand ordinal de Veblen (en) (la limite des ordinaux de la forme $\phi (\ldots )$ avec un nombre transfini (mais de la même forme) de variables),
• la limite $\psi (\varepsilon _{\Omega +1})$ de $\psi (\Omega )$, $\psi (\Omega ^{\Omega })$, $\psi (\Omega ^{\Omega ^{\Omega }})$, etc., est l'ordinal de Bachmann-Howard (en). Ensuite, la fonction $\psi$ est constante, et il est impossible d'aller plus loin avec cette construction.

Notations jusqu'à l'ordinal de Bachmann-Howard

Généralisant la forme normale de Cantor, la fonction $\psi$ permet de définir des notations «  canoniques » pour tous les ordinaux jusqu'à l'ordinal de Bachmann-Howard.

Bases de représentation

Si $\delta$ est un ordinal qui est une puissance de $\omega$ (par exemple $\omega$ lui-même, ou $\varepsilon _{0}$, ou $\Omega$), tout ordinal $\alpha$ (non nul) possède une représentation unique de la forme $\delta ^{\beta _{1}}\gamma _{1}+\ldots +\delta ^{\beta _{k}}\gamma _{k}$, où $k$ est un entier, $\gamma _{1},\ldots ,\gamma _{k}$ sont des ordinaux non nuls strictement inférieurs à $\delta$, et $\beta _{1}>\beta _{2}>\cdots >\beta _{k}$ sont des ordinaux ($\beta _{k}$ pouvant être nul). Cette « représentation en base $\delta$ » généralise la forme normale de Cantor (qui correspond au cas $\delta =\omega$). Il est possible que cette forme n'apporte rien, lorsque $\alpha =\delta ^{\alpha }$, mais dans tous les autres cas, les $\beta _{i}$ sont tous inférieurs à $\alpha$ ; cette représentation est également triviale lorsque $\alpha <\delta$, auquel cas $k\leq 1$ et $\gamma _{1}=\alpha$.

Si $\alpha$ est un ordinal inférieur à $\varepsilon _{\Omega +1}$, sa représentation en base $\Omega$ a des coefficients $\gamma _{i}<\Omega$ (par définition) et des exposants $\beta _{i}<\alpha$ (puisque $\alpha <\varepsilon _{\Omega +1}$) ; on peut donc réécrire ces exposants en base $\Omega$ et répéter cette opération jusqu'à l'arrêt de l'algorithme (toute suite décroissante d'ordinaux étant finie). L'expression correspondante est appelée représentation itérée de $\alpha$ en base $\Omega$ aet les différents coefficients apparaissant (y compris en tant qu'exposants) les morceaux de la représentation (tous $<\Omega$), ou, pour abréger, les $\Omega$-morceaux de $\alpha$.

Propriétés de 𝜓

• La fonction $\psi$ est non-décroissante et continue.
• Si $\psi (\alpha )=\psi (\beta )$ avec $\beta <\alpha$, alors $C(\alpha )=C(\beta )$. En fait, aucun ordinal $\beta '$ avec $\beta \leq \beta '<\alpha$ ne peut appartenir à $C(\alpha )$.
• Toute valeur $\gamma =\psi (\alpha )$ prise par $\psi$ est un $\varepsilon$-ordinal (c'est-à-dire un point fixe de $\beta \mapsto \omega ^{\beta }$).
• Soit $\delta$ un $\varepsilon$-ordinal et $\alpha$ un ordinal tel que $\psi (\beta )<\delta$ pour tout $\beta <\alpha$ ; alors les $\Omega$-morceaux de tout élément de $C(\alpha )$ sont inférieurs à $\delta$. De plus, $\psi (\alpha )\leq \delta$ (et $\delta \not \in C(\alpha )$).
• Tout $\varepsilon$-ordinal inférieur à un élément de l'image de $\psi$ est lui-même dans l'image de $\psi$.
• Si $\psi (\alpha )=\delta$, l'ensemble $C(\alpha )$ est formé des ordinaux $\gamma$ (inférieurs à $\varepsilon _{\Omega +1}$) dont les $\Omega$-morceaux sont inférieurs à $\delta$.

Notations ordinales jusqu'à l'ordinal de Bachmann-Howard

Les résultats précédents permettent de définir une notation ordinale canonique pour tout ordinal $\gamma$ inférieur à l'ordinal de Bachmann-Howard, par récurrence transfinie sur $\gamma$.

Si $\gamma$ est inférieur à $\varepsilon _{0}$, on prend pour notation de $\gamma$ la forme normale de Cantor (itérée pour les exposants). Sinon, il existe un plus grand $\varepsilon$-ordinal $\delta$ inférieur ou égal à $\gamma$ (parce que l'ensemble des $\varepsilon$-ordinaux est fermé); si $\delta <\gamma$, par hypothèse de récurrence une notation a été définie pour $\delta$ et dont la représentation de $\gamma$ en base $\delta$ est une notation de $\gamma$.

Le seul cas restant est celui où $\gamma =\delta$ est un $\varepsilon$-ordinal :dans ce cas, on peut écrire $\delta =\psi (\alpha )$ pour un certain ordinal $\alpha <\varepsilon _{\Omega +1}$ (éventuellement non dénombrable) ; soit $\alpha$ le plus grand ordinal ayant cette propriété (il existe, puisque $\psi$ est continue). On utilise la représentation (itérée) en base $\Omega$ de $\alpha$ ; il ne reste qu'à montrer que chaque morceau de cette représentation est inférieur à $\delta$ (et donc a déjà une représentation). Si ce n'était pas le cas, $C(\alpha )$ ne contiendrait pas $\alpha$ et alors on aurait $C(\alpha +1)=C(\alpha )$ (ils sont fermés pour les mêmes opérations, la valeur de $\psi$ à $\alpha$ ne pouvant pas être utilisée), et donc on aurait $\psi (\alpha +1)=\psi (\alpha )=\delta$, contredisant la maximalité de $\alpha$.

Ces notations canoniques sont définies également pour certains ordinaux non dénombrables, ceux dont les $\Omega$-morceaux sont inférieurs à l'ordinal de Bachmann-Howard ; cette notation est utilisée pour les arguments (éventuellement non dénombrables) de la fonction $\psi$.

Exemples

Pour les ordinaux inférieurs à $\varepsilon _{0}=\psi (0)$, cette notation canonique coïncide par définition avec la forme normale de Cantor

Pour les ordinaux inférieurs à $\varepsilon _{1}=\psi (1)$, la notation coïncide avec la représentation (itérée) en base $\varepsilon _{0}$ notation, ainsi $\omega ^{\omega ^{\varepsilon _{0}+\omega }}$ sera écrit ${\varepsilon _{0}}^{\omega ^{\omega }}$, ou plus rigoureusement $\psi (0)^{\omega ^{\omega }}$.

De même, pour les ordinaux inférieurs à $\varepsilon _{2}=\psi (2)$, on utilise la représentation en base $\varepsilon _{1}$ les morceaux étant écrits en base $\varepsilon _{0}$ (et les morceaux de cela étant écrit en forme normale de Cantor), ainsi $\omega ^{\omega ^{\varepsilon _{1}+\varepsilon _{0}+1}}$ est noté ${\varepsilon _{1}}^{\varepsilon _{0}\omega }$, ou plus précisément $\psi (1)^{\psi (0)\,\omega }$. Jusqu'à $\zeta _{0}=\psi (\Omega )$, on utilise ainsi comme base le plus grand $\varepsilon$-ordinal donnant une représentation non triviale.

Au delà, on doit utiliser des ordinaux plus grands que $\Omega$ ; on les représente toujours en base $\Omega$ (itérée), les morceaux eux-mêmes, sont notés comme précédemment (avec comme base le plus grand $\varepsilon$-ordinal possible).

Bien que $\psi (\varepsilon _{\Omega +1})$ soit égal à l'ordinal de Bachmann–Howard, ce n'en est pas une notation canonique en ce sens ; celles-ci ne sont définies que pour les ordinaux plus petits.

Conditions de canonicité

Ce système de notations a la propriété de décroissance des arguments des fonctions $\psi$ emboîtées (c'est-à-dire que les arguments d'une fonction $\psi$ «  intérieure » sont toujours plus petits que ceux d'une fonction $\psi$ qui l'appelle) ; ceci est une conséquence de ce que les $\Omega$-morceaux de $\alpha$, où $\alpha$ est le plus grand possible tel que $\psi (\alpha )=\delta$ pour un certain $\varepsilon$-ordinal $\delta$, sont tous inférieurs à $\delta$. Par exemple, $\psi (\psi (\Omega )+1)$ n'est pas une notation ; c'est une expression bien formée, égale à $\psi (\Omega )=\zeta _{0}$ puisque $\psi$ est constante entre $\zeta _{0}$ et $\Omega$, mais elle n'est pas produite par l'algorithme récursif qui vient d'être décrit.

La canonicité peut être vérifiée syntaxiquement par récurrence : une expression est canonique isi et seulement si c'est la forme normale de Cantor (itérée) d'un ordinal inférieur à $\varepsilon _{0}$, ou une représentation (itérée) en base $\delta$ dont tous les morceaux sont canoniques pour un $\delta$ de la forme $\delta =\psi (\alpha )$, où $\alpha$ est lui même écrit en représentation de base $\Omega$ dont tous les morceaux sont canoniques et inférieurs à $\delta$.

Par exemple, $\psi (\Omega ^{\omega +1}\,\psi (\Omega )+\psi (\Omega ^{\omega })^{\psi (\Omega ^{2})}42)^{\psi (1729)\,\omega }$ est une notation canonique pour un ordinal inférieur à l'ordinal de Feferman–Schütte ; utilisant les fonctions de Veblen, il s'écrit $\phi _{1}(\phi _{\omega +1}(\phi _{2}(0))+\phi _{\omega }(0)^{\phi _{3}(0)}42)^{\phi _{1}(1729)\,\omega }$.

La comparaison des ordinaux écrit sous forme canonique se fait lexicographiquement, en remarquant que (par hypothèse) $\Omega$ est supérieur à $\psi (\alpha )$ pour tout $\alpha$. Ainsi, $\psi (\Omega ^{\Omega })$ (l'ordinal de Feferman–Schütte) iest beaucoup plus grand que $\psi (\Omega ^{\psi (\Omega )})=\phi _{\phi _{2}(0)}(0)$, et ce dernier est lui-même beaucoup plus grand que $\psi (\Omega )^{\psi (\Omega )}=\phi _{2}(0)^{\phi _{2}(0)}$ ; en fait, $\psi (\Omega )^{\psi (\Omega )}$ est déjà inférieur à $\psi (\Omega +1)$.

Suites fondamentales de notations ordinales

Une importante application de ces notations canoniques est la possibilité de définir des suites fondamentales (ou suites standard) convergeant vers n'importe quel ordinal limite inférieur à l'ordinal de Bachmann–Howard (l'algorithme qui suit définit également des suites standard pour certains ordinaux non dénombrables, à condition qu'ils soient de cofinalité dénombrable)

Les règles ci-dessous sont plus ou moins évidentes à l'exception de la dernière :

• Le cas des représentations itérées en base $\delta$ : pour définir une suite fondamentale convergeant vers $\alpha =\delta ^{\beta _{1}}\gamma _{1}+\cdots +\delta ^{\beta _{k}}\gamma _{k}$, avec $\delta$ = $\omega$ ou $\psi (\cdots )$ (ou $\Omega$, mais ce cas est détaillé ci-dessous) :
  • si $\beta _{k}$ est nul et $\gamma _{k}$ est un successeur, $\alpha$ est un successeur ;
  • si $\gamma _{k}$ est limite, on prend la suite fondamentale convergeant vers $\gamma _{k}$ et on remplace $\gamma _{k}$ dans l'expression de $\alpha$ par les éléments de cette suite ;
  • si $\gamma _{k}$ est un successeur et $\beta _{k}$ est limite, on réécrit le dernier terme $\delta ^{\beta _{k}}\gamma _{k}$ comme $\delta ^{\beta _{k}}(\gamma _{k}-1)+\delta ^{\beta _{k}}$, et on remplace $\beta _{k}$ dans le second terme par les éléments de la suite fondamentale convergeant vers lui ;
  • si $\gamma _{k}$ et $\beta _{k}$ sont successeurs, on réécrit le dernier terme $\delta ^{\beta _{k}}\gamma _{k}$ comme $\delta ^{\beta _{k}}(\gamma _{k}-1)+\delta ^{\beta _{k}-1}\delta$, et on remplace le dernier $\delta$ de cette expression par les éléments de la suite fondamentale convergeant vers lui.
• La suite fondamentale pour $\delta$ = $\omega$ est la suite évidente $0$, $1$, $2$, $3$… ;
• La suite fondamentale pour $\delta =\psi (0)$ est la suite $\omega$, $\omega ^{\omega }$, $\omega ^{\omega ^{\omega }}$… ;
• La suite fondamentale pour $\delta =\psi (\alpha +1)$ est la suite $\psi (\alpha )$, $\psi (\alpha )^{\psi (\alpha )}$, $\psi (\alpha )^{\psi (\alpha )^{\psi (\alpha )}}$… ;
• Si $\delta =\psi (\alpha )$, où $\alpha$ est un ordinal limite de cofinalité dénombrable, $\alpha$ possède une suite standard ; la suite standard pour $\delta$ est obtenue en appliquant $\psi$ à la suite standard pour $\alpha$ (utilisant le fait que $\psi$ est continue et croissante). Voici quelques exemples de ces suites :
  • la suite fondamentale pour $\omega ^{2}$ est : $0$, $\omega$, $\omega 2$, $\omega 3$…
  • la suite fondamentale pour $\psi (\omega ^{\omega })$ est : $\psi (1)$, $\psi (\omega )$, $\psi (\omega ^{2})$, $\psi (\omega ^{3})$…
  • la suite fondamentale pour $\psi (\Omega )^{\omega }$ est : $1$, $\psi (\Omega )$, $\psi (\Omega )^{2}$, $\psi (\Omega )^{3}$…
  • la suite fondamentale pour $\psi (\Omega +1)$ est : $\psi (\Omega )$, $\psi (\Omega )^{\psi (\Omega )}$, $\psi (\Omega )^{\psi (\Omega )^{\psi (\Omega )}}$…
  • la suite fondamentale pour $\psi (\Omega ^{\psi (0)})$ est : $\psi (\Omega ^{\omega })$, $\psi (\Omega ^{\omega ^{\omega }})$, $\psi (\Omega ^{\omega ^{\omega ^{\omega }}})$… (déduite de la suite fondamentale pour $\psi (0)$).
• Le seul cas difficile est donc celui où $\delta =\psi (\alpha )$, où $\alpha$ est de cofinalité non dénombrable (par exemple $\alpha =\Omega$). Il n'y a évidemment pas de suite convergeant vers $\alpha$, mais il est possible de définir une suite convergeant vers $\rho <\alpha$ tel que $\psi$ soit constante entre $\rho$ et $\alpha$. Ce $\rho$ sera le premier point fixe d'une fonction $\xi \mapsto h(\psi (\xi ))$, construite en appliquant les mêmes règles de décomposition à la forme $\alpha =h(\Omega )$. On obtient ainsi une suite $0$, $h(\psi (0))$, $h(\psi (h(\psi (0))))$… convergeant vers $\rho$, et la suite fondamentale pour $\psi (\alpha )=\psi (\rho )$ est donc $\psi (0)$, $\psi (h(\psi (0)))$, $\psi (h(\psi (h(\psi (0)))))$… Voici quelques exemples  :
  • la suite fondamentale pour $\psi (\Omega )$ est : $\psi (0)$, $\psi (\psi (0))$, $\psi (\psi (\psi (0)))$… Elle converge bien vers $\rho =\psi (\Omega )=\zeta _{0}$.
  • la suite fondamentale pour $\psi (\Omega 2)$ est: $\psi (0)$, $\psi (\Omega +\psi (0))$, $\psi (\Omega +\psi (\Omega +\psi (0)))$… Elle converge vers la valeur $\zeta _{1}$ de $\psi$ à $\rho =\Omega +\psi (\Omega 2)=\Omega +\zeta _{1}$(après lequel $\psi$ est constante jusqu'à $\Omega 2$.
  • un exemple plus complexe est la suite fondamentale pour $\psi (\Omega ^{\Omega ^{2}+\Omega 3})$ : $\psi (0)$, $\psi (\Omega ^{\Omega ^{2}+\Omega 2+\psi (0)})$, $\psi (\Omega ^{\Omega ^{2}+\Omega 2+\psi (\Omega ^{\Omega ^{2}+\Omega 2+\psi (0)})})$… (on remarquera la légère transformation du terme $\Omega 3$).
  • la suite fondamentale pour $\psi (\Omega ^{\psi (\Omega )})$ est : $\psi (\Omega ^{\psi (0)})$, $\psi (\Omega ^{\psi (\psi (0))})$, $\psi (\Omega ^{\psi (\psi (\psi (0)))})$… (utilisant les premières règles, et la suite fondamentale pour $\psi (\Omega )$).

Bien que l'ordinal de Bachmann–Howard $\psi (\varepsilon _{\Omega +1})$ n'a pas lui-même de notation canonique, il est également utile de prendre pour lui la suite canonique $\psi (\Omega )$, $\psi (\Omega ^{\Omega })$, $\psi (\Omega ^{\Omega ^{\Omega }})$…

Une utilisation de ces suites est la possibilité d'une définition (plus ou moins canonique, et prolongeant les définitions données usuellement) de la hiérarchie de croissance rapide jusqu'à $f_{\psi (\varepsilon _{\Omega +1})}$.

Un processus qui s'arrête

Partant d'un ordinal inférieur ou égal à l'ordinal de Bachmann–Howard, appliquer répétitivement (jusqu'à l'arrêt éventuel sur l'ordinal 0) la règle suivante :

• si l'ordinal est successeur, le remplacer par l'ordinal précédent (autrement dit, soustraire 1)
• si l'ordinal est limite, le remplacer par un ordinal arbitraire de la suite fondamentale qui lui correspond

Ce processus s'arrête toujours (parce qu'une suite décroissante d'ordinaux est toujours finie), mais comme pour les suites de Goodstein :

1. la longueur de la suite avant l'arrêt peut être inimaginablement grande,
2. la démonstration de l'arrêt peut être impossible dans des systèmes moins puissants que ZFC (par exemple dans l'arithmétique de Peano).

Par exemple, voici le début d'une telle suite (obtenu en choisissant à chaque étape 2 le troisième terme de la suite fondamentale) : en partant de $\psi (\Omega ^{\Omega ^{\omega }})$ (le petit ordinal de Veblen), on peut descendre à $\psi (\Omega ^{\Omega ^{3}})$, puis à $\psi (\Omega ^{\Omega ^{2}\psi (0)})$, puis $\psi (\Omega ^{\Omega ^{2}\omega ^{\omega }})$ puis $\psi (\Omega ^{\Omega ^{2}\omega ^{3}})$ puis $\psi (\Omega ^{\Omega ^{2}\omega ^{2}3})$ puis $\psi (\Omega ^{\Omega ^{2}(\omega ^{2}2+\omega )})$ puis $\psi (\Omega ^{\Omega ^{2}(\omega ^{2}2+1)})$ puis $\psi (\Omega ^{\Omega ^{2}\omega ^{2}2+\Omega \psi (\Omega ^{\Omega ^{2}\omega ^{2}2+\Omega \psi (0)})})$ puis $\psi (\Omega ^{\Omega ^{2}\omega ^{2}2+\Omega \psi (\Omega ^{\Omega ^{2}\omega ^{2}2+\Omega \omega ^{\omega ^{\omega }}})})$, etc. Bien que ces expressions semblent de plus en plus compliquées, elles représentent bien en fait une suite d'ordinaux décroissante.

Le point 1 ci-dessus peut être illustré plus précisément comme suit : pour un ordinal donné $\alpha$, on peut définir une fonction $f_{\alpha }(n)$ qui compte le nombre d'étapes avant la fin en prenant systématiquement le $n$-ème élément de la suite fondamentale (on a donc $f_{\alpha }(n)=f_{\alpha [n]}(n)+1$). Cette fonction est à croissance assez rapide : $f_{\omega ^{\omega }}(n)$ vaut environ $n^{n}$, $f_{\psi (\Omega ^{\omega })}(n)$ est comparable à la fonction d'Ackermann $A(n,n)$, et $f_{\psi (\varepsilon _{\Omega +1})}(n)$ est comparable à la fonction de Goodstein. Une légère modification, prenant $g_{\alpha }(n)=g_{\alpha [n]}(n+1)+1$, amène à des fonctions à peu près aussi rapidement croissantes que celles de la hiérarchie de croissance rapide.

Le point 2 correspond à la notion d'analyse ordinale (en) : la théorie des ensembles de Kripke-Platek, par exemple, peut démontrer que le processus s'arrête pour tout ordinal $\alpha$ inférieur à l'ordinal de Bachmann-Howard ordinal, mais ne peut le faire pour l'ordinal de Bachmann-Howard lui-même. Il est bien connu (depuis les travaux de Gentzen) que l'arithmétique de Peano est limitée de même aux ordinaux inférieurs à $\varepsilon _{0}$.

Variations sur l'exemple précédent

Diminuer la puissance de la fonction

Si l'on limite les opérations permises pour définir $\psi$ (ce qui n'a pas vraiment d'intérêt pratique), on découvre que l'affaiblissement ne provient pas tant des opérations sur les ordinaux dénombrables, que des ordinaux qu'on ne peut plus utiliser en partant de $\Omega$. Par exemple, si on supprime l'exponentiation dans les opérations permettant de construire $C(\alpha )$, ion obtient$\psi (0)=\omega ^{\omega }$ (le plus petit ordinal qu'on ne peut construire à partir de $0$, $1$ et $\omega$), puis $\psi (1)=\omega ^{\omega ^{2}}$ et de même $\psi (\omega )=\omega ^{\omega ^{\omega }}$, $\psi (\psi (0))=\omega ^{\omega ^{\omega ^{\omega }}}$jusqu'au premier point fixe, qui sera donc$\psi (\Omega )=\varepsilon _{0}$. Ensuite, $\psi (\Omega +1)={\varepsilon _{0}}^{\omega }$ et ainsi de suite jusqu'à $\psi (\Omega 2)=\varepsilon _{1}$. On peut ensuite former $\psi (\Omega ^{2})=\phi _{2}(0)$, $\psi (\Omega ^{3})=\phi _{3}(0)$ etc., mais la construction s'arrête là, puisqu'on ne peut atteindre $\Omega ^{\omega }$.

Au-delà de l'ordinal de Bachmann-Howard

On a vu que $\psi (\varepsilon _{\Omega +1})$ est l'ordinal de Bachmann-Howard. Avec les définitions précédentes $\psi (\varepsilon _{\Omega +1}+1)$ n'est pas plus grand, parce qu'il n'y a pas de notations pour $\varepsilon _{\Omega +1}$ (il n'appartient à aucun $C(\alpha )$ et en est toujours la borne supérieure). On pourrait ajouter aux opérations permises dans la construction de $C(\alpha )$ les fonctions $\varepsilon$ (ou plus généralement les fonctions de Veblen), mais il s'avère que cela ne permet pas d'aller beaucoup plus loin, essentiellement parce que la fonction $\psi$ ne construit pas de nouveaux ordinaux non dénombrables (par exemple, $\psi (\Omega +1)$ est$\varepsilon _{\phi _{2}(0)+1}$, certainement pas $\varepsilon _{\Omega +1}$) ; la solution est d'introduire un nouvel ordinal non dénombrable $\Omega _{2}$ (plus grand que tous les ordinaux qui vont être construits, par exemple on prend $\Omega =\omega _{1}$ et $\Omega _{2}=\omega _{2}$) et de construire une nouvelle fonction $\psi _{1}$ sur le même modèle :

$\psi _{1}(\alpha )$ est le plus petit ordinal qui ne peut être exprimé à partir des ordinaux dénombrables, de $\Omega$ et de $\Omega _{2}$, en utilisant sommes, produits, exponentielles, et les valeurs de $\psi _{1}$ sur les ordinaux déjà construits inférieurs à $\alpha$.

Ainsi, $\psi _{1}(0)=\varepsilon _{\Omega +1}$, et plus généralement $\psi _{1}(\alpha )=\varepsilon _{\Omega +1+\alpha }$ pour tous les ordinaux dénombrables, et même au delà ($\psi _{1}(\Omega )=\varepsilon _{\Omega 2}$ et $\psi _{1}(\psi _{1}(0))=\varepsilon _{\varepsilon _{\Omega +1}}$) : cela reste vrai jusqu'au premier point fixe $\zeta _{\Omega +1}$ (après $\Omega$) de la fonction $\xi \mapsto \varepsilon _{\xi }$, lequel est la limite de la suite $\psi _{1}(0)$, $\psi _{1}(\psi _{1}(0))$, etc. Ensuite $\psi _{1}(\alpha )=\zeta _{\Omega +1}$ est constante jusqu'à $\Omega _{2}$: comme on l'a vu pour $\psi (\Omega )$, on a$\psi _{1}(\Omega _{2})=\zeta _{\Omega +1}$ et $\psi _{1}(\Omega _{2}+1)=\varepsilon _{\zeta _{\Omega +1}+1}$.

La fonction $\psi _{1}$ donne un système de notations (si on en a un pour les ordinaux dénombrables !) pour les ordinaux inférieurs à $\psi _{1}(\varepsilon _{\Omega _{2}+1})$ (la limite de $\psi _{1}(\Omega _{2})$, $\psi _{1}({\Omega _{2}}^{\Omega _{2}})$, etc.).

Ces notations peuvent se réinjecter dans la fonction $\psi$ initiale, obtenant la définition élargie :

$\psi (\alpha )$ est le plus petit ordinal qui ne peut être exprimé à partir de $0$, $1$, $\omega$, $\Omega$ et $\Omega _{2}$, en utilisant sommes, produits, exponentielles, la fonction $\psi _{1}$, et les valeurs de $\psi$ sur les ordinaux déjà construits inférieurs à $\alpha$.

Cette nouvelle fonction $\psi$ coïncide avec la précédente jusqu'à $\psi (\psi _{1}(0))$, l'ordinal de Bachmann–Howard, mais on peut à présent le dépasser : $\psi (\psi _{1}(0)+1)$ est $\varepsilon _{\psi (\psi _{1}(0))+1}$ (l'$\varepsilon$-ordinal après lui). Notre système de notations est à présent doublement imprédicatif : les notations que nous venons de créer pour des ordinaux dénombrables utilisent des notations pour certains ordinaux entre $\Omega$ et $\Omega _{2}$, elles-mêmes définies à l'aide d'ordinaux au-delà de $\Omega _{2}$.

Ce schéma peut se généraliser à une infinité de nouveaux cardinaux $\Omega _{\alpha }$ (avec des définitions légèrement différentes, pour ne pas avoir à construire des récurrences sur le nombre de cardinaux) ; ainsi, utilisant $\omega +1$ nouveaux cardinaux, $\Omega _{1},\Omega _{2},\ldots ,\Omega _{\omega }$, on obtient un système essentiellement équivalent à celui introduit par Buchholz (la construction de Buchholz n'utilise pas l'addition ou la multiplication, ni les nombres $1$ et $\omega$, obtenant une définition plus élégante et plus concise, mais aussi plus difficile à comprendre). Ce système est également équivalent à ceux définis auparavant par Takeuti et par Feferman (les fonctions $\theta$) : ils atteignent tous le même ordinal ($\psi _{0}(\varepsilon _{\Omega _{\omega }+1})$, qu'on pourrait donc appeler l'ordinal de Takeuti-Feferman–Buchholz, et qui correspond à la force ordinale de la $\Pi _{1}^{1}$-compréhension (en)).

Relations avec l'analyse ordinale

Comme mentionné dans l'introduction, la définition de fonctions d'effondrement ordinales est en relation étroite avec l'analyse ordinale (en), ainsi l'effondrement de grands cardinaux est utilisé pour décrire la force de diverses théories :

• Gerhard Jäger et Wolfram Pohlers utilisent l'effondrement d'un cardinal inaccessible pour décrire la force de la théorie des ensembles de Kripke-Platek. L'idée est d'ajouter la fonction $\alpha \mapsto \Omega _{\alpha }$elle-même à la liste des constructions auxquelles s'applique le système d'effondrement $C(\cdot )$.
• Michael Rathjen a ensuite utilisé l'effondrement de cardinaux bien plus vastes (Mahlo et faiblement compacts) pour décrire la force de la même théorie augmentée de certains principes de réflexion (en).
• À partir de 2005, Rathjen a commencé à étudier la possibilité d'effondrement de cardinaux plus vastes encore, dans l'espoir de parvenir à une analyse ordinale de la $\Pi _{2}^{1}$-compréhension (en).

Références

• (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Ordinal collapsing function » (voir la liste des auteurs).
• (en) Gaisi Takeuti, « Consistency proofs of subsystems of classical analysis », Annals of Mathematics, vol. 86, n^o 2,‎ 1967, p. 299–348 (DOI 10.2307/1970691, JSTOR 1970691)
• (de) Gerhard Jäger et Pohlers, Wolfram, « Eine beweistheoretische Untersuchung von ($\Delta _{2}^{1}$-CA)+(BI) und verwandter Systeme », Bayerische Akademie der Wissenschaften. Mathematisch-Naturwissenschaftliche Klasse Sitzungsberichte, vol. 1982,‎ 1983, p. 1–28
• (en) Wilfried Buchholz, « A New System of Proof-Theoretic Ordinal Functions », Annals of Pure and Applied Logic, vol. 32,‎ 1986, p. 195–207 (DOI 10.1016/0168-0072(86)90052-7)
• (en) Michael Rathjen, « Proof-theoretic analysis of KPM », Archive for Mathematical Logic, vol. 30, n^os 5–6,‎ 1991, p. 377–403 (DOI 10.1007/BF01621475)
• (en) Michael Rathjen, « Proof theory of reflection », Annals of Pure and Applied Logic, vol. 68, n^o 2,‎ 1994, p. 181–224 (DOI 10.1016/0168-0072(94)90074-4, lire en ligne)
• (en) Michael Rathjen, « Recent Advances in Ordinal Analysis: $\Pi _{2}^{1}$-CA and Related Systems », The Bulletin of Symbolic Logic, vol. 1, n^o 4,‎ 1995, p. 468–485 (DOI 10.2307/421132, JSTOR 421132, lire en ligne)
• (en) Reinhard Kahle, « Mathematical proof theory in the light of ordinal analysis », Synthese, vol. 133,‎ 2002, p. 237–255 (DOI 10.1023/A:1020892011851)
• (en) Michael Rathjen, « An ordinal analysis of stability », Archive for Mathematical Logic, vol. 44,‎ 2005, p. 1–62 (DOI 10.1007/s00153-004-0226-2, CiteSeer^x 10.1.1.15.9786, lire en ligne)
• (en) Michael Rathjen, « Proof Theory: Part III, Kripke–Platek Set Theory » [archive du 12 juin 2007], août 2005 (consulté le 17 avril 2008)(diapos d'une conférence donnée à Fischbachau)