Méta / avant-propos
L'écriture de cette entrée aura été assez chaotique, et un peu un échec : j'ai changé plusieurs fois d'avis sur ce que je voulais y mettre, et du coup le résultat est parti un peu dans tous les sens. Cela faisait longtemps que je me disais que je devrais écrire quelque chose sur des ordinaux remarquables (comme une suite de l'entrée d'introduction à leur sujet), j'y ai repensé en écrivant l'entrée sur la programmation transfinie, je m'y suis remis en reprenant (et en copiant-collant) des bouts de choses que j'avais écrites antérieurement et laissées de côté, mais ça s'est enlisé. Je commence par expliquer pourquoi — et dans une certaine mesure, comment lire cette entrée.
Ajout : j'aurais sans doute ajouter quelque part un lien vers ce billet passé où je parle de l'aspect psychologique de pourquoi les ordinaux me fascinent.
Mon idée initiale était d'aider le lecteur à situer un certain nombre d'ordinaux intéressants (dont j'ai pu parler par le passé ou dont je pourrais parler ultérieurement) en les classant dans l'ordre (ce qui est bien avec les ordinaux, c'est qu'ils sont, justement, bien ordonnés) : j'ai déjà écrit cet autre texte à ce sujet (lié depuis l'entrée précédente), mais il est un plutôt technique, son but étant surtout de rassembler des pointeurs vers la littérature mathématique publiée, alors qu'ici je voulais donner un aperçu plus intuitif de (certains de) ces ordinaux intéressants.
Je me suis dit que j'allais faire un plan en trois parties, que
j'appellerai domaines
: (1) les ordinaux calculables (et a
fortiori dénombrables), c'est-à-dire les ordinaux strictement
inférieurs à l'ordinal de Church-Kleene ω₁CK, (2) les
ordinaux non calculables mais néanmoins dénombrables, c'est-à-dire
≥ω₁CK mais néanmoins <ω₁ (qui, en gros, ne sont
intéressants que s'ils sont « admissibles »), et (3) les ordinaux non
dénombrables (qui, en gros, ne sont intéressants que s'ils sont des
cardinaux). Ce plan a le bon goût de permettre d'insister sur le fait
que, par exemple, certains ordinaux, bien que monstrueusement grands
et complexes à définir, sont néanmoins encore calculables
(domaine (1), c'est-à-dire <ω₁CK), ce qui donne une
petite idée de combien ω₁CK est gigantesque.
Mais ce plan a aussi l'inconvénient que l'ordre naturel sur les
ordinaux (la taille, quoi) n'est pas du tout la même chose que l'ordre
d'importance, d'intérêt, ou de difficulté à les définir (je peux
définir ω₁ en disant que c'est le plus petit ordinal indénombrable, ou
que c'est l'ensemble des ordinaux dénombrables triés par ordre de
taille : ça ne laisse peut-être pas comprendre à quel point il est
riche et complexe, mais au moins, c'est une définition nette et
précise, alors que certains ordinaux beaucoup plus petits, quoique
structuralement moins riches, sont beaucoup plus subtils à définir,
puisqu'on veut les définir, justement, de façon beaucoup plus précise
et complète). Plus subtilement, d'ailleurs, mon plan par taille des
ordinaux a aussi l'inconvénient que l'ordre de taille n'est même pas
l'ordre de dépendance logique des ordinaux : c'est ce
phénomène qu'on appelle imprédicativité
qui veut qu'on fasse
appel, pour construire certains ordinaux, à des ordinaux encore plus
grands ; ainsi, la construction de l'ordinal de Bachmann-Howard (qui
est <ω₁CK, donc dans le domaine (1) de mon plan) fait
appel à une « fonction d'écrasement », qui présuppose de savoir ce que
c'est que ω₁CK ou peut-être ω₁ (l'un ou l'autre peut
servir, et on lui donne le nom de Ω dans les notations), et c'est
encore pire dans la construction d'ordinaux calculables encore plus
grands, qui nécessitent d'invoquer des ordinaux récursivement grands
ou de grands cardinaux.
Je le savais, bien sûr, mais je pensais pouvoir contourner ces difficultés en fournissant au fur et à mesure des informations minimales sur les grands ordinaux des domaines (2) et (3) alors que je décrivais le domaine (1), quitte à y revenir plus tard. Finalement, c'est une très mauvaise idée, et cette partie (1) a beaucoup trop gonflé et est devenue, du même coup, assez illisible. (Un autre problème est que ce qui rend les ordinaux calculables vraiment intéressants est leur lien avec certaines théories logiques, et il faudrait vraiment beaucoup de place pour expliquer ce que sont exactement des théories telles que la « théorie des ensembles de Kripke-Platek », l'« arithmétique du second ordre limitée à la Δ¹₂-compréhension », la « théorie des définitions inductives ».) En même temps que ça, j'ai commencé à en avoir vraiment marre d'écrire sur des ordinaux de plus en plus techniques à expliquer. Du coup, j'ai calé sur la partie (1), ce qui casse vraiment l'intention initiale, puisque j'avais surtout envie (pour rester sur la lancée de la programmation transfinie) d'essayer de dire des choses sur les ordinaux nonprojectibles, stables et compagnie, qui sont résolument dans la partie (2).
Au final, c'est un peu n'importe quoi : cette entrée me fait l'effet d'une moussaka géante où on ne comprend plus rien. Mais je pense qu'il y a quand même un certain intérêt à ce que je publie ce « n'importe quoi » plutôt que de le ranger dans mes cartons, c'est-à-dire dans le vaste cimetière des entrées que j'ai commencées et jamais publiées. Car après tout, ce que j'écris est correct (enfin, je crois), et même si vers la fin je lance dans l'air de plus en plus de termes non définis faute de patience pour les définir, ou que je pars complètement dans l'agitage de mains, certains en tireront quand même quelque chose.
Finalement, les différentes sous-parties de cette entrée sont, je l'espère, assez indépendantes les unes des autres, donc comme d'habitude, et même plus encore que d'habitude, j'encourage à sauter les passages qu'on trouve incompréhensibles ou trop techniques (beaucoup d'entre eux ne servent, finalement, à rien).
Comme expliqué ci-dessus, je vais d'abord faire quelques remarques générales sur les ordinaux intéressants, expliquer plus précisément le plan que j'avais en tête, puis parler d'ordinaux calculables (i.e., <ω₁CK, le domaine (1)), et m'arrêter en queue de poisson.
- Méta / avant-propos
- Introduction
- (1) Ordinaux calculables (=constructifs, =récursifs)
- Qu'est-ce qu'un ordinal calculable ?
- Le lien avec la force logique de théories
- Petits ordinaux calculables et fonctions de Veblen
- L'idée générale des fonctions d'écrasement
- Une définition de l'ordinal de Bachmann-Howard
- Quelques idées sur des écrasements plus sophistiqués
- Comment on peut tricher pour décrire de grands ordinaux de preuve
- Tout ce dont je n'ai pas parlé