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 BuchholzBuchholz, 1986 (Ann. Pure Appl. Logic), 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, de la multiplication et de 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érieure à par hypothèse). Par ailleurs, 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 , 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 si 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 , , … ;