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  le plus petit ordinal non dénombrable (généralement noté ). On définit une fonction  (qui sera non décroissante et continue)  envoyant n'importe quel ordinal  vers un ordinal dénombrable , par récurrence transfinie sur , de la manière suivante : supposons que  ait été défini pour tous les . Soit  l'ensemble des ordinaux engendrés (récursivement) à partir de , ,  et , de l'addition, la multiplication et l'exponentiation ordinale, et de la fonction , c'est-à-dire de la restriction de  aux ordinaux  (plus rigoureusement, on pose   et pour tout  ;  est la réunion de tous les ).   est alors défini comme le plus petit ordinal n'appartenant pas à  . 

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 , donc) ; on donne ainsi des noms à des ordinaux non dénombrables, et la liste de ces ordinaux étant nécessairement dénombrable,   les « effondrera »  vers des ordinaux dénombrables.

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

Début prédicatif 
Par construction,  contient les ordinaux , , , , , , , , , , , ,  , etc.,  ainsi que les ordinaux  , , , . Le premier ordinal qu'il ne contient pas est  (la limite de , , , etc., inférieur à  par hypothèse).  La borne supérieure de  est   (la limite de , ,  , etc.), mais cela n'intervient pas dans la suite.  Ainsi, .

De même,  contient les ordinaux qu'on peut former à partir de  , , ,  ainsi à présent que , ce qui permet de construire tous les ordinaux jusqu'à  (mais pas ce dernier) et donc .  Par récurrence transfinie sur , on démontre que  ; cette démonstration ne fonctionnant que tant que .  Ainsi :

 pour tous les , où  est le plus petit point fixe de  (ici, les  sont les fonctions de Veblen définies en partant de ).

Ainsi , mais  n'est pas plus grand, puisqu'on ne peut pas construire  par un nombre fini d'itérations de  et donc  n'appartient à aucun ensemble  pour  ; la fonction  est donc longtemps « bloquée »  à  :  pour tous les  tels que .

Premières valeurs non prédicatives 
On continue à avoir .  Mais pour le calcul de , quelque chose a changé :   ayant été (artificiellement) inclus dans tous les , les règles permettent d'utiliser la valeur . Ainsi,   contient tous les ordinaux qu'on peut construire à partir de , , ,  la fonction  jusqu'à  et cette fois également .  Le plus petit ordinal qu'on ne peut construire ainsi est   (le premier -ordinal après ).

La définition , et les valeurs suivantes de  telles que  sont dites imprédicatives  parce qu'elles utilisent des ordinaux (ici, ) supérieurs à ceux qu'on veut définir (ici, ).

Valeurs de  jusqu'à l'ordinal de Feferman-Schütte 
Le fait que  reste vrai pour tous les   (en particulier , mais maintenant que  est construit, rien n'empêche de continuer au delà).  cependant, à  (le premier point fixe de  après ), la construction est à nouveau bloquée, car  ne peut être obtenu à partir de  (et des ordinaux plus petits) par un nombre fini d'application de la fonction . On voit ainsi comme précédemment que .

Le même raisonnement montre que  pour tous les  (où  énumère les points fixes de  et  est le premier point fixe de ).  On obtient ainsi.

On voit de même que  tant que  est plus petit que le premier point fixe  de , lequel est  l'ordinal de Feferman-Schütte.  Ainsi,

Au-delà de l'ordinal de Feferman-Schütte 
On a pour tous les  , où  est le prochain point fixe de .  Utilisant la fonction  qui énumère ces points fixes (et qu'on peut également noter  à l'aide des fonctions de Veblen à plusieurs variables), on a , jusqu'au premier point fixe  de la fonction  elle-même, qui sera  (et le premier point fixe  des fonctions  sera ).  Continuant ainsi :
  est l' (la limite des ordinaux de la forme ),
  est le  (la limite des ordinaux de la forme  avec un nombre fini de variables),
  est le  (la limite des ordinaux de la forme  avec un nombre transfini (mais de la même forme) de variables),
 la limite  de , , , etc., est l'. Ensuite, la fonction  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  permet de définir des notations «  canoniques » pour tous les ordinaux jusqu'à l'ordinal de Bachmann-Howard.

Bases de représentation 
Si  est un ordinal qui est une puissance de  (par exemple  lui-même, ou , ou ), tout ordinal  (non nul) possède une représentation unique de la forme , où  est un entier,  sont des ordinaux non nuls strictement inférieurs à , et  sont des ordinaux ( pouvant être nul).  Cette  « représentation en base  » généralise la forme normale de Cantor (qui correspond au cas ).  Il est possible que cette forme n'apporte rien, lorsque , mais dans tous les autres cas, les  sont tous inférieurs à  ; cette représentation est également triviale lorsque , auquel cas  et .

Si  est un ordinal inférieur à , sa représentation en base   a des coefficients  (par définition) et des exposants  (puisque ) ; on peut donc réécrire ces exposants  en base  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  en base  aet les différents coefficients apparaissant (y compris en tant qu'exposants) les morceaux de la représentation (tous ), ou, pour abréger, les -morceaux de .

Propriétés de  
 La fonction  est non-décroissante et continue.
 Si  avec , alors .  En fait, aucun ordinal  avec  ne peut appartenir à .
 Toute valeur  prise par  est un -ordinal (c'est-à-dire un point fixe de ).  
 Soit  un -ordinal et  un ordinal tel que  pour tout  ; alors les -morceaux de tout élément de  sont inférieurs à . De plus,   (et ).
 Tout -ordinal inférieur à un élément de l'image de  est lui-même dans l'image de .  
 Si , l'ensemble  est formé des ordinaux  (inférieurs à ) dont les -morceaux sont inférieurs à .

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  inférieur à l'ordinal de Bachmann-Howard, par récurrence transfinie sur .

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

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

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

Exemples 
Pour les ordinaux inférieurs à , cette notation canonique coïncide par définition avec la forme normale de Cantor

Pour les ordinaux inférieurs à  , la notation coïncide avec la représentation (itérée) en base  notation, ainsi   sera écrit , ou plus rigoureusement .  

De même, pour les ordinaux inférieurs à , on utilise la représentation en base  les morceaux étant écrits en base   (et les morceaux de cela étant écrit en forme normale de Cantor),  ainsi  est noté , ou plus précisément .  Jusqu'à , on utilise ainsi comme base le plus grand -ordinal donnant une représentation non triviale.

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

Bien que  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   emboîtées (c'est-à-dire que les arguments d'une fonction  «  intérieure » sont toujours plus petits que ceux d'une fonction  qui l'appelle) ; ceci est une conséquence de ce que les -morceaux de , où  est le plus grand possible tel que  pour un certain -ordinal , sont tous inférieurs à .  Par exemple,  n'est pas une notation ; c'est une expression bien formée, égale à   puisque  est constante entre  et , 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 à , ou une représentation (itérée) en base  dont tous les morceaux sont  canoniques pour un  de la forme , où  est lui même écrit en représentation de base  dont tous les morceaux sont canoniques et inférieurs à . 

Par exemple,  est une notation canonique pour un ordinal inférieur à l'ordinal de Feferman–Schütte ; utilisant les fonctions de Veblen, il s'écrit .

La comparaison des ordinaux écrit sous forme canonique se fait lexicographiquement, en remarquant que (par hypothèse)  est supérieur à  pour tout . Ainsi,  (l'ordinal de Feferman–Schütte) iest beaucoup plus grand que , et ce dernier est lui-même beaucoup plus grand que  ; en fait,  est déjà inférieur à .

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  : pour définir une suite fondamentale convergeant vers  , avec   =  ou  (ou , mais ce cas est détaillé ci-dessous) :
 si   est nul et  est un successeur,   est un successeur ;
 si  est limite, on prend la suite fondamentale convergeant vers  et on remplace  dans l'expression de  par les éléments de cette suite ;
 si  est un successeur et  est limite, on réécrit le dernier terme  comme , et on remplace  dans le second terme par les éléments de la suite fondamentale convergeant vers lui ;
 si  et  sont successeurs, on réécrit le dernier terme  comme , et on remplace le dernier  de cette expression par les éléments de la suite fondamentale convergeant vers lui.
 La suite fondamentale pour  =  est la suite évidente , , , … ;
 La suite fondamentale pour  est la suite , , … ;
 La suite fondamentale pour  est la suite , , … ;
 Si ,  où  est  un ordinal limite de cofinalité dénombrable,  possède une suite standard ; la suite standard pour  est obtenue en appliquant  à la suite standard pour  (utilisant le fait que  est continue et croissante). Voici quelques exemples de ces suites :
 la suite fondamentale pour  est : , , , …
 la suite fondamentale pour  est : , , , …
 la suite fondamentale pour  est : , , , …
 la suite fondamentale pour  est : , , …
 la suite fondamentale pour  est : , , … (déduite de la suite fondamentale pour ).
 Le seul cas difficile est donc celui où , où  est de cofinalité non dénombrable (par exemple ).  Il n'y a évidemment pas de suite convergeant vers , mais il est possible de définir une suite convergeant vers  tel que  soit constante entre  et .  Ce  sera le premier point fixe d'une fonction , construite en appliquant  les mêmes règles de décomposition à la forme  . On obtient ainsi une suite , , … convergeant vers , et la suite fondamentale pour  est donc , , … Voici quelques exemples  :
 la suite fondamentale pour  est : , , …  Elle converge bien vers .
 la suite fondamentale pour  est: , , …  Elle converge vers la valeur  de  à (après lequel  est constante jusqu'à .
 un exemple plus complexe est la suite fondamentale pour  : , , … (on remarquera la légère transformation du terme ).
 la suite fondamentale pour  est : , , … (utilisant les premières règles, et la suite fondamentale pour ).

Bien que l'ordinal de Bachmann–Howard  n'a pas lui-même de notation canonique, il est également utile de prendre pour lui la suite canonique , , …

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'à .

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 : 
 la longueur de la suite avant l'arrêt peut être inimaginablement grande,
 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  (le petit ordinal de Veblen), on peut descendre à , puis à , puis  puis  puis  puis  puis  puis  puis , 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é , on peut définir une fonction  qui compte le nombre d'étapes avant la fin en prenant systématiquement le -ème élément de la suite fondamentale (on a donc  ).  Cette fonction est à croissance assez rapide :   vaut environ ,  est comparable à la fonction d'Ackermann , et  est comparable à la fonction de Goodstein. Une légère modification, prenant , 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' : la théorie des ensembles de Kripke-Platek, par exemple, peut démontrer que le processus s'arrête pour tout ordinal  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 à .

Variations sur l'exemple précédent

Diminuer la puissance de la fonction 
Si l'on limite les opérations permises pour définir   (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 . Par exemple, si on supprime l'exponentiation dans les opérations permettant de construire , ion obtient (le plus petit ordinal qu'on ne peut construire à partir de ,  et ), puis  et de même , jusqu'au premier point fixe, qui sera donc.  Ensuite,  et ainsi de suite jusqu'à .  On peut ensuite former ,  etc., mais la construction s'arrête là, puisqu'on ne peut atteindre .

Au-delà de l'ordinal de Bachmann-Howard 
On a vu que  est l'ordinal de Bachmann-Howard.  Avec les définitions précédentes  n'est pas plus grand, parce qu'il n'y a pas de notations pour  (il n'appartient à aucun  et en est toujours la borne supérieure).  On pourrait ajouter aux opérations permises dans la construction de  les fonctions  (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  ne construit pas de nouveaux ordinaux non dénombrables (par exemple,  est, certainement pas ) ; la solution est d'introduire un nouvel ordinal non dénombrable  (plus grand que tous les ordinaux qui vont être construits, par exemple on prend  et ) et de construire une nouvelle fonction  sur le même modèle :

 est le plus petit ordinal qui ne peut être exprimé à partir des ordinaux dénombrables, de  et de , en utilisant sommes, produits, exponentielles, et les valeurs de  sur les ordinaux déjà construits inférieurs à  .

Ainsi, , et plus généralement  pour tous les ordinaux dénombrables, et même au delà ( et ) : cela reste vrai jusqu'au premier point fixe   (après ) de la fonction , lequel est la limite de la suite , , etc.  Ensuite  est constante jusqu'à :  comme on l'a vu pour , on a et .

La fonction  donne un système de notations (si on en a un pour les ordinaux dénombrables !) pour les ordinaux inférieurs à   (la limite de , , etc.).

Ces notations peuvent se réinjecter dans la fonction  initiale, obtenant la définition élargie :
 est le plus petit ordinal qui ne peut être exprimé à partir de , , ,  et , en utilisant sommes, produits, exponentielles, la fonction , et les valeurs de  sur les ordinaux déjà construits inférieurs à  .

Cette nouvelle fonction  coïncide avec la précédente jusqu'à  , l'ordinal de Bachmann–Howard, mais on peut à présent le dépasser :  est  (l'-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  et , elles-mêmes définies à l'aide d'ordinaux au-delà de .

Ce schéma peut se généraliser à une infinité de nouveaux cardinaux  (avec des définitions légèrement différentes, pour ne pas avoir à construire des récurrences sur le nombre de cardinaux) ; ainsi, utilisant  nouveaux cardinaux, , 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  et , 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 ) : ils atteignent tous le même ordinal (, qu'on pourrait donc appeler l'ordinal de Takeuti-Feferman–Buchholz, et qui correspond à la force ordinale de la ).

Relations avec l'analyse ordinale 
Comme mentionné dans l'introduction, la définition de fonctions d'effondrement ordinales est en relation étroite avec l', 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 elle-même à la liste des constructions auxquelles s'applique le système d'effondrement .
 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 .
 À 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 .

Notes

Références 

(diapos d'une conférence donnée à Fischbachau)

Nombre ordinal