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[1], mais se limite à un seul cardinal pour simplifier l'exposé.
Définition
Soit le plus petit ordinal non dénombrable (généralement noté
)[2]. 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'ordinal d'Ackermann (en) (la limite des ordinaux de la forme
),
est le petit ordinal de Veblen (en) (la limite des ordinaux de la forme
avec un nombre fini de variables),
est le grand ordinal de Veblen (en) (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'ordinal de Bachmann-Howard (en). 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.
- si
- 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
).
- 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
).
- 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'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 inférieur à l'ordinal de Bachmann-Howard ordinal, mais ne peut le faire pour l'ordinal de Bachmann-Howard lui-même[3]. 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[1] (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[4] 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
-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[5] 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)[6],[7] 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[8], dans l'espoir de parvenir à une analyse ordinale de la
-compréhension (en).
Notes
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, no 2, , p. 299–348 (DOI 10.2307/1970691, JSTOR 1970691)
- (de) Gerhard Jäger et Pohlers, Wolfram, « Eine beweistheoretische Untersuchung von (
-CA)+(BI) und verwandter Systeme », Bayerische Akademie der Wissenschaften. Mathematisch-Naturwissenschaftliche Klasse Sitzungsberichte, vol. 1982, , p. 1–28
- (en) Wilfried Buchholz, « A New System of Proof-Theoretic Ordinal Functions », Annals of Pure and Applied Logic, vol. 32, , 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, nos 5–6, , p. 377–403 (DOI 10.1007/BF01621475)
- (en) Michael Rathjen, « Proof theory of reflection », Annals of Pure and Applied Logic, vol. 68, no 2, , p. 181–224 (DOI 10.1016/0168-0072(94)90074-4, lire en ligne)
- (en) Michael Rathjen, « Recent Advances in Ordinal Analysis:
-CA and Related Systems », The Bulletin of Symbolic Logic, vol. 1, no 4, , 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, , p. 237–255 (DOI 10.1023/A:1020892011851)
- (en) Michael Rathjen, « An ordinal analysis of stability », Archive for Mathematical Logic, vol. 44, , p. 1–62 (DOI 10.1007/s00153-004-0226-2, CiteSeerx 10.1.1.15.9786, lire en ligne)
- (en) Michael Rathjen, « Proof Theory: Part III, Kripke–Platek Set Theory » [archive du ], (consulté le )(diapos d'une conférence donnée à Fischbachau)