## 2. Panorama de l'hypercalculabilité

La hiérarchie arithmétique admet plusieurs caractérisations. Elle est originally définie en termes d'alternance de quantificateurs du premier ordre. Par le fameux théorème de Post, les ensembles $\Delta_n^0$ et $\Sigma_n^0$ sont respectivement les ensembles calculables et caculatoirement énumérables à l'aide de l'oracle $\emptyset^{(n-1)}$. La hiérarchie arithmétique peut être étendue via cette correspondance, à l'aide d'itérations transfinies du saut Turing.

**Itérations du saut Turing.** Le saut Turing peut être vu comme une opération sur les ensembles, définie par $X \mapsto X' = \{e : \Phi_e^X(e) \downarrow\}$. Les ensembles $\emptyset^{(n)}$ sont définis en itérant cette opération le long des entiers naturels, à savoir

$$ \emptyset^{(0)} = \emptyset \quad \text{et} \quad \emptyset^{(n+1)} = (\emptyset^{(n)})'. $$

Il est cependant possible d'aller au-delà des itérations finies du saut Turing, en définissant son $\omega$-itération $\emptyset^{(\omega)} = \bigoplus_n \emptyset^{(n)}$, puis son $(\omega + 1)$-itération $\emptyset^{(\omega+1)} = (\emptyset^{(\omega)})'$, et ainsi de suite.

**Ordinaux.** L'itération du saut Turing au-delà des nombres finis demande d'étendre la notion d'entier naturel à des nombres transfinis, appelés *ordinaux*. Il s'agit d'un concept introduit au départ par Cantor, et qui peut être vu comme une extension de la notion d'entier naturel pour laquelle le principe suivant reste vrai : tout sous-ensemble non vide d'ordinaux admet un plus petit élément. Les opérations arithmétiques standard se généralisent également aux ordinaux. Nous noterons donc 0, 1, 2, ... les premiers ordinaux et $\omega$ le plus petit ordinal infini. De manière générale, on notera les ordinaux avec des lettres grecques : $\alpha, \beta, \gamma, ...$

Les ordinaux peuvent être arbitrairement complexes, et sont pour la plupart indénombrables. On se restreindra donc, pour les besoins de l'hypercalculabilité, à une sous-collection d'ordinaux que l'on peut représenter à l'aide d'entiers naturels et de la calculabilité. Kleene a défini un ensemble $O \subseteq \mathbb{N}$ de codes d'ordinaux, en associant à chaque entier $n \in O$ un ordinal $|n|$. Les ordinaux admettant un code dans $O$ sont appelés *constructibles*, et forment un segment initial. On notera $\omega_1^{ck}$ le plus petit ordinal non constructible. Ces notions seront étudiées dans le chapitre 27.

**Ensembles hyperarithmétiques.** Les sauts Turing peuvent être itérés le long des ordinaux constructibles. On peut étendre la hiérarchie arithmétique à des niveaux ordinaux, en définissant pour tout ordinal constructible $\alpha$ la classe $\Sigma_\alpha^0$ des ensembles calculatoirement énumérables en $\emptyset^{(\alpha)}$. On obtient alors la *hiérarchie hyperarithmétique*. La correspondance entre calculabilité et définissabilité peut être étendue aux ensembles hyperarithmétiques, à l'aide de formules infinitaires.
Les ensembles hyperarithmétiques forment une classe relativement naturelle, et admettent notamment de nombreuses caractérisations. Une fonction $f: \mathbb{N} \to \mathbb{N}$ est un modulus d'un ensemble $X$ si toute fonction $g$ dominant $f$ calcule $X$. Les ensembles hyperarithmétiques sont exactement les ensembles admettant un modulus, ou encore les ensembles calculables par un singleton $\Pi_2^0$ dans $2^{\mathbb{N}}$. Ces notions seront étudiées dans le chapitre 28.

**Hiérarchie borélienne effective.** De la même manière que la hiérarchie hyperarithmétique classifie les ensembles d'entiers naturels en fonction de leur complexité définitionnelle, les classes dans l'espace de Cantor peuvent être classifiées en hiérarchies effectives. Nous avions défini les classes $\Sigma_n^0$ et $\Pi_n^0$ de réels pour tout $n \in \mathbb{N}$. Cette hiérarchie peut être étendue le long des ordinaux constructibles. On obtient la *hiérarchie borélienne effective*, ou les *classes hyperarithmétiques* qui seront présentées dans le chapitre 28.

**Ensembles et classes $\Sigma_1^1$ et $\Pi_1^1$.** Au lieu d'itérer les constructions le long des ordinaux constructibles, on peut étendre la hiérarchie arithmétique et la hiérarchie borélienne effective en considérant les formules du second ordre. Un ensemble ou une classe est $\Sigma_1^1$ s'il est définissable par formule de la forme $\exists XF(X)$, où $F$ est une formule arithmétique. De la même manière, un ensemble ou une classe est $\Pi_1^1$ s'il est définissable par formule de la forme $\forall XF(X)$. Les ensembles et classes $\Delta_1^1$ sont ceux à la fois $\Sigma_1^1$ et $\Pi_1^1$. L'usage du second ordre donne une puissance descriptive bien supérieure, et tous les ensembles et classes hyperarithmétiques sont en particulier $\Delta_1^1$. Kleene a montré que les ensembles et classes $\Delta_1^1$ sont exactement les hyperarithmétiques, donnant ainsi une nouvelle définition purement définitionnelle des hyperarithmétiques sans avoir recours aux ordinaux. Ces notions seront abordées dans la section 29-1.

## 3. Correspondance avec la calculabilité classique

Les constructions présentées dans la section précédente sont principalement définitionnelles, et ne donnent pas un éclairage sur la nature calculatoire des ensembles au-delà des arithmétiques. Il existe cependant une correspondance informelle entre certains concepts de calculabilité classique, et ceux d'hypercalculabilité. Tout comme la notion d'ensemble calculable induit la réduction Turing par relativisation, on définit la *réduction hyperarithmétique* par $X \leq_h Y$ si $X$ est hyperarithmétique relativement à $Y$. La correspondance entre calculabilité classique et hypercalculabilité est essquissée avec la figure 3.1.

Cette correspondance peut paraître surprenante sous certains aspects, notamment le fait que les ensembles hypercalculatoirement énumérables soient les ensembles $\Pi_1^1$.
<table><caption>FIGURE 3.1 – *Correspondance calculabilité classique/hypercalculabilité*</caption><thead><tr><td>Calculabilité classique</td><td>Hypercalculabilité</td></tr></thead><tbody><tr><td>Calculable</td><td>Hyperarithmétique</td></tr><tr><td>Ensemble c. e.</td><td>Ensemble Π<sub>1</sub><sup>1</sup></td></tr><tr><td>Problème de l'arrêt</td><td>O de Kleene</td></tr><tr><td>Classe Π<sub>1</sub><sup>0</sup></td><td>Classe Σ<sub>1</sub><sup>1</sup></td></tr><tr><td>Réduction Turing</td><td>Réduction hyperarithmétique</td></tr></tbody></table>

Voici quelques éléments permettant de mieux comprendre la figure 3.1.

O de Kleene. Une propriété caractéristique du problème de l'arrêt est sa $\Sigma_1^0$-complétude pour la réduction many-one. Autrement dit, le problème de l'arrêt est une forme d'ensemble calculatoirement énumérable universel. De la même manière, le O de Kleene est $\Pi_1^1$-complet pour la réduction many-one.

Tout comme le problème de l'arrêt {$e : \Phi_e(e) \downarrow$} induit par sa relativisation un opérateur $X \mapsto \{e : \Phi_e^X(e) \downarrow\}$ appelé saut Turing, on peut définir la notion d'ordinal X-constructible, ce qui induit un opérateur

$$X \mapsto \mathcal{O}^X = \{e : e \text{ code pour un ordinal X-constructible}\}.$$

**Ensembles** $\Pi_1^1$. Si l'on dénote par $\mathcal{O}_{<\alpha}$ la restriction du O de Kleene aux codes d'ordinaux inférieurs à $\alpha$, pour un ordinal constructible $\alpha < \omega_1^{ck}$, l'ensemble $\mathcal{O}_{<\alpha}$ est un ensemble $\Sigma_{\alpha+1}^0$, dès lors hyperarithmétique. On peut donc approximer le O de Kleene par des ensembles hyperarithmétiques croissants $\mathcal{O}_{<0}$, $\mathcal{O}_{<1}$, $\mathcal{O}_{<2}$, ... le long des ordinaux constructibles, avec

$$\mathcal{O} = \bigcup_{\alpha < \omega_1^{ck}} \mathcal{O}_{<\alpha}.$$

Le O de Kleene étant $\Pi_1^1$ complet pour la réduction many-one, ses approximations induisent des approximations de tout ensemble $\Pi_1^1$ à l'aide d'ensembles hyperarithmétiques le long des ordinaux constructibles. Les ensembles $\Pi_1^1$ sont donc les ensembles que l'on peut hypercalculatoirement énumérer.

**Classes** $\Sigma_1^1$. De même qu'une classe $\Pi_1^1$ peut être vue comme l'ensemble des chemins d'un arbre calculable dans $2^{<\mathbb{N}}$, une classe $\Sigma_1^1 \mathcal{B} \subseteq 2^{<\mathbb{N}}$ peut être codée par un arbre $T \subseteq \mathbb{N}^{<\mathbb{N}}$, de telle sorte que

$$\mathcal{B} = \{X : \exists f \in \mathbb{N}^{<\mathbb{N}} X \oplus f \in [T]\}.$$

Nous prouverons plusieurs théorèmes de base pour les classes $\Sigma_1^1$ qui ad-
mettent une correspondance directe avec les théorèmes de base pour les
classes $\Pi_1^0$. Par exemple, toute classe $\Sigma_1^1$ non vide admet un membre $hy-$
perlow, c'est-à-dire un ensemble $X$ tel que $O^X \equiv_T O$. De plus, si $Y$ est un
ensemble non hyperarithmétique, alors toute classe $\Sigma_1^1$ non vide contient un
élément $X$ tel que $Y \not\le_h X$. Ces deux théorèmes de base sont des analogues
des théorèmes de base low et d'évitement de cône pour les classes $\Pi_1^0$.
<figure><img src="image_163.png" /></figure>
Chapitre
27

Nombres transfinis

Nous allons aborder dans ce chapitre un concept fondamental en mathémati-
ques permettant de réaliser des constructions itératives allant au-delà des
entiers naturels, au sens où les itérations ne se contenteront pas d'atteindre
toute étape finie : elles atteindront leur limite, et continueront au-delà.
Afin d'illustrer ce mécanisme, nous allons montrer dans quelle mesure le
saut Turing peut être itéré à l'infini et au-delà. Nous nous trouverons alors
confrontés à des problématiques de gestion des étapes infinies, qui trou-
veront leur résolution à travers la notion d'ordinal, véritable révolution
conceptuelle initiée par Cantor en 1883.

1. Motivation : itérations calculables du saut

Revenons sur la construction des itérations du saut Turing de $\emptyset$. On dispose sur les ensembles d'une opération $X \mapsto X' = \{e : \Phi_e^X(e) \downarrow\}$, que l'on va itérer à partir de l'ensemble vide $\emptyset$. Initialement, $\emptyset^{(0)} = \emptyset$. Puis, on définit à l'étape 1 le premier saut Turing $\emptyset^{(1)} = (\emptyset^{(0)})'$, puis à l'étape 2 le double saut $\emptyset^{(2)} = (\emptyset^{(1)})'$, et ainsi de suite, en définissant à l'étape $n+1$ l'ensemble $\emptyset^{(n+1)} = (\emptyset^{(n)})'$. Nous avons également vu dans la section 26-1 que la construction ne s'arrêtait pas aux itérations finies. Il est possible de définir l'ω-saut à l'étape dite « $\omega$ » par $\emptyset^{(\omega)} = \bigoplus_n \emptyset^{(n)}$. Il est clair que $\emptyset^{(\omega)} >_m \emptyset^{(n)}$ pour tout $n$, où $\le_m$ désigne la réduction many-one (voir la section 5-4). L'ensemble $\emptyset^{(\omega)}$ contient la réponse à toutes les questions arithmétiques, et comme nous l'avons vu, il n'est lui-même pas arithmétique. On peut à partir de là continuer à itérer le saut : pour tout $n$ on définit

$$
\emptyset^{(\omega+n+1)} = (\emptyset^{(\omega+n)})', \text{ puis } \emptyset^{(\omega+\omega)} = \bigoplus_n \emptyset^{(\omega+n)}.
$$
Là encore, on aura $\emptyset^{(\omega+\omega)} >_m \emptyset^{(\omega+n)}$ pour tout $n$.

Arrêtons-nous afin d'identifier, pour le moment de manière informelle, les étapes fondamentales de ce processus.

(1) *Étape initiale.* Il s'agit du cas de base : le processus n'a pas encore été itéré. Dans le cas du saut Turing, l'itération zéro $\emptyset^{(0)}$ est simplement l'ensemble $\emptyset$ lui-même.

(2) *Étape successeur.* Supposons que l'on ait itéré le processus un nombre $\alpha$ d'étapes, pour obtenir dans le cas du saut Turing l'ensemble $\emptyset^{(\alpha)}$, il est toujours possible de l'itérer une fois de plus. On passe donc à l'étape successeur $\alpha+1$. Dans le cas du saut Turing, on définit $\emptyset^{(\alpha+1)} = (\emptyset^{(\alpha)})'$. (2)

(3) *Étape limite.* Étant donné des itérations $\emptyset^{(\alpha_n)}$ du saut pour $n \in \mathbb{N}$ et avec $\emptyset^{(\alpha_n)} <_m \emptyset^{(\alpha_{n+1})}$, on peut définir son itération *limite*

$$ \emptyset^{(\gamma)} = \bigoplus_n \emptyset^{(\alpha_n)}. $$

On appelle ce genre de processus une itération *transfinie*, caractérisée par des étapes successeurs et des étapes limites. Il s'agit d'une extension des constructions par récurrence sur les entiers naturels, auxquelles l'ajout d'étapes limites permet d'aller au-delà du cas fini. Ce nouveau type d'étape mérite notre attention. Le premier cas limite $\emptyset^{(\omega)} = \bigoplus_n \emptyset^{(n)}$ est simple, mais il est important de remarquer qu'à degré Turing près — ou même à degré many-one près — il y aurait bien d'autres manières de définir $\emptyset^{(\omega)}$, par exemple en prenant $\bigoplus_n \emptyset^{(2n)}$. À mesure que l'on avance dans les itérations transfinies, il n'y a rapidement plus nécessairement de choix canoni-que qui s'impose pour sélectionner une quantité dénombrable d'éléments permettant d'itérer le saut à ces étapes limites. On utilise alors pour cela un système de codage imaginé par Kleene et qui va nous permettre de procéder proprement.

1.1. O de Kleene

Afin de formaliser la construction transfinie sur les sauts Turing, nous al-
lons commencer par nommer (ou coder) les étapes, en leur attribuant à
chacune un entier naturel. Si l'on procède naïvement et associe l'entier 0
pour l'étape initiale, et l'entier $n+1$ pour l'étape successeur de l'étape $n$,
tous les entiers naturels seront utilisés pour nommer les premières étapes
successeurs, et il n'en restera plus pour nommer les étapes limites. Nous
allons donc avoir recours à un codage plus élaboré basé sur le théorème
fondamental de l'arithmétique, qui affirme l'unicité de la décomposition en
facteurs premiers.
**Définition 1.1 (Kleene [114]).** On définit inductivement un ensemble
de notations $\mathcal{O} \subseteq \mathbb{N}$ avec un ordre partiel $<_o$ sur ses éléments :

(1) $1 \in \mathcal{O}$;

(2) si $a \in \mathcal{O}$ alors $2^a \in \mathcal{O}$. On a alors $a <_o 2^a$, et $b <_o a$ implique $b <_o 2^a$
pour tout $b$;

(3) si $\Phi_e : \mathbb{N} \to \mathbb{N}$ est une fonction totale calculable telle que
$$ \forall n \Phi_e(n) \in \mathcal{O}, \text{ avec } \Phi_e(n) <_o \Phi_e(n+1) \text{ pour tout } n, $$
alors $3 \times 5^e \in \mathcal{O}$. De plus, pour chaque $b \in \mathcal{O}$ tel que $b <_o \Phi_e(n)$ pour
un certain $n$, on a $b <_o 3 \times 5^e$. $\diamond$

Formellement, l'ordre partiel $<_o \subseteq \mathbb{N} \times \mathbb{N}$ peut être défini comme le plus
petit ensemble contenant $1 <_o 2$ et clos par les opérations (2) et (3). L'en-
semble $\mathcal{O}$ est alors le domaine de cet ordre partiel.

Intuitivement, le cas (1) définit le code pour l'étape 0, tandis que les cas (2) et (3) correspondent respectivement au cas successeur et au cas limite. Les détails de la définition sont principalement conventionnels, l'essentiel étant d'obtenir un système de codage pour les étapes successeurs et limites qui ne se « morde pas la queue » : les entiers 2, 3 et 5 utilisés sont tous des nombres premiers, et le théorème fondamental de l'arithmétique — l'unicité de la décomposition des nombres en facteurs premiers — nous garantit que la construction d'un élément de $\mathcal{O}$ à une étape limite ou successeur ne sera jamais égale à un code précédemment construit. En particulier, dans le cas (3), l'utilisation de $3 \times 5^e$ plutôt que $3^e$ est simplement là pour éviter de retomber sur 1 dans le cas $e = 0$. On aurait aussi bien pu noter cette étape $3^{e+1}$.

On notera que dans le cas limite — le cas (3) — seules les limites de certaines suites croissantes d'étapes admettent un codage par un entier, à savoir les limites de suites calculables d'étapes. Cette restriction est cependant nécessaire, dans la mesure où il n'y a qu'une quantité dénombrable d'entiers, tandis qu'il existe une quantité indénombrable de suites. La figure 1.2 illustre l'ordre $<_o$ sur $\mathcal{O}$.

**Notation**

On écrira parfois $a \leqledo b$ pour des éléments $a, b \in \mathcal{O}$ pour signifier $a <_o b$
ou $a = b$. On parlera parfois du « $\mathcal{O}$ de Kleene » pour parler de l'en-
semble défini ci-dessus.

Le $\mathcal{O}$ de Kleene peut être à présent utilisé pour mener proprement les
itérations transfinies du saut, effectuées traditionnellement avec la lettre $H$.
<figure><img src="image_164.png" /><figcaption>FIGURE 1.2 – Ordre partiel $<_o$ sur $\mathcal{O}$</figcaption></figure>

**Définition 1.3.** On définit les itérations transfinies $H_a$ du saut pour les éléments $a \in \mathcal{O}$ :

(1) $H_1 = \emptyset$;

(2) $H_{2a} = H'_{a}$;

(3) $H_{3 \times 5^e} = \bigoplus_n H_{\Phi_e(n)}$. $\diamond$

Notons l'avantage de l'utilisation des codes : étant donné $a \in \mathcal{O}$, on peut énumérer tous les éléments $b \in \mathcal{O}$ tels que $b <_o a$. En effet, si $a$ est de la forme $2^b$, on énumère $b$, et l'on relance récursivement l'énumération sur $b$; et, si $a$ est de la forme $3 \times 5^e$, on énumère $\Phi_e(n)$ pour tout $n$, et l'on relance petit à petit récursivement l'énumération sur chaque $\Phi_e(n)$.

De ce fait, étant donné un ensemble $H_a$, sous réserve de la connaissance du code $a$, on peut alors énumérer tous les couples $(H_b, b)$ pour $b <_o a$, en ajoutant à notre énumération l'ensemble $H_b$ correspondant, que l'on peut retrouver de manière calculable à partir de $H_a$ et de $a$. On a en particulier $H_b <_T H_a$ pour $b <_o a$. On pourrait en fait montrer avec un peu plus de travail que l'on a $H_b <_m H_a$ pour $b <_o a$. Cela sera une conséquence du corollaire 28-1.14.

**Remarque**

Toute itération finie du saut Turing est représentée de manière unique à l'aide de la définition 1.3. En effet, pour tout $n$, $\emptyset^{(n)} = H_a$ avec

$$a = \underbrace{2^{2^{\cdot^{2^1}}}}_{n \text{ copies de } 2}.$$

En revanche, il existe plusieurs codes de $\emptyset^{(\omega)}$, car une même fonction calculable possède une infinité de codes Turing. Ainsi, si $\Phi_e = \Phi_i$ et que $3 \times 5^e \in \mathcal{O}$, alors $3 \times 5^i \in \mathcal{O}$, et $H_{3 \times 5^e} = H_{3 \times 5^i}$. Comme expliqué précédemment, si l'on considère les itérations de la définition 1.3 du
point de vue des degrés Turing, il existe également des fonctions $\Phi_e$ et $\Phi_i$ qui ne sont pas équivalentes, mais telles que $H_{3\times5^e} \equiv_T H_{3\times5^i}$. Par exemple, si $3\times5^e \in O$ et $\Phi_i(n) = \Phi_e(n+1)$ pour tout $n$, alors $3\times5^i \in O$, et $H_{3\times5^e} \equiv_T H_{3\times5^i}$.

## 2. Ordinaux

Nous allons voir que les éléments de $O$ sont utilisés en quelque sorte comme une extension des entiers, que l’on appelle *ordinaux* ou *nombres transfinis*. Les premiers codes de $O$ sont de fait linéairement ordonnés comme les entiers : $1 < 2 < 2^2 < 2^{2^2} < \dots$.

Pour cette raison, on dira aussi que $1 \in O$ est un code de $\emptyset$, que $2 \in O$ est un code de $1$, etc., et l’on écrira $|1| = \emptyset, |2| = 1$, et de manière générale si $|a| = \mathfrak{n}$, alors $|2^a| = \mathfrak{n} + 1$. Les notations $0, 1, 2, \dots$ et $\mathfrak{n}$ désignent les *ordinaux finis* et sont utilisées pour éviter toute confusion avec leur codes correspondants.

Considérons à présent un code de fonction calculable $e$ tel que $\Phi_e(n)$ renvoie $a_n \in O$ pour tout $n$ et où $|a_n| = \mathfrak{n}$. Alors, $3 \times 5^e$ code en quelque sorte pour un *nombre transfini*, le plus petit $\ll$ nombre $\gg$ plus grand que chaque entier. Appelons ce nombre $\omega$. Les éléments de $O$ codant pour $\omega$ ne sont pas uniques. Considérons $e_1, e_2$ deux codes de fonctions telles que $|\Phi_{e_1}(n)| = 2\mathfrak{n}$ et $|\Phi_{e_2}(n)| = 2\mathfrak{n} + 1$. Les éléments $3 \times 5^{e_1}$ et $3 \times 5^{e_2}$ codent moralement pour la même chose, en l'occurrence $\omega$, le plus petit nombre transfini plus grand que chaque entier. Comme expliqué dans la remarque 1.1, on a $H_{3 \times 5^{e_1}} \equiv_T H_{3 \times 5^{e_2}}$.

On aimerait une manière de pouvoir rendre compte formellement de cette équivalence. C'est précisément ce que permettent de faire les *ordinaux*. Si le concept fut introduit par Cantor en 1883, ce n'est toutefois pas sa définition que nous présenterons tout de suite, mais celle de von Neumann imaginée en 1923, qui présente l'avantage d'être plus concrète.

### 2.1. Approche de von Neumann : les ordinaux ensemblistes

John von Neumann définit les ordinaux de manière ensembliste. En substance, on a le principe suivant.

**Principe des ordinaux de von Neumann**

Un ordinal est donné par l'ensemble des ordinaux qui le précèdent, l'ordre sur les ordinaux étant alors établi par leur relation d'appartenance.
Une implémentation de ce principe peut se faire de manière informelle via
la construction suivante.

(1) L'ensemble vide $\emptyset$ est un ordinal.

(2) Si $\alpha$ est un ordinal, alors $\alpha \cup \{\alpha\} = \{\beta : \beta = \alpha \text{ ou } \beta \in \alpha\}$ est l'ordinal successeur de $\alpha$.

(3) Soit $(\alpha_i)_{i \in I}$ une collection d'ordinaux n'ayant pas de plus grand élément pour la relation d'appartenance. Alors, $\bigcup_{i \in I} \alpha_i = \{\beta : \exists i \in I \beta \in \alpha_i\}$ est un ordinal limite.

On vérifie effectivement que si $\alpha$ est l'ensemble des ordinaux qui le précède,
alors $\alpha \cup \{\alpha\}$ est un ensemble qui contient exactement $\alpha$ et tous les ordi-
naux qui précèdent $\alpha$: il s'agit de l'ordinal successeur de $\alpha$. De la même
manière, si chaque $\alpha_i$ pour $i \in I$ est l'ensemble des ordinaux qui le précède,
alors $\bigcup_{i \in I} \alpha_i$ est bien un ensemble d'ordinaux clos par le bas : il contient
tous les ordinaux qui précèdent $\bigcup_{i \in I} \alpha_i$ au sens de la relation d'apparte-
nance.

Moralement « l'ensemble » des ordinaux est le plus petit ensemble conte-
nant $\emptyset$ et qui est clos par (2) et (3) de notre construction informelle. Nous
verrons toutefois rapidement que « la collection » des ordinaux n'est pas
un ensemble, et nous verrons bientôt une manière plus rigoureuse de les
définir. Néanmoins, la construction précédente contient tout ce qu'il faut
pour comprendre ce que sont les ordinaux.

**Exemple 2.1.** Les premiers ordinaux sont en correspondance directe avec les entiers naturels. Pour ces raisons, on les notera de la manière suivante.

$$
\Delta 0 = \emptyset
$$

$$
\Delta 1 = \{0\} = \{\emptyset\}
$$

$$
\Delta 2 = \{0, 1\} = \{\emptyset, \{\emptyset\}\}
$$

$$
\Delta 3 = \{0, 1, 2\} = \{\emptyset, \{\emptyset\}, \{\emptyset, \{\emptyset\}\}\}
$$

▷ ...

Il est une pratique commune d'identifier les entiers naturels et leurs or-
dinaux correspondants : il s'agit d'un « codage » du même concept.

Le premier ordinal limite est donné par $\omega = \{0, 1, 2, \dots\}$.

Nous voyons à présent la définition formelle des ordinaux, qui nécessitera
un peu de travail pour se ramener à l'intuition que nous en avons donnée
et que nous rappelons ici : un ordinal est l'ensemble des ordinaux qui le
précèdent.
<figure><img src="image_165.png" /><figcaption>FIGURE 2.3 – Représentation des premiers ordinaux</figcaption></figure>

**Définition 2.2 (von Neumann).** Un ensemble $\alpha$ est un ordinal si

(1) $\alpha$ est *transitif* : $\forall \beta \in \alpha, \beta \subseteq \alpha$;

(2) la relation d'appartenance sur $\alpha$ est un ordre total strict;

(3) toute partie non vide de $\alpha$ possède un plus petit élément pour l'appartenance.

On dira qu'un ordinal $\alpha$ est plus petit qu'un ordinal $\beta$, et l'on écrira $\alpha < \beta$ si $\alpha \in \beta$. ◇

Notons que la relation d'appartenance coïncidant avec la relation d'ordre, la condition (1) est équivalente à dire que l'ensemble $\alpha$ est clos par le bas : pour tout $\beta \in \alpha$, pour tout $\gamma < \beta$, $\gamma \in \alpha$. Voyons à présent quelques propositions permettant de clarifier la structure des ordinaux. La première proposition peut sembler curieuse, et n'a de fait d'intérêt qu'en l'absence de l'axiome de fondation (nous renvoyons le lecteur à la section 9-4 pour plus de détails sur ce sujet).

**Proposition 2.4.** Pour tout ordinal $\alpha$, on a $\alpha \notin \alpha$.

*

**PREUVE.** Supposons $\alpha \in \alpha$. Alors, $\alpha$ contient un élément (lui-même, $\alpha$) qui s'appartient à lui-même. La relation d'appartenance n'est donc pas un ordre strict sur $\alpha$ puisque que $\alpha$ contient un élément $x$ tel que $x \in x$ (l'ordre n'est donc pas strict). Donc, $\alpha$ n'est pas un ordinal. ■

Nous voyons à présent une première direction permettant de revenir à notre intuition.
**Proposition 2.5.** Un ordinal $\alpha$ est toujours l'ensemble de tous les ordinaux plus petits que lui. ★

PREUVE. Par définition, si $\beta < \alpha$, alors $\beta \in \alpha$. Il reste à montrer que $\alpha$ ne contient que des ordinaux. Soit $x \in \alpha$, et soient $z \in y \in x$. Comme $\alpha$ est transitif, alors $z, y \in \alpha$. Comme la relation d'appartenance est une relation d'ordre sur $\alpha$, alors $z \in x$. Donc, $x$ est transitif. Puisque $x \subseteq \alpha$ et que la relation d'appartenance sur $\alpha$ est un ordre total strict, alors elle l'est également restreinte à $x$. Enfin, par transitivité, toute partie non vide de $x$ est aussi une partie non vide de $\alpha$, et contient donc un plus petit élément. Donc, $x$ est un ordinal. ■

Nous montrons à présent que les ordinaux eux-mêmes sont totalement ordonnés entre eux.

**Théorème 2.6**

Soient $\alpha_1, \alpha_2$ deux ordinaux distincts. Alors, $\alpha_1 < \alpha_2$ ou $\alpha_2 < \alpha_1$.

PREUVE. Montrons d'abord la chose suivante. Pour tous ordinaux distincts $\alpha, \beta$, on a $\alpha \subseteq \beta$ implique $\alpha < \beta$. Comme $\alpha \neq \beta$, alors $\beta \setminus \alpha$ est non vide, et possède donc un plus petit élément $\gamma$. Par minimalité de $\gamma$, tous ses éléments sont des éléments de $\alpha$. On a donc $\gamma \subseteq \alpha$. Soit à présent $x \in \alpha \subseteq \beta$. Comme la relation d'appartenance est totale sur $\beta$, on a alors $x \in \gamma$ ou $\gamma \in x$ ou $\gamma = x$. Si $\gamma = x$, alors $\gamma \in \alpha$, ce qui contredit le choix de $\gamma$. De la même manière, si $\gamma \in x \in \alpha$, alors par transitivité de $\alpha$ on aurait $\gamma \in \alpha$, ce qui est aussi une contradiction. Donc, $x \in \gamma$, si bien que $\alpha \subseteq \gamma$, et donc $\alpha = \gamma$, égalité qui implique $\alpha < \beta$.

Passons à la preuve. Soit $A = \alpha_1 \setminus \alpha_2$. Si $A$ est vide, alors $\alpha_1 \subseteq \alpha_2$, et donc $\alpha_1 < \alpha_2$. Sinon, $A$ a un plus petit élément $\beta$ tel que $\beta \notin \alpha_2$. En particulier, tous les éléments de $\beta$ appartiennent à $\alpha_2$, et donc $\beta \subseteq \alpha_2$. On ne peut avoir par définition $\beta < \alpha_2$. Donc, $\beta = \alpha_2$ et $\alpha_2 < \alpha_1$. ■

Le théorème suivant permet de complètement se ramener à notre intuition de départ.

**Théorème 2.7**

Un ensemble $\alpha$ est un ordinal si, et seulement si, c'est un ensemble d'ordinaux clos par le bas.

PREUVE. Nous avons vu avec la proposition 2.5 qu'un ordinal $\alpha$ est toujours l'ensemble de tous les ordinaux plus petits que lui. Soient $\gamma \in \beta \in \alpha$. Par transitivité, $\gamma \in \alpha$, d'où il résulte que $\alpha$ est clos par le bas.
Supposons à présent que $\alpha$ soit un ensemble d'ordinaux clos par le bas. Soient $\gamma \in \beta \in \alpha$. Comme $\alpha$ est clos par le bas, alors $\gamma \in \alpha$. Ainsi, $\alpha$ est transitif. D'après la proposition 2.4, la relation d'appartenance sur $\alpha$ est anti-réflexive. D'après le théorème 2.6, elle est totale. Étant donné que $\alpha$ ne contient que des ordinaux qui sont des ensembles transitifs, la relation d'appartenance est aussi transitive. Elle est donc nécessairement aussi anti-symétrique, car si $x \in y$ et $y \in x$, alors par transitivité $x \in x$, ce qui contredit l'anti-réflexivité. La relation d'appartenance sur $\alpha$ est donc un ordre total strict. Enfin, soit $A \subseteq \alpha$ un ensemble non vide. Prenons $\beta \in A$. Ou bien $\beta$ est le plus petit élément de $A$, auquel cas il n'y a rien à vérifier ; ou bien non, auquel cas $A \cap \beta \subseteq \beta$ est non vide, et comme $\beta$ est un ordinal, alors $A \cap \beta$ possède un plus petit élément, qui est aussi le plus petit élément de l'ensemble $A$.

■

**Corollaire 2.8**

(1) Soit $\alpha$ un ordinal. Alors, $\alpha \cup \{\alpha\}$ est un ordinal.

(2) Soit $\{\alpha_i\}_{i \in I}$ une collection d'ordinaux. Alors, $\bigcup_{i \in I} \alpha_i$ est un ordinal.

PREUVE. Si $\alpha$ est un ordinal, alors $\alpha \cup \{\alpha\}$ est un ensemble d'ordinaux clos par le bas. De la même manière, si $\{\alpha_i\}_{i \in I}$ une collection d'ordinaux, alors $\bigcup_{i \in I} \alpha_i$ est un ensemble d'ordinaux clos par le bas.

■

**Notation**

Pour un ordinal $\alpha$, on notera $\mathrm{succ}(\alpha)$ pour $\alpha \cup \{\alpha\}$, l'ordinal successeur de $\alpha$. Pour une collection d'ordinaux $(\alpha_i)_{i \in I}$, on notera $\sup_{i \in I} \alpha_i$ pour l'ordinal $\bigcup_{i \in I} \alpha_i$ (qui est limite si $(\alpha_i)_{i \in I}$ n'a pas de plus grand élément).

Notons que tout ordinal $\alpha$ est soit $\emptyset$, soit un ordinal successeur, soit un ordinal limite. En effet, si $\alpha \neq \emptyset$, alors $\alpha$ admet au moins un élément. Si $\alpha$ admet un élément maximal $\beta$, alors $\alpha = \mathrm{succ}(\beta)$. Sinon, $\alpha = \sup_{\beta \in \alpha} \beta$. Nous pouvons donc raisonner sur les ordinaux par analyse de cas sur cette trichotomie.

**Notation**

On note $\mathrm{Ord} \ll \text{l'ensemble} \gg$ de tous les ordinaux.

Le terme $\ll \text{ensemble} \gg$ de la notation précédente a été mis entre guillemet. La raison est la suivante.

**Proposition 2.9.** La classe $\mathrm{Ord}$ n'est pas un ensemble.

*

PREUVE. Il est aisé de voir que la classe $\mathrm{Ord}$ des ordinaux, munie de la relation d'appartenance $\in$, satisfait les propriétés (1) à (3) de la définition 2.2.
On en déduit que $\mathbf{Ord}$ est un ordinal, et donc que $\mathbf{Ord} \in \mathbf{Ord}$, ce qui contre-dit la proposition 2.4. Cela est réglé de la manière suivante : $\mathbf{Ord}$ n’est pas un ensemble, et n’est donc pas sujet à la définition 2.2. ■

Si $\mathbf{Ord}$ n’est pas un ensemble, alors quelle est sa nature ? Il est aisé de construire une formule $F(x)$ du premier ordre de la théorie des ensembles telle que $F(x)$ est vraie ssi $x$ est un ordinal. Pour autant, on ne peut pas en déduire que l’ensemble des éléments qui satisfont cette formule existe : afin d’éviter le paradoxe de Russell, l’axiome de compréhension nécessite un ensemble pré-existant : pour tout ensemble $a$ et toute formule $G(x)$, l’ensemble $\{x \in a : G(x)\}$ existe, mais rien ne garantit l’existence de l’ensemble $\{x : G(x)\}$, et dans le cas de la formule $F(x)$ définissant les ordinaux, la proposition précédente montre que l’ensemble $\{x : F(x)\}$ n’existe pas, sous peine d’arriver à une contradiction. En quelque sorte, $\mathbf{Ord}$ est « trop gros » pour être un ensemble. On parlera alors de classes (à ne pas confondre avec notre utilisation du terme classe qui désigne tout au long de ce livre les sous-ensembles de $2^\mathbb{N}$) :

**Définition 2.10.** En théorie des ensembles une classe est une collection d’éléments qui satisfont une formule de la théorie des ensembles. ◇

Nous voyons tout de suite un exemple de l’utilisation de la notion de classe, qui sera réutilisée de temps à autre dans le cadre de notre manipulation des ordinaux.

**Proposition 2.11.** Toute classe non vide d’ordinaux possède un plus petit élément. ★

PREUVE. Soit $F(x)$ une formule de la théorie des ensembles. Supposons que pour au moins un ordinal $\alpha$ on ait $F(\alpha)$. Alors, l’ensemble $A$ des ordinaux $\beta \in \text{succ}(\alpha)$ tels que $F(\beta)$ est vrai, est non vide. Comme $\text{succ}(\alpha)$ est un ordinal, alors $A$ possède un plus petit élément, qui est aussi le plus petit élément $\beta$ tel que $F(\beta)$. ■

## 2.2. Approche de Cantor : les bons ordres

La définition des ordinaux de von Neumann s’est imposée jusqu’à aujourd’hui comme standard. Le concept n’a toutefois pas été inventé par von Neumann, mais par Cantor [27], qui l’introduisit en 1883 dans la continuation de son travail sur l’infini et la cardinalité. Les nombres transfinis de von Neumann sont pratiques en ce sens qu’il s’agit d’objets « concrets ». Nous allons à présent dépouiller ces derniers de cette représentation concrète afin d’en dévoiler l’essence. Cette montée en abstraction fut le point de départ de la définition de Cantor : ce qui caractérise un ordinal, c’est son *type d’ordre*, c’est-à-dire l’ordre qu’il représente, à isomorphisme près.
**Définition 2.12.** Un ordre $<_R \subseteq A \times A$ strict sur un ensemble $A$ est bien fondé s'il n'existe pas de suite infinie $(a_n)_{n \in \mathbb{N}}$ telle que $a_{n+1} <_R a_n$. Si de plus $<_R$ est total, on dira que $<_R$ est un bon ordre. ◇

Voyons à présent un petit lemme qui permet de rapprocher la définition de bon ordre présentée ci-dessus, avec la définition des ordinaux de von Neumann.

**Lemme 2.13.** Soit $<_R \subseteq A \times A$ un ordre. Les deux énoncés suivants sont équivalents :

(1) il n'existe pas de suite infinie $(x_n)_{n \in \mathbb{N}}$ de $A$ telle que $x_{n+1} <_R x_n$ pour tout $n$;

(2) tout sous-ensemble $B \subseteq A$ possède un élément minimal.

*

PREUVE. Montrons (1) $\rightarrow$ (2), par contraposition. Supposons qu'il existe un sous-ensemble infini $B \subseteq A$ ne possédant pas d'élément minimal, c'est-à-dire tel que, pour tout $a \in B$, il existe $b \in B$ tel que $b <_R a$. On peut alors aisément construire une suite infinie $(x_n)_{n \in \mathbb{N}}$ de $B \subseteq A$ telle que $x_{n+1} <_R x_n$.

Montrons (2) $\rightarrow$ (1) de la même manière. Supposons qu'il existe une suite infinie $(x_n)_{n \in \mathbb{N}}$ de $A$ telle que $x_{n+1} <_R x_n$. Alors, cette suite constitue un sous-ensemble $B \subseteq A$ ne possédant pas d'élément minimal. ■

Via notre nouveau vocabulaire, nous pouvons définir les ordinaux de von Neumann comme suit.

**Ordinaux de von Neumann**

Un ordinal de von Neumann est un ensemble transitif sur lequel la relation d'appartenance est un bon ordre.

Cantor définit les ordinaux comme étant les classes d'équivalence des bons ordres, via la relation d'équivalence d'isomorphisme entre les ordres.

**Définition 2.14.** Deux ordres $<_1 \subseteq A_1 \times A_1$ et $<_2 \subseteq A_2 \times A_2$ sur $A_1$ et $A_2$ respectivement sont *isomorphes* s'il existe une bijection $f : A_1 \rightarrow A_2$ telle que $x <_1 y$ ssi $f(x) <_2 f(y)$. ◇

Nous allons maintenant montrer que la définition de von Neumann constitue en quelque sorte un représentant canonique de ces classes d'équivalence. Si un ordinal selon von Neumann n'est pas à proprement parler une relation d'ordre, il en induit une via la relation d'appartenance sur les éléments que contiennent l'ordinal, et cette relation d'ordre est un bon ordre.
**Théorème 2.15**

Soit $<_R \subseteq A \times A$ un bon ordre sur un ensemble $A$. Alors, il existe un ordinal de von Neumann $\alpha$ et un isomorphisme $f : A \to \alpha$, pour lequel on a donc $x <_R y$ ssi $f(x) < f(y)$.

**PREUVE.** On définit la fonction $f$ sur $A$ par $f(y) = \{f(x) : x <_R y\}$. Une telle fonction $f$ est définie par récurrence transfinie sur le bon ordre $<_R$. Nous verrons la validité d'une telle définition via le corollaire 3.10 de la section suivante. Supposons par l'absurde qu'il existe $x \in A$ tel que $f(x)$ n'est pas un ordinal. Comme $<_R$ est un bon ordre, il existe un tel $x$ qui est minimal. En particulier, pour tout $y <_R x$, l'ensemble $f(y)$ est un ordinal. Donc, $f(x)$ est un ensemble d'ordinaux. Montrons que $f(x)$ est clos par le bas. Soit $\alpha \in f(y) \in f(x)$. Par définition de $f$, $\alpha = f(z)$ pour $z <_R y$. Par transitivité de $<_R$, on a $z <_R x$, et donc $f(z) \in f(x)$. Ainsi, $f(x)$ est bien clos par le bas, et est donc un ordinal, contradiction. Donc, pour tout $x \in A$, l'ensemble $f(x)$ est un ordinal. On montre de même que l'ensemble $\{f(x) : x \in A\}$ est clos par le bas, et donc qu'il s'agit d'un ordinal que nous appellerons $\alpha$.

Il est clair par définition que $x <_R y$ implique $f(x) \in f(y)$. Réciproquement, si l'on n'a pas $x <_R y$, alors $x = y$ ou $y <_R x$ (car $<_R$ les bons ordres sont totaux), d'où $f(x) = f(y)$ ou $f(y) \in f(x)$. On n'a donc pas $f(x) \in f(y)$. Étant donné que $x <_R y$ ssi $f(x) < f(y)$, et que $x \neq y$ implique $x <_R y$ ou $y <_R x$, on obtient que $f$ est injectif. Donc, $f$ est un isomorphisme de $A$ vers son image. ■

**Notation**

Étant donné un bon ordre $< \subseteq A \times A$ sur $A$, on écrit $|<|$ pour dénoter l'ordinal $\alpha$ dont l'ordre des éléments est isomorphe à $<$.

Voici des exemples sur la représentation des ordinaux par des ordres sur $\mathbb{N}$.

**Exemple 2.16.**

▷ L'ordinal $\aleph \in \omega$ correspond au bon ordre $0 < 1 < \dots < n - 1$.

▷ L'ordinal $\omega$ correspond à l'ordre de tous les entiers. Pour continuer il nous faut alors changer l'ordre naturel des entiers.

▷ L'ordinal $\text{succ}(\omega)$ correspond au bon ordre $1 < 2 < 3 < \dots < 0$.

▷ L'ordinal $\sup\{\text{succ}(\omega), \text{succ}(\text{succ}(\omega)), \text{succ}(\text{succ}(\text{succ}(\omega))), \dots\}$ correspond au bon ordre $0 < 2 < 4 < 6 < \dots < 1 < 3 < 5 < 7 < \dots$.

Tout comme il n'y a pas qu'un seul code de $\mathcal{O}$ pour un même ordinal, il n'y a pas non plus qu'un seul bon ordre pour un même ordinal. Par exemple, l'ordinal $\omega$ correspond également au bon ordre $1 < 0 < 2 < 3 < 4 < \dots$.
# 3. Induction et récurrence transfinie

Les ordinaux ont plusieurs intérêts. Nous verrons par exemple dans la section 4.1 qu'ils peuvent, à l'aide de l'axiome du choix, servir de socle à une approche unifiée de la cardinalité des ensembles. Ils permettent également de formaliser les itérations transfinies. C'est ce dernier aspect que nous développons dans cette section.

## 3.1. Exemple avec la hiérarchie borélienne

Souvenons-nous par exemple de la définition 17-3.1 sur les classes $\Sigma_n^0$ et $\Pi_n^0$ de la hiérarchie borélienne.

Cette définition est en fait incomplète, car elle ne capture pas toutes les classes boréliennes, dont nous donnons ci-après la définition complète.

**Définition 3.1 (Classes boréliennes)**

La collection des classes Boréliennes de $2^N$ est la plus petite collection contenant les ouverts et les fermés, et qui est close par complémentaire et réunion dénombrable. ◇

Selon cette définition, une réunion dénombrable $\bigcup_n B_n$, où chaque $B_n$ est une classe $\Pi_n^0$, est bien une classe borélienne. Toutefois, si chaque $B_n$ est un $\Pi_n^0$ propre, c'est-à-dire non $\Sigma_n^0$ et en particulier non $\Pi_{n-1}^0$, alors $\bigcup_n B_n$ n'est elle-même $\Sigma_m^0$ pour aucun $m \in \mathbb{N}$ : elle est en fait $\Sigma_\omega^0$, et il est nécessaire d'utiliser les ordinaux pour capturer les complexités possibles de classes boréliennes.

<figure><img src="image_166.png" /><figcaption>FIGURE 3.2 – Hiérarchie borélienne transfinie. Ici, $\omega + n$ dénote le n-ième successeur de $\omega$ (voir la définition 3.5 à venir).</figcaption></figure>
**Définition 3.3 (Hiérarchie borélienne)**

La hiérarchie borélienne est définie par induction sur les ordinaux.

▷ Une classe $\Sigma_1^0$ est un ouvert de $2^N$.

▷ Pour $\alpha$ ordinal, une classe $\Pi_\alpha^0$ est le complémentaire d'une classe $\tilde{\Sigma}_\alpha^0$.

▷ Soit $\alpha = \text{succ}(\beta)$ un ordinal successeur. Une classe $\tilde{\Sigma}_\alpha^0$ est une réunion dénombrable de classes $\Pi_\beta^0$.

▷ Soit $\alpha$ un ordinal limite. Une classe $\tilde{\Sigma}_\alpha^0$ est une réunion $\bigcup_n \mathcal{B}_n$ dénombrable, où chaque $\mathcal{B}_n$ est une classe $\Pi_{\tilde{\beta}_n}^0$ telle que $\sup_n \beta_n = \alpha$. ◇

Notons qu'en l'absence d'ambiguïté possible et afin de rester cohérent avec les notations précédentes, nous écrivons $\Sigma_1^0$ et non $\tilde{\Sigma}_1^0$. Il est possible de raccourcir un peu la définition précédente en rassemblant les cas limites et successeurs en un seul cas, ce qui sera parfois fait dans les différentes hiérarchies à venir.

**Définition 3.4 (Hiérarchie borélienne (déf. alternative))**

La hiérarchie borélienne est définie par induction sur les ordinaux.

▷ Une classe $\Sigma_1^0$ est un ouvert de $2^N$.

▷ Pour $\alpha$ ordinal, une classe $\Pi_\alpha^0$ est le complémentaire d'une classe $\tilde{\Sigma}_\alpha^0$.

▷ Soit $\alpha$ un ordinal. Une classe $\tilde{\Sigma}_\alpha^0$ est une réunion dénombrable $\bigcup_n \mathcal{B}_n$, où chaque $\mathcal{B}_n$ est une classe $\Pi_{\tilde{\beta}_n}^0$ telle que $\sup_n (\text{succ}(\beta_n)) = \alpha$. ◇

Notons que la hiérarchie borélienne est définie ci-dessus sur tous les ordinaux. En pratique, on suppose en général l'axiome du choix dénombrable qui implique que seuls les ordinaux dénombrables servent à la création de classes boréliennes. Nous verrons cela un peu plus en détail dans la section 4.

## 3.2. Exemple avec l'arithmétique des ordinaux

Nous voyons à présent un autre exemple de définition par récurrence sur les ordinaux, avec les extensions des opérations arithmétiques usuelles. L'addition, la multiplication et l'exponentiation se définissent de manière standard par récurrence sur les entiers, en traitant le cas de base, et le cas successeur. Pour leur extension aux ordinaux, on y rajoute une règle pour le cas limite. Comme nous l'avons vu dans l'exemple 2.1, les premiers ordinaux peuvent s'identifier aux entiers naturels, munis de leur ordre standard. Les définitions suivantes montrent que les ordinaux peuvent être vus comme une extension des entiers naturels. Les cas 1 et 2 des définitions suivantes correspondent aux définitions par récurrence de l'addition, la
multiplication et l'exponentiation sur les entiers. Par exemple, $n + 0 = 0$ et $n + (m + 1) = (n + m) + 1$ définissent complètement l'addition sur $\mathbb{N}$. Le cas 3, à savoir le cas limite, permet de « dépasser » la barrière de $\omega$, et continuant l'itération sur des ordinaux arbitraires.

**Définition 3.5**

$$1. \alpha+0 = \alpha,$$

$$2. \alpha+\mathrm{succ}(\beta) = \mathrm{succ}(\alpha + \beta),$$

$$3. \alpha+\beta = \sup_{\gamma \in \beta}(\alpha+\gamma) \text{ si } \beta \text{ limite.}$$

$$1. \alpha \times 0 = 0,$$

$$2. \alpha \times \mathrm{succ}(\beta) = (\alpha \times \beta)+\alpha,$$

$$3. \alpha \times \beta = \sup_{\gamma \in \beta}(\alpha \times \gamma) \text{ si } \beta \text{ limite.}$$

$$1. \alpha^0 = 1,$$

$$2. \alpha^{\mathrm{succ}(\beta)} = (\alpha^{\beta}) \times \alpha,$$

$$3. \alpha^{\beta} = \sup_{\gamma \in \beta}(\alpha^{\gamma}) \text{ si } \beta \text{ limite.}$$

<figure><img src="image_167.png" /></figure>

Les définitions précédentes ne sont pas forcément évidentes à appréhender et le lecteur peut consulter la figure 3.6 pour une représentation graphique des premiers ordinaux ainsi que de l'utilisation de la multiplication et de la puissance ordinale.

Notons que l'addition et la multiplication ne sont plus commutatives dans les ordinaux : $\omega + 2 = \mathrm{succ}(\mathrm{succ}(\omega))$ et $2 + \omega = \sup_{n \in \omega}(2 + n) = \omega$.

La raison clef qui fait que les définitions précédentes sont valides est le fait que les ordinaux sont bien ordonnés, et la difficulté supplémentaire par rapport à l'induction sur les entiers est la compréhension des étapes limites. Si l'on veut effectuer l'opération $\alpha + \mathrm{succ}(\beta)$, où $\beta$ est limite, nous avons besoin d'après la définition précédente de connaître $\alpha + \beta$, et pour connaître $\alpha + \beta$ nous avons alors besoin de connaître $\alpha + \gamma$ pour tout $\gamma < \beta$, et ainsi de suite pour chacune de ces additions $\alpha + \gamma$. Contrairement à l'induction sur les entiers, la définition de $\alpha + \mathrm{succ}(\beta)$ dépend ici d'une infinité « d'étapes précédentes ». L'addition est néanmoins bien définie, car l'ordre sur les ordinaux est bien fondé : si la valeur de $\alpha + \beta_1$ a besoin de la valeur de $\alpha + \beta_2$, laquelle a besoin de la valeur de $\alpha + \beta_3$, et ainsi de suite pour $\beta_1 > \beta_2 > \beta_3 > \dots$, on arrivera nécessairement à $\beta_n = 0$ pour un certain entier $n$.

Nous allons voir dans la prochaine section une justification formelle aux définitions par récurrence sur les ordinaux. Avant de nous y atteler, voici un petit exercice pour apprendre à manipuler un peu le transfini.

**Exercice 3.7. (★★)** Des Blarks — créatures bêtes et méchantes — se trouvent devant vous dans une file indienne transfinie indexée par tous les ordinaux successeurs. Il n'y a que $\omega$ Blarks pour le moment. Vous avez à votre disposition un marteau de guerre avec lequel vous devez écraser chaque Blark l'un après l'autre. Le problème est que dès que vous écrasez un
<figure><img src="image_168.png" /><figcaption>FIGURE 3.6 – Représentation des premiers ordinaux. Chaque barre représente un ordinal.</figcaption></figure>
Blork, un autre apparaît au fond de la file indienne. Ainsi, après écrasement du Blork numéro $\emptyset$, un autre apparaît en position $\omega + 1$. Après écrasement du Blork numéro 1, un autre apparaît en position $\omega + 2$, etc.

(1) À quelle étape transfinie aurez-vous enfin anéanti tous les Blorks ?

(2) Même question, mais cette fois-ci dès que vous écrasez un Blork, ce sont $\omega$ Blorks qui apparaissent au fond de la file indienne !

(3) Laissons de côté votre marteau, et supposons à présent qu'à chaque étape un éclair foudroie un Blork *au hasard*. À ce moment, si un Blork est bien foudroyé (ce qui est le cas s'il reste au moins un Blork) $\omega$ Blorks apparaissent au fond de la file indienne. Peut-on être sûr qu'à une certaine étape transfinie, il n'y aura plus de Blork ? Ou bien cela dépend-il du sort ? (Cette dernière question est difficile.) $\diamond$

### 3.3. Justification formelle de la récurrence ordinale

Commençons par une généralisation de l'induction arithmétique aux ordinaux : si une propriété $P$ est vraie sur $\emptyset$ et si le fait qu'elle soit vraie sur un entier $n$ implique qu'elle le soit sur l'entier $n + 1$, alors elle est vraie sur tout $n \in \mathbb{N}$. La proposition suivante étend ce principe aux ordinaux, et vient simplement du fait que l'ordre sur les ordinaux est bien fondé.

**Proposition 3.8 (Induction transfinie sur les ordinaux).** Soit $F(x)$ une formule du premier ordre, telle que pour tout ordinal $\alpha$, si $F(\beta)$ est vraie pour tout $\beta < \alpha$, alors $F(\alpha)$ est vraie. Alors, $F(\alpha)$ est vraie pour tout ordinal $\alpha$. $\star$

**PREUVE.** Supposons par l'absurde que $F$ ne soit pas vraie pour tous les ordinaux $\alpha$. D'après la proposition 2.11, il existe un plus petit ordinal $\alpha$ tel que $F(\alpha)$ est faux. En particulier, par minimalité de $\alpha$, on a $F(\beta)$ pour tout $\beta < \alpha$. Donc, $F(\alpha)$ est vraie, ce qui est une contradiction. $\blacksquare$

Nous avons vu avec la définition 3.5 des fonctions définies par récurrence sur les ordinaux. Tout comme dans le cas de l'induction, il s'agit formellement d'une extension de la récurrence sur les entiers : il est possible de définir une fonction $f : \mathbb{N} \to \mathbb{N}$ en réutilisant pour la définition de $f(n)$ des valeurs $f(0), \dots, f(n-1)$. Souvent, seules quelques valeurs précédentes de $f$ sont utilisées pour définir $f(n+1)$, comme dans la définition de la suite de Fibonacci : $f(0) = 0$, $f(1) = 1$ et $f(n+2) = f(n) + f(n+1)$, mais ce n'est pas toujours le cas. Par exemple, la définition 25-4.22 récursive des nombres de Catalan, $C_{n+1} = \sum_{i=0}^{n} C_i C_{n-i}$, utilise toutes les valeurs précédentes. Ce genre de définition est tout à fait valide, et le théorème général qui pourrait être formulé est que, pour toute fonction $g : \mathbb{N}^{<\mathbb{N}} \to \mathbb{N}$, il existe une unique fonction $f : \mathbb{N} \to \mathbb{N}$ telle que $f(n) = g(f|_n)$ pour tout $n$. Par exemple, une
telle fonction $g : \mathbb{N}^{<\mathbb{N}} \to \mathbb{N}$ correspondant à la suite de Fibonacci est donnée par $g(\sigma) = 0$ si $|\sigma| = 0$, $g(\sigma) = 1$ si $|\sigma| = 1$, et $g(\sigma) = \sigma(|\sigma| - 2) + \sigma(|\sigma| - 1)$ sinon. Nous voyons une extension de ce théorème, qui demande un peu de travail pour être démontré en toute généralité sur la classe des ordinaux. Pour commencer, nous avons besoin de manipuler des objets un peu plus généraux que les fonctions afin de traiter uniformément de l'induction sur tous les ordinaux, et nous introduisons pour cela le concept de relation fonctionnelle suivant.

**Notation**

Une relation fonctionnelle $G : \mathcal{V} \to \mathcal{V}$, où $\mathcal{V}$ est la classe de tous les ensembles, est simplement une formule du premier ordre telle que pour tout $x$ il existe un unique ensemble $r$ pour lequel $G(x, r)$ est vrai. On écrira alors $G(x) = r$.

Via cette nouvelle notation, le sens formel par exemple de l'addition de la définition 3.5 en théorie des ensemble est le suivant : pour tout $\alpha$, nous avons une relation fonctionnelle $G_{\alpha}$ telle que si $f$ est une fonction définie sur un ordinal $\gamma$ quelconque, alors

$$ 
\begin{align*} 
G_{\alpha}(f) &= \alpha \text{ dans le cas où } \gamma = 0, \\ 
G_{\alpha}(f) &= \text{succ}(f(\gamma')) \text{ dans le cas où } \gamma = \text{succ}(\gamma') \\ 
\text{et} \\ 
G_{\alpha}(f) &= \sup_{\gamma' < \gamma} f(\gamma') \text{ dans le cas où } \gamma \text{ est limite.} 
\end{align*} 
$$

Bien entendu, l'objectif est d'utiliser $G_{\alpha}$ non pas sur n'importe quelle fonction $f$, mais bien sur la fonction $f$ qui consiste déjà en l'addition de $\alpha$ à $\gamma'$ pour $\gamma' < \gamma$. Le théorème suivant nous garantit l'existence et l'unicité de cette fonction $f$ à chaque étape, ce qui donne la validité des définitions par induction sur la classe des ordinaux.

**Théorème 3.9 (Récursion transfinie sur les ordinaux)**

Soit $\mathcal{V}$ la classe de tous les ensembles. Soit $G : \mathcal{V} \to \mathcal{V}$ une relation fonctionnelle. Alors, il existe une unique relation fonctionnelle

$$ F : \text{Ord} \to \mathcal{V} \text{ telle que } F(\alpha) = G(F \upharpoonright_{\alpha}). $$

**PREUVE**

On définit le prédicat $H(\alpha, f)$ comme étant : $\ll \alpha$ est un ordinal, $f$ est une fonction de domaine $\alpha$ telle que, pour tout $\beta \in \alpha$, on a $G(f \upharpoonright_{\beta}) = f(\beta) \gg$.

La relation $F(\alpha) = r$ est alors définie comme étant : $\ll$ il existe une fonction $f$ telle que $H(\alpha, f)$ et $G(f) = r$. $\gg$
Montrons d'abord que pour tout ordinal $\alpha$, pour toutes fonctions $f_1, f_2$ définies sur $\alpha$, si $H(\alpha, f_1)$ et $H(\alpha, f_2)$, alors $f_1 = f_2$. D'après la proposition 3.8, il suffit de montrer que si c'est le cas pour tout $\beta < \alpha$, alors c'est le cas pour $\alpha$. Supposons effectivement que ce soit le cas pour tout $\beta < \alpha$. Soient $f_1, f_2$ telles que $H(\alpha, f_1)$ et $H(\alpha, f_2)$. Par définition de $H$, pour tout $\beta < \alpha$, on a $H(\beta, f_1 \upharpoonright_\beta)$ et $H(\beta, f_2 \upharpoonright_\beta)$ (où $f \upharpoonright_\beta$ désigne la restriction de $f$ aux éléments de $\beta$). Par hypothèse, on a donc $f_1 \upharpoonright_\beta = f_2 \upharpoonright_\beta$ pour tout $\beta < \alpha$. Si $\alpha$ est limite ou égal à $0$, on a donc $f_1 = f_2$. Si $\alpha = \text{succ}(\beta)$, alors $f_1(\beta) = G(f_1 \upharpoonright_\beta) = G(f_2 \upharpoonright_\beta) = f_2(\beta)$, et donc $f_1 = f_2$. Ainsi, pour tout ordinal $\alpha$, on a $H(\alpha, f_1)$ et $H(\alpha, f_2)$ implique $f_1 = f_2$.

Montrons que, pour tout ordinal $\alpha$, il existe un unique ensemble $r$ (égal à $G(F \upharpoonright_\alpha)$) tel que $F(\alpha) = r$. D'après la proposition 3.8, il suffit de montrer que si c'est le cas pour tout $\beta < \alpha$, alors c'est le cas pour $\alpha$. Supposons effectivement que ce soit le cas pour tout $\beta < \alpha$. Si $\alpha = \text{succ}(\beta)$, alors il existe une fonction $f_\beta$ telle que $H(\beta, f_\beta)$. Soit $r = G(f_\beta)$. La fonction $f$ définie sur $\alpha$ par $f(\beta) = r$ et par $f(\gamma) = f_\beta(\gamma)$ pour $\gamma < \beta$ existe et vérifie $H(\alpha, f)$. On a en particulier $F(\alpha) = r$, et cette valeur $r$ est unique. À présent, si $\alpha$ est limite ou égale à $0$, alors pour tout $\beta < \alpha$ il existe une unique fonction $f_\beta$ telle que $H(\beta, f_\beta)$. En utilisant l'axiome de remplacement, l'ensemble $\{f : \exists \beta < \alpha H(\beta, f)\}$ existe et, d'après le paragraphe précédent, la fonction $f = \bigcup_{\beta<\alpha} f_\beta$ est bien définie, est unique et vérifie $H(\alpha, f)$. On a alors $F(\alpha) = r$ pour $r = G(f)$. $\blacksquare$

D'après la correspondance entre ordinaux et bons ordres, on peut donc faire des définitions par récurrence transfinie sur n'importe quel bon ordre. Dans le corollaire suivant la notation $Y^<A$ désigne l'ensemble des segments initiaux de $A$ via la relation de bon ordre sur $A$.

**Corollaire 3.10 (Récursion transfinie)**

Soit $<_R$ un bon ordre sur un ensemble $A$ et soit $Y$ un ensemble.

Considérons $g : Y^<A \to Y$ une fonction. Il existe alors une unique fonction $f : A \to Y$ telle que pour tout $a \in A$, $f(a) = g(f \upharpoonright_a)$.

# 4. Ordinaux dénombrables et indénombrables

Par définition, un ordinal $\alpha$ est dénombrable s'il existe $f : \alpha \to \mathbb{N}$ bijective. Notons qu'il s'agit d'une bijection au sens ensembliste, c'est-à-dire que l'on n'impose pas que l'ordre soit respecté. De manière équivalente, un ordinal est dénombrable si l'on peut le représenter par un bon ordre sur $\mathbb{N}$.
**Proposition 4.1.** Soit $\alpha$ un ordinal. Alors, $\alpha$ est dénombrable si, et seulement si, il existe $X \in 2^N$ tel que la relation $<_X \subseteq \mathbb{N} \times \mathbb{N}$ définie par $a <_X b$ ssi $\langle a, b \rangle \in X$ est un bon ordre sur $\mathbb{N}$ pour lequel $|<_X| = \alpha$. ★

PREUVE. Supposons $\alpha$ dénombrable. Soit $f : \mathbb{N} \to \alpha$ une bijection. On définit $X$ par $\langle a, b \rangle \in X$ ssi $f(a) \in f(b)$. L'ordre $<_X$ est par définition isomorphe à celui des éléments de $\alpha$ pour la relation d'appartenance. On a donc $|<_X| = \alpha$.

Réciproquement, soit $X \in 2^N$ tel que la relation $<_X$ soit un bon ordre sur $\mathbb{N}$, pour lequel $\alpha = |<_X|$. D'après le théorème 2.15, on a $f : \mathbb{N} \to \beta$ qui est un isomorphisme entre $<_X$ et un certain ordinal $\beta$, lequel est donc tel que $|<_X| = \beta$. Par hypothèse, $|<_X| = \alpha$, et donc $\alpha = \beta$. Ainsi, on a bien une bijection entre $\mathbb{N}$ et $\alpha$. ■

On introduit à présent le plus petit ordinal non dénombrable.

**Notation**

Soit $\omega_1 = \{\alpha : \alpha$ est un ordinal dénombrable\}$.

Par le théorème 2.7, $\omega_1$ est un ordinal. Il ne peut pas en revanche être dénombrable, car on aurait alors $\omega_1 \in \omega_1$. On en conclut que l'ensemble des ordinaux dénombrables ne l'est pas. De plus, si $\alpha$ est un autre ordinal non dénombrable, on a nécessairement $\omega_1 < \alpha$ puisque par définition de $\omega_1$ on n'a pas $\alpha \in \omega_1$. Ainsi, $\omega_1$ est le plus petit ordinal non dénombrable. En pratique, nous travaillerons ici uniquement avec des ordinaux dénombrables, et donc représentables par un bon ordre sur $\mathbb{N}$.

**4.1. Les ordinaux et l'axiome du choix**

La présente section utilise les notions de théorie des ensembles développées dans la section 9-4. L'axiome du choix permet de montrer que tout ensemble peut être mis en bijection avec un ordinal, ce qui a pour conséquence les énoncés qui suivent.

▷ Tout ensemble est bien ordonnable : étant donné un ensemble $A$ quel-
conque, on peut construire un bon ordre $\subset \subseteq A \times A$ sur ses éléments.

▷ Le cardinalité de tout ensemble est comparable : cela vient directement du fait que pour tous ordinaux $\alpha, \beta$, soit $\alpha \subseteq \beta$ soit $\beta \subseteq \alpha$.

Au fond, l'axiome du choix est équivalent au fait que tout ensemble soit bien ordonnable. Ce n'est pas une équivalence dont le père des ordinaux et de la cardinalité des ensembles avait pleinement conscience. Cantor écrivit par exemple (voir [12, p. 143]) ce qui suit.
« Qu'il soit toujours possible de mettre tout ensemble bien défini sous la forme d'un ensemble bien ordonné est, me semble-t-il, une loi de la pensée, fondamentale, riche de conséquences et particulièrement remarquable par son universalité, loi sur laquelle je me promets de revenir dans un travail ultérieur. »

Cet extrait des écrits de Cantor illustre bien la part importante d'intuition qu'il y avait dans son travail. C'est finalement Zermelo, et non Cantor, qui reviendra sur « cette loi fondamentale de la pensée » dans un travail ultérieur, et qui comprendra que la possibilité de pouvoir bien ordonner tout ensemble nécessite un axiome, équivalent à l'axiome du choix.

**Théorème 4.2 (Zermelo)**

L'axiome du choix est équivalent au fait que tout ensemble est bien ordonné.

PREUVE. Rappelons pour cette preuve que $\mathcal{P}(A)$ dénote, pour un ensemble $A$, l'ensemble de ses parties. Supposons que l'on dispose de l'axiome du choix. Soit $A$ un ensemble que l'on souhaite bien ordonner. Il existe en particulier une fonction de choix $f$ définie sur $\mathcal{P}(A)\setminus\emptyset$ et qui à chaque partie non vide $B \subseteq A$ associe un élément de $B$. On définit par induction sur les ordinaux $g(0) = f(A)$, puis pour tout ordinal $\alpha$ tel que $A \cup_{\beta<\alpha} \{g(\beta)\}$ est non vide, on définit $g(\alpha) = f(A \cup_{\beta<\alpha} \{g(\beta)\})$. Par l'axiome de compréhension, soit $B \subseteq A$ le sous-ensemble des éléments de $A$ égaux à $g(\alpha)$ pour un certain ordinal $\alpha$. Par l'axiome de remplacement, soit $\alpha$ l'ordinal supremum des $g^{(-1)}(a)$ pour $a \in B$. Alors, on a forcément $A \setminus B$ vide, sinon $g(\text{succ}(\alpha))$ serait envoyé vers un élément de $A \setminus B$, ce qui contredit la définition de $B$. Donc, $g$ est une bijection d'un ordinal $\alpha$ vers $A$, via laquelle $A$ est bien ordonné.

Réciproquement, supposons tout ensemble bien ordonné. Soit $(A_i)_{i \in I}$ une collection d'ensembles non vides ; on met alors un bon ordre sur $\cup_{i \in I} A_i$, et l'on définit la fonction de choix $f$ en assignant à un élément $i \in I$ le plus petit élément de $x \in \cup_{i \in I} A_i$ tel que $x \in A_i$. $\blacksquare$

## 4.2. Axiome du choix dénombrable et boréliens

Zermelo a mis en évidence que l'axiome du choix était utilisé de manière intuitive et instinctive par plusieurs mathématiciens. Ainsi, par exemple le fait que tout espace vectoriel de dimension infinie ait une base, nécessite l'axiome du choix. Pour ce qui est de l'étude de la cardinalité des ensembles, l'axiome du choix est nécessaire pour montrer que la cardinalité de tout ensemble est comparable, ou par exemple pour montrer qu'une réunion
dénombrable d'ensembles dénombrables est dénombrable. Cette dernière propriété nous intéresse particulièrement, et ne nécessite qu'une version faible de l'axiome du choix.

Il est fréquent aujourd'hui, de la part des théoriciens des ensembles, de tra-
vailer avec l'axiome du choix restreint aux collections dénombrables d'en-
sembles (qui eux ne sont pas nécessairement dénombrables), sans forcément
admettre l'axiome du choix dans sa globalité : « Pour toute collection
d'ensembles ($\mathcal{A}_n$)$_{n \in \mathbb{N}}$, il existe une fonction de choix de $n$ vers $\mathcal{A}_n$ ».
La version dénombrable de l'axiome du choix permet de montrer que la
réunion dénombrable d'ensembles dénombrables est dénombrable. Elle a en
particulier la conséquence suivante : si $(\alpha_n)_{n \in \mathbb{N}}$ est une suite dénombrable
d'ordinaux dénombrables, alors $\sup_n \alpha_n$ est un ordinal dénombrable. Cela
implique en particulier que toute classe borélienne est toujours $\Sigma_\alpha^0$ pour
un certain $\alpha$ dénombrable. Cela est dû au fait que les boréliens se construi-
sent par réunion dénombrable de boréliens de rang inférieur. Aussi est-il im-
possible d'avoir une suite d'ordinaux dénombrables $(\beta_n)_{n \in \mathbb{N}}$ pour laquelle
on a $\sup_n \beta_n = \omega_1$. Il n'y a donc aucun nouveau borélien à l'étape $\omega_1$, et
donc aux étapes suivantes non plus. Indépendamment des axiomes utilisés,
on considérera toujours dans ce livre que les boréliens sont construits le
long des ordinaux dénombrables, et si par un hasard incongru une suite
d'ordinaux dénombrables $(\alpha_n)_{n \in \mathbb{N}}$ avec $\sup_n \alpha_n = \omega_1$ venait à profiter de
l'absence de cet axiome pour faire son apparition, alors une classe $\bigcup_n \mathcal{B}_n$,
où chaque $\mathcal{B}_n$ serait strictement $\Sigma_{\alpha_n}^0$, ne serait pas considérée comme
borélienne.

On sait aujourd'hui que la version dénombrable de l'axiome du choix n'en-
 traîne pas les situations contre-intuitives qui surviennent avec sa version
 indénombrable : l'axiome du choix dénombrable est par exemple compa-
tible avec le fait que tout ensemble soit mesurable (voir la section 17-4)
ou ait la propriété de Baire (voir la définition 10-4.9). Le sujet dépasse le
cadre de cet ouvrage, et le lecteur pourra consulter l'excellent ouvrage de
théorie des ensembles de Patrick Dehornoy [44] pour plus de détails.

4.3. Ordinaux et hypothèse du continu

L'ordinal $\omega_1$ représente en quelque sorte « le plus petit bon ordre » non dénombrable. Cet infini coïncide-t-il avec celui des nombres réels ? En d'autres termes, existe-t-il une bijection entre $\omega_1$ et $2^\mathbb{N}$ ? Cette question peut être vue comme une formulation de l'hypothèse du continu. La question originelle de Cantor portait sur les sous-ensembles de réels (si $\mathcal{A} \subseteq \mathbb{R}$ est indénombrable, existe-t-il une injection de $2^\mathbb{N}$ vers $\mathcal{A}$ ?). Si l'on admet l'axiome du choix, la question de Cantor est alors équivalente à celle de savoir s'il existe une injection de $2^\mathbb{N}$ vers $\omega_1$. Notons que sans l'axiome du choix il n'est pas clair non plus qu'une injection existe de $\omega_1$ vers $2^\mathbb{N}$ :
**Proposition 4.3.** « Moralement », il existe une injection de $\omega_1$ vers $2^N$, c'est-à-dire qu'il existe une fonction $f$ qui à $\alpha < \omega_1$ associe une classe non vide de réels $A_\alpha$ telle que $\beta_1 \neq \beta_2$ implique $A_{\beta_1} \cap A_{\beta_2} = \emptyset$. ★

PREUVE. Par la proposition 4.1, pour tout $\alpha$ dénombrable, il existe $X$ tel que $|\langle X \rangle| = \alpha$, où $\langle X \rangle$ est défini par $a \langle X \rangle b$ ssi $(a, b) \in X$. On associe à chaque $\alpha$ dénombrable la classe des réels $X$ tels que $|\langle X \rangle| = \alpha$. ■

La proposition précédente est bien évidemment insatisfaisante. On a une injection qui associe $\alpha < \omega_1$ vers des ensembles non vides $A_\alpha$ de réels, deux à deux disjoints. Mais comment choisir un unique réel dans chaque ensemble $A_\alpha$ ? Il s'agit de quelque chose d'impossible à faire sans l'axiome du choix, avec lequel on construit en revanche aisément une injection de $\omega_1$ dans $2^N$.

Rappelons qu'un ensemble $X$ est subpotent (resp. équipotent) à un ensemble $Y$ s'il existe une injection (resp. bijection) de $X$ vers $Y$ (voir le chapitre 2). On peut itérer la définition de $\omega_1$ de la manière suivante.

**Définition 4.4.** Supposons $\omega_n$ défini pour $n \in \mathbb{N}$. Soit

$$ \omega_{n+1} = \{ \beta : \beta \text{ est subpotent (strictement ou pas) à } \omega_n \}. \diamond $$

On montre aisément par induction que $\omega_n$ n'est pas équipotent à $\omega_{n+1}$ : il s'agit d'une hiérarchie d'infinis de plus en plus grands.

Gödel a construit un modèle de ZFC — son fameux univers des construc- tibles — dans lequel $\omega_1$ est équipotent à $2^N$. Cohen a montré comment, pour tout $n$, construire un modèle de ZFC dans lequel $2^N$ est équipotent à $\omega_n$.

Indépendamment des axiomes utilisés, nous verrons bientôt que pour un grand nombre de classes d'ensembles, l'hypothèse du continu est vérifiée dans le sens de Cantor : soit la classe est dénombrable, soit la classe contient un fermé parfait et donc une injection continue de $2^N$ vers elle-même. Ce sera en particulier le cas pour toute classe borélienne.

# 5. Ordinaux effectifs

Les ordinaux étant en quantité indénombrable, ils ne peuvent évidemment pas tous être décrits par un algorithme. Dans cette section, nous allons étudier deux définitions d'ordinaux effectifs, basées respectivement sur l'ap- proche de von Neumann et celle de Cantor, et montrer leur équivalence. La classe des ordinaux effectifs servira de socle pour le développement de l'hypercalculabilité.
## 5.1. Ordinaux constructifs

La première approche, celle de Kleene, suit le principe des ordinaux de von Neumann, en définissant les ordinaux de manière inductive en termes de successeurs et d'ordinaux limites. Comme nous l'avons vu dans la section 1.1, Kleene a défini un ensemble $\mathcal{O}$ de codes d'ordinaux en se basant sur l'unicité de la décomposition d'un entier en le produit de ses facteurs premiers. Rappelons ici la définition de $\mathcal{O}$.

**Définition 5.1 (Kleene [114]).** On définit inductivement un ensemble de notations $\mathcal{O} \subseteq \mathbb{N}$, avec un ordre partiel $<_o$ sur ses éléments.

(1) $1 \in \mathcal{O}$.

(2) Si $a \in \mathcal{O}$, alors $2^a \in \mathcal{O}$. Par suite, $a <_o 2^a$, et $b <_o a$ implique $b <_o 2^a$ pour tout $b$.

(3) Si $\Phi_e : \mathbb{N} \to \mathbb{N}$ est une fonction totale calculable telle que
$$ \forall n \Phi_e(n) \in \mathcal{O}, \text{ avec } \Phi_e(n) <_o \Phi_e(n+1) \text{ pour tout } n, $$
alors $3 \times 5^e \in \mathcal{O}$. De plus, pour chaque $b \in \mathcal{O}$ tel que $b <_o \Phi_e(n)$ pour un certain $n$, on a $b <_o 3 \times 5^e$. $\diamond$

**Définition 5.2.** On assigne naturellement un ordinal à chaque code de $\mathcal{O}$ de la manière suivante.

1. $|1| = \emptyset$,

2. $|2^a| = \text{succ}(|a|)$,

3. $|3 \times 5^e| = \sup_n |\Phi_e(n)|$.

Un ordinal $\alpha$ est *constructif* s'il existe un code $a \in \mathcal{O}$ tel que $\alpha = |a|$. $\diamond$

**Notation**

Soit $\alpha$ un ordinal. On écrira $\mathcal{O}_{<\alpha}$ (resp. $\mathcal{O}_{=\alpha}$) pour l'ensemble des éléments $a \in \mathcal{O}$ tels que $|a| < \alpha$ (resp. $|a| = \alpha$).

Les ordinaux ne sont pas, bien entendu, tous constructifs. Comme les codes de $\mathcal{O}$ sont en quantité dénombrable, et qu'il existe une quantité indénombrable d'ordinaux dénombrables, il existe alors un plus petit ordinal dénombrable qui n'est pas constructif.

**Notation**

On note $\omega_1^{ck}$ le plus petit ordinal non constructif.

L'exposant $\ll$ ck $\gg$ de l'ordinal $\omega_1^{ck}$ est l'acronyme de $\ll \text{Church Kleene} \gg$ pour Alonzo Church et Stephen Cole Kleene, qui ont introduit [36] le concept. Notons qu'aucun ordinal plus grand que $\omega_1^{ck}$ n'est constructif.
**Exercice 5.3.** Montrer que les ordinaux constructifs sont clos par le bas. ◇

Nous verrons petit à petit de nombreuses propriétés remarquables de l'or-
dinal $\omega_1^{ck}$. Nous verrons notamment avec le théorème 29-6.1 qu'il s'agit
du plus petit ordinal non définissable, pour de très puissantes notions de
définissabilité.

Les ordinaux constructifs permettent de faire des définitions de fonctions
calculables par induction sur les ordinaux. On peut en particulier calculer
une fonction d'addition sur les codes d'ordinaux constructifs.

**Exemple 5.4.** On définit la fonction d'addition $+_o : \mathbb{N} \times \mathbb{N} \rightarrow \mathbb{N}$ totale calculable, telle que pour tout $a, b \in \mathcal{O}$ la fonction renvoie $(a+_o b) \in \mathcal{O}$ avec $|a| + |b| = |a+_o b|$ et $a \leqq_o (a+_o b)$ :

$$
a+_o 1 = a,
$$

$$
a +_o 2^b = 2^{a+_{o}b},
$$

$$
a+_o 3 \times 5^e = 3 \times 5^{f(e,a)}, \quad \text{où } f(e,a) \text{ est le code de la fonction telle} \\
\qquad \text{que } \Phi_{f(e,a)}(n) = a+_o \Phi_e(n),
$$

$$
a +_o b = 1 \qquad \text{si } b \text{ n'est pas de la forme } 1, 2^c \text{ ou } 3 \times 5^e.
$$

Notons que la définition de $+_o$ utilise le théorème du point fixe, afin de
réutiliser le code de $+_o$ dans la fonction $f(e, a)$.

**Exercice 5.5.** (⋆) Montrer que pour tous $a, b \in \mathcal{O}$, $|a| + |b| = |a+_o b|$. ◇

**5.2. Les ordinaux calculables**

La définition des ordinaux constructifs de Kleene est dans l'esprit de celle
de von Neumann : un ordinal est un objet qui << contient >> les ordinaux
qui le précèdent. Cette définition étant équivalente à celle de Cantor dans
le cas général, il est naturel de se demander si une définition à la Cantor
des ordinaux effectifs n'aurait pas elle aussi son intérêt. On introduit donc
la définition suivante.

**Définition 5.6.** Un ordinal $\alpha$ est calculable s'il est fini ou si $\alpha = |<|$ pour $< \subseteq \mathbb{N} \times \mathbb{N}$ un bon ordre calculable sur $\mathbb{N}$. ◇

Un premier résultat facile est l'inclusion des ordinaux constructifs dans les
ordinaux calculables.

**Proposition 5.7.** Les ordinaux constructifs sont calculables. On peut en
fait uniformément transformer un code $a \in \mathcal{O}$ en un code $e$ calculant un
bon ordre $<_e$ tel que $|a| = |<_e|$.

La preuve tient dans les deux lemmes qui suivent.
**Lemme 5.8.** Soit $<_R \subseteq \mathbb{N} \times \mathbb{N}$ un bon ordre c. e. sur $A \subseteq \mathbb{N}$ avec $|A|$ infini. Alors, il existe un bon ordre c. e. $<_S \subseteq \mathbb{N} \times \mathbb{N}$ sur $\mathbb{N}$ tel que $|<_R| = |<_S|$. ★

**PREUVE.** Si $<_R$ est une relation calculatoirement énumérable sur $A$, alors $A$ est bien sûr lui aussi calculatoirement énumérable : quand $\langle a, b \rangle$ est énuméré dans $<_R$, on énumère $a$ et $b$ dans $A$. Notons qu'une énumération de $A$ avec $|A|$ infini induit naturellement une bijection calculable $f : \mathbb{N} \to A$ en définissant $f(n)$ comme étant le $n$-ième élément énuméré dans $A$ (en ne prenant pas en compte les redondances). On définit alors $<_S$ comme étant $\langle f^{-1}(a), f^{-1}(b) \rangle$ pour chaque $\langle a, b \rangle$ énuméré dans $<_R$. ■

**Lemme 5.9.** Soit $<_R \subseteq \mathbb{N} \times \mathbb{N}$ un bon ordre c. e. sur $\mathbb{N}$. Alors, $<_R$ est calculable. ★

**PREUVE**

Si $<_R$ est un ordre total sur $\mathbb{N}$, on a pour tout entier $a, b$ avec $a \neq b$, soit $a <_R b$ soit $b <_R a$. Ainsi, $\langle b, a \rangle \notin <_R$ ssi $a = b$ ou $\langle a, b \rangle \in <_R$. Le complémentaire de $<_R$ est donc lui aussi calculatoirement énumérable. On conclut que $<_R$ est calculable. ■

**PREUVE DE LA PROPOSITION 5.7.** Supposons que $a \in O$ code pour un ordinal infini. On peut énumérer la relation $<_a \subseteq \mathbb{N} \times \mathbb{N}$ définie comme étant la relation $<_o$ restreinte aux éléments $b, c <_o a$, ce qui nous donne un bon ordre c. e. sur une partie $A \subseteq \mathbb{N}$ avec $A$ infini et tel que $|<_a| = |a|$. On applique alors le lemme 5.8 et le lemme 5.9. ■

Les avantages des ordinaux constructifs par rapport aux ordinaux calculables sont clairs : étant donné un code $e \in O$, on voit tout de suite si $e$ code pour un ordinal successeur (auquel cas on peut obtenir un code pour l'ordinal prédécesseur) ou si $e$ code pour un ordinal limite (auquel cas on peut obtenir une suite calculable de codes pour les ordinaux constituants la limite). Cela permet de faire des définitions de fonctions calculables par induction sur les ordinaux constructifs comme avec l'exemple 5.4. Il n'est pas possible de le faire avec les ordinaux calculables. Le double saut est par exemple nécessaire pour savoir si un ordinal calculable est limite ou successeur. Pourtant les deux notions coïncident.

**Théorème 5.10 (Kleene, Markwald)**

Les ordinaux calculables sont constructifs.

On peut uniformément transformer le code $e$ d'un ordre total calculable bien fondé $<_e$ en un code $a \in O$ tel que $|<_e| \le |a|$.

La preuve du théorème utilise le lemme suivant.
**Lemme 5.11.** Il existe une fonction totale calculable $f : \mathbb{N} \to \mathbb{N}$ telle que si $W_e \subseteq \mathcal{O}$, alors $f(e) \in \mathcal{O}$, avec $\sup_{a \in W_e} |a| \le |f(e)|$. ★

**PREUVE.** On peut considérer sans perte de généralité que $W_e$ est infini. Afin de s'en assurer, on pourra par exemple y énumérer en plus de ce qui s'y trouve déjà tous les codes constructifs d'ordinaux finis. On définit $f(e)$ comme étant $3 \times 5^a$, où $a$ est tel que $\Phi_a(n)$ renvoie la somme finie des $n$ premiers codes distincts et différents de 1 (le code de $\emptyset$), d'ordinaux énumérés dans $W_e$. La somme finie est faite via la fonction $+_o$ de l'exemple 5.4. Notons que l'on a bien $\Phi_a(n) <_o \Phi_a(n+1)$, et l'on a donc bien $3 \times 5^a \in \mathcal{O}$. ■

**PREUVE DU THÉORÈME 5.10.** Soit $<_R \subseteq \mathbb{N} \times \mathbb{N}$ un bon ordre calculable sur $\mathbb{N}$. Soit $f : \mathbb{N} \to \mathbb{N}$ la fonction du lemme précédent. On définit une fonction $g : \mathbb{N} \to \mathbb{N}$ qui sur $a$ calcule le code $e_a$ de l'ensemble

$$W_{e_a} = \{g(b) : b <_R a\}$$

et renvoie $f(e_a)$. Notons que l'existence de la fonction $g$ fait appel au théorème du point fixe.

Voyons ce que donne la fonction $g$ sur le premier élément de $<_R$. Soit $a$ le plus petit élément de $<_R$. Alors, $W_{e_a} = \emptyset$, et l'on a bien $f(e_a) \in \mathcal{O}$ d'après le lemme précédent, de sorte que $g(a) \in \mathcal{O}$. En partant de ce cas initial, on montre facilement par une induction que, pour tout $a \in \mathbb{N}$, on a $g(a) \in \mathcal{O}$, avec $|<_R|_{X_a}| \le |g(a)|$ où $X_a$ est l'ensemble des éléments plus petits que l'entier $a$ via $<_R$.

On calcule ensuite aisément le code $e$ de la fonction qui énumère $g(a)$ pour tout $a \in \mathbb{N}$ et l'on renvoie $f(e)$. On a alors $|<_R| \le |f(e)|$. Comme les ordinaux constructifs sont clos par le bas, l'ordinal $|<_R|$ est donc constructif. ■

Notons que l'on n'a pas de conversion effective du code d'un ordinal calculable $<_R$ en un code $a$ d'ordinal constructif tel que $|<_R| = |a|$. On a en effet à la place seulement $|<_R| \le |a|$, et il est possible de montrer que l'égalité ne peut être obtenue de manière uniforme.

**Exercice 5.12. (★)** Montrer l'existence d'une fonction $f : \mathbb{N} \to \mathbb{N}$ totale calculable telle que $f(n)$ code toujours pour un ordinal calculable via une relation $<_{f(n)}$

$$\text{telle que } n \in \emptyset' \to |<_{f(n)}| = \omega + 1 \text{ et telle que } n \notin \emptyset' \to |<_{f(n)}| = \omega.$$

En déduire l'impossibilité de transformer uniformément un code d'ordinal calculable en un code constructif pour le même ordinal. ◇
### 5.3. Représentation des ordinaux par des arbres

Il existe une autre représentation usuelle des ordinaux dénombrables, facile à manipuler et bien utile dans de nombreux cas : via des arbres de l'espace de Baire $N^N$, comme introduits dans la section 8-7.

On rappelle que la manipulation des arbres et des chaînes de l'espace de Baire est analogue à celle de l'espace de Cantor, pour lequel on reprend les mêmes notations. On en introduit deux nouvelles, qui seront utilisées de temps à autre dans ce qui suit.

**Notation**

Soit $T$ un arbre avec $\sigma \in T$.

(1) la notation $T \upharpoonright_\sigma$ désigne l'arbre des nœuds de $T$ comparables avec $\sigma$.

(2) La notation $T \upharpoonright_\sigma$ désigne l'arbre $\{\tau \in N^< : \sigma\tau \in T\}$, c'est-à-dire l'arbre $T \upharpoonright_\sigma$ mais en « prenant $\sigma$ comme racine ».

**Définition 5.13.** Un arbre $T \subseteq N^<$ est bien fondé s'il ne contient pas de chemins infinis, c'est-à-dire si $[T]$ est vide. Pour $T$ bien fondé et $\sigma \in T$, on définit par induction $|\sigma| = \sup\{|\sigma n| + 1 : n \in N, \sigma n \in T\}$. On définit enfin $|T| = |\epsilon|$, où $\epsilon$ est la racine de $T$. On dira parfois que $|T|$ est la *hauteur* de $T*.

<figure><img src="image_169.png" /><figcaption>FIGURE 5.14 – Représentation de l'ordinal $\omega$ par un arbre $T$. On a noté pour chaque nœud $\sigma$ l'ordinal correspondant à $\sigma$, c'est-à-dire l'ordinal $|T \upharpoonright_\sigma|$.</figcaption></figure>

Notons que la valeur $|\sigma|$ du nœud $\sigma$ d'un arbre bien fondé $T$ dépend de $T$. Si jamais il y a une possible ambiguïté, nous utiliserons plutôt $|T \upharpoonright_\sigma|$, qui
est égal à $|\sigma|$ et se place explicitement dans le contexte de $T$.

Pour $T$ un arbre mal fondé, la valeur $|T|$ n'est pas définie, mais on l'utilisera parfois par abus de notation en la considérant plus grande que tous les ordinaux.

**Notation**

On note $\mathcal{T}$ l'ensemble des codes c. e. d'arbres bien fondés. On note $\mathcal{T}_{<\alpha}$ (resp. $\mathcal{T}_{=\alpha}$) l'ensemble des codes c. e. d'arbres $T \in \mathcal{T}$ tels que $|T| < \alpha$ (resp. tels que $|T| = \alpha$).

Il est à relever que les nœuds de $T$ forment un ordre bien fondé via leur relation de suffixe : $\sigma < \tau$ ssi $\tau < \sigma$. Via cet ordre < la définition 5.13 est équivalente à

$$|\sigma| = \sup\{|\tau| + 1 : \tau < \sigma, \tau \in T\}.$$

Si cet ordre n'est pas total, il permet néanmoins de représenter des ordinaux. On aura parfois besoin de « rendre total » la relation d'ordre sur les nœuds d'un arbre bien fondé $T$. Cela peut se faire via l'ordre de Kleene-Brouwer. On définit $\sigma < \tau$ pour $\sigma, \tau \in T$ ssi $\tau < \sigma$ ou alors si $\sigma, \tau$ ne sont pas préfixes l'un de l'autre et que $\sigma$ est lexicographiquement plus petit que $\tau$. On vérifie facilement que l'ordre ainsi donné est total sur les nœuds de $T$, et qu'il s'agit d'un bon ordre quand $T$ est bien fondé.

<figure><img src="image_170.png" /><figcaption>FIGURE 5.15 – Représentation de l'ordinal $\omega^2$ avec l'ordre de Kleene-Brouwer sur les arbres</figcaption></figure>

Voyons formellement l'ordinal associé aux nœuds d'un arbre via l'ordre de Kleene-Brouwer.

**Définition 5.16.** Pour un arbre $T$ bien fondé, l'ordre $<_{KB}$ de Kleene-Brouwer sur les éléments de $T$ est défini par $\sigma <_{KB} \tau$ si $\tau < \sigma$ ou alors si $\sigma, \tau$ ne sont pas préfixes l'un de l'autre et si $\sigma$ est lexicographiquement plus petit que $\tau$. Pour un nœud $\sigma \in T$, on définit par induction :

$$|\sigma|_{KB} = \sup \{ (|\tau|_{KB} + 1) : \tau <_{KB} \sigma, \tau \in T \}.$$
On définit enfin $|T|_{KB} = |\epsilon|_{KB}$, où $\epsilon$ est la racine de $T$.

◇

**Exercice 5.17.** (⋆) Montrer par induction que l'on a toujours $|T| \le |T|_{KB}$, pour un arbre $T$ bien fondé.

◇

Montrons à présent que les arbres c. e. sont des représentations d'ordinaux calculables.

**Proposition 5.18.** Un ordinal est calculable si, et seulement si, il est égal à $|T|$ pour un arbre c. e. $T \subseteq \mathbb{N}^{<\mathbb{N}}$. On peut uniformément transformer le code d'un bon ordre $<_R$ en un code d'un arbre c. e. $T$ tel que $|<_R| \le |T|$, et réciproquement, on peut uniformément transformer le code d'un arbre c. e. $T$ en un code de bon ordre $<_R$ tel que $|T| \le |<_R|$.

⋆

**PREUVE.** Soit $<_R$ un bon ordre calculable sur $\mathbb{N}$. On énumère dans $T$ tous les nœuds $n$, pour $n \in \mathbb{N}$. Puis, inductivement, pour chaque nœud de la forme $\sigma a$ énuméré dans $T$, on énumère comme fils de $\sigma a$ tous les nœuds $\sigma ab$ pour $b$ tel que $b <_R a$. L'arbre $T$ ainsi défini est bien fondé, car un chemin infini de $T$ induirait une suite infinie $\dots <_R a_2 <_R a_1 <_R a_0$, ce qui ne peut arriver car $<_R$ est un bon ordre. On vérifie facilement par induction que $|<_R| \le |T|$.

Pour la réciproque, il suffit de considérer l'ordre de Kleene-Brouwer sur les nœuds de $T$. Par l'exercice 5.17, on a $|T| \le |T|_{KB}$ et, via un codage des éléments de $\mathbb{N}^{<\mathbb{N}}$, on énumère un bon ordre $<_R$ sur une partie $A \subseteq \mathbb{N}$ telle que $|T|_{KB} = |<_R|$. Le lemme 5.8 et le lemme 5.9 permettent de conclure. ■

Notons qu'en suivant ce même principe, un ordinal est dénombrable si, et seulement si, il est égal à $|T|$ pour un arbre bien fondé $T$ — mais qui n'est pas nécessairement c. e.

# 6. Relativisation

Les notions d'ordinaux constructibles et calculables se relativisent à un oracle.

**Définition 6.1.** Soit $X \in 2^{\mathbb{N}}$. On définit l'ensemble $O^X$ de la manière suivante.

1. $1 \in O^X$, avec $|1| = 0$.

2. Si $a \in O^X$, alors $2^a \in O^X$ avec $|2^a| = \text{succ}(|a|)$. De plus $a <_o 2^a$, et $b <_o a$ implique $b <_o 2^a$ pour tout $b$.

3. Si $\Phi_e$ est une fonctionnelle totale sur $X$ avec

$$ \Phi_e(X, n) \in O^X \text{ et } \Phi_e(X, n) <_o \Phi_e(X, n+1), \text{ pour tout } n, $$
alors $3 \times 5^e \in \mathcal{O}^X$, avec $|3 \times 5^e| = \sup_n |\Phi_e(X, n)|$. De plus, pour tout $a$, si $a <_o \Phi_e(X, n)$ pour un certain $n$, alors $a <_o 3 \times 5^e$.

Un ordinal $\alpha$ est X-constructif s'il existe $a \in \mathcal{O}^X$ tel que $\alpha = |a|$. $\diamond$

Étant donné $X$ fixé, l'ordre $<_o$ sur les éléments de $\mathcal{O}^X$ n'est bien entendu pas le même que l'ordre $<_o$ sur les éléments de $\mathcal{O}$. Aussi écrira-t-on par-fois $>_o$ pour lever toute ambiguïté quand il y a lieu, tout comme il nous arrivera d'écrire $|a|^X$ à la place de $|a|$ pour un ordinal $a \in \mathcal{O}^X$.

**Définition 6.2**

Un ordinal $\alpha$ est X-calculable s'il est fini ou s'il existe $<_R \subseteq \mathbb{N} \times \mathbb{N}$ un bon ordre X-calculable sur $\mathbb{N}$ tel que $|<_R| = \alpha$. $\diamond$

**Notation**

On note $\mathcal{T}^X$ l'ensemble des codes d'arbres X-c. e. bien fondés de l'espace de Baire.

Les différentes équivalences vues jusqu'ici se relativisent sans problème à un oracle $X$.

**Théorème 6.3**

Un ordinal est X-constructif si, et seulement si, il est X-calculable, ou ce qui revient au même s'il est égal à $|T|$ pour un arbre X-c. e. $T \in \mathcal{T}^X$.

Souvenons-nous à présent du symbole $\omega_1^{ck}$ désignant le plus petit ordinal non constructible, ou de manière équivalente non calculable. Là encore, la notion se relativise.

**Notation**

On note $\omega_1^X$ le plus petit ordinal non X-calculable.

Notons que si $\omega_1^X$ peut être supérieur à $\omega_1^{ck}$, il n'en reste pas moins dénombrable. Réciproquement, tout ordinal dénombrable est calculable pour un certain $X$, en considérant par exemple un oracle qui code pour une relation d'ordre représentant l'ordinal. Cela nous donne l'énoncé qui suit.

**Proposition 6.4.** L'ordinal $\omega_1$ est le supremum des ordinaux X-calculables pour un certain oracle X. $\star$
<figure><img src="image_171.png" /></figure>
Chapitre 28

Ensembles hyperarithmétiques

De la même manière que les classes $\Sigma_n^0$ et $\Pi_n^0$ de la hiérarchie borélienne peuvent être généralisées en des classes $\Sigma_\alpha^0$ et $\Pi_\alpha^0$ pour tout ordinal $\alpha$ dénombrable afin de définir l'intégralité des boréliens, la hiérarchie arithmétique peut également être itérée de long des ordinaux calculables, produisant une nouvelle classe d'ensembles appelés *ensembles hyperarithmétiques*. Nous verrons à travers ce chapitre et le chapitre 29, qui suit, que cette classe est extrêmement robuste, dans le sens où elle admet de nombreuses caractérisations, en termes d'itérations du saut Turing, de singletons $\Pi_2^0$, ou de modulus.

Ce chapitre va nécessiter le développement d'un arsenal de codages de boréliens et d'ensembles d'entiers à l'aide d'entiers naturels. Les preuves feront souvent appel à des manipulations un peu laborieuses de ces codages, mais le lecteur sera récompensé par l'ajout des ensembles hyperarithmétiques à sa boîte à outils. Ce développement culminera avec deux résultats : d'une part, le corollaire 1.14, qui affirme que les ensembles $H_a$ pour $a \in O$ — autrement dit les $\alpha$-itérations du saut Turing de $\emptyset$ — sont complets aux différents niveaux de la hiérarchie de Kleene, et d'autre part le théorème 4.4, qui caractérise les classes $\Sigma_\alpha^0$ de la hiérarchie borélienne effective en termes des $\alpha$-itérations du saut Turing.

# 1. Hiérarchie de Kleene

On généralise la définition 5-1.1 des ensembles arithmétiques de la manière suivante.
<figure><img src="image_172.png" /><figcaption>FIGURE 1.2 – Le dépliage le long d’un arbre d’un $Π_2^0$-code $c$, qui code pour le complémentaire du $Σ_2^0$ codé par $\langle 2, e \rangle$, où $\Phi_e$ énumère des $Π_1^0$-codes qui correspondent eux-mêmes à des complémentaires d’ensembles $Σ_1^0$ codés par chaque $e_i$.</figcaption></figure>

**Définition 1.1.** La hiérarchie hyperarithmétique de Kleene est définie par induction sur les ordinaux.

▷ Un $Σ_1^0$-code est donné par une paire $\langle 0, e \rangle$. L’ensemble $A \subseteq \mathbb{N}$ correspondant est donné par $A = W_e$.

▷ Un $Π_α^0$-code est donné par une paire $\langle 1, e \rangle$, où $e$ est un $Σ_α^0$-code. L’ensemble $A \subseteq \mathbb{N}$ correspondant est donné par $A = \mathbb{N} \setminus B$, où $B$ est l’ensemble correspondant au code $e$.

▷ Un $Σ_α^0$-code est donné par une paire $\langle 2, e \rangle$, où $W_e$ est non vide et énumère des $Π_{β_n}^0$-codes pour $β_n < α$, avec $\sup_n(β_n + 1) = α$. L’ensemble $A \subseteq \mathbb{N}$ correspondant est donné par $\bigcup_n A_n$, où $A_n$ est l’ensemble correspondant au $n$-ième code énuméré par $W_e$.

On dit qu’un ensemble $A$ est $Σ_α^0$ (resp. $Π_α^0$) s’il correspond à un $Σ_α^0$-code $e$ (resp. $Π_α^0$-code $e$). On dit que $A$ est $Δ_α^0$ s’il est à la fois $Σ_α^0$ et $Π_α^0$. On dira enfin qu’un ensemble $A$ est hyperarithmétique s’il est $Σ_α^0$ pour un certain ordinal $α$. ◇

Souvenons-nous des ensembles $H_a$ de la définition 27-1.3, correspondants aux versions itérées du saut pour $a \in O$. Pour tout $a \in O$ tel que $|a| = n$, l’ensemble $H_a = \emptyset^{(n)}$ est $Σ_n^0$. Pour $a = 3 \times 5^e$ tel que $|a| = ω$, l’ensemble $H_a$ est quant à lui $Δ_ω^0$. En effet, on a $\langle n, m \rangle \in H_a$ ssi $n \in H_{Φ_e(m)}$, et donc aussi $\langle n, m \rangle \notin H_a$ ssi $n \notin H_{Φ_e(m)}$. Les ensembles

$$ \{\langle n, m \rangle : n \in H_{\Phi_e(m)}\} \text{ et } \{\langle n, m \rangle : n \notin H_{\Phi_e(m)}\} $$

sont $Δ_1^0(H_{Φ_e(m)})$ uniformément en $m$, et donc $Π_{|Φ_e(m)|+1}^0$ uniformément en $m$, d’après le théorème 5-5.5. Cela nous permet de faire une définition $Σ_ω^0$
de $H_a$ ainsi que de son complémentaire. L'ensemble $H_{2a}$ est quant à lui $\Sigma_{\omega}^0$, et cela s'itère sans problème sur les éléments de $O$. Pour être tout à fait rigoureux, nous aurons toutefois besoin de quelques lemmes de manipulation des codes $\Sigma_{\alpha}^0$ et $\Pi_{\alpha}^0$, à commencer par une généralisation des deux lemmes 5-1.7 et 5-1.6.

**Lemme 1.3.** Les ensembles $\Sigma_{\alpha}^0$ et $\Pi_{\alpha}^0$ sont stables par réunions et intersections finies. ★

**PREUVE.** On peut récursivement utiliser les relations suivantes pour des ensembles quelconques $A, B$ et $A_n, B_n$, avec $n \in \mathbb{N}$ :

$$ (\bigcup_{n \in \mathbb{N}} A_n) \cap (\bigcup_{n \in \mathbb{N}} B_n) = \bigcup_{n_1, n_2 \in \mathbb{N}} (A_{n_1} \cap A_{n_2}); $$

$$ (\bigcup_{n \in \mathbb{N}} A_n) \cup (\bigcup_{n \in \mathbb{N}} B_n) = \bigcup_{n \in \mathbb{N}} C_n, \text{ avec } C_{2n} = A_n \text{ et } C_{2n+1} = B_n; $$

$$ A \cap (\bigcup_{n \in \mathbb{N}} B_n) = \bigcup_{n \in \mathbb{N}} A \cap B_n; $$

$$ A \cup (\bigcup_{n \in \mathbb{N}} B_n) = \bigcup_{n \in \mathbb{N}} C_n, \text{ avec } C_0 = A \text{ et } C_{n+1} = B_n; $$

$$ (\mathbb{N} \setminus A) \cap (\mathbb{N} \setminus B) = \mathbb{N} \setminus (A \cup B); $$

$$ (\mathbb{N} \setminus A) \cup (\mathbb{N} \setminus B) = \mathbb{N} \setminus (A \cap B). $$

En utilisant le théorème du point fixe, on crée les fonctions calculables de réunion et d'intersection de deux codes, qui propagent leur application en utilisant les relations ci-dessus. ■

**Lemme 1.4.** Les ensembles $\Sigma_{\alpha}^0$ sont stables par réunions dénombrables uniformes. ★

**PREUVE.** Étant donné des $\Sigma_{\alpha}^0$-codes $(\langle 2, e_n \rangle)_{n \in \mathbb{N}}$, il suffit bien entendu de créer le code $\langle 2, e \rangle$, où $e$ énumère $\bigcup_n W_{e_n}$. ■

Nous terminons par deux lemmes de manipulation des codes qui nous seront utiles de temps à autre.

**Lemme 1.5.** Soit $x \in \mathbb{N}$. Il existe une fonction calculable qui sur le code $\Sigma_{\alpha}^0$ (resp. $\Pi_{\alpha}^0$) d'un ensemble $A$ renvoie le code $\Sigma_{\alpha}^0$ (resp. $\Pi_{\alpha}^0$) d'un ensemble $B$ tel que $B = \mathbb{N}$ si $x \in A$, et $B = \emptyset$ sinon. ★

**PREUVE.** Il suffit de « déplier » le code et de remplacer chaque feuille correspondant à un ensemble $W_k$ par un ensemble c. e. égal à $\mathbb{N}$ si $x \in W_k$ et égal à $\emptyset$ sinon.

La procédure fonctionne trivialment pour les codes $\Sigma_1^0$. Supposons que la procédure fonctionne pour les codes $\Sigma_{\alpha}^0$. Soit $a = \langle 1, b \rangle$ un code $\Pi_{\alpha}^0$ d'un ensemble $A = \mathbb{N} \setminus B$, où $b$ est un code de $B$. Alors, la procédure appliquée à $b$ renvoie $\mathbb{N}$ si $x \in B$ et $\emptyset$ sinon, ce qui appliqué à $a$ passe au complémentaire et donne bien $\mathbb{N}$ si $x \in A$, et $\emptyset$ sinon. On vérifie de même par induction que l'on a le résultat attendu avec les codes de la forme $\langle 2, b \rangle$ correspondant à des réunions. ■
**Lemme 1.6.** Soit $A$ un ensemble $\Sigma_{\alpha}^{0}$ et soit $f$ une fonction calculable. Alors, $f(A)$ est un ensemble $\Sigma_{\alpha}^{0}$.

PREUVE. D'après le lemme 1.5, on peut créer pour tout $x$ le code $\Sigma_{\alpha}^{0}$ d'un ensemble $B_{x}$ égal à $\mathbb{N}$ si $x \in A$, et égal à $\emptyset$ sinon.

On a $f(A)=\bigcup_{x \in \mathbb{N}}\{f(x)\} \cap B_x$. D'après le lemme 1.3, l'ensemble $\{f(x)\} \cap B_x$ est $\Sigma_{\alpha}^{0}$ uniformément en $x$. D'après le lemme 1.4, l'ensemble $f(A)$ est donc lui aussi $\Sigma_{\alpha}^{0}$.

Nous avons à présent tous les outils nécessaires pour attaquer la complexité des ensembles issus de l'itération transfinie du saut Turing.

**Proposition 1.7.** Pour tout ordinal $\alpha \ge \omega$ et tout $a \in O_{=\alpha}$, l'ensemble $H_{2^a}$ est $\Sigma_{\alpha}^{0}$ uniformément en $a$.

PREUVE. On montre la proposition par induction sur les éléments de $O$. L'induction commence avec les ensembles $H_a$ pour $|a|$ fini, qui sont tous $\Sigma_{|a|}^{0}$ d'après la proposition 5-5.3. Nous verrons dans le reste de la preuve (comme cela a été esquissé dans le paragraphe suivant la définition 1.1) que cela amène à avoir que $H_{2^a}$ est $\Sigma_{|a|}^{0}$ pour $a \in O_{=\omega}$. Supposons la proposition vraie pour tout $b <_o a$ et montrons que $H_a$ est $\Delta_{|a|}^{0}$.

Si $a = 2^b$ code pour un ordinal successeur, alors par hypothèse d'induction l'ensemble $H_a$ est $\Sigma_{|a|}^{0}$. Donc, lui et son complémentaire sont tous deux $\Delta_{|a|}^{0}$. Si $a = 3 \times 5^e$ code pour un ordinal limite, on a

$$ \langle n, m \rangle \in H_a \Leftrightarrow n \in H_{\Phi_e(m)}, \text{ ainsi que } \langle n, m \rangle \notin H_a \Leftrightarrow n \notin H_{\Phi_e(m)}. $$

Vu que l'ensemble $H_{\Phi_e(m)}$ est par induction uniformément $\Sigma_{|\Phi_e(m)|}^0$, on a d'après le lemme 1.6 appliqué à chaque $H_{\Phi_e(m)}$, un $\Sigma_{|a|}^0$-code de $H_a$ ainsi que de son complémentaire. Donc, $H_a$ est un ensemble $\Delta_{|a|}^0$.

Dans les deux cas, $H_a$ est un ensemble $\Delta_{|a|}^0$. Par ailleurs, on a $n \in H_{2^a}$ si, et seulement si, $\Phi_n(H_a, n) \downarrow$, ce qui est une condition $\Sigma_1^0(H_a)$. Comme l'ensemble $H_a$ et son complémentaire sont $\Delta_{|a|}^0$, alors l'ensemble $H_{2^a}$ est $\Sigma_{|a|}^0$ via le prédicat $n \in H_{2^a}$ si, et seulement si,

$$ \exists \sigma \exists t \Phi_n(\sigma, n)[t] \downarrow \wedge \forall i < |\sigma| \left( (\sigma(i) = 0 \wedge i \notin H_a) \vee (\sigma(i) = 1 \wedge i \in H_a) \right). $$

La manière d'obtenir réellement un $\Sigma_{|a|}^0$-code pour $H_{2^a}$ à partir de la formule ci-dessus n'est pas forcément claire, et nous détaillons donc comment procéder. Étant donné une chaîne $\sigma$ et un entier $i < |\sigma|$, on peut calculer uniformément le code $e_{\sigma, i}$ d'un ensemble $\Sigma_{|a|}^0$ égal à $\mathbb{N}$ si $\sigma(i) = 0$ et $i \notin H_a$, ou si $\sigma(i) = 1$ et $i \in H_a$, et égal à $\emptyset$ sinon : il suffit d'appliquer le lemme 1.5
à i et $\mathbb{N} - H_a$ si $\sigma(i) = 0$, et à i et $H_a$ si $\sigma(i) = 1$. Soit $B_{e_{\sigma,i}}$ l'ensemble $\Sigma_{|a|}^0$ ainsi décrit. Alors,

$$H_{2^a} = \bigcup_{\sigma} \left( \{n : \Phi_n(\sigma, n) \downarrow\} \cap \bigcap_{i < |\sigma|} B_{e_{\sigma, i}} \right).$$

D'après le lemme 1.3 et le lemme 1.4, il s'agit bien d'un ensemble $\Sigma_{|a|}^0$. ■

## Alternance de quantificateurs

Notons que dans la preuve précédente, à partir du fait que $H_{2^a}$ soit $\Sigma_1^0(X)$ avec $X$ un ensemble $\Delta_{|a|}^0$, on obtient une description $\Sigma_{|a|+1}^0$ de $H_{2^a}$. Ainsi, l'équivalence entre la quantification $\exists$ et la réunion, tout comme celle entre la quantification $\forall$ et l'intersection, se poursuivent « moralement » dans le transfini, mais le langage du premier ordre ne nous permet simplement plus d'en rendre compte formellement (il nous faudrait des phrases de taille infinie).

## Complexité des itérations du saut

Notons que pour $a \in O_{<\omega}$ l'ensemble $H_a$ est $\Sigma_{|a|}^0$ (c'est-à-dire que $\emptyset^{(n)}$ est $\Sigma_n^0$), alors que pour $a \in O_{\ge\omega}$ c'est l'ensemble $H_{2^a}$ qui est $\Sigma_{|a|}^0$. Ce phénomène est dû aux étapes limites.

Nous avons vu antérieurement, avec la proposition 5-5.3, que pour $a \in O_{<\omega}$, l'ensemble $H_a$ est $\Sigma_{|a|}^0$-complet. Nous allons à présent démontrer que chaque ensemble $H_{2^a}$ pour $|a| \ge \omega$, est $\Sigma_{|a|}^0$-complet, c'est-à-dire que chaque ensemble $\Sigma_{|a|}^0$ est many-one réductible à $H_{2^a}$. Cela demande toutefois un peu de travail, et nous commençons par une transformation effective des $\Sigma_\alpha^0$-codes en arbres bien fondés de hauteur $\alpha$.

**Proposition 1.8.** Il existe une fonction totale calculable $f : \mathbb{N} \to \mathbb{N}$ telle que $e$ est un $\Sigma_\alpha^0$-code de la hiérarchie effective de Kleene si, et seulement si, $f(e) \in T_{=\alpha}$.

<figure><img src="image_173.png" /></figure>

La preuve de la proposition précédente n'est pas difficile et nous en donnons simplement ici l'idée générale, en laissant les détails au lecteur. La fonction $f$ renvoie le code de l'arbre correspondant au dépliage du $\Sigma_\alpha^0$-code en omettant simplement le passage au complémentaire de $\Pi_\alpha^0$ vers $\Sigma_\alpha^0$. Si à un certain moment on s'aperçoit que $e$ n'est pas un code valide, la fonction renvoie alors le code d'un arbre mal fondé. Notons que cela implique d'avoir $\omega_1^{ck}$ comme borne sur les ensembles $\Sigma_\alpha^0$.

## Corollaire 1.9

Si un sous-ensemble de $\mathbb{N}$ est $\Sigma_\alpha^0$, alors $\alpha < \omega_1^{ck}$.
Voyons à présent le théorème clef dans la preuve que chaque ensemble $H_{2^a}$ est $\Sigma_{|a|}^0$-complet.

**Théorème 1.10 (Spector [214])**

Pour tout ordinal $\alpha < \omega_1^{ck}$ et tout $a \in O_{=\alpha}$, on a

1. $O_{<\alpha} \leq_T H_{2^a}$, uniformément en $a$;

2. $T_{<\alpha} \leq_T H_{2^a}$, uniformément en $a$.

PREUVE. On veut deux fonctionnelles $\Psi_1, \Psi_2$ telles que pour tout $a \in O_{=\alpha}$ et $x \in \mathbb{N}$ on a :

$$ \triangleright x \in O_{<\alpha} \rightarrow \Psi_1(H_{2^a}, a, x) = 1 \text{ et } x \notin O_{<\alpha} \rightarrow \Psi_1(H_{2^a}, a, x) = 0; $$

$$ \triangleright x \in T_{<\alpha} \rightarrow \Psi_2(H_{2^a}, a, x) = 1 \text{ et } x \notin T_{<\alpha} \rightarrow \Psi_2(H_{2^a}, a, x) = 0. $$

La fonction $\Psi_1(H_{2^a}, a, x)$ fait les calculs suivants.

1. Si $a=1$, alors le calcul renvoie 0, et effectivement $O_{<|a|}$ est vide.

2. Si $a=2^b$, alors le calcul renvoie 1 si la condition suivante est vraie (et renvoie 0 sinon) :

(a) $\Psi_1(H_{2^b}, b, x) = 1$, ce qui correspond au fait que $x \in O_{<|b|}$. Il reste à couvrir les cas où $|x| = |b|$;

(b) ou $x = 2^y, |b|$ est successeur et $\Psi_1(H_{2^b}, b, y) = 1$, ce qui correspond au fait que $x \in O_{=|b|}$ avec $b$ successeur;

(c) ou $x = 3 \times 5^e, b$ est limite et l'énoncé $\Pi_1^0(H_b)$ suivant est vrai : pour tout $n \in \mathbb{N}$, on a $\Phi_e(n) \downarrow_{<o} \Phi_e(n+1) \downarrow$ et pour tout $n$ il existe $c <_o b$ tel que $\Psi_1(H_{2^c}, c, \Phi_e(n)) = 1$. Ce cas correspond au fait que $x \in O_{=|b|}$ avec $b$ limite. Notons que l'énoncé $\Pi_2^0(H_b)$ est aussi $\Pi_1^0(H'_b)$. Comme $H_{2^a} = H''_b$, c'est une question à laquelle on peut répondre à l'aide de notre oracle.

3. Si $a = 3 \times 5^e$, alors le calcul renvoie 1 si la condition $\Sigma_1^0(H_a)$ suivante est vraie (et renvoie 0 sinon) : il existe $b <_o a$ tel que $\Psi_1(H_{2^b}, b, x) = 1$. Ce cas correspond au fait que $x \in O_{<|a|}$, avec $a$ limite. Comme $H_{2^a} = H'_a$, c'est une question à laquelle on peut répondre à l'aide de notre oracle.

On vérifie aisément par induction que le calcul fait bien ce qui est attendu. La fonction $\Psi_2(H_{2^a}, a, x)$ fait quant à elle les calculs suivants.

1. Si $a=1$, alors $\Psi_2(H_{2^a}, a, x) = 0$, et effectivement $T_{<|a|}$ est vide.

2. Si $a = 2^b$, soit $T$ l'arbre codé par $x$. Alors, $\Psi_2(H_{2^a}, a, x) = 1$ ssi l'énoncé $\Pi_1^0(H_{2^b})$ suivant est vrai : pour tout $n \in T$ — autrement dit, pour tout nœud de profondeur 1 dans $T$ — et tout $x_n$ où $x_n$ est le code de $T^1_n$, on a $\Psi_2(H_{2^b}, b, x_n) = 1$. Cela correspond au fait que pour chaque sous-arbre $T^1_n$ on ait $|T^1_n| < |b|$, et donc au fait que $|T| < |a|$.
3. Si $a = 3 \times 5^e$, alors $\Psi_2(H_{2^a}, a, x) = 1$ ssi l'énoncé $\Sigma_1^0(H_a)$ suivant est vrai : il existe $b <_o a$ tel que $\Psi_2(H_{2^b}, b, x) = 1$. Ce cas correspond au fait que $x \in \mathcal{T}_{<|a|}$ avec $a$ limite. $\blacksquare$

Le théorème précédent ne peut pas être amélioré. Pour beaucoup d'orfinaux $\alpha$, l'ensemble $O_{<\alpha}$ sera en fait calculable par des ensembles $H_a$ pour $a \in O_{<\alpha}$, mais pour les ordinaux $\alpha$ qui sont limites de limites, il est possible de montrer que l'ensemble $\mathcal{T}_{<\alpha}$ est $\Sigma_\alpha^0$ mais pas $\Pi_\alpha^0$, et que l'ensemble $\mathcal{T}_{<\alpha+1}$ est $\Pi_{\alpha+1}^0$ mais pas $\Sigma_{\alpha+1}^0$. Les bornes précises sont données dans l'exercice suivant.

**Exercice 1.11. (★★)** Montrez que pour tout $\alpha = \emptyset$ ou limite, et pour tout $\mathfrak{k}, \mathfrak{p} \in \omega$ :

1. l'ensemble $\mathcal{T}_{<\omega(\alpha+\mathfrak{k})}$ est $\Sigma_{\alpha+2\mathfrak{k}}^0$-complet;

2. l'ensemble $\mathcal{T}_{\le \omega(\alpha+\mathfrak{k})+\mathfrak{p}}$ est $\Pi_{\alpha+2\mathfrak{k}+1}^0$-complet.

◇

Montrons à présent que les ensembles de la forme $H_a$ sont complets pour leurs classes de complexité.

**Théorème 1.12**

Soit $\alpha < \omega_1^{ck}$, et soient $a \in O_{=\alpha}$ et $A$ un ensemble $\Sigma_\alpha^0$. Alors, $A$ est many-one réductible à $H_{2^a}$, uniformément en $a$ et en un $\Sigma_\alpha^0$-code de $A$.

Nous aurons besoin du lemme suivant.

**Lemme 1.13.** Soit $e$ un $\Sigma_\alpha^0$-code. Soit $b \in O$ tel que $\alpha+2 \le |b|$. Alors, $H_b$ peut retrouver uniformément en $b$ et en $e$ un code $a <_o b$ tel que $|a| = \alpha.*$

**PREUVE.** On commence par transformer $e$ en un code $f(e) \in \mathcal{T}_{=\alpha}$ via la proposition 1.8. Étant donné $b$, on énumère tous les codes $a$ tels que $2^a <_o b$ tout en cherchant le plus petit tel que $f(e) \in \mathcal{T}_{=|a|}$, c'est-à-dire l'unique $a$ tel que :

$$ (1) \ f(e) \in \mathcal{T}_{<\mathrm{succ}(|a|)}, $$

$$ (2) \ \forall c <_o a \ f(e) \notin \mathcal{T}_{<\mathrm{succ}(|c|)}. $$

Pour (1), d'après le théorème 1.10, on a $\mathcal{T}_{<\mathrm{succ}(|a|)} \le_T H_{2^{2a}}$, qui est au pire égal à $H_b$. Pour (2), la question requiert — toujours en utilisant le théorème 1.10 — $H'_{2a}$, qui dans le pire des cas est égal à $H_b$. L'oracle $H_b$ suffit donc pour identifier $a$. $\blacksquare$

**PREUVE DU THÉORÈME 1.12.** On cherche à définir une fonction totale calculable $f: \mathbb{N}^3 \to \mathbb{N}$ telle que pour tout $\alpha < \omega_1^{ck}$, pour tout $\Sigma_\alpha^0$-code $e$ d'un ensemble $A$ on a $x \in A$ ssi $f(a, e, x) \in H_{2^a}$.

La fonction $f(a, e, x)$ renvoie le code de la fonctionnelle dont on suppose qu'elle dispose de l'oracle $H_a$ et qui traite les cas suivants.
1. Si $\alpha = 1$ — le cas initial correspondant aux ensembles $\Sigma_1^0$, alors la fonctionnelle s’arrête sur sa propre entrée ssi $x$ appartient à l’ensemble $\Sigma_1^0$ de code $e$.

2. Sinon, si $\alpha$ est limite, la fonctionnelle énumère les $\Sigma_{\beta_n}^0$-codes $e_n$ d'ensembles $A_n$ tels que $A = \bigcup_n (\mathbb{N} \setminus A_n)$ et avec $\sup_n(\beta_n + 1) = \alpha$. Notons que l'on a $\beta_n + 2 \le \alpha$ pour chaque $n$. On peut donc appliquer le lemme 1.13 avec l'oracle $H_a$ pour trouver pour chaque $e_n$ un code $b_n <_o a$ tel que $|b_n| = \beta_n$. La fonctionnelle s'arrête sur sa propre entrée ssi la condition $\Sigma_1^0(H_a)$ suivante est vraie : $\exists n f(b_n, e_n, x) \notin H_{b_n}$.

3. Sinon, si $\alpha = \text{succ}(\beta)$ avec $a = 2^b$, la fonctionnelle énumère les $\Sigma_{\beta_{n,m}}^0$-codes $e_{n,m}$ d'ensembles $A_{n,m}$, avec

$$ \sup_m (\beta_{n,m} + 1) = \alpha_n \le \beta, \quad \sup_n (\alpha_n + 1) = \alpha \quad \text{et} \quad A = \bigcup_m \bigcap_n A_{n,m}. $$

Notons que l'on a $\beta_{n,m} + 2 \le \alpha$ pour chaque $n,m$. On peut donc appliquer le lemme 1.13 avec l'oracle $H_a$ pour trouver pour chaque $e_{n,m}$ un code $b_{n,m} <_o a$ tel que $|b_{n,m}| = \beta_{n,m}$. La fonctionnelle s'arrête sa propre entrée si, et seulement si, la condition $\Sigma_2^0(H_b)$ suivante est vraie : $\exists n \forall m f(b_{n,m}, e_{n,m}, x) \in H_{b_{n,m}}$. ■

Nos efforts sont à présent récompensés par trois corollaires qui viennent structurer un peu nos connaissances des ensembles hyperarithmétiques. Le premier d'entre eux est simplement la juxtaposition du théorème 1.12 et de la proposition 1.7.

**Corollaire 1.14**

Pour tout $\alpha < \omega_1^{ck}$ tel que $\alpha \ge \omega$, et tout $a \in \mathcal{O}_{=\alpha}$, l'ensemble $H_{2^a}$ est $\Sigma_\alpha^0$-complet uniformément en $a$.

Le deuxième corollaire nous indique qu'aucun niveau n'est superflu dans la hiérarchie de Kleene : pour tout $\alpha < \omega_1^{ck}$ il existe un ensemble $\Sigma_\alpha^0$ qui n'est pas $\Pi_\alpha^0$.

**Corollaire 1.15**

La hiérarchie de Kleene est stricte.

**PREUVE.** Pour un ordinal calculable $\alpha \ge \omega$, pour $a \in \mathcal{O}_{=\alpha}$, chaque ensemble $H_{2^a}$ est $\Sigma_\alpha^0$. Supposons par l'absurde que l'un d'eux soit aussi $\Pi_\alpha^0$. Alors, son complémentaire est $\Sigma_\alpha^0$. On a donc d'après le théorème 1.12 une fonction totale calculable $f$ telle que $e \notin H_{2^a}$ ssi $f(e) \in H_{2^a}$, c'est-à-dire $\Phi_e(H_a, e) \uparrow$ ssi $\Phi_{f(e)}(H_a, f(e)) \downarrow$.
Notons que l’on a aussi une fonction totale calculable $g$ telle que $\Phi_e(H_a, e) \downarrow$ implique $\forall n \ \Phi_{g(e)}(H_a, n) \downarrow$, et $\Phi_e(H_a, e) \uparrow$ implique $\forall n \ \Phi_{g(e)}(H_a, n) \uparrow$. Donc, en particulier, $\Phi_e(H_a, e) \uparrow$ ssi $\Phi_{g(f(e))}(H_a, e) \downarrow$. D’après le théorème du point fixe, il existe $e$ tel que $\Phi_e(H_a, e) = \Phi_{g(f(e))}(H_a, e)$, ce qui est une contradiction. ■

Le dernier corollaire va finalement nous permettre de nous abstraire un peu de notre système de notation pour les ordinaux.

**Corollaire 1.16**

Soit $\alpha < \omega_1^{ck}$, et soient $a, b \in O_{=\alpha}$. Alors, $H_{2^a} \equiv_m H_{2^b}$.

**PREUVE.** Le corollaire est évident quand $\alpha$ est un ordinal fini. Pour $\alpha \ge \omega$, il suffit de constater que chaque $H_{2^a}$ est $\Sigma^0_{|a|}$-complet. ■

Remarquons que les équivalences many-one ne fonctionnent que pour les cas successeurs. Qu’en est-il des ensembles $H_a$ pour $a$ un ordinal limite ? Ces ensembles sont $\Delta^0_{|a|}$ et si l’on a toujours $H_a \equiv_T H_b$ pour $a, b \in O_{=\alpha}$ avec $\alpha$ limite, on n’aura pas nécessairement $H_a \equiv_m H_b$. Moschovakis [162] a montré que l’équivalence tient malgré tout quand $\alpha$ est de la forme $\beta + \omega$, mais que la structure des degrés many-one au sein du degré Turing d’un $H_a$ est très chaotique dans le cas où $|a|$ est une limite de limite.

On utilisera le corollaire précédent pour considérer les itérations $\alpha$ du saut à degré many-one près (ou à degré Turing près dans le cas limite).

**Notation**

Pour $\alpha < \omega_1^{ck}$, on écrira parfois $\emptyset^{(\alpha)}$ pour signifier l'ensemble $H_a$ pour un certain $a \in O_{=\alpha}$ sans préciser davantage.

En particulier, chaque ensemble $\emptyset^{(\alpha+1)}$ est à degré many-one près l'ensemble $\Sigma^0_\alpha$-complet, et pour $\alpha$ limite l'ensemble $\emptyset^{(\alpha)}$ est bien défini à degré Turing près.

# 2. Les singletonst $\Pi_2^0$

Nous avons vu dans la section 26-1 que les singletonst $\Pi_2^0$ dans l'espace de Cantor dépassaient la hiérarchie arithmétique, et notamment que l'ω-saut Turing de $\emptyset$ était un singletonst $\Pi_2^0$. Nous allons maintenant voir que l'on peut trouver des singletonst $\Pi_2^0$ à tous les niveaux de la hiérarchie de Kleene, et en particulier que tout ensemble hyperarithmétique est calculable par un
singleton $\Pi_2^0$. Nous verrons plus tard dans la section 29-5 que la réciproque est vraie.

**Théorème 2.1**

Il existe $\mathcal{P} \subseteq \mathbb{N} \times 2^{\mathbb{N}}$ une classe $\Pi_2^0$ telle que pour tout $a \in \mathcal{O}$ la classe
$\{X : (a, X) \in \mathcal{P}\}$
est le singleton $H_a$.

PREUVE. Souvenons-nous de $S$ de l'exemple 17-3.7 : la classe $\Pi_2^0$ contenant exactement les ensembles qui sont des sauts Turing d'autres ensembles. Notons également $\Psi$ la fonctionnelle telle que $\Psi(X') = X$ pour tout $X$.

En utilisant le théorème du point fixe, on définit alors la classe $\mathcal{P}$ comme
étant :

$$
\mathcal{P} = \left\{ (a, X) : \begin{array}{l} a=1 \text{ et } X=\emptyset \text{ ou} \\ a=2^b \text{ et } X \in \mathcal{S} \text{ et } (b, \Psi(X)) \in \mathcal{P} \text{ ou} \\ a=3 \times 5^b \text{ et } X = \bigoplus_n X_n \text{ avec } \forall n (\Phi_b(n), X_n) \in \mathcal{P} \end{array} \right\}.
$$

Voyons un peu plus formellement comment est définie la classe $\mathcal{P}$. Pour tout $n \in \mathbb{N}$, soit $S_n \subseteq 2^{<\mathbb{N}}$ l'ensemble $\Sigma_1^0$ tel que $S = \bigcap_n [S_n]$. On peut supposer sans perte de généralité que chaque $S_n$ est clos par suffixe : si $\sigma \in S_n$, alors toute extension de $\sigma$ appartient à $S_n$. Afin d'utiliser le théorème du point fixe, on définit la fonction $f : \mathbb{N} \to \mathbb{N}$ qui sur un code $e$ renvoie le code $f(e)$ tel que :

$$
\begin{array}{rcl}
(a & = & 1 \wedge \sigma \prec 0^{\infty}) \\
\Phi_{f(e)}(a, n, \sigma) \downarrow & \leftrightarrow & \vee (a = 2^b \wedge \sigma \in S_n \wedge \Phi_e(b, n, \Psi(\sigma)) \downarrow) \\
& & \vee (a = 3 \times 5^b \wedge \Phi_e(\Phi_b(n), n, \sigma_n)), \text{ où } \sigma = \oplus_m \sigma_m.
\end{array}
$$

D'après le théorème du point fixe, soit $e$ tel que $\Phi_{f(e)} = \Phi_e$. On montre
alors par induction que pour tout $a \in \mathcal{O}$, la classe $\Pi_2^0$ donnée par

$$
\bigcap_n [\{\sigma : \Phi_e(a, n, \sigma) \downarrow\}]
$$

contient l'ensemble $H_a$, et uniquement lui.

**Corollaire 2.2**

Tout ensemble hyperarithmétique est calculable par un singleton $\Pi_2^0$.

PREUVE. D'après le théorème 1.12 et le théorème 2.1.

À quoi ressemble $\{X : (a, X) \in \mathcal{P}\}$ pour un élément $a \notin \mathcal{O}$ ? Pour la
plupart de ces éléments, la classe en question sera vide, mais nous ver-
rons avec le théorème 31-3.3 que ce n’est pas toujours le cas : il existe
des éléments $a \notin \mathcal{O}$, mais qui ressemblent à des éléments de $\mathcal{O}$. Plus
précisément, il existe des éléments $a \notin \mathcal{O}$ qui ressemblent à des éléments
de $\mathcal{O}$ : ils sont de la forme $2^b$ ou $3 \times 5^e$, et récursivement sur les éléments
« plus petits qu’eux ».
Simplement, cette énumération contiendra une suite infinie d'éléments

$$ \dots < b_4 < b_3 < b_2 < b_1 < a. $$

Ce phénomène-là, aux conséquences fascinantes, sera étudié ultérieurement dans les sections 31-3 et 31-4.

Voyons à présent une notion introduite par Groszek et Slaman, et qui comme nous le verrons avec le théorème 29-5.4 caractérise exactement les ensembles hyperarithmétiques. La définition suivante peut être vue comme une extension de la définition de modulus des ensembles $\Delta_2^0$ (voir la définition 4-7.7).

**Définition 2.3 (Groszek et Slaman [79]).** Un ensemble $X$ admet un modulus s'il existe une fonction $f: \mathbb{N} \to \mathbb{N}$ telle que, pour toute fonction $g \ge f$, on a $g \ge_T X$. ◇

**Théorème 2.4**

Tout ensemble hyperarithmétique admet un modulus.

**PREUVE.** Soit $\bigcap_n U_n$ une classe $\Pi_2^0$ contenant un unique élément $X$. Soit une fonction $f: \mathbb{N} \to \mathbb{N}$ telle que $X \in U_n[f(n)]$ pour tout $n$. Pour tout $g \ge f$, la classe $\bigcap_n U_n[g(n)]$ est $\Pi_1^0(g)$ et ne contient que le point $X$. D'après la proposition 8-3.6, pour tout $g \ge f$ l'ensemble $X$ est $g$-calculable. Tout singleton $\Pi_2^0$ admet donc un modulus. Le corollaire 2.2 permet de conclure. ■

Nous verrons la réciproque du précédent résultat avec le théorème 29-5.4, qui nous fournira une élégante caractérisation des ensembles hyperarithmétiques.

## 3. Relativisation

L'itération du saut se relativise à n'importe quel oracle $X$.

**Définition 3.1.** Soit $X \in 2^\mathbb{N}$. On définit les itérations transfinies $H_a^X$ du saut pour les éléments $b \in O^X$ :

1. $H_1^X = X$ :

2. $H_{2a}^X = (H_a^X)'$ :

3. $H_{3.5^e}^X = \bigoplus_n H_{\Phi_e(X,n)}^X$.

◇

La hiérarchie de Kleene se relativise elle aussi sans problème à un oracle $X$, le long des ordinaux $\alpha < \omega_1^{ck}$, de même que les différents théorèmes vus jusqu'ici. En voici, notamment, trois exemples.
**Théorème 3.2**

Pour tout $X \in 2^N$, tout ordinal $\alpha < \omega_1^X$ et tout $a \in O_{=\alpha}^X$, on a

1. $O_{<\alpha}^X \leq_T H_{2^\alpha}^X$, uniformément en $a$;

2. $T_{<\alpha}^X \leq_T H_{2^\alpha}^X$, uniformément en $a$.

**Théorème 3.3**

Soit $X \in 2^N$, et soit $\alpha < \omega_1^X$. Soit $a \in O_{=\alpha}^X$. L'ensemble $H_{2^\alpha}^X$ est $\Sigma_\alpha^0(X)$-complet, uniformément en $X$ et $a$.

**Théorème 3.4**

Il existe $\mathcal{P} \subseteq \mathbb{N} \times 2^N \times 2^N$ une classe $\Pi_2^0$ telle que pour tout $X$, pour tout $a \in O^X$, la classe $\{Y : (a, X, Y) \in \mathcal{P}\}$ est le singleton $H_a^X$.

Notons dans les théorèmes précédents que l'on doit également relativiser le plus petit ordinal non calculable $\omega_1^{ck}$, et utiliser à la place $\omega_1^X$, le plus petit ordinal non $X$-calculable.

# 4. Hiérarchie borélienne effective

En suivant l'exemple de la hiérarchie de Kleene pour les ensembles d'entiers, il est possible de donner une version effective de la hiérarchie borélienne dont la version complète fut introduite avec la définition 27-3.3. Nous en donnons ici directement la version relativisée à n'importe quel oracle $X$.

**Définition 4.1.** La hiérarchie borélienne effective est définie par induction sur les ordinaux, relativement à un oracle $X \in 2^N$.

▷ Un $\Sigma_1^0(X)$-code est donné par une paire $\langle 0, e \rangle$. La classe $\mathcal{U}$ correspondante est donnée par $\mathcal{U} = \bigcup_{\sigma \in W_e^X} [\sigma]$.

▷ Un $\Pi_\alpha^0(X)$-code est donné par une paire $\langle 1, e \rangle$, où $e$ est un $\Sigma_\alpha^0(X)$-code. La classe $\mathcal{B}$ correspondante est donnée par $\mathcal{B} = 2^N \setminus \mathcal{A}$ où $\mathcal{A}$ est l'ensemble correspondant au code $e$.

▷ Un $\Sigma_\alpha^0(X)$-code est donné par une paire $\langle 2, e \rangle$, où $W_e^X \neq \emptyset$ énumère avec l'oracle $X$ des $\Pi_{\beta_n}^0(X)$-codes pour $\beta_n < \alpha$, avec $\sup_n(\beta_n+1) = \alpha$. La classe $\mathcal{B}$ correspondante est donnée par $\bigcup_n \mathcal{A}_n$ où $\mathcal{A}_n$ est la classe correspondant au $n$-ième code énuméré par $W_e^X$. ◇

On dit qu'une classe $\mathcal{B} \subseteq 2^N$ est $\Sigma_\alpha^0(X)$ (resp. $\Pi_\alpha^0(X)$) si elle correspond à un $\Sigma_\alpha^0(X)$-code (resp. un $\Pi_\alpha^0(X)$-code). On dit que la classe $\mathcal{B}$ est $\Delta_\alpha^0(X)$ si elle est à la fois $\Sigma_\alpha^0(X)$ et $\Pi_\alpha^0(X)$.

Souvenons-nous de la définition des boréliens non effectifs à travers les ordinaux. Nous avions insisté sur l'utilisation de l'axiome du choix dénombrable
afin de garantir que tout borélien est bien $\Sigma_{\alpha}^0$ pour un certain ordinal $\alpha$ dénombrable. Le principal intérêt est alors d'avoir tout borélien comme étant effectif relativement à un certain oracle $X$ : comme $\alpha$ est dénombrable il peut être encodé par un oracle, qui peut ensuite encoder l'arbre bien fondé correspondant au dépliage du code du borélien.

On obtient ainsi que tout borélien est $\Sigma_{\alpha}^0(X)$ pour un certain oracle $X$.

**Proposition 4.2.** Si une classe est $\Sigma_{\alpha}^0(X)$ alors $\alpha < \omega_1^X$.

★

PREUVE. Il suffit de répéter la preuve de la proposition 1.8 pour transformer un $\Sigma_{\alpha}^0(X)$-code en élément de $T^X$. On en déduit que $\alpha < \omega_1^X$. ■

Tout comme la hiérarchie de Kleene est stricte, il est possible de montrer que la hiérarchie borélienne est elle aussi stricte, dans un sens fort.

**Théorème 4.3**

Soit $X \in 2^N$. Pour tout $\alpha < \omega_1^X$, il existe une classe $\Sigma_{\alpha}^0(X)$ qui n'est pas $\Pi_{\alpha}^0$.

PREUVE. La preuve détaillée est laissée en exercice. On suppose pour simplifier la présentation $X = \emptyset$, la relativisation ne posant pas de problème particulier. L'idée générale est la suivante : on définit une fonctionnelle $\Psi$ telle que, pour tout $a \in O$, on ait :

(1) pour tout $Y \in 2^N$, la valeur $\Psi(Y, a)$ est un $\Sigma_{|a|}^0(Y)$-code;

(2) pour toute classe $\Sigma_{|a|}^0 A$, il existe un oracle $Y$ tel que $\Psi(Y, a)$ est un $\Sigma_{|a|}^0(Y)$-code de $A$;

(3) pour tout $Y \in 2^N$, la classe $\{Y \in 2^N : Y$ appartient à la classe de code $\Psi(Y, a)\}$ est $\Sigma_{\alpha}^0$.

La fonctionnelle $\Psi$ procède simplement à un système de codage des boréliens via son oracle, en utilisant $a \in O$ pour contrôler la hauteur du code produit. On montre alors que la classe

$C = \{Y \in 2^N : Y \text{n'appartient pas à la classe de code } \Psi(Y, a)\}$ ne peut pas être $\Sigma_{|a|}^0$. En effet, si tel était le cas, il y aurait un oracle $Y$ tel que $\Psi(Y, a)$ renvoie un $\Sigma_{|a|}^0(Y)$-code pour ce borélien. On aurait alors $Y \notin C$ssi $Y \in C$, ce qui est une contradiction. ■

Nous faisons à présent le lien entre la hiérarchie de Kleene et la hiérarchie borélienne effective.
Théorème 4.4

Une classe $\mathcal{A} \subseteq 2^\mathbb{N}$ est $\Sigma_\alpha^0$ si, et seulement si, il existe pour $a \in \mathcal{O}_{=\alpha}$ un entier $n$ tel que

$$ \mathcal{A} = \{ X : n \in H_{2^a}^X \}. $$

PREUVE. Montrons que pour $n \in \mathbb{N}$ et $a \in \mathcal{O}_{=\alpha}$ la classe $\{X : n \in H_{2^a}^X\}$ est $\Sigma_\alpha^0$, uniformément en $n$ et $a$. D'après le théorème 3.3, l'ensemble $H_{2^a}^X$ est $\Sigma_\alpha^0(X)$, uniformément en $X$ et $a$.

On a donc une fonction calculable $g : \mathbb{N} \to \mathbb{N}$ telle que $g(a)$ est un $\Sigma_\alpha^0(X)$-code de l'ensemble $H_{2^a}^X$ pour tout $X$.

Définissons à présent une fonction calculable $f : \mathbb{N}^2 \to \mathbb{N}$ telle que :

(1) l'entier $f(a, n)$ est le $\Sigma_\alpha^0$-code d'une classe borélienne pour tout $a \in \mathcal{O}_{=\alpha}$ et pour tout $n$;

(2) l'entier $n \in H_{2^a}^X$ si, et seulement si, $X$ appartient à la classe décrite par le $\Sigma_\alpha^0$-code $f(a, n)$.

La fonction $f(a, n)$ calcule le code $g(a)$, qui est pour tout $X$ un $\Sigma_\alpha^0(X)$-code de l'ensemble $H_{2^a}^X$. On utilise ensuite une fonction $h_n : \mathbb{N} \to \mathbb{N}$ définie induc- tivement sur les nœuds de l'arbre décrit par le code $g(a)$ (dépendamment d'un oracle $X$). Sur un code $\langle 2, e \rangle$, la fonction $h_n$ renvoie un code corres- pondant à la réunion des $[\sigma] \cap \mathcal{B}_\sigma$ pour chaque $\sigma$ tel que $W_e^\sigma$ énumère un code $e_\sigma$, et où $\mathcal{B}_\sigma$ est la classe codée par $h_n(e_\sigma)$. Sur un code $\langle 1, e \rangle$, la fonction $h_n$ renvoie $\langle 1, h_n(e) \rangle$. Sur un code $\langle 0, e \rangle$, la fonction $h_n$ renvoie le code $\langle 0, d \rangle$, où $d$ est le code de la classe $\Sigma_1^0$ qui énumère les chaînes $\sigma$ telles que $n \in W_e^\sigma$. La fonction $f(a, n)$ renvoie finalement $h_n(g(a))$. Il suffit de montrer par induction que $f$ satisfait les points (1) et (2) ci-dessus.

Montrons à présent que pour $\mathcal{A}$ une classe $\Sigma_\alpha^0$, on peut uniformément trou- ver un entier $e$ tel que $\mathcal{A} = \{X : e \in H_{2^a}^X\}$. Pour ce faire, on montre d'abord comment trouver un entier $d$ qui est pour tout $X$ le $\Sigma_\alpha^0(X)$-code d'un en- semble contenant 0 ssi $X \in \mathcal{A}$. On transforme pour cela uniformément en $X$ l'arbre correspondant au $\Sigma_\alpha^0$-code de $\mathcal{A}$ en $\Sigma_\alpha^0(X)$-code du même arbre, excepté que chaque feuille correspondant à $\mathcal{U} \subseteq 2^\mathbb{N}$, une classe $\Sigma_1^0$, est remplacée par une feuille correspondant à $U \subseteq \mathbb{N}$ un ensemble $\Sigma_1^0(X)$ tel que $0 \in U$ ssi un préfixe $\sigma$ de $X$ est tel que $[\sigma] \subseteq \mathcal{U}$. On montre fa- cilement par induction que 0 appartient au $\Sigma_\alpha^0(X)$-code $d$ ssi $X \in \mathcal{A}$. On utilise à présent le théorème 3.3 pour trouver une fonction calculable $h$ telle que 0 appartient à notre ensemble $\Sigma_\alpha^0(X)$ ssi $h(0) \in H_{2^a}^X$. On a alors $\mathcal{A} = \{X : h(0) \in H_{2^a}^X\}$. ■

Nous voyons pour finir une autre version du théorème précédent, mais pour les classes $\{Y : n \in \mathcal{O}_{<\alpha}^Y\}$.
**Théorème 4.5**

Soit $Y \in 2^\mathbb{N}$. Pour tout $n \in \mathbb{N}$ et $\alpha < \omega_1^Y$, la classe $\{X : n \in O_{<\alpha}^X\}$ est une classe $\Sigma_{\alpha+1}^0(Y)$, uniformément en $Y$ et en $n$.

PREUVE. On peut faire la même construction que dans le théorème précédent, d'une fonction calculable $f : \mathbb{N}^2 \to \mathbb{N}$ telle que :

(1) l'entier $f(a, n)$ est le $\Sigma_{\alpha+1}^0(Y)$-code d'une classe borélienne pour tout $a$ dans $O_{=\alpha}^Y$ et pour tout $n$;

(2) l'entier $n \in O_{<\alpha}^X$ si, et seulement si, $X$ appartient à la classe décrite par le $\Sigma_{\alpha+1}^0(Y)$-code $f(a, n)$.

D'après le théorème 3.2, pour tous $X, Y$, et pour tout $\alpha < \omega_1^Y$, on a

$$O_{<\alpha}^{X \oplus Y} \leq_T H_{2^a}^{X \oplus Y},$$

uniformément en $X, Y$, et en $a \in O_{=|\alpha|}^Y$. On a clairement $O_{<\alpha}^X \leq_m O_{<\alpha}^{X \oplus Y}$, car pour savoir si $e \in O_{<\alpha}^X$ il suffit de regarder si $e' \in O_{<\alpha}^{X \oplus Y}$, où $e'$ fait la même chose que $e$, mais en utilisant « la moitié » de son oracle correspondant à $X$. D'après le théorème 3.3, l'ensemble $H_{2^a}^{X \oplus Y}$ est $\Sigma_\alpha^0(X \oplus Y)$, uniformément en $X, Y$ et $a$. L'ensemble $O_{<\alpha}^X$ est donc $\Delta_{\alpha+1}^0(X \oplus Y)$, uniformément en $X, Y$ et en $\alpha < \omega_1^Y$, et il est donc en particulier $\Sigma_{\alpha+1}^0(X \oplus Y)$.

On peut alors procéder de manière similaire à la preuve précédente pour créer $f$. Les détails sont laissés au lecteur. ■

**Exercice 4.6.** (⋆) Montrer que l'on peut considérer sans perte de généralité que les classes $\Sigma_\alpha^0$ (de la forme $\bigcup_n B_n$) sont croissantes (c'est-à-dire qu'elles vérifient $B_n \subseteq B_{n+1}$). ◇

**Exercice 4.7.** (⋆) Montrer que la proposition 17-4.3 se poursuit dans le transfini : pour $\mathcal{A}$ une classe $\Sigma_\alpha^0$, l'ensemble $\{q \in \mathbb{Q} : \lambda(\mathcal{A}) > q\}$ est $\Sigma_\alpha^0$, uniformément en un code de $\mathcal{A}$. ◇
<figure><img src="image_174.png" /></figure>
Chapitre 29

Au delà des hyperarithmétiques

Qu'y a-t-il au-delà des ensembles hyperarithmétiques ? D'après une variation de l'exercice 28-1, les fragments du $\mathcal{O}$ de Kleene sont arbitrairement complexes dans la hiérarchie hyperarithmétique

Dans ce chapitre, nous allons introduire les classes et ensembles $\Sigma_1^1$ et $\Pi_1^1$ définis à l'aide de quantifications du second ordre. Ces notions vont nous permettre de donner une caractérisation des ensembles hyperarithmétiques purement en termes de définissabilité par des formules du second ordre, et d'en déduire de nouvelles caractérisations en termes de modulus ou de singletons $\Pi_2^0$.

Les ensembles $\Pi_1^1$ jouent un rôle central, notamment dans la correspondance entre calculabilité classique et hypercalculabilité. Nous verrons dans quelle mesure les ensembles $\Pi_1^1$ peuvent être perçus comme des ensembles « hypercalculatoirement énumérables ». Nous verrons en particulier que le $\mathcal{O}$ de Kleene joue pour les hyperarithmétiques un rôle analogue à celui joué par $\emptyset'$ pour les calculables. Cette correspondance entre calculabilité et hypercalculabilité sera poussée plus loin dans le chapitre 30, où nous verrons que les classes $\Sigma_1^1$ peuvent être vues comme le pendant hypercalculable des classes $\Pi_1^0$.

1. Un peu d'histoire : l'école de Moscou

Au XIXe siècle, les écrivains Nicolas Gogol et Fiodor Dostoïevski théorisent « l'âme russe », concept flou encore aujourd'hui, souvent perçu comme un mélange de mysticisme, d'irrationalité, de démesure et d'abattement.
On ne peut s'empêcher de voir la manifestation de cette fameuse âme
russe — qu'elle soit fantasmée ou réelle — quand on se plonge dans l'his-
toire de la théorie des ensembles moscovite du début du XXe siècle. Les
mathématiciens Jean-Michel Kantor et Loren Graham ont mené une enquête
historique approfondie dans laquelle ils étudient l'impact des différences
culturelles entre la Russie et l'Europe occidentale, sur l'accueil et la per-
ception des nouvelles mathématiques que constitue alors la théorie des en-
sembles. Ils écrivent notamment [107] :

« *Les mathématiciens russes de la fin du XIXe siècle et du début du XXe siècle pensaient que leurs travaux étaient étroitement liés à la philosophie, à la religion et à l'idéologie en général. De ce point de vue, ils se démarquaient de la plupart de leurs collègues français.* »

Egorov et Luzin

Nous avons parlé dans la section 17-1 du célèbre trio Français : Borel, Baire et Lebesgue, dont le travail avait éclos au début du XXe siècle sur un ensemble de résultats d'une grande richesse faisant suite aux travaux de Cantor sur l'infini. Les concepts d'ensembles boréliens font alors peu à peu leur chemin dans la communauté mathématique, qui en perçoit l'esthétique et l'intérêt. C'est dans la lignée de leurs travaux que va naître sous l'impulsion de Dimitri Egorov et de Nicolaï Luzin l'École mathématique de Moscou, une des plus impressionnantes qui ait jamais existé. Egorov et Luzin ont étudié les mathématiques auprès de Nikolai Vasilievich Bugaev (1837-1903), qui s'intéressa beaucoup à la théorie des fonctions discontinues, lesquelles avaient pour lui un intérêt philosophique qui allait bien au-delà des considérations logiques des mathématiciens français et allemands [107, p.89] :

« *La discontinuité est une affirmation de l'individualité indépendante et autonome. La discontinuité intervient aussi là où surgissent les questions des causes finales et les problèmes esthétiques et éthiques.* »

On voit le contraste saisissant avec les déclarations de Poincaré (voir la
section 17-1.1) pour qui la discontinuité est une aberration logique sans
lien avec le monde réel, là où Bugaev voit dans les objets mathématiques
discontinus un intérêt abstrait, presque mystique. Bugaev fut le professeur
de mathématiques d'Egorov, qui au cours de plusieurs séjours en France
et en Allemagne, se familiarisa avec les tout récents développements de
la théorie des ensembles. Cette théorie le passionne, et Egorov décide de
l'enseigner une fois de retour à Moscou. Luzin figure parmi ses étudiants
préférés, et ils monteront ensemble ce qui sera d'abord un séminaire de
mathématiques baptisé Lusitanie — on ne sait pas vraiment aujourd'hui
si ce nom fut choisi en l'honneur de Luzin ou non — qui constituera les
prémisses de ce qui deviendra plus tard l'École de mathématique de Moscou. L'histoire de la Lusitanie s'inscrit elle-même dans la grande Histoire et les profonds bouleversements qui agiteront la Russie au début du XXe siècle. Mentionnons à ce sujet une anecdote sur la jeunesse de Luzin. Ce dernier est profondément marqué par la révolution manquée de 1905. Il perd son intérêt pour les mathématiques et traverse trois années durant une crise profonde, comme en témoignent les lettres qu'il écrit à Egorov [107, p.106] :

> « Quand vous m'avez rencontré à l'Université, je n'étais qu'un enfant ignorant. Je ne sais pas ce qui s'est passé, mais je ne peux me satisfaire aujourd'hui des fonctions analytiques et des séries de Taylor... La misère du peuple, les tourments de la vie... sont des visions insupportables... je ne peux plus vivre uniquement de science... je n'ai rien, pas de vision du monde et pas d'éducation. »

Luzin sortira de sa dépression avec l'aide de son ami et guide spirituel Pavel Florensky — prêtre et mathématicien —, notamment suite à la lecture de la thèse de Florensky « De la vérité religieuse ». Luzin reprend alors ses travaux mathématiques. Toute sa vie, il s'intéressera essentiellement à la théorie des ensembles, qu'il étudiera avec toute la rigueur scientifique d'un mathématicien, mais aussi avec une conviction qui relève d'une certaine forme de foi religieuse. On trouvera par exemple dans ses notes :

> « Nous pensons que les nombres entiers existent objectivement. Nous pensons que la totalité des nombres transfinis de seconde classe existe objectivement. Nous désirons la chose suivante : ayant supposé leur évidence, nous associons à chacun des nombres transfinis une définition, un nom, et cela pour tous les nombres transfinis que nous envisageons. »

## La Lusitanie

Egorov et Luzin lancent peu de temps avant la Seconde Guerre mondiale un séminaire pour un petit groupe d'étudiants motivés : la Lusitanie, qui connaîtra un succès et une pérennité inattendue.

Dans la première décennie du XXe siècle, la Russie ne comptait quasi aucun mathématicien de renommée mondiale. Cela changera avec la création de la Lusitanie. En dix ans à peine, de nombreux très jeunes mathématiciens issus de cette école vont se faire une place sur la scène internationale, parmi lesquels on peut citer Pavel Alexandrov, qui développera une part importante de la topologie moderne, Pavel Urysohn, autre topologue de renom, ou encore Nina Bari, connue pour ses travaux sur les séries trigonométriques. Andreï Kolmogorov, certainement le plus célèbre mathématicien russe, passera aussi par la Lusitanie, mais un peu plus tard. En 1930, Moscou sera devenu une des principales capitales mathématiques mondiales.
Le séminaire d'Egorov et de Lusin prend rapidement : entre la pédagogie et l'investissement passionné des deux professeurs, la motivation et la qualité scientifique exceptionnelle des étudiants, l'alchimie se fait. Rapidement, un groupe très soudé, joyeux et travailleur se forme, et découvre avec admiration les derniers développements de ces « nouvelles mathématiques » que constitue la théorie des ensembles, à travers lesquelles se forme le sentiment de prendre part à quelque chose d'important, à une aventure intellectuelle plus grande que soi.

L'histoire de la Lusitanie est d'autant plus remarquable que les nombreux développements mathématiques de premier plan qui y eurent lieu se firent dans des conditions matérielles catastrophiques : la Première Guerre mondiale participe à la famine et aux pénuries généralisées qui sévissent dans le pays. La révolution d'Octobre (1917) plonge le pays dans une violente guerre civile. Les étudiants de Lusin et d'Egorov souffrent du froid et de la faim. La température des salles de classe descend parfois sous les 0-degrés [107, p.137]. Qu'importe, les étudiants viennent tout de même.

## La théorie descriptive des ensembles

Le premier accomplissement d'importance de la Lusitanie est celui qui concerne l'objet du chapitre à venir : la naissance de la théorie descriptive des ensembles. Une des questions centrales était à l'époque celle de l'hypothèse du continu de Cantor. Alexandrov, alors à peine âgé de dix-huit ans montre que l'hypothèse du continu est vraie pour toutes les classes boréliennes. Nous verrons une forme moderne et effective de ce théorème avec le corollaire 30-3.3. Nous le savons aujourd'hui, l'hypothèse du continu demandera des efforts et développements bien plus conséquents, mais pour l'époque, il s'agissait tout de même d'une étape importante vers sa résolution. Pouvait-on étendre la preuve d'Alexandrov à toutes les classes ? À l'époque, l'existence de classes non boréliennes n'était pas encore complète-claire, et des exemples précis de ces classes l'étaient encore moins. Un an plus tard, un autre jeune étudiant de la Lusitanie, Mikhaïl Souslin, repère une erreur dans une preuve de Lebesgue datant de 1905, qui restera fameuse comme « l'erreur de Lebesgue », marquant le point de départ d'un champ de recherche nouveau : la théorie descriptive des ensembles. La démonstration de Lebesgue porte sur l'énoncé suivant : l'image d'une classe borélienne par une fonction continue est aussi une classe borélienne. Souslin montrera que ce n'est pas nécessairement vrai : l'image de certains boréliens par certaines fonctions continues sont des ensembles strictement plus complexes que les boréliens. C'est la découverte par Souslin des classes dites analytiques ou comme nous les appelons dans cet ouvrage, les classes $\Sigma_1^1$. Souslin [219] montrera par la suite que les boréliens sont exactement les classes $\Sigma_1^1$ dont le complémentaire est également $\Sigma_1^1$. Plus tard,
Kleene [116] donnera — en s’appuyant sur des résultats de Spector [214] — une version effective du théorème de Souslin, et qui s’applique non seulement aux classes, mais aussi aux ensembles d’entiers. C’est ce résultat que nous présenterons dans la section 5.

## La fin

Si l'héritage de la Lusitanie perdure jusqu'à aujourd'hui, les troubles politiques du pays auront raison de la Lusitanie elle-même, qui s'achèvera vers les années 1920. La nouvelle génération de mathématiciens formée par Luzin et Egorov s'adapte au nouvel ordre des choses dicté par le pouvoir en place, là où l'ancienne génération ne s'y fait pas. Egorov ne cache ni ses convictions religieuses, ni son animosité envers le nouveau régime. Il est arrêté en 1930, accusé de mélanger mathématiques et religion. En prison, Egorov entame une grève de la faim, suite à laquelle il doit être transféré à l'hôpital où il meurt peu de temps après.

Luzin quant à lui fait profil bas. L'arrestation de son collègue et ami le terrorise, aussi se fait-il aussi discret que possible. Il cache ses convictions religieuses, et essaye de montrer sa loyauté envers l'état soviétique. Mais son passé le rattrape. Il est la cible d'attaques répétées jusqu'en 1936, au moment où il est accusé lors d'un procès d'être, en substance, un ennemi du parti soviétique. Plusieurs de ses anciens étudiants témoignent contre lui, l'accusant de plagiat et de népotisme. C'est un coup terrible pour Luzin, qui pour une raison encore floue aujourd'hui, et malgré une condamnation officielle, ne sera finalement ni arrêté ni expulsé de l'Académie des sciences.

En dépit de cet épisode douloureux de l'histoire des mathématiques, L'école fondée par Egorov et Luzin a perduré, et à travers elle, la Russie a posé une marque profonde et durable sur les mathématiques, apportant peut-être un peu de cette mystérieuse âme russe, à travers un style, et une intensité dans l'engagement mathématique. Nous terminons notre interlude historique par une citation du livre de Jean Michel Kantor et Loren Graham, qui montre bien la façon dont l'école russe a marqué l'imaginaire du mathématicien :

> « On citait encore avec une admiration mêlée de crainte les légendaires séminaires de mathématiques de Moscou où les exposés, commencés dans l'après-midi, se prolongeaient souvent tard dans la soirée, organisateurs et assistants du séminaire soumettant les orateurs à une longue suite de questions dans le but de comprendre. Chaque personne assistant au séminaire pouvait d'ailleurs être envoyée au tableau à l'improviste, ce qui rendait impossible l'habitude occidentale d'assister à un séminaire en spectateur distant et distrait. »

Les auteurs de ce livre, qui ont eu la chance de travailler avec leurs collègues moscovites, peuvent attester que la légende comporte bien un fond de vérité...
## 2. Quantifications du second ordre

Nous avons vu avec la hiérarchie de Kleene que la hiérarchie arithmétique pouvait être étendue de manière naturelle le long des ordinaux calculables, pour donner les ensembles hyperarithmétiques. D'après la remarque suivant la proposition 28-1.7, cette extension peut-être pensée en termes d'alternance de quantificateurs sur des formules infinies.

Il existe une autre approche naturelle pour étendre la hiérarchie arithmétique, consistant à autoriser les quantificateurs du second ordre, autrement dit les quantificateurs sur les ensembles d'entiers. On obtient alors une hiérarchie dont le premier niveau contient déjà tous les ensembles hyperarithmétiques, comme nous le verrons par la suite.

**Définition 2.1.** Soit un ensemble $A \subseteq \mathbb{N}$.

1. A est $\Sigma_1^1$ s'il existe une classe arithmétique $B \subseteq 2^\mathbb{N} \times \mathbb{N}$ telle que
   $$A = \{n \in \mathbb{N} : \exists X \in 2^\mathbb{N} (X, n) \in B\}.$$

2. A est $\Pi_1^1$ s'il existe une classe arithmétique $B \subseteq 2^\mathbb{N} \times \mathbb{N}$ telle que
   $$A = \{n \in \mathbb{N} : \forall X \in 2^\mathbb{N} (X, n) \in B\}.$$

3. A est $\Delta_1^1$ si A est $\Pi_1^1$ et $\Sigma_1^1$.

Les ensembles $\Sigma_1^1$ et $\Pi_1^1$ sont aussi qualifiés respectivement d'analytiques et co-analytiques effectifs. ◇

Notons que les $\Pi_1^1$ sont les complémentaires des $\Sigma_1^1$, et vice-versa. Un ensemble $\Sigma_1^1$ (resp. $\Pi_1^1$) a le droit d'utiliser des quantifications existentielles (resp. universelles) non pas sur les entiers, mais sur les ensembles d'entiers. Cela donne beaucoup plus de pouvoir expressif, et nous verrons que les ensembles hyperarithmétiques sont tous $\Pi_1^1$ et $\Sigma_1^1$. Nous verrons en fait avec le théorème 5.2 que les ensembles hyperarithmétiques sont exactement les ensembles $\Delta_1^1$.

On définit de la même manière les notions de $\Sigma_1^1$ et $\Pi_1^1$ pour les classes.

**Définition 2.2.** Soit une classe $\mathcal{A} \subseteq 2^\mathbb{N}$.

1. A est $\Sigma_1^1$ s'il existe une classe arithmétique $B \subseteq 2^\mathbb{N} \times 2^\mathbb{N}$ telle que
   $$A = \{X \in 2^\mathbb{N} : \exists Y \in 2^\mathbb{N} (Y, X) \in B\}.$$

2. A est $\Pi_1^1$ s'il existe une classe arithmétique $B \subseteq 2^\mathbb{N} \times 2^\mathbb{N}$ telle que
   $$A = \{X \in 2^\mathbb{N} : \forall Y \in 2^\mathbb{N} (Y, X) \in B\}.$$

3. A est $\Delta_1^1$ si, seulement si, A est $\Pi_1^1$ et $\Sigma_1^1$.
Les classes $\Sigma_1^1$ et $\Pi_1^1$ sont aussi qualifiées respectivement d'analytiques et co-analytiques effectives. ◇

Notons que les définitions de $\Sigma_1^1$ et $\Pi_1^1$ s'étendent naturellement à l'espace de Baire ainsi qu'au produit de différents espaces sur lesquels la définition a cours.

**Exemple 2.3.** Une classe $\mathcal{A} \subseteq \mathbb{N}^\mathbb{N} \times 2^\mathbb{N} \times \mathbb{N}$ est $\Sigma_1^1$ s'il existe un ensemble arithmétique $\mathcal{B} \subseteq 2^\mathbb{N} \times \mathbb{N}^\mathbb{N} \times 2^\mathbb{N} \times \mathbb{N}$ tel que

$$ A = \{(f, X, n) : \exists Y \in 2^{\mathbb{N}} (Y, f, X, n) \in \mathcal{B}\}. $$

## 2.1. Propriétés de clôture

Nous allons voir que, de manière équivalente, les quantifications des classes et ensembles $\Sigma_1^1$ et $\Pi_1^1$ peuvent se faire sur les fonctions plutôt que sur les ensembles d'entiers. De manière générale, ces classes seront plus simples à manipuler via des quantifications sur les fonctions. Nous introduisons pour cela quelques notations qui nous seront utiles.

### Notation

* Soit $X$ un ensemble infini. Alors, $f_X$ désigne la fonction de $\mathbb{N}$ dans $\mathbb{N}$ encodée par $X$, c'est-à-dire la fonction telle que $f_X(n)$ renvoie le $n$-ième élément de $X$.

* La notation $\exists X \oplus Y \mathcal{B}(X, Y)$ est un raccourci pour signifier $\exists Z \mathcal{B}(Z^{[0]}, Z^{[1]})$, où $Z^{[i]} = \{2n + i : n \in Z\}$.

* Il en va de même pour la notation $\exists (\bigoplus_m X_m) \forall m \mathcal{B}(X_m, m)$.

La proposition suivante implique en particulier que les classes ou ensembles $\Sigma_1^1$ peuvent être définis avec un nombre arbitraire de quantificateurs existentiels sur les ensembles, essentiellement en codant deux quantifications en une seule à l'aide de la jointure effective.

### Proposition 2.4.

(1) Les ensembles ou classes $\Sigma_1^1$ sont clos par réunion effective indexée par les ensembles d'entiers ou indexée par les fonctions de $\mathbb{N}$ dans $\mathbb{N}$.

(2) Les ensembles ou classes $\Pi_1^1$ sont clos par intersection effective indexée par les ensembles d'entiers ou par les fonctions de $\mathbb{N}$ dans $\mathbb{N}$. ★

**PREUVE.** Notons que (1) est équivalent à (2), par passage au complémentaire. Nous montrons donc uniquement (1), et nous le faisons à la fois pour les classes et les ensembles en considérant des classes de l'espace produit $2^\mathbb{N} \times \mathbb{N}$.
Soit $\mathcal{A} \subseteq 2^{\mathbb{N}} \times 2^{\mathbb{N}} \times \mathbb{N}$ la classe $\Sigma_1^1$ égale à $\{(Y, X, n) : \exists Z (Z, Y, X, n) \in \mathcal{B}\}$,
pour $\mathcal{B}$ un ensemble arithmétique. Montrons que la classe

$$ \{X : \exists Y (Y, X, n) \in \mathcal{A}\} $$

est aussi $\Sigma_1^1$. On a

$$ \exists Y (Y, X, n) \in \mathcal{A} \Leftrightarrow \exists Z \exists Y (Z, Y, X, n) \in \mathcal{B} \Leftrightarrow \exists Z \oplus Y (Z, Y, X, n) \in \mathcal{B}. $$

On obtient ainsi la clôture pour les réunions indexées par des ensembles d'entiers.

Soit $\mathcal{A} \subseteq \mathbb{N}^{\mathbb{N}} \times 2^{\mathbb{N}} \times \mathbb{N}$ la classe $\Sigma_1^1$ égale à $\{(f, X, n) : \exists Y (Y, f, X, n) \in \mathcal{B}\}$,
pour $\mathcal{B}$ un ensemble arithmétique. Montrons que la classe

$$ \{(X, n) : \exists f (f, X, n) \in \mathcal{A}\} $$

est aussi $\Sigma_1^1$. On a

$$ \exists f (f, X, n) \in \mathcal{A} \Leftrightarrow \exists Y \exists f (Y, f, X, n) \in \mathcal{B} $$

$$ \Leftrightarrow \exists Y \exists Z \text{ tel que } (Z \text{ est infini et } (Y, f_Z, X, n) \in \mathcal{B}). $$

Être infini est bien un prédicat arithmétique. Par la propriété de clôture du paragraphe précédent, la classe est bien $\Sigma_1^1$. ■

## Quantification sur $\mathbb{N}^\mathbb{N}$ vs $2^\mathbb{N}$

La proposition précédente a une implication importante : les ensembles ou classes $\Sigma_1^1$ peuvent se décrire de manière équivalente via des quantifications du second ordre sur $\mathbb{N}^\mathbb{N}$ ou bien sur $2^\mathbb{N}$. C'est une propriété que nous utiliserons pour le théorème de forme normale à venir.

Pour la preuve de la proposition suivante, nous utiliserons l'axiome du choix dénombrable, afin de nous simplifier la vie. Cet axiome n'est toutefois pas absolument nécessaire : nous verrons plus tard avec la proposition 30-1.2 qu'il est automatiquement vérifié pour les classes $\Sigma_1^1$ (qui sont celles sur lesquelles on l'utilise dans la proposition).

**Proposition 2.5.** Les ensembles ou classes $\Sigma_1^1/\Pi_1^1$ sont clos par réunion ou intersection effective indexée par les entiers. ★

**PREUVE.** Là encore, on montre la proposition à la fois pour les classes et les ensembles. Soit $\mathcal{A} \subseteq \mathbb{N} \times (2^{\mathbb{N}} \times \mathbb{N})$ la classe $\Sigma_1^1$ égale à

$$ \{(m, X, n) : \exists f (f, m, X, n) \in \mathcal{B}\}, $$

pour $\mathcal{B}$ un ensemble arithmétique. Montrons que la classe

$$ \{(X, n) : \exists m (m, X, n) \in \mathcal{A}\} $$

est aussi $\Sigma_1^1$. On a

$$ \exists m (m, X, n) \in \mathcal{A} \Leftrightarrow \exists m \exists f (f, m, X, n) \in \mathcal{B} \Leftrightarrow \exists f \exists m (f, m, X, n) \in \mathcal{B}. $$

Le prédicat $\exists m (f, m, X, n) \in \mathcal{B}$ étant arithmétique, la classe est bien $\Sigma_1^1$.
Montrons que la classe $\{(X, n) : \forall m (m, X, n) \in \mathcal{A}\}$ est aussi $\Sigma_1^1$.
On a $\forall m (m, X, n) \in \mathcal{A}$ ssi $\forall m \exists f (f, m, X, n) \in \mathcal{B}$. En particulier, pour tout $m$, il existe une fonction $f$ telle que $(f, m, X, n) \in \mathcal{B}$. En utilisant l'axiome du choix, il suffit de choisir pour chaque $m$ une fonction $f_m$ telle que $(f_m, m, X, n) \in \mathcal{B}$. En considérant la fonction $\bigoplus_m f_m$, on a alors

$$ \forall m \exists f (f, m, X, n) \in \mathcal{B} \Leftrightarrow \exists \left( \bigoplus_m f_m \right) \forall m (f_m, m, X, n) \in \mathcal{B}. $$

Le prédicat $\forall m (f_m, m, X, n) \in \mathcal{B}$ étant arithmétique, la classe est bien $\Sigma_1^1$.
Par passage au complémentaire, les ensembles ou classes $\Pi_1^1$ sont clos par réunion ou intersection effective indexée par les entiers. $\blacksquare$

Nous verrons avec la proposition 30-1-2 que l'on peut construire des fonctions de choix sur les suites dénombrables de classes $\Sigma_1^1$ —sans utiliser bien sûr l'axiome du choix. Dans la deuxième partie de la proposition précédente, les classes $\mathcal{B}_m = \{f \in \mathbb{N}^\mathbb{N} : (f, m, X, n) \in \mathcal{B}\}$ sont arithmétiques (avec l'oracle $X$), et donc en particulier $\Sigma_1^1(X)$. On peut dès lors choisir dans chaque $\mathcal{B}_m$ une fonction $f_m$ sans utiliser l'axiome du choix. Il faut simplement vérifier que les développements menant à la construction de cette fonction de choix n'utilisent pas la proposition précédente. C'est bien le cas, les développements en question tiennent essentiellement au théorème de forme normal de Kleene de la section suivante, qui n'a pas besoin de la clôture des $\Sigma_1^1$ par réunion ou intersection effective.

## 2.2. Formes normales

L'avantage d'utiliser des quantifications sur les fonctions plutôt que sur les ensembles d'entiers, est la simplicité des formes normales suivantes, pour les prédicats $\Sigma_1^1$ et $\Pi_1^1$.

**Théorème 2.6 (Kleene [115])**

Soit une classe $\mathcal{A} \subseteq 2^{\mathbb{N}} \times \mathbb{N}$.

(1) La classe $\mathcal{A}$ est $\Sigma_1^1$ si, et seulement si, il existe une fonctionnelle $\Phi_e$ telle que $(X, n) \in \mathcal{A} \Leftrightarrow \exists f \Phi_e(f, X, n) \uparrow$.

(2) La classe $\mathcal{A}$ est $\Pi_1^1$ si, et seulement si, il existe une fonctionnelle $\Phi_e$ telle que $(X, n) \in \mathcal{A} \Leftrightarrow \forall f \Phi_e(f, X, n) \downarrow$.

### PREUVE

Notons que (1) est équivalent à (2) par passage au complémentaire. On montre donc tout simplement (1). Sans perte de généralité, une classe $\Sigma_1^1$ de $2^{\mathbb{N}} \times \mathbb{N}$ est de la forme $\{(X, n) : \exists f \mathcal{B}(f, X, n)\}$. Par ailleurs, $\mathcal{B}$ est de la forme $\exists x_1 \forall x_2 \dots \mathcal{R}(x_1, x_2, \dots, x_m, f, X, n)$, pour un certain $m$ et un certain prédicat récursif $\mathcal{R}$. On montre par induction que l'on peut « avaler » les quantifications de $\mathcal{B}$ par la quantification existentielle sur les fonctions.
Soit $\mathcal{A} = \{(X, n) : \exists f \exists y (f, y, X, n) \in \mathcal{B}\}$ pour un prédicat arithmétique $\mathcal{B}$. Alors, on peut avaler $y$ dans la quantification de $f$, car on a aussi $\mathcal{A} = \{(X, n) : \exists f (f \upharpoonright_{\mathbb{N}^*}, f(0), X, n) \in \mathcal{B}\}$, où $f \upharpoonright_{\mathbb{N}^*}$ est la fonction telle que $f \upharpoonright_{\mathbb{N}^*} (n) = f(n + 1)$ pour tout $n$.

Soit $\mathcal{A} = \{(X, n) : \exists f \forall y \exists z (f, y, z, X, n) \in \mathcal{B}\}$, pour un prédicat arithmétique $\mathcal{B}$. Alors, on a aussi $\mathcal{A} = \{(X, n) : \exists f \oplus g \forall y (f, y, g(y), X, n) \in \mathcal{B}\}$.

On peut ainsi « avaler » les quantificateurs arithmétiques jusqu’à arriver à un prédicat du type $\mathcal{A} = \{(X, n) : \exists f \forall y (f, y, X, n) \in \mathcal{R}\}$, où $\mathcal{R}$ et un prédicat calculable, que l’on transforme facilement en fonctionnelle $\Phi_e$ telle que $\mathcal{A} = \{(X, n) : \exists f \Phi_e(f, X, n) \uparrow\}$.

## 2.3. Relativisation

Tout comme pour les hiérarchies hyperarithmétiques, les notions d'ensembles/classes $\Sigma_1^1/\Pi_1^1$ se relativisent à un oracle. Le théorème de forme normale se relativise aussi sans problème.

**Théorème 2.7 (Forme normale relativisée)**

Soit une classe $\mathcal{A} \subseteq 2^{\mathbb{N}} \times \mathbb{N}$ et soit $Z \in 2^{\mathbb{N}}$.

1. La classe $\mathcal{A}$ est $\Sigma_1^1(Z)$ si, et seulement si, il existe une fonctionnelle $\Phi_e$ telle que $(X, n) \in \mathcal{A} \Leftrightarrow \exists f \Phi_e(f, Z, X, n) \uparrow$.

2. La classe $\mathcal{A}$ est $\Pi_1^1(Z)$ si, et seulement si, il existe une fonctionnelle $\Phi_e$ telle que $(X, n) \in \mathcal{A} \Leftrightarrow \forall f \Phi_e(f, Z, X, n) \downarrow$.

Tout comme pour les boréliens, les classes $\Sigma_1^1/\Pi_1^1$ ont aussi une version non effective. Ce sont ces versions non effectives qui furent d'abord découvertes et étudiées par Mikhail Souslin [219] en 1917.

**Définition 2.8.** Une classe $\mathcal{A} \subseteq 2^{\mathbb{N}} \times \mathbb{N}$ est $\Sigma_1^1$ si $\mathcal{A}$ est $\Sigma_1^1(Z)$ pour un certain $Z$. De la même manière, $\mathcal{A}$ est $\Pi_1^1$ si $\mathcal{A}$ est $\Pi_1^1(Z)$ pour un certain $Z$. $\diamond$

La définition que nous donnons ici n’est pas la définition originelle : les classes $\Sigma_1^1$, ou *analytiques*, étudiées par Souslin étaient les images de classes boréliennes par des fonctions continues. Nous verrons dans la section 30-1 que les classes $\Sigma_1^1(X)$ admettent effectivement une représentation canonique qui en font les images de $\mathbb{N}^\mathbb{N}$ par des fonctions calculables en $O^X$. Les classes $\Pi_1^1$ sont quant à elles qualifiées aussi de *co-analytiques*.

**Exercice 2.9.** Montrer que si $X$ est $\Sigma_1^1(Y)$ et $Y$ est $\Delta_1^1(Z)$, alors $X$ est $\Sigma_1^1(Z)$. $\diamond$
## 2.4. Séparations

Nous montrons finalement que les ensembles/classes $\Sigma_1^1/\Pi_1^1$ sont distincts. Ces résultats de séparation sont fondamentaux, notamment à la lumière du théorème 5.2 et du corollaire 5.15 à venir, qui nous fourniront alors une séparation entre les classes boréliennes et les classes $\Sigma_1^1/\Pi_1^1$.

**Théorème 2.10**

Il existe des ensembles $\Pi_1^1$ qui ne sont pas $\Sigma_1^1$, et vice-versa.

PREUVE. Soit $A \subseteq \mathbb{N}$ la classe $\Pi_1^1$ suivante : $n \in A$ ssi $\forall f \Phi_n(f, n) \downarrow$. Supposons par l'absurde que le complémentaire de $A$ soit $\Pi_1^1$. Alors, d'après la forme normale de Kleene, il existe un code $e$ tel que $n \in \mathbb{N} \setminus A$ ssi $\forall f \Phi_e(f, n) \downarrow$. On a donc $e \in \mathbb{N} \setminus A$ ssi $\forall f \Phi_e(f, e) \downarrow$ ssi $e \in A$, ce qui est une contradiction. Donc, $A$ est $\Pi_1^1$, mais pas $\Sigma_1^1$. Son complémentaire est donc $\Sigma_1^1$, mais pas $\Pi_1^1$. ■

La preuve du théorème précédent est très similaire à celle qui montre que $\emptyset'$ est un ensemble $\Sigma_1^0$ qui n'est pas $\Pi_1^0$. Cette vision des choses sera renforcée dans la section 4 avec l'analogie entre ensembles $\Pi_1^1$ et ensembles c. e.

**Théorème 2.11**

Il existe des classes $\Pi_1^1$ qui ne sont pas $\Sigma_1^1$, et des classes $\Sigma_1^1$ qui ne sont pas $\Pi_1^1$.

PREUVE. Soit $\mathcal{A}$ la classe $\Pi_1^1$ égale à $\{1^n 0 X : \forall f \Phi_n(f, X, 1^n 0 X) \downarrow\}$. Supposons par l'absurde que $\mathcal{A}$ soit $\Sigma_1^1$, c'est-à-dire que $2^\mathbb{N} \setminus \mathcal{A}$ soit $\Pi_1^1$. Alors, il existe $Y$ tel que $2^\mathbb{N} \setminus \mathcal{A}$ est $\Pi_1^1(Y)$, et il existe donc $e$ tel que

$$2^\mathbb{N} \setminus \mathcal{A} = \{X : \forall f \Phi_e(f, Y, X) \downarrow\}.$$

À présent, on a $1^e 0 Y \in \mathcal{A}$ ssi $\forall f \Phi_e(f, Y, 1^e 0 Y) \downarrow$ ssi $1^e 0 Y \in 2^\mathbb{N} \setminus \mathcal{A}$, ce qui est une contradiction. Donc, $\mathcal{A}$ n'est pas $\Sigma_1^1$ et, par passage au complémentaire, $2^\mathbb{N} \setminus \mathcal{A}$ est une classe $\Sigma_1^1$ qui n'est pas $\Pi_1^1$. ■

# 3. Les $\Pi_1^1$ et les bons ordres

Nous voyons dans cette section le lien étroit entre les ensembles $\Pi_1^1$ et la notion de bon ordre.

**Théorème 3.1**

L'ensemble $O^X$ est $\Pi_1^1(X)$ uniformément en $X$.

PREUVE. On montre le théorème pour $O$. La preuve se relativise sans problème uniformément à un oracle $X$. Nous étendons pour cette preuve l'ordre $<_o$ au maximum d'entiers possibles.
Pour un entier $a$ quelconque, on écrira $a <_o 2^a$. Pour tout entier $e$, si $\Phi_e(n) \downarrow$, on écrira $\Phi_e(n) <_o 3 \times 5^e$. On clôt ensuite la relation $<_o$ transitivement (notons que des cycles peuvent apparaître et que $<_o$ n’est plus une relation d’ordre sur certains sous-ensembles d’entiers).

On définit une première condition $\Pi_2^0$ pour qu’un élément $a$ appartienne à $O$. Soit $A$ l’ensemble contenant $a$ ainsi que les éléments $b <_o a$; alors, la condition est la suivante.

(1) La relation $<_o$ est un ordre total restreint aux éléments de $A$, et ces derniers sont égaux à 1, ou à $2^b$ pour un certain $b$, ou à $3 \times 5^e$ pour un code $e$ tel que $\Phi_e$ est total avec $\Phi_e(n) <_o \Phi_e(n+1)$ pour tout $n$.

Cette condition n’est pas suffisante : il se pourrait qu’un code $a$ la satisfasse mais soit tel que l’énumération de $A$ contienne une suite infinie d’éléments de plus en plus petits : ... $<_o a_3 <_o a_2 <_o a_1 <_o a$. Il faut alors en plus satisfaire la condition $\Pi_1^1$ suivante.

(2) Pour tout $B \subseteq A$, si $B$ est non vide, alors $B$ contient un plus petit élément pour $<_o$.

Il est clair que tout élément de $O$ satisfait (1) et (2). Réciproquement, montrons que si $a$ satisfait (1) et (2), alors $a \in O$. Raisonnons par l'absurde et supposons que $a \notin O$. Comme $a \in A$, $A \setminus O \neq \emptyset$, donc par (2), $A \setminus O$ possède un plus petit élément, que l'on note $d$. Par (1), soit $d=1$, soit $d$ est de la forme $2^b$, soit de la forme $3 \times 5^e$ avec $\Phi_e(n) <_o \Phi_e(n+1)$ pour tout $n$. Comme $1 \in O$, $d$ est donc d'une des deux formes suivantes.

▷ Si $d = 2^b$. Comme $b <_o 2^b$ par définition de $<_o$, alors $b \in A$ par clôture de $A$ par le bas. Par minimalité de $d$, $b \in O$. Mais alors $2^b \in O$, ce qui contredit $d \notin O$.

▷ Si $d = 3 \times 5^e$. Comme pour tout $n$, $\Phi_e(n) <_o 3 \times 5^e$ par définition de $<_o$, alors $\Phi_e(n) \in A$ par clôture de $A$ par le bas. Par minimalité de $d$, $\Phi_e(n) \in O$ pour tout $n$. Alors, $3 \times 5^e \in O$, ce qui contredit $d \notin O$.

Dans les deux cas, nous obtenons une contradiction. Ainsi, pour tout $a$ qui satisfait (1) et (2), il vient $a \in O$. ■

**Théorème 3.2**

Soit $A \subseteq 2^N \times N$. Alors, $A$ est $\Pi_1^1$ si, et seulement si, il existe $h : N \to N$ totale calculable telle que $(X, n) \in A \iff h(n) \in O^X$.

**PREUVE.** Supposons $(X, n) \in A$ ssi $h(n) \in O^X$. En utilisant le théorème 3.1, on donne facilement une description $\Pi_1^1$ de la classe $A$.
Montrons à présent la réciproque. Soit $\mathcal{A}$ un ensemble $\Pi_1^1$. D'après le théorème de forme normale, il existe un code $e$ tel que

$$ (X, n) \in \mathcal{A} \Leftrightarrow \forall f \Phi_e(f, X, n) \downarrow. $$

Uniformément en $n$ et $X$, on définit un arbre calculable $T_n^X$ tel que

$$ \sigma \in T_n^X \Leftrightarrow \Phi_e(\sigma, X, n)[|\sigma|] \uparrow. $$

L'arbre $T_n^X$ est bien fondé ssi $\forall f \ f \notin [T_n^X]$ ssi $\forall f \ \exists t \ \Phi_e(f \upharpoonright_t X, n)[t] \downarrow$ ssi $(X, n) \in \mathcal{A}$.

La fonction $h$ transforme simplement l'arbre $T_n^X$ en un code d'ordinal calculable à l'aide de l'ordre de Kleene-Brouwer comme utilisé dans la preuve de la proposition 27-5.18, puis transforme le code de l'ordinal calculable en code d'un ordinal constructif en utilisant la transformation des ordinaux calculables en ordinaux constructifs comme effectué dans la preuve du théorème 27-5.10. Notons que si l'arbre $T_n^X$ est mal fondé les transformations effectuées dans chacune de ces preuves restent valides, mais simplement aboutissent à un entier n'appartenant pas à $\mathcal{O}^X$. ■

### Remarque

Le théorème précédent généralise les deux cas particuliers qui nous intéressent.

* Un ensemble $A \subseteq \mathbb{N}$ est $\Pi_1^1$ si, et seulement si, il existe $h : \mathbb{N} \to \mathbb{N}$ totale calculable telle que $n \in A \Leftrightarrow h(n) \in \mathcal{O}$.

* Une classe $\mathcal{A} \subseteq 2^{\mathbb{N}}$ est $\Pi_1^1$ si, et seulement si, il existe $e \in \mathbb{N}$ tel que $X \in \mathcal{A} \Leftrightarrow e \in \mathcal{O}^X$.

### Corollaire 3.3

Pour tout $X$, l'ensemble $\mathcal{O}^X$ est many-one complet pour les ensembles $\Pi_1^1(X)$ (ou encore $\Pi_1^1(X)$-complet).

PREUVE. Il s'agit d'une simple reformulation du théorème 3.2. ■

### Corollaire 3.4

Pour tout $X$, l'ensemble $\mathcal{O}^X$ est $\Pi_1^1(X)$, mais n'est pas $\Sigma_1^1(X)$.

PREUVE. On montre le corollaire pour $\mathcal{O}$, la preuve se relativisant sans problème à $\mathcal{O}^X$ pour tout $X$. On montre aisément que tout ensemble many-one réductible à un ensemble $\Pi_1^1$ est aussi $\Pi_1^1$, et que tout ensemble many-one réductible à un ensemble $\Sigma_1^1$ est aussi $\Sigma_1^1$. Donc, si $\mathcal{O}$ est $\Sigma_1^1$, alors tout ensemble $\Pi_1^1$ est aussi $\Sigma_1^1$, ce qui contredit le théorème 2.10. ■
<figure><img src="image_175.png" /><figcaption>FIGURE 3.5 – Illustration du fait qu’un ensemble $\Pi_1^1$ est une réunion crois-sante le long de $\omega_1^{ck}$ d’ensembles $\Sigma_{\alpha+1}^0$</figcaption></figure>

Nous voyons à présent deux autres corollaires importants : les ensembles / -classes $\Pi_1^1$ sont des réunions uniformes de boréliens indexés par les ordinaux dénombrables.

**Corollaire 3.6**

Soit $A \subseteq \mathbb{N}$ un ensemble $\Pi_1^1$. Alors, pour tout $\alpha < \omega_1^{ck}$, uniformément en un code de $\alpha$, on peut trouver le code de $A_\alpha$, un ensemble $\Sigma_{\alpha+1}^0$, tel que $A = \bigcup_{\alpha < \omega_1^{ck}} A_\alpha$.

**PREUVE.** D’après le théorème 3.2, on a une fonction calculable $h : \mathbb{N} \to \mathbb{N}$ telle que $n \in A \Leftrightarrow h(n) \in O$. En particulier, $A = \bigcup_{\alpha < \omega_1^{ck}} \{n : h(n) \in O_{<\alpha}\}$. D’après le théorème 28-1.10, l’ensemble $O_{<\alpha}$ est uniformément Turing réductible à un ensemble $\Sigma_\alpha^0$, et est donc $\Delta_{\alpha+1}^0$. L’ensemble $\{n : h(n) \in O_{<\alpha}\}$ est en particulier $\Sigma_{\alpha+1}^0$. ■

Le corollaire précédent est remarquable : on a réussi à transformer une quantification universelle sur les fonctions de l'espace de Baire en quantification existentielle sur les ordinaux calculables. On passe en particulier d'une quantification ayant la puissance du continu à une quantification dénombrable. Le corollaire suivant suit la même idée, mais pour les classes.

**Corollaire 3.7**

Soit $\mathcal{A} \subseteq 2^{\mathbb{N}}$ une classe $\Pi_1^1$. Alors, pour tout $\alpha < \omega_1$, uniformément en un oracle $X$ codant pour $\alpha$, on peut trouver le code de $\mathcal{A}_\alpha$, une classe $\Sigma_{\alpha+1}^0(X)$, telle que $\mathcal{A} = \bigcup_{\alpha < \omega_1} \mathcal{A}_\alpha$.

**PREUVE.** D’après le théorème 3.2, on a un code $e$ tel que $Y \in \mathcal{A} \Leftrightarrow e \in O^Y$. En particulier, $\mathcal{A} = \bigcup_{\alpha < \omega_1} \{Y : e \in O_{<\alpha}^Y\}$. D’après le théorème 28-4.5, pour tout $\alpha < \omega_1$, pour tout $X$ tel que $\alpha < \omega_1^X$ et pour tout $a \in O_{=\alpha}^X$, l’ensemble $\{Y : e \in O_{<\alpha}^Y\}$ est $\Sigma_{\alpha+1}^0(X)$ uniformément en $X$ et $a$. ■
<figure><img src="image_176.png" /><figcaption>FIGURE 3.8 – Illustration du fait qu’une classe $\Pi_1^1$ est une réunion croissante le long de $\omega_1$ de classes $\Sigma_{\alpha+1}^0(Y)$ en n’importe quel $Y$ calculant $\alpha$. On note que, pour $X \in \mathcal{A} \setminus \mathcal{A}_{\omega_1^{ck}}$, on a nécessairement $\omega_1^X > \omega_1^{ck}$.</figcaption></figure>

**Exercice 3.9.** (★★) (Lusin). La mesure de Lebesgue, bien définie sur les classes boréliennes, peut être étendue de la manière suivante : une classe $\mathcal{A} \subseteq 2^\mathbb{N}$ est mesurable si elle est égale à $\mathcal{B} \cup \mathcal{C}$, où $\mathcal{B}$ est une classe borélienne et $\mathcal{C}$ est incluse dans une classe borélienne de mesure nulle. La mesure de $\mathcal{A}$ est alors définie comme étant celle de $\mathcal{B}$. Montrer que toute classe $\Pi_1^1$ — et donc aussi toute classe $\Sigma_1^1$ — est mesurable.

Indication.– Commencer par montrer qu’il existe un ordinal dénombrable $\alpha$ tel que la classe des ensembles $X$ qui calculent un code pour $\alpha$ est de mesure nulle. ◇

## 4. Analogies entre ensembles $\Pi_1^1$ et ensembles c. e.

Il existe une analogie entre les ensembles $\Pi_1^1$ et les ensembles c. e. Pour commencer, il devrait être à peu près clair, via le corollaire 3.3, que le $\mathcal{O}$ de Kleene est une version du problème de l’arrêt pour les prédicats $\Pi_1^1$. L’analyse va plus loin que cela : il est possible de considérer les ensembles $\Pi_1^1$ comme étant réellement des ensembles calculatoirement énumérables, mais avec des temps de calcul qui peuvent se prolonger le long des ordinaux calculables. Cette manière de voir les choses découle directement du corollaire 3.6 : étant donné $A=\bigcup_{\alpha<\omega_1^{ck}} A_\alpha$, on peut voir les éléments de $A_{\alpha+1}\setminus A_\alpha$ comme étant les éléments $\langle \text{énumérés} \rangle$ dans $A$ à l’étape $\alpha+1$. Cette idée sera énoncée précisément avec le théorème 4.3.

Nous commençons par énoncer un théorème caractéristique de cette analyse entre ensembles $\Pi_1^1$ et ensemble c. e. : supposons que l’on ait une
suite $(A_n)_{n \in \mathbb{N}}$ de sous-ensembles de $\mathbb{N}$, avec chaque $A_n$ c. e. uniformément en $n$. Alors, il est possible de définir une fonction partielle calculable telle que $A_n \neq \emptyset$ implique $f(n) \in A_n$ : il suffit pour tout $n$ de définir $f(n)$ comme étant le premier élément énuméré dans $A_n$. On peut faire exactement la même chose dans le cas $\Pi_1^1$, mais en considérant cette fois-ci les éléments comme étant énumérés le long de temps de calcul ordinaux.

### Théorème 4.1 (Uniformisation $\Pi_1^1$ de Kreisel)

Soit $A \subseteq \mathbb{N} \times \mathbb{N}$ une classe $\Pi_1^1$. Alors, il existe une fonction $\Pi_1^1$ (c'est-à-dire de graphe $\Pi_1^1$) partielle $f : \mathbb{N} \to \mathbb{N}$ telle que :

$$ \forall n \; (\exists m \; (n, m) \in A \rightarrow (n, f(n)) \in A). $$

PREUVE. En utilisant le corollaire 3.6, soit $A = \bigcup_{\alpha < \omega_1^{ck}} A_\alpha$, où chaque $A_\alpha$ est un ensemble $\Sigma_{\alpha+1}^0$ uniformément en un code de $\alpha$.

On définit $f$ de la manière suivante : $f(n) = x$ si $x$ est le plus petit élément tel que $(n, x) \in A_\alpha$ pour $\alpha$ le plus petit ordinal tel que $\{y : (n, y) \in A_\alpha\}$ est non vide. Formellement, $f(n) = x$ s'il existe $\alpha < \omega_1^{ck}$ tel que $(n, x) \in A_\alpha$, tel que $(n, y) \notin A_\beta$ pour tout $y$ et pour tout $\beta < \alpha$, et tel que $(n, y) \notin A_\alpha$ pour tout $y < x$.

Pour voir qu'il s'agit bien d'une définition $\Pi_1^1$, il faut commencer par passer par les codages des ordinaux par des éléments de $\mathcal{O}$. Nous anticipons ensuite un peu sur le théorème 5.1 à venir pour profiter du fait que les prédicats de la forme $x \in A$ pour $A$ un ensemble $\Sigma_\alpha^0$ sont uniformément $\Delta_1^1$ : étant donné une réduction many-one $h$ de $A$ à $H_{2^a}$ pour $a \in \mathcal{O}_{=\alpha}$, on a $x \in A$ ssi $\exists X \mathcal{P}(2^a, X) \wedge h(x) \in X$ ssi $\forall X \mathcal{P}(2^a, X) \rightarrow h(x) \in X$. On utilise ici la classe $\Pi_2^0 \mathcal{P}$ du théorème 28-2.1.

Comme c'est le premier exemple de ce genre, nous donnons ici la définition $\Pi_1^1$ formelle de notre fonction $f$. Dans la suite, on s'autorisera les descriptions $\Pi_1^1$ de la forme $\exists \alpha < \omega_1^{ck} \dots$. Pour cela, soit $h$ la fonction calculable telle que $h(a, e, n, x) \in H_{2^a}$ ssi $(n, x)$ appartient à l'ensemble $\Sigma_{|a|}^0$ de code $e$. Soit $g$ la fonction calculable telle que $g(a)$ est le $\Sigma_{|a|}^0$-code de $A_{|a|}$ pour tout $a \in \mathcal{O}$. Pour finir, étant donné un ensemble $X$ dont on suppose qu'il est égal à $H_{2^a}$, on note $X_b$ pour $b <_o a$ l'ensemble obtenu de manière calculable à partir de $X$, qui est égal à $H_{2^b}$ si $X = H_{2^a}$. On a alors $f(n) = x$ si :

$$ \exists a \; a \in \mathcal{O} \wedge \forall X \left( \mathcal{P}(2^a, X) \Rightarrow \left( \begin{array}{l} h(a, g(a), n, x) \in X \\ \wedge \quad \forall b <_o a \quad \forall y \ h(b, g(b), n, y) \notin X_b \\ \wedge \quad \forall y < x \ h(a, g(a), n, y) \notin X \end{array} \right) \right). $$

<figure><img src="image_177.png" /></figure>

Notons que la preuve du théorème d'uniformisation fonctionne aussi pour les classes $\Pi_1^1 A \subseteq 2^\mathbb{N} \times \mathbb{N}$ et des fonctionnelles $\Pi_1^1$ partielles $f : 2^\mathbb{N} \to \mathbb{N}$
qui sur un oracle $X$ tel que $\{n : (X, n) \in \mathcal{A}\}$ est non vide, renvoient un entier tel que $(X, f(X)) \in \mathcal{A}$. Nous verrons avec le corollaire 30-5.3 — et c’est bien plus difficile à montrer — que le théorème d’uniformisation $\Pi_1^1$ fonctionne même pour des classes $\Pi_1^1 \mathcal{A} \subseteq 2^\mathbb{N} \times 2^\mathbb{N}$.

En attendant, continuons sur l'analogie entre être $\Pi_1^1$ et c. e. Reprenons notre exemple d'ensemble c. e. $(A_n)_{n \in \mathbb{N}}$ et de notre fonction partielle calculable telle que $A_n \neq \emptyset$ implique $f(n) \in A_n$. Supposons un instant qu'aucun ensemble $A_n$ ne soit vide. Alors, notre fonction devient une fonction totale calculable, et donc descriptible de manière $\Delta_1^0$. En fait, n'importe quelle fonction totale de graphe c. e. admet un graphe calculable, puisque pour décider si $f(n) = x$ il suffit de chercher l'unique $y$ tel que $f(n) = y$ et de voir si $x = y$. Il en va de même pour les fonctions de graphes $\Pi_1^1$.

**Proposition 4.2.** Soit $f : \mathbb{N} \to \mathbb{N}$ une fonction $\Pi_1^1$ totale. Alors, $f$ est $\Delta_1^1$.★

### PREUVE

Il suffit de voir que la relation $f(n) \neq x$ est équivalente à $\exists y \neq x f(n) = y$. La relation $f(n) \neq x$ est donc elle aussi $\Pi_1^1$, ce qui rend la fonction $\Delta_1^1$. ■

Nous verrons dans la prochaine section que les ensembles $\Delta_1^1$ coïncident avec les ensembles hyperarithmétiques. En attendant, voici l'aspect formel du fait que les $\Pi_1^1$ peuvent être vus comme un analogue d'être c. e.

### Théorème 4.3

Pour tout $\Pi_1^1$ non vide $A \subseteq \mathbb{N}$, il existe une fonction $\Pi_1^1$ totale $f : \mathcal{O} \to \mathbb{N}$ telle que pour tout $\mathcal{O}_1 \subseteq \mathcal{O}$ où chaque ordinal calculable admet exactement un code dans $\mathcal{O}_1$, on a $A = \{f(a) : a \in \mathcal{O}_1\}$.

PREUVE. Il s'agit d'une amélioration de la preuve du théorème d'uniformisation. Soit $A = \bigcup_{\alpha < \omega_1^{ck}} A_\alpha$, et soit $y \in A$ un élément fixé. On définit la fonction $f : \mathcal{O} \to \mathbb{N}$ de la manière suivante. Sur un élément $a \in \mathcal{O}$ codant pour un ordinal $\alpha$, la fonction commence par calculer le code d'un ordinal $\beta$ et d'un entier $n$ tel, que $\alpha = \beta \times \omega + n$. Puis, la fonction renvoie le $n$-ième élément de $A_\beta$ s'il existe. Sinon, $f(a) = y$.

Il suffit de montrer que

▷ (1) pour chaque ordinal $\alpha$, il existe une unique ordinal $\beta$ et un unique entier $n$ tels que $\alpha = \beta \times \omega + n$;

▷ (2) pour tout $\beta < \omega_1^{ck}$, l'ordinal $\beta \times \omega + n < \omega_1^{ck}$.

Nous laissons ces preuves élémentaires au lecteur.

La fonction $f$ est bien définie par l'unicité de $\beta$ et $n$, et est totale car $f(a)=y$ si $A_\beta$ ne possède pas de $n$-ième élément. De plus, pour tout $a \in \mathcal{O}$, $f(a) \in A$.
Soit $O_1 \subseteq O$ un ensemble contenant exactement un code de chaque ordinal calculable. Montrons que $A \subseteq \{f(a) : a \in O_1\}$.

Soit $z \in A$, et soient $\beta < \omega_1^{ck}$ et $n \in \mathbb{N}$ tels que $z$ est le $n$-ième élément de $A_\beta$. Par (2), $\beta \times \omega + n < \omega_1^{ck}$, donc il existe un $a \in O_1$ tel que $|a| = \beta \times \omega + n$, donc $f(a) = z$. Ainsi, $A = \{f(a) : a \in O_1\}$. ■

L'analogie entre être c. e. et être $\Pi_1^1$ n'est pas uniquement formelle. En 1989, Joel David Hamkins et Jeff Kidder imaginent une machine de Turing où le temps de calcul peut être n'importe quel ordinal. Concrètement, la machine de Turing a le même comportement qu'habituellement aux étapes de calcul successeurs. Aux étapes limites, chaque cellule de la machine prend comme valeur la limite inférieure des valeurs aux étapes précédentes, la machine rentre dans un état « limite » et la tête de lecture revient à la première cellule. L'article fondateur [82] sur l'étude de ces machines de Turing à temps infini ne viendra que plus tard, et leurs auteurs y montrent notamment que les réels énumérables par de telles machines, en temps ordinal inférieur à $\omega_1^{ck}$, sont exactement les ensembles $\Pi_1^1$.

# 5. Théorème d'équivalence de Kleene/Souslin

Nous voyons dans cette section un théorème fondamental : les ensembles/-classes $\Delta_1^1$ et hyperarithmétiques coïncident. Ce résultat remonte aux travaux de Souslin au début du XXe siècle. La notion de calculabilité était alors balbutiante, aussi le résultat de Souslin porte-t-il sur les classes $\Sigma_1^1$, qu'il avait lui-même découvertes un peu plus tôt, via la fameuse « erreur de Lebesgue », dont nous avons déjà parlé dans l'interlude historique au début du chapitre.

## 5.1. Le théorème d'équivalence pour les ensembles

Nous commençons par montrer la direction simple : si un ensemble est hyperarithmétique, alors il est $\Delta_1^1$.

### Théorème 5.1 (Kleene [116])

*Les ensembles hyperarithmétiques sont $\Delta_1^1$.*

PREUVE. Soit $\mathcal{P} \subseteq \mathbb{N} \times 2^{\mathbb{N}}$ la classe $\Pi_2^0$ du théorème 28-2.1, telle que pour $a \in O$ la classe $\{X : \mathcal{P}(a, X)\}$ est la classe $\Pi_2^0$ contenant uniquement $H_a$. Soit $X$ hyperarithmétique. Par le théorème 28-1.12, soient $e \in \mathbb{N}$ et $a \in O$ tels que $\Phi_e(H_a) = X$. Alors, on a

(1) $n \in X$ ssi $\exists Y \mathcal{P}(a, Y)$ et $\exists \sigma < Y \Phi_e(\sigma, n) \downarrow = 1$;

(2) $n \notin X$ ssi $\exists Y \mathcal{P}(a, Y)$ et $\exists \sigma < Y \Phi_e(\sigma, n) \downarrow = 0$.

On a bien une description $\Sigma_1^1$ de $X$ et de son complémentaire. ■
Notons que l'on peut de plus à partir d'un $\Sigma_\alpha^0$-code d'un ensemble $A$ et d'un élément $a \in O_{=\alpha}$, obtenir uniformément un code $\Delta_1^1$ pour $A$, c'est-à-dire une paire de codes $\Sigma_1^1$ et $\Pi_1^1$ pour $A$. On utilise pour cela la réduction many-one uniforme des ensembles $\Sigma_\alpha^0$ aux ensembles $H_a$ pour $a \in O_{\alpha+1}$.

En particulier, on peut obtenir uniformément en $a$ un code $\Delta_1^1$ de l'ensemble $O_{<a}$, ce qui sera utilisé pour le prochain lemme.

**Théorème 5.2 (Kleene)**

Un ensemble $X \subseteq \mathbb{N}$ est $\Delta_1^1$ si, et seulement si, il est hyperarithmétique.

Nous avons déjà la direction $X$ hyperarithmétique implique $X \Delta_1^1$. L'autre direction est plus subtile, et fait appel au lemme de majoration $\Sigma_1^1$ de Spector.

**Lemme 5.3 (Majoration $\Sigma_1^1$, Spector [214]).** Soit $A \subseteq O$ un ensemble $\Sigma_1^1$. Alors, $\sup_{a \in A} |a| < \omega_1^{ck}$. $\star$

PREUVE. Supposons au contraire que $\sup_{a \in A} |a| = \omega_1^{ck}$. Alors, on peut donner la description $\Sigma_1^1$ de $O$ suivante, en contradiction avec le corollaire 3.4 :

$$a \in O \Leftrightarrow \exists b \in A \text{ tel que } a \in O_{<b}.$$

Comme on peut obtenir un code $\Sigma_1^1$ pour chaque ensemble $O_{<b}$ uniformément en $b$, la description ci-dessus est bien $\Sigma_1^1$, ce qui contredit le fait que $O$ n'admette pas de description $\Sigma_1^1$. Donc, $\sup_{a \in A} |a| < \omega_1^{ck}$. $\blacksquare$

PREUVE DU THÉORÈME 5.2. D'après le théorème 5.1, les ensembles hyperarithmétiques sont $\Delta_1^1$. Supposons à présent que $A \subseteq \mathbb{N}$ soit $\Delta_1^1$. Comme $A$ est $\Pi_1^1$, il existe une fonction calculable $f : \mathbb{N} \to \mathbb{N}$ telle que $n \in A$ ssi $f(n) \in O$. Comme $A$ est $\Sigma_1^1$, l'ensemble $\{f(n) : n \in A\}$ est $\Sigma_1^1$. D'après le lemme de majoration $\Sigma_1^1$, il existe un ordinal $\alpha < \omega_1^{ck}$ tel que $n \in A$ ssi $f(n) \in O_{<\alpha}$. Comme $O_{<\alpha}$ est hyperarithmétique, alors $A$ est aussi hyperarithmétique. $\blacksquare$

## 5.2. Première conséquence

L'équivalence de Kleene/Souslin nous permet de compléter le théorème 28-2.4, qui stipule que les ensembles arithmétiques ont tous un modulus. Rappelons qu'une fonction $f : \mathbb{N} \to \mathbb{N}$ est un modulus d'un ensemble $A \subseteq \mathbb{N}$ si toute fonction dominant $f$ calcule $A$.

**Théorème 5.4 (Groszek et Slaman [79])**

Un ensemble $X \subseteq \mathbb{N}$ est hyperarithmétique si, et seulment si, il admet un modulus.
La première direction est le théorème 28-2.4. L'autre direction du théorème nécessite le lemme suivant qui est intéressant indépendamment de l'utilisation que l'on en fera.

**Lemme 5.5.** Soit $X$ un ensemble admettant un modulus. Alors, $X$ admet un modulus uniforme : il existe un code $e$, et une fonction $f : \mathbb{N} \to \mathbb{N}$ telle que pour toute fonction $g \ge f$ on a $\Phi_e(g) = X$.

\star

PREUVE. Soit $f$ une fonction telle que, pour tout $g \ge f$, on ait $g \geq_{T} X$. Supposons par l'absurde que $X$ n'admette pas de modulus uniforme, c'est-à-dire que, pour tout $e$ et toute fonction $g$, il existe une fonction $h \ge g$ telle que $\Phi_e(h) \neq X$. On construit alors par forcing une fonction $g \ge f$ telle que $g \not\ge_{T} X$, contredisant le fait que $f$ soit un modulus.

On introduit pour la construction la notation suivante : pour $\sigma \in \mathbb{N}^{<\mathbb{N}}$ et $g \in \mathbb{N}^{\mathbb{N}}$, on note $\sigma g$ la fonction résultant de la concatenation de $\sigma$ et $g$, c'est-à-dire la fonction qui à $n < |\sigma|$ associe $\sigma(n)$, et qui à $n \ge |\sigma|$ associe $g(n - |\sigma|)$.

Nos conditions $\mathbb{P}$ sont simplement des couples $(\sigma, g)$ tels que $\sigma g \ge f$. L'extension de nos conditions de forcing est définie par $(\tau, h) \preceq (\sigma, g)$ si $\tau \succeq \sigma$ et $\tau h \ge \sigma g$. De plus, étant donné $(\sigma, g) \in \mathbb{P}$ et $\tau \in \mathbb{N}^{<\mathbb{N}}$, on écrit $\tau \in [\sigma, g]$ si $\tau \succeq \sigma$ et $\tau(n) \ge (\sigma g)(n)$ pour tout $n < |\tau|$.

Étant donné une condition $(\sigma, g) \in \mathbb{P}$ et un code $e$, on affirme que l'une des deux possibilités suivantes arrive nécessairement.

(1) Il existe $m \in \mathbb{N}$ et il existe $\tau \in [\sigma, g]$ tels que $\Phi_e(\tau, m) \downarrow \neq X(m)$

(2) Il existe $(\tau, h) \preceq (\sigma, g)$ et il existe $m \in \mathbb{N}$ tel que, pour tout $\rho \in [\tau, h]$, on a $\Phi_e(\rho, m) \uparrow$

Supposons que ni (1) ni (2) n'arrive, alors on a la conjonction des deux énoncés suivants.

(3) Pour tout entier $m \in \mathbb{N}$ et pour tout $\tau \in [\sigma, g]$, on a $\Phi_e(\tau, m) \downarrow$ implique $\Phi_e(\tau, m) = X(m)$

(4) Pour tout $(\tau, h) \preceq (\sigma, g)$ et pour tout $m \in \mathbb{N}$, il existe $\rho \in [\tau, h]$ tel que $\Phi_e(\rho, m) \downarrow$

Il existe par conséquent une unique fonctionnelle $\Phi$ telle que, pour toute fonction $h \ge \sigma g$, on a $\Phi(h) = X$. Étant donné un tel $h$ et un entier $m$, la fonctionnelle cherche $\rho \succeq \sigma$, avec $\rho(n) \ge h(n)$ pour tout $|\sigma| \le n < |\rho|$ et tel que $\Phi_e(\rho, m) \downarrow = i$. Puis, la fonctionnelle renvoie $i$. D'après (4), une telle recherche aboutit forcément. D'après (3), la valeur $i$ est nécessairement égale à $X(m)$.

Comme l'existence d'une telle fonctionnelle contredit nos hypothèses, on peut donc pour chaque code $e$ et chaque condition de forcing trouver une
extension satisfaisant (1) ou (2). Dans chacun des cas, on s'assure que notre générique ne calculera pas $X$ via $\Phi_e$. Le générique consistera alors en une fonction $g \ge f$ telle que $X \not\le_T g$, ce qui contredit le fait que $f$ soit un modulus pour $X$.

Donc, si $X$ admet un modulus, il admet un modulus uniforme.

**PREUVE DU THÉORÈME 5.4.** Nous avons vu avec le théorème 28-2.4 que tout ensemble hyperarithmétique admet un modulus. Supposons à présent que $X$ admette un modulus. D'après le lemme 5.5, $X$ admet un modulus uniforme via une fonctionnelle $\Phi_e$. Dans ce qui suit, on écrit $\sigma \ge f$ pour signifier $\sigma(m) \ge f(m)$ pour tout $m < |\sigma|$. Soit $\Psi(n)$ le prédicat $\Sigma_1^1$ donné par

$$ \exists f \text{ tel que } \forall \sigma \ge f \text{ on a } \Phi_e(\sigma, n) \downarrow \to \Phi_e(\sigma, n) = 1. $$

Si $n \in X$, alors $\Psi(n)$ est clairement vrai en prenant $f$ comme étant le témoin de notre modulus. Si à présent $\Psi(n)$ est vrai pour une certaine fonction $f$, alors en prenant $g > f$ suffisamment grand pour que $\Phi_e(g) = X$, on a par conséquent $\Phi_e(\sigma, n) \downarrow = X(n)$ pour un certain $\sigma < g$. Comme $\Psi(n)$ est vrai avec $f$, on a en fait $\Phi_e(\sigma, n) \downarrow = 1$, et donc $n \in X$. Il s'ensuit que $n \in X$ ssi $\Psi(n)$ est vrai. Donc, $X$ est $\Sigma_1^1$. On procède de la même manière pour montrer que le complémentaire de $X$ est $\Sigma_1^1$, ce qui implique que $X$ est $\Delta_1^1$, et donc hyperarithmétique.

## 5.3. Uniformité du théorème d'équivalence

Nous avons vu qu'il est possible d'obtenir le code $\Delta_1^1$ d'un ensemble $A$ à partir de son code hyperarithmétique. Dans l'autre sens, le théorème 5.2 ne nous donne en revanche aucun moyen d'obtenir un code hyperarithmétique d'un ensemble $A$ à partir de son code $\Delta_1^1$. Le point crucial se situe dans la démonstration du lemme de majoration $\Sigma_1^1$ de Spector, qui permet de montrer l'existence d'un majorant pour un ensemble $\Sigma_1^1$ d'ordinaux $A \subseteq \mathcal{O}$, mais sans le spécifier.

Nous voyons ici qu'il est possible d'obtenir cette borne uniformément, au prix bien entendu d'une construction plus complexe. Nous utiliserons pour cela des représentations des ordinaux via des arbres bien fondés de l'espace de Baire, et des lemmes de manipulation sur ces derniers.

**Définition 5.6.** Soient deux arbres $T_1, T_2 \subseteq \mathbb{N}^<$. On appelle *morphisme* de $T_1$ vers $T_2$ une fonction $f : T_1 \to T_2$ telle que $|f(\sigma)| = |\sigma|$ et telle que $\sigma \le \tau$ implique $f(\sigma) \le f(\tau)$. ◇

La notation $|\sigma|$ ci-dessus signifie la taille de $\sigma$. On commence par une première proposition permettant de comparer les ordinaux codés par des arbres bien fondés via l'existence de morphisme de l'un vers l'autre.
Souvenons-nous pour la preuve qui suit de la notation $|T \upharpoonright_n|$ introduite dans la section 27-5.3.

**Proposition 5.7.** Étant donné deux arbres bien fondés $T_1, T_2 \subseteq \mathbb{N}^{<\mathbb{N}}$, on a $|T_1| \le |T_2|$ si, et seulement si, il existe un morphisme de $T_1$ vers $T_2$. ★

**PREUVE.** On montre la proposition par induction sur les ordinaux codés par $T_1$. Si $|T_1| = 0$, alors $T_1$ est l'ensemble vide, et la proposition est clairement vraie avec n'importe quel arbre $T_2$. Supposons à présent la proposition vraie pour n'importe quel arbre $T_1$ tel que $|T_1| < \alpha$ et n'importe quel arbre $T_2$. Considérons un arbre $T_1$ avec $|T_1| = \alpha$.

Supposons d'abord $|T_1| \le |T_2|$. Alors, pour chaque nœud $n \in T_1$ — c'est-à-dire chaque nœud de $T$ de taille 1—, il y a un nœud $m_n \in T_2$ tel que

$$|T_1 \upharpoonright_n| \le |T_2 \upharpoonright_{m_n}|$$

(s'il y en a plusieurs, on choisit le plus petit). Par hypothèse d'induction, on a donc un morphisme $f_n : T_1 \upharpoonright_n \to T_2 \upharpoonright_{m_n}$. On définit alors $f : T_1 \to T_2$ par $f(n\sigma) = m_n f_n(\sigma)$, et l'on vérifie sans peine que c'est un morphisme de $T_1$ vers $T_2$.

Réciproquement, supposons qu'il existe un morphisme de $f : T_1 \to T_2$. Alors, pour chaque $n \in T_1$, la fonction $f_n : T_1 \upharpoonright_n \to T_2 \upharpoonright_{f(n)}$ est un morphisme de $T_1 \upharpoonright_n$ vers $T_2 \upharpoonright_{f(n)}$. On obtient par hypothèse d'induction que $|T_1 \upharpoonright_n| \le |T_2 \upharpoonright_{f(n)}|$. Donc, $|T_1| \le |T_2|$. ■

On définit à présent des fonctions calculables $\wedge: \mathbb{N} \times \mathbb{N} \to \mathbb{N}$ et $\vee: \mathbb{N} \times \mathbb{N} \to \mathbb{N}$ sur les paires de codes c. e. d'arbres bien fondés de $\mathbb{N}^{<\mathbb{N}}$.

**Lemme 5.8.** Il y a une fonction totale calculable $\wedge: \mathbb{N} \times \mathbb{N} \to \mathbb{N}$ qui sur deux codes d'arbre c. e. $T_1, T_2$ renvoie le code d'un arbre c. e. $T_1 \wedge T_2$ bien fondé si, et seulement si, $T_1$ et $T_2$ sont tous deux bien fondés, auquel cas on a $|T_1 \wedge T_2| \ge \sup(|T_1|, |T_2|)$. ★

**PREUVE.** On définit simplement $T_1 \wedge T_2$ comme étant la réunion disjointe de $T_1$ et $T_2$. Concrètement, on met dans $T_1 \wedge T_2$ les nœuds $\langle n, i \rangle \sigma$ pour tout $n\sigma \in T_i$ pour $i \in \{1, 2\}$. L'existence d'un morphisme de $T_1$ ou $T_2$ vers $T_1 \wedge T_2$ est claire. On a donc $|T_1 \wedge T_2| \ge \sup(|T_1|, |T_2|)$.

**Lemme 5.9.** Il existe une fonction totale calculable $\vee$, qui sur deux codes d'arbres c. e. $T_1, T_2$ renvoie le code d'un arbre c. e. $T_1 \vee T_2$ qui est bien fondé si $T_1$ ou $T_2$ est bien fondé, auquel cas $|T_1 \vee T_2| \ge \min(|T_1|, |T_2|)$. ★

**PREUVE.** Dans ce qui suit, on utilise une fonction de couplage sur les chaînes de même taille de $\mathbb{N}^{<\mathbb{N}}$, définie en appliquant successivement la
bijection $\langle\rangle : \mathbb{N}^2 \to \mathbb{N}$ sur chaque pair d'entiers se trouvant à la même position dans les deux chaînes. Formellement, pour $n = |\sigma_1| = |\sigma_2|,$

$$ \langle\sigma_1, \sigma_2\rangle = \langle\sigma_1(0), \sigma_2(0)\rangle \wedge \dots \wedge \langle\sigma_1(n-1), \sigma_2(n-1)\rangle. $$

La définition de $T_1 \lor T_2$ est simple : on énumère un nœud $\sigma$ dans $T_1 \lor T_2$ si $\sigma = \langle\sigma_1, \sigma_2\rangle$ où pour $i \in \{1, 2\}$, chaque chaîne $\sigma_i$ a été énumérée dans $T_i$. Il est clair que l'on a un chemin infini dans $T_1 \lor T_2$ ssi l'on a un chemin infini dans $T_1$ et $T_2$.

Pour montrer l'inégalité $|T_1 \lor T_2| \ge \min(|T_1|, |T_2|)$, on suppose sans perte de généralité que $|T_1| \le |T_2|$. Soit $f : T_1 \to T_2$ un morphisme (notons que, dans le cas où $T_2$ est mal fondé, un morphisme existe toujours en envoyant tous les nœuds de $T_1$ vers le chemin infini de $T_2$). Alors, chaque nœud $\langle\sigma, f(\sigma)\rangle$ appartient à $T_1 \lor T_2$. On peut alors définir le morphisme $g : T_1 \to |T_1 \lor T_2|$ qui à $\sigma \in T_1$ associe $\langle\sigma, f(\sigma)\rangle$. Il s'ensuit que $|T_1 \lor T_2| \ge |T_1|$. $\blacksquare$

Nous aurons également besoin de combiner une suite infinie d'arbres.

**Lemme 5.10.** Il existe une fonction totale calculable qui, pour chaque code énumérant une suite infinie $(T_i)_{i \in \mathbb{N}}$ d'arbres c. e., renvoie le code d'un arbre c. e. $\bigwedge_{i \in \mathbb{N}} T_i$, lequel est bien fondé ssi chaque $T_i$ est bien fondé, auquel cas on a $|\bigwedge_{i \in \mathbb{N}} T_i| \ge \sup_i |T_i|$. $\star$

**PREUVE.** On définit simplement $T$ comme étant la réunion disjointe des $T_i$. Concrètement, on met dans $T$ les nœuds $\langle n, i \rangle \sigma$ pour tout $n \sigma \in T_i$. Il est clair que l'on a un morphisme de chaque $T_i$ vers $|\bigwedge_{i \in \mathbb{N}} T_i|$, et donc que $|\bigwedge_{i \in \mathbb{N}} T_i| \ge \sup_i |T_i|$. $\blacksquare$

**Exercice 5.11.** $(\star)$ Montrer l'existence d'une fonction totale calculable $\lor$, qui pour chaque code énumérant une suite infinie $(T_i)_{i \in \mathbb{N}}$ d'arbres c. e., renvoie le code d'un arbre c. e. $\bigvee_{i \in \mathbb{N}} T_i$, lequel est bien fondé ssi au moins l'un des $T_i$ est bien fondé, auquel cas on a

$$ \min_i(|T_i|) + \omega > \left| \bigvee_{i \in \mathbb{N}} T_i \right| \ge \min_i(|T_i|). $$

$\diamond$

On peut à présent montrer la version uniforme du lemme de majoration $\Sigma_1^1$ de Spector.

**Lemme 5.12 (Borne uniforme, majoration $\Sigma_1^1$ pour les entiers).** Il existe une fonction calculable telle que si $e$ est le code de $A \subseteq \mathcal{O}$ un ensemble $\Sigma_1^1$, alors $f(e) \in \mathcal{O}$ est tel que $\sup_{a \in A} |a| \le |f(e)|$. $\star$

**PREUVE.** Soit $A \subseteq \mathcal{O}$ un ensemble $\Sigma_1^1$. D'après la proposition 27-5.18, on a une fonction calculable $f$ tel que $f(e)$ code pour un arbre c. e. $T_e$ tel que $T_e$ est bien fondé ssi $e \in \mathcal{O}$. De plus, si $e \in \mathcal{O}$, on a $|e| \le |T_e|$. $\blacksquare$
En utilisant le fait que $A$ soit $\Sigma_1^1$, on obtient via le théorème 3.2 et la proposition 27-5.18 — uniformément en un code de $A$ — une fonction calculable $g$ telle que $g(e)$ code pour un arbre c. e. $U_e$ tel que $U_e$ est bien fondé ssi $e \notin A$. Notons que pour tout $e \in \mathbb{N}$, l'arbre $T_e \vee U_e$ est bien fondé. De plus, d'après le lemme 5.9, si $e \in A \subseteq \mathcal{O}$, on a $|e| \le |T_e \vee U_e|$.

On prend alors l'arbre c. e. $T$ de code $\bigwedge_{e \in \mathbb{N}} (T_e \vee U_e)$. D'après le lemme 5.10 on a $|T_e \vee U_e| \le |\bigwedge_{e \in \mathbb{N}} (T_e \vee U_e)|$ pour tout $e$, et donc $|e| \le |\bigwedge_{e \in \mathbb{N}} (T_e \vee U_e)|$ pour tout $e \in A \subseteq \mathcal{O}$. On peut alors, pour conclure, retransformer le code de $T$ en un code de $\mathcal{O}$ à l'aide du théorème 27-5.10. ■

On déduit aisément du lemme une borne uniforme permettant de transformer le code $\Delta_1^1$ d'un ensemble en code hyperarithmétique.

## 5.4. Le théorème d'équivalence pour les classes

Nous voyons à présent le théorème d'équivalence de Kleene/Souslin pour les classes, et nous montrons cette fois-ci directement la version uniforme du théorème.

**Proposition 5.13.** Si une classe $\mathcal{A} \subseteq 2^\mathbb{N}$ est hyperarithmétique, elle est alors $\Delta_1^1$. ★

PREUVE. Soit $\mathcal{A} \subseteq 2^\mathbb{N}$ une classe $\Sigma_\alpha^0$. Soit $\mathcal{P} \subseteq \mathbb{N} \times 2^\mathbb{N} \times 2^\mathbb{N}$ la classe $\Pi_2^0$ du théorème 28-3.4, c'est-à-dire telle que, pour $a \in \mathcal{O}^X$ et $X \in 2^\mathbb{N}$, la classe $\{Y : \mathcal{P}(a, X, Y)\}$ est la classe $\Pi_2^0(X)$ contenant uniquement $H_a^X$.

D'après le théorème 28-4.4, on a un code $e$ tel que $X \in \mathcal{A}$ ssi $e \in H_{2a}^X$ pour $a \in \mathcal{O}_{=\alpha}$. Il est à noter que l'on peut supposer sans perte de généralité $\mathcal{O} \subseteq \mathcal{O}^X$ — afin de satisfaire formellement les hypothèses du théorème 28-3.4. On a la définition $\Sigma_1^1$ suivante pour $\mathcal{A}$ :

$$ \mathcal{A} = \{X : \exists Y \mathcal{P}(2^a, X, Y) \text{ et } e \in Y\}, $$

et la définition $\Sigma_1^1$ suivante pour $2^\mathbb{N} \setminus \mathcal{A}$ :

$$ 2^\mathbb{N} \setminus \mathcal{A} = \{X : \exists Y \mathcal{P}(2^a, X, Y) \text{ et } e \notin Y\}. $$

La classe $\mathcal{A}$ est donc $\Delta_1^1$. ■

Montrons à présent le lemme de majoration $\Sigma_1^1$ pour les classes, dû à Spector [214].

## Lemme 5.14 (Majoration $\Sigma_1^1$ pour les classes)

Soit une classe $\Sigma_1^1 \mathcal{A} \subseteq 2^\mathbb{N}$ telle que $X \in \mathcal{A} \to e \in \mathcal{O}^X$ pour un certain $e$. Alors, on peut trouver $a \in \mathcal{O}$ uniformément en $e$ et en un code de $\mathcal{A}$ tels que $X \in \mathcal{A} \to |e|^X < |a|$. ★
PREUVE. On réutilise ici la fonction de couplage sur les chaînes de $\mathbb{N}^{<\mathbb{N}}$ de même taille, définie dans la preuve du lemme 5.9. Soit $U_1^X$ l'arbre c. e. bien fondé ssi $X \notin \mathcal{A}$. Soit $U_2^X$ l'arbre c. e. bien fondé ssi $e \in \mathcal{O}^X$. On calcule uniformément en $X$ l'arbre bien fondé $T^X = U_1^X \vee U_2^X$. On calcule finalement l'arbre c. e. $T$ suivant : pour chaque chaîne $\sigma \in 2^{<\mathbb{N}}$ tel qu'un nœud $m$ de taille 1 est énuméré dans $T^\sigma$, on énumère le nœud $\langle m, b(\sigma) \rangle$ de taille 1 dans $T$, en utilisant une bijection $b: 2^{<\mathbb{N}} \to \mathbb{N}$. Pour tout nœud $\langle \tau, b(\sigma_1) \dots b(\sigma_n) \rangle$ énuméré dans $T$ avec $|\tau| = n$, si une chaîne $\tau m$ est énumérée dans $T^{\sigma_{n+1}}$ pour une chaîne $\sigma_{n+1} \supseteq \sigma_n$, on énumère alors

$$ \langle \tau m, b(\sigma_1) \dots b(\sigma_n) b(\sigma_{n+1}) \rangle $$

dans $T$.

L'arbre $T$ est bien fondé : un chemin infini $g \oplus f$ de $[T]$ correspondrait à un élément $g \in [T^Y]$ pour $b^{-1}(f(0)) \preceq b^{-1}(f(1)) \preceq b^{-1}(f(2)) \preceq \dots \preceq Y$, contredisant le fait que chaque $T^Y$ soit bien fondé. De plus, pour tout $X$, on a un morphisme $f$ de $T^X$ dans $T$, défini pour un nœud $\tau$ de taille $n$ par $f(\tau)$ comme étant $\tau \oplus b(\sigma_1) \dots b(\sigma_n)$ pour les premières chaînes $\sigma_1 \preceq \sigma_2 \preceq \dots \preceq \sigma_n < X$ trouvées telles que $\tau \in T^{\sigma_n}$. On en déduit donc $|T^X| \le |T|$ pour tout $X$. ■

### Théorème 5.15

Une classe $\mathcal{A} \subseteq 2^{\mathbb{N}}$ est $\Delta_1^1$ si, et seulement si, elle est hyperarithmétique.

PREUVE. Nous avons vu avec la proposition 5.13 qu'une classe hyperarithmétique est $\Delta_1^1$. Supposons à présent que $\mathcal{A} \subseteq 2^{\mathbb{N}}$ soit une classe $\Delta_1^1$. Comme $\mathcal{A}$ est $\Pi_1^1$, d'après le théorème 3.2 il existe un code $e$ tel que $X \in \mathcal{A}$ si, et seulement si, $e \in \mathcal{O}^X$. Comme $\mathcal{A}$ est $\Sigma_1^1$, la classe $\{X : e \in \mathcal{O}^X\}$ est $\Sigma_1^1$. D'après le lemme de majoration $\Sigma_1^1$ pour les réels, il existe $\alpha < \omega_1^{ck}$ tel que $\mathcal{A} = \{X : e \in \mathcal{O}_{<\alpha}^X\}$. D'après le théorème 28-4.5, la classe $\mathcal{A}$ est donc hyperarithmétique. ■

# 6. Autres théorèmes de majoration

La technique utilisée pour le lemme de majoration $\Sigma_1^1$ est très puissante, et peut être exploitée pour mettre en évidence plusieurs autres phénomènes remarquables. Nous en voyons deux pour le moment.

### Théorème 6.1

Soit $T$ est un arbre bien fondé $\Sigma_1^1$. Alors, $|T| < \omega_1^{ck}$.

PREUVE. Supposons par l'absurde $|T| \ge \omega_1^{ck}$. On montre alors que l'on a une description $\Sigma_1^1$ de $\mathcal{O}$, ce qui est une contradiction.
Soit $f$ la fonction calculable telle que $f(e)$ est un code d'arbre c. e. $T_e$ et tel que $T_e$ est bien fondé ssi $e \in O$. On peut alors donner une description $\Sigma_1^1$ de $O$ de la manière suivante : $e \in O$ ssi il existe un morphisme $f$ de $T_e$ vers $T$. Étant donné $f$, l'énoncé n'utilise que des questions d'appartenance à $T$ positive (c'est-à-dire de la forme $\sigma \in T$ et non de la forme $\sigma \notin T$), et est donc bien $\Sigma_1^1$ :

$$ \forall \sigma \in T_e f(\sigma) \in T \wedge |f(\sigma)| = |\sigma| \wedge \sigma \leq \tau \text{ implique } f(\sigma) \leq f(\tau). $$

On en déduit que $O$ est $\Sigma_1^1$, ce qui est une contradiction. ■

Le théorème précédent est absolument fascinant : le plus petit ordinal non calculable est le même que le plus petit ordinal non hyperarithmétique ! Toute la puissance conférée par des itérations arbitraires du saut ne permet pas de calculer une représentation de $\omega_1^{ck}$. La preuve que nous avons donnée est non constructive. Il est toutefois possible d'en donner une version constructive, mais avec bien sûr un peu plus de travail.

**Exercice 6.2. (★★)** Montrer que l'on peut uniformément transformer un $\Sigma_1^1$-code d'un arbre bien fondé $T$ en un code c. e. d'arbre bien fondé $T'$ tel que $|T'| \geq |T|$.

Indication.– On pourra reprendre des éléments de la preuve du lemme 5.12, et utiliser la fonction de l'exercice 5.11. ◇

Voyons à présent notre deuxième théorème, qui s'appuie là encore sur la même technique. Nous commençons par un lemme général.

**Lemme 6.3.** Soit $\mathcal{A}$ une classe $\Sigma_1^1$ telle que $\forall X \in \mathcal{A} \exists a \in \mathcal{O}^X \mathcal{B}(a, X)$ où $\mathcal{B}$ est un prédicat $\Pi_1^1$. Alors, il existe un ordinal $\alpha < \omega_1^{ck}$ tel que

$$ \forall X \in \mathcal{A} \exists a \in \mathcal{O}_{<\alpha}^X \mathcal{B}(a, X). $$

★

**PREUVE.** Supposons par l'absurde que pour tout ordinal $\alpha < \omega_1^{ck}$ il existe $X \in \mathcal{A}$ tel que $\forall a \in \mathcal{O}_{<\alpha}^X \neg\mathcal{B}(a, X)$. Alors, on peut donner la description $\Sigma_1^1$ suivante du $O$ de Kleene : $b \in O$ si, et seulement si,

$$ (1) \exists X \in \mathcal{A} \forall a (a \notin \mathcal{O}^X \lor \neg\mathcal{B}(a, X) \lor b \in \mathcal{O}_{<|a|}). $$

Supposons $b \in O$. Par hypothèse, il existe $X \in \mathcal{A}$ tel que

$$ \forall a \in \mathcal{O}_{\text{succ}(|b|)}^X \neg\mathcal{B}(a, X). $$

On vérifie alors sans peine que (1) est vrai pour cet élément $X$. Supposons à présent $b \notin O$. Soit $X \in \mathcal{A}$. Soit $a \in \mathcal{O}^X$ tel que $\mathcal{B}(a, X)$. Comme $b \notin O$, on a aussi $b \notin \mathcal{O}_{<|a|}$. Donc, pour tout $X \in \mathcal{A}$, il existe $a \in \mathcal{O}^X$ tel que $\mathcal{B}(a, X)$ et $b \notin \mathcal{O}_{<|a|}$. Ainsi, (1) est faux. On a donc $b \in O$ ssi (1) est vrai. Donc, $O$ admet une description $\Sigma_1^1$, ce qui est une contradiction. ■
**Théorème 6.4**

Soit $\mathcal{A}$ une classe $\Sigma_1^1$ ne contenant que des éléments hyperarithmétiques.
Alors, il existe $\alpha < \omega_1^{ck}$ tel que tous les éléments de $\mathcal{A}$ sont calculables
en $\emptyset^{(\alpha)}$.

PREUVE. Il suffit d'appliquer le lemme précédent avec la formule suivante :

$$
\forall X \in \mathcal{A} \ \exists a \in \mathcal{O} \ \text{tel que } \emptyset^{(|a|)} \geq_T X.
$$

**Exercice 6.5. (★★)** Soit $\mathcal{A}$ une classe $\Sigma_1^1$ ne contenant que des éléments hyperarithmétiques. Montrer que l'on peut trouver uniformément un ordi- nal $\alpha < \omega_1^{ck}$ tel que tous les éléments de $\mathcal{A}$ sont calculables par $\emptyset^{(\alpha)}$. $\diamond$

7. Réduction hyperarithmétique

De la même manière que la version relativisée de la calculabilité induit
une notion de réduction sur les ensembles, appelée réduction Turing, la
relativisation des ensembles hyperarithmétiques induit une réduction sur
les ensembles, appelée réduction hyperarithmétique. Cette réduction, plus
« grossière » que la réduction Turing, est souvent plus appropriée en hy-
percalculabilité.

**Définition 7.1.** Un ensemble $X$ est hyperarithmétiquement réductible à un autre ensemble $Y$ si $X$ est $\Delta_1^1(Y)$. On écrira alors $X \leq_h Y$, ainsi que $X <_h Y$ si $X \leq_h Y$ et $Y \not\leq_h X$. $\diamond$

De manière équivalente, $X \leq_h Y$ ssi il existe $a \in \mathcal{O}^Y$ tel que $X \leq_T H_a^Y$, ou
avec nos notations alternatives, ssi il existe $\alpha < \omega_1^Y$ tel que $X \leq_T Y^{(\alpha)}$. Les
deux théorèmes suivants illustrent un peu plus l'analogie entre $\mathcal{O}^X$ et $X'$.

Théorème 7.2

Soient $X, Y \in \mathbb{N}^\mathbb{N}$. Les deux énoncés suivants sont équivalents :

(1) $X \leq_h Y$;

(2) $\mathcal{O}^X \leq_m \mathcal{O}^Y$.

PREUVE. Supposons que $X$ soit $\Delta_1^1(Y)$. Comme $\mathcal{O}^X$ est $\Pi_1^1(X)$, alors d'après l'exercice 2.9 $\mathcal{O}^X$ est $\Pi_1^1(Y)$. Comme $\mathcal{O}^Y$ est many-one complet pour les ensembles $\Pi_1^1(Y)$, on a $\mathcal{O}^X \leq_m \mathcal{O}^Y$.

Réciproquement, supposons $\mathcal{O}^X \leq_m \mathcal{O}^Y$. On a alors aussi $X \leq_m \mathcal{O}^X \leq_m \mathcal{O}^Y$ et $\mathbb{N} \setminus X \leq_m \mathcal{O}^X \leq_m \mathcal{O}^Y$. Comme $\mathcal{O}^Y$ est $\Pi_1^1(Y)$, alors $X$ et $\mathbb{N} \setminus X$ sont tous les deux $\Pi_1^1(Y)$. Donc, $X$ est $\Delta_1^1(Y)$. $\blacksquare$
**Théorème 7.3**

Soit $X \in 2^N$. Alors, on a $X <_h O^X$. Plus précisément, $X <_m O^X$
et $O^X \not\le_h X$

PREUVE. Il est clair que $X <_m O^X$. On ne peut avoir $O^X \not\le_h X$, car sinon $O^X$ serait $\Delta_1^1(X)$, ce qui est une contradiction.
■

Les nombreuses analogies entre $X'$ et $O^X$ justifient le vocabulaire suivant.

**Définition 7.4.** Étant donné un ensemble $X$, l'ensemble $O^X$ est appelé l'hypersaut de $X$. ◇

Voyons pour finir les rapports entre le calcul du $O$ de Kleene et le calcul de $\omega_1^{ck}$.

**Théorème 7.5**

Soient $X, Y \in 2^N$. On a $X \le_h Y$ implique $\omega_1^X \le \omega_1^Y$.

PREUVE. Soit $X$ un ensemble $\Delta_1^1(Y)$, et soit $\alpha$ un ordinal $X$-calculable.
Alors, $\alpha$ a une représentation qui est $\Delta_1^1(Y)$. D'après la version relativisée
du théorème 6.1, on a donc $\alpha < \omega_1^Y$. Par suite, $\omega_1^X \le \omega_1^Y$.
■

On verra avec le théorème 30-2.2 que la réciproque n’est pas vraie. En particulier, il existe un ensemble non hyperarithmétique $X$ tel que $\omega_1^X = \omega_1^{ck}$.

**Théorème 7.6**

Soit $X \in 2^N$. Les deux énoncés suivants sont équivalents :

(1) $X \ge_h O$;

(2) $\omega_1^X > \omega_1^{ck}$.

PREUVE. Supposons $X \ge_h O$. Alors, $\omega_1^X \ge \omega_1^O$ d'après le théorème 7.5. On a par ailleurs $\omega_1^O > \omega_1^{ck}$ : on peut définir la fonctionnelle $\Phi_e$ qui à l'aide de l'oracle $O$ renvoie sur son entrée $n$ la somme des $n$ premiers éléments de $O$ (via la fonction $+_o$ de l'exemple 27-5.4). L'élément $3 \times 5^e \in O^O$ cdera pour un ordinal plus grand que tous les ordinaux calculables. On a donc $\omega_1^X \ge \omega_1^O > \omega_1^{ck}$, et donc $\omega_1^X > \omega_1^{ck}$. Supposons à présent $\omega_1^X > \omega_1^{ck}$. Soit $T$ un arbre $X$-calculable tel que $|T| = \omega_1^{ck}$. On procède alors comme dans la preuve du théorème 6.1 pour donner une description $\Sigma_1^1(X)$ de $O$: étant donné $f$ la fonction calculable telle que $f(e)$ est un code d'arbre c. e. $T_e$ pour lequel $T_e$ est bien fondé ssi $e \in O$, on a $e \in O$ ssi il existe un morphisme $f$ de $T_e$ vers $T$. Il s'agit bien d'une description $\Sigma_1^1(X)$ de $O$. Ainsi, $O$ est $\Delta_1^1(X)$, et donc $X \ge_h O$.
■

**Exercice 7.7.** (**) Montrer que pour tout ensemble $X$ qui est $\Pi_1^1$ et non $\Delta_1^1$, on a $X \ge_h O$. ◇
Chapitre 30

Classes Σ¹₁ et Π¹₁

Nous allons maintenant concentrer notre étude sur les classes Σ¹₁ et Π¹₁. Suivant l'analogie entre hypercalculabilité et calculabilité classique que nous avons abordée dans la section 29-4, les classes Σ¹₁ jouent informellement le rôle des classes Π₀₁ (voir le chapitre 8). Nous étudierons en particulier un certain nombre de théorèmes de base Σ¹₁, dont des analogues des théorèmes de base low et d'évitement de cône pour les classes Π₀₁. Nous verrons que les classes Π¹₁ ont un comportement assez différent : si les singletons Σ¹₁ sont exactement les ensembles hyperarithmétiques, les singletons Π¹₁ peuvent être de complexité bien plus élevée, et contiennent la hiérarchie des hyper-sauts (voir la définition 6.2).

# 1. Représentation canonique des classes Σ¹₁

Les classes Σ¹₁ se représentent aisément par des arbres calculables de l'espace de Baire. En effet, soit $\mathcal{A} \subseteq 2^N$ une classe Σ¹₁. Alors, il existe un code $e$ tel que $X \in \mathcal{A}$ ssi $\exists f \Phi_e(f, X) \uparrow$. On définit alors l'arbre

$$ T = \{ \langle \sigma, \tau \rangle : |\sigma| = |\tau| = t \text{ et } \Phi_e(\sigma, \tau)[t] \uparrow, \text{ avec } \sigma \in N^{<N} \text{ et } \tau \in 2^{<N} \}. $$

Les éléments de la classe $\mathcal{A}$ sont alors exactement les éléments $X$ tels que $\langle f, X \rangle \in [T]$ pour un certain $f$. Cette représentation vient directement du théorème conséquence avec la proposition 1.2, à venir : étant donné une collection $\{\mathcal{A}_i\}_{i \in I}$ de classes $\Sigma^1_1$ non vides, on peut choisir uniformément un élément dans chaque $\mathcal{A}_i$. En particulier, l'axiome du choix est superflu