<figure><img src="image_178.png" /><figcaption>FIGURE 1.1 – Représentation de classes $\Sigma_1^1$ par un arbre : chaque élément X de la classe est considéré avec ses fonctions témoins potentiels. Ces fonctions témoins sont représentées par les chemins en pointillé, et les éléments de la classe par les chemins en trait plein.</figcaption></figure>

pour les classes $\Sigma_1^1$. Il convient toutefois de préciser ce que l'on entend par « collection de classes $\Sigma_1^1$ non vides ». D'après notre définition, une classe est $\Sigma_1^1$ est une classe $\Sigma_1^1(Z)$ pour un certain $Z$. On suppose ici que la présentation de chaque classe de notre suite est un objet concret, c'est-à-dire un couple $(e, Z)$ où $e$ est la formule $\Sigma_1^1(Z)$ correspondant à notre classe.

**Proposition 1.2.** On peut choisir un élément dans chaque classe $\Sigma_1^1(Z)$ uniformément en un code $\Sigma_1^1(Z)$ de la classe et en $Z$. En particulier, l'axiome du choix est superflu pour les classes $\Sigma_1^1$. ★

**PREUVE.** Soit $\mathcal{A} \subseteq 2^\mathbb{N}$ une classe $\Sigma_1^1(Z)$. Soit $T \subseteq \mathbb{N}^{<\mathbb{N}}$ l'arbre Z-calculable canonique tel que $X \in \mathcal{A}$ ssi il existe $f$ tel que $\langle f, X \rangle \in [T]$. Notons que le théorème de forme normale de Kleene est uniforme, et que l'arbre correspondant s'obtient donc lui aussi de manière uniforme.
Il suffit de choisir le plus petit chemin $\langle f, X \rangle$ de $[T]$, pour l'ordre lexico-graphique. L'élément choisi sera donc $X$ —ainsi que son « témoin » $f$ que l'on peut alors oublier. ■

Insistons une fois de plus sur l'uniformité dans la présentation de nos classes $\Sigma_1^1$, et sans laquelle on ne peut pas faire grand-chose, comme en témoignent les classes d'équivalence de degrés Turing, qui sont toutes $\Sigma_3^0$, mais pour lesquelles on ne peut démontrer l'existence d'une fonction de choix.

## 2. Théorèmes de base pour les classes $\Sigma_1^1$

Quelle est la puissance nécessaire pour calculer un élément d'une classe $\Sigma_1^1$ ? D'après la proposition 4.2 à venir, la classe des ensembles non hyper-arithmétiques est $\Sigma_1^1$. On a donc besoin de quelque chose qui aille au-delà de la puissance hyperarithmétique. Il n'est pas très difficile de voir que le $O$ de Kleene suffit : étant donné un arbre $T \subseteq \mathbb{N}^\mathbb{N}$, on cherche à l'aide de $O$ le premier nœud $\sigma \in T$ de taille 1 tel que $T \upharpoonright_\sigma$ est mal fondé, et l'on recommence inductivement pour calculer petit à petit le chemin infini le plus à gauche de $T$. Le théorème suivant prouve quelque chose de plus fort : un analogue pour les classes $\Sigma_1^1$ du théorème 8-4.3 de la base low des classes $\Pi_1^0$.

### 2.1. Théorème de la base hyperlow

Rappelons que le $O$ de Kleene joue le rôle du problème de l'arrêt dans la correspondance entre hypercalculabilité et calculabilité classique. La définition suivante correspond donc à la notion d'ensemble low en hypercalculabilité.

**Définition 2.1.** Un ensemble $X$ est hyperlow si $O^X \leq_T O$.

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

Notons que si $X$ est hyperlow, on ne peut pas avoir $O \leq_h X$, car on aurait alors $O^X \leq_h X$, ce qui est impossible par le théorème 29-7.3. En particulier, $\omega_1^X = \omega_1^{ck}$ pour tout $X$ hyperlow.

**Théorème 2.2 (Théorème de base de Gandy [72])**

Toute classe $\Sigma_1^1$ non vide contient un élément $X$ hyperlow. En particulier, avec $\omega_1^X = \omega_1^{ck}$.

PREUVE. Soit $\mathcal{A}$ une classe $\Sigma_1^1$. À l'étape $n$ de la construction, supposons que l'on ait un arbre calculable $T_n \subseteq \mathbb{N}^\mathbb{N}$ tel que $[T_n]$ est non vide et une chaîne $\sigma_n$ telle que tous les nœuds de $T_n$ sont compatibles avec $\sigma_n$.
Supposons que les chemins infinis de $[T_n]$ encodent de manière calculable des éléments de $\mathcal{A}$, via une fonction de décodage $\Phi_n$, telle que pour $f \in [T_n]$ et pour tout $m$ on ait $\Phi_n(f \upharpoonright_m) = X \upharpoonright_m$, où $X$ est l'élément de $\mathcal{A}$ encodé par $f$. On commence la construction avec $T_0$ comme étant l'arbre encodant les éléments de $\mathcal{A}$, $\Phi_0$ la fonction de décodage de ces éléments et $\sigma_0 = \epsilon$.

On considère $\mathcal{B}_{n+1}$ la classe $\Sigma_1^1$ des $f \in [T_n]$ telles que $n \notin \mathcal{O}^{\Phi_n(f)}$. Il y a deux cas possibles.

Le cas 1. La classe $\mathcal{B}_{n+1}$ est vide, auquel cas on prend $T_{n+1} = T_n \upharpoonright_{(\sigma_n m)}$ pour $m$ le plus petit tel que $[T_n \upharpoonright_{(\sigma_n m)}]$ est non vide et $\sigma_{n+1} = \sigma_n m$. On prend aussi $\Phi_{n+1} = \Phi_n$. Notons que dans ce cas tous les éléments $X \in \mathcal{A}$ encodés dans $T_{n+1}$ sont tels que $n \in \mathcal{O}^X$.

Le cas 2. La classe $\mathcal{B}_{n+1}$ est non vide. Soit alors $U$ l'arbre calculable dont les chemins infinis encodent les éléments de $\mathcal{B}_{n+1}$ et soit $\Psi$ la fonction de décodage de $\mathcal{B}_{n+1}$, c'est-à-dire qui renvoie des éléments de $[T_n]$. Soit $\tau$ la plus petite chaîne de $U$ dans l'ordre lexicographique telle que $\Psi(\tau) = \sigma_n$ et telle que $[U \upharpoonright_{(\tau m)}]$ est non vide pour un certain $k$. Soit $m$ le plus petit de ces entiers $k$. On prend $T_{n+1} = U \upharpoonright_{\tau m}$ et $\sigma_{n+1} = \tau m$. La fonction de décodage $\Phi_{n+1}$ est donnée par $\Phi_{n+1}(\tau) = \Phi_n(\Psi(\tau))$. Notons que dans ce cas tous les éléments $X \in \mathcal{A}$ encodés dans $T_{n+1}$ via $\Phi_{n+1}$ sont tels que $n \notin \mathcal{O}^X$.

Notons finalement que $\mathcal{O}$ peut mener à bien la construction de manière calculable, le prédicat $\ll [T]$ est non vide $\gg$ pour un arbre calculable $T$ étant $\Sigma_1^1$. On obtient petit à petit un élément

$$X = \Phi_0(\sigma_0) \prec \Phi_1(\sigma_1) \prec \Phi_2(\sigma_2) \prec \dots$$

Il s'agit alors de montrer que ce point limite $X$ appartient bien à $\mathcal{A}$. L'ensemble $X$ est construit petit à petit avec son témoin $g$, de telle sorte que chaque préfixe de $f_0 = \langle g, X \rangle$ appartient à $T_0$. Comme $T_0$ est un arbre, alors $f_0$ appartient à $[T_0]$, et donc $X$ à $\mathcal{A}$. Comme vérifié durant la construction, à chaque étape $n$, si l'on est dans le cas 1 alors $n \in \mathcal{O}^X$, et si l'on est dans le cas 2 alors $n \notin \mathcal{O}^X$. Comme la construction est calculable en $\mathcal{O}$, ce dernier peut donc décider petit à petit pour chaque entier $n$ si celui-ci appartient à $\mathcal{O}^X$ ou non. On conclut dès lors que $\mathcal{O}^X \leq_T \mathcal{O}$.

## 2.2. Espace topologique généré par les classes $\Sigma_1^1$

La démonstration du théorème de base de Gandy est très similaire à la démonstration du théorème 8-4.3 (que toute classe $\Pi_1^0$ non vide contient un ensemble low). Dans chacune des preuves, on construit une suite décroissante de classes $A_0 \supseteq A_1 \supseteq \dots$ telle que $\bigcap_n A_n$ contienne notre élément, low dans le premier cas et hyperlow dans le second, et où $A_n$ est $\Pi_1^0$ dans le premier cas et $\Sigma_1^1$ dans l'autre. Il y a malgré tout une complication dans le cas des classes $\Sigma_1^1$: tandis qu'une intersection décroissante $\bigcap_n A_n$ de
classes $\Pi_1^0$, où chaque $\mathcal{A}_n$ est non vide, est nécessairement elle-même non vide, ce n'est plus du tout le cas pour les classes $\Pi_2^0$ et $\mathcal{a fortiori} \Sigma_1^1$. On a donc été forcé dans la preuve ci-dessus de « ruser » et de travailler avec l'arbre qui encode les éléments de nos classes $\Sigma_1^1$, en construisant non pas uniquement un élément $X$ commun à chacune de ces classes, mais aussi en construisant pour chacune de ces classes une fonction témoin associée à $X$. Le théorème suivant est une abstraction qui brode sur cette idée pour dire en termes savants la chose suivante : dans l'espace topologique généré par les classes $\Sigma_1^1$, une intersection d'ouverts denses est dense. Il s'agit d'un résultat important et qui présente de nombreuses applications, en théorie descriptive des ensembles comme en hypercalculabilité. Nous en verrons un exemple avec le théorème 2.4.

**Théorème 2.3 (Gandy)**

Considérons la classe $\bigcap_n \bigcup_m \mathcal{A}_{n,m}$, où chaque $\mathcal{A}_{n,m}$ est une classe $\Sigma_1^1$ telle que pour tout $n$ la classe $\bigcup_m \mathcal{A}_{n,m}$ a une intersection non vide avec toute classe $\Sigma_1^1$ non vide. Alors, $\bigcap_n \bigcup_m \mathcal{A}_{n,m}$ a une intersection non vide avec toute classe $\Sigma_1^1$ non vide.

**PREUVE.** On considère $\mathcal{A}$ une classe $\Sigma_1^1$ non vide quelconque, et l'on construit un élément dans $\mathcal{A} \cap \bigcap_n \bigcup_m \mathcal{A}_{n,m}$. On procède de manière similaire à la construction du théorème précédent. À l'étape 0, on définit $T_0$ comme étant l'arbre canonique qui encode les chemins de $\mathcal{A}$, et l'on définit ensuite $\tau_0^0 = \epsilon, \sigma^0 = \epsilon$ et $\eta_0 = \langle \tau_0^0, \sigma^0 \rangle$. À l'étape $n$ de la construction, supposons que l'on ait des arbres calculables $T_0, \dots, T_n$, où $[T_i]$ est non vide pour $i \le n$, où les nœuds de $T_i$ pour $i \le n$ sont de la forme $\langle \tau_n, \dots, \tau_0, \sigma \rangle$, avec $\langle \tau_{i+1}, \dots, \tau_0, \sigma \rangle \in T_{i+1}$ implique $\langle \tau_i, \dots, \tau_0, \sigma \rangle \in T_i$ pour $i < n$, et où les chemins infinis $\langle f, X \rangle$ de $[T_0]$ encodent les éléments $X \in \mathcal{A}$ et les chemins infinis $\langle f_{i+1}, \dots, f_0, X \rangle$ de $[T_{i+1}]$ encodent les chemins infinis $\langle f_i, \dots, f_0, X \rangle$ de $[T_i]$ pour $i < n$. On suppose de plus que l'on a un nœud $\eta_n = \langle \tau_n^n, \dots, \tau_0^n, \sigma^n \rangle \in T_n$ de taille $n$ tel que les nœuds de $T_n$ sont tous compatibles avec $\eta_n$. Notons que le fait que $[T_n]$ soit non vide, implique, en notant $\eta_i = \langle \tau_i^n, \dots, \tau_0^n, \sigma^n \rangle$ pour $i \le n$, que la classe $[T_i \upharpoonright \eta_i]$ est également non vide.

L'étape $n+1$ est alors relativement simple : sachant que $\bigcup_m \mathcal{A}_{n,m}$ intersecte toute classe $\Sigma_1^1$ non vide, on considère la classe $\Sigma_1^1$ des éléments $X$ tels qu'il existe des fonctions $f_n, \dots, f_0$ pour lesquelles $\langle f_n, \dots, f_0, X \rangle \in T_n$. On choisit $m$ tel que l'intersection entre $\mathcal{A}_{n,m}$ et cette classe soit non vide. Soit $U$ l'arbre des nœuds $\langle \tau, \sigma \rangle$ qui encodent les éléments de $\mathcal{A}_{n,m}$, et soit donc $T$ l'arbre de tous les nœuds $\langle \tau_{n+1}, \tau_n, \dots, \tau_0, \sigma \rangle$ pour $\langle \tau_n, \dots, \tau_0, \sigma \rangle \in T_n$ et $\langle \tau_{n+1}, \sigma \rangle \in U$. Notons que par hypothèse sur $\mathcal{A}_{n,m}$, la classe $[T]$ est non vide. On définit alors $\tau_{n+1}$ comme étant la première chaîne telle que
pour $\eta = \langle \tau_{n+1}, \tau_n^n, \dots, \tau_0^n, \sigma^n \rangle$ la classe $[T]_{\eta}$ est non vide, et l'on définit ensuite $\eta_{n+1}$ comme étant le premier fils de $\eta$ dans $T$ tel que $[T]_{\eta_{n+1}}$ est non vide. On définit enfin $T_{n+1} = T]_{\eta_{n+1}}$.

De la suite $(\eta_n)_{n \in \mathbb{N}}$ on peut extraire pour tout $i$ la suite d'éléments de $T_i$ donnée par $\langle \tau_i^0, \dots, \tau_i^0, \sigma^0 \rangle \prec \langle \tau_i^1, \dots, \tau_i^1, \sigma^1 \rangle \prec \langle \tau_i^2, \dots, \tau_i^2, \sigma^2 \rangle \prec \dots$, qui converge vers $\langle f_i, \dots, f_0, X \rangle$. Comme chaque $T_i$ est un arbre, on a alors

$$ \langle f_i, \dots, f_0, X \rangle \in [T_i], \quad \text{pour tout } i. $$

En particulier, $X \in \mathcal{A}$ et $X \in \bigcup_m \mathcal{A}_{n,m}$ pour tout $n$. Donc, $\mathcal{A} \cap \bigcap_n \bigcup_m \mathcal{A}_{n,m}$ est non vide. Comme $\mathcal{A}$ est arbitraire, la classe $\bigcap_n \bigcup_m \mathcal{A}_{n,m}$ intersecte toute classe $\Sigma_1^1$ non vide. ■

## 2.3. Théorème de base d'évitement de cône hyperarithmétique

Notons que dans le théorème précédent ni l'intersection ni les réunions n'ont besoin d'être effectives. Voyons-en tout de suite une application, avec un autre théorème de base pour les classes $\Sigma_1^1$, celui-ci analogue au théorème 8-4.7 de base d'évitement de cône pour les classes $\Pi_1^0$.

### Théorème 2.4 (Théorème de base de Kreisel)

Soit $\mathcal{A}$ une classe $\Sigma_1^1$ non vide et soit $X$ non hyperarithmétique. Alors, il existe $Y \in \mathcal{A}$ tel que $Y \not\supseteq_h X$.

PREUVE. La preuve de ce théorème utilise deux résultats que nous démontrerons un peu plus tard : d'une part, la proposition 4.3 qui implique que la classe $\{Y : \omega_1^Y = \omega_1^{ck}\}$ est $\Sigma_1^1$, et la proposition 3.1 d'autre part qui stipule que si une classe $\Sigma_1^1$ ne contient qu'un seul élément, alors cet élément est $\Delta_1^1$.

D'après le théorème 2.2, il existe un élément $Y \in \mathcal{A}$ tel que $\omega_1^Y = \omega_1^{ck}$. D'après la proposition 4.3 (de la section suivante), la classe $\{Y : \omega_1^Y = \omega_1^{ck}\}$ est $\Sigma_1^1$. Quitte à intersecter $\mathcal{A}$ avec cette classe, on peut donc supposer sans perte de généralité $\omega_1^Y = \omega_1^{ck}$ pour tous les éléments $Y \in \mathcal{A}$. En particulier, si $Y \supseteq_h X$ pour $Y \in \mathcal{A}$, il existe alors $a \in \mathcal{O}$ tel que $H_a^Y \supseteq_T X$.

Montrons une première chose : il n'est pas possible d'avoir $\Phi_e(H_a^Y) = X$ pour $a \in \mathcal{O}$, $e \in \mathbb{N}$ et tous les éléments $Y$ d'une classe $\Sigma_1^1$ non vide. En effet, si tel était le cas, alors $X$ serait le singleton $\Sigma_1^1$ suivant :

$$ \{X : \exists Y \in \mathcal{A} \ \Phi_e(H_a^Y) = X\} $$

(on utilise ici la classe $\mathcal{P}$ du théorème 28-3.4 pour récupérer $H_a^Y$ à partir de $Y$ de manière $\Sigma_1^1$). D'après la proposition 3.1, qui arrive sous peu, $X$ serait donc $\Delta_1^1$, en contradiction avec nos hypothèses.
Soient $e \in \mathbb{N}$, $a \in O$ et $\mathcal{A}_d$ la classe $\Sigma_1^1$ de code $d$. Pour tout $m$, soit $\mathcal{A}_{\langle e,a \rangle, \langle d,m \rangle}$ la classe $\Sigma_1^1$ des éléments $Y \in \mathcal{A}_d$ tels que $\Phi_e(H_a^Y) \neq X(m)$. D'après ce que l'on vient de montrer, si $\mathcal{A}_d$ est non vide, alors il existe $m$ tel que $\mathcal{A}_{\langle e,a \rangle, \langle d,m \rangle}$ est non vide. En particulier, la réunion $\bigcup_{d,m} \mathcal{A}_{\langle e,a \rangle, \langle d,m \rangle}$ a une intersection non vide avec toute classe $\Sigma_1^1$ non vide. Par ailleurs, $\Phi_e(H_a^Y) \neq X$ pour tout élément $Y \in \bigcup_{d,m} \mathcal{A}_{\langle e,a \rangle, \langle d,m \rangle}$. D'après le théorème 2.3, il existe un élément $Y$ dans $\mathcal{A} \cap \bigcap_{e \in \mathbb{N}, a \in O} \bigcup_{d,m} \mathcal{A}_{\langle e,a \rangle, \langle d,m \rangle}$. On a donc $H_a^Y \not\supsetneq_T X$ pour tout $a \in O$, et donc $Y \not\supsetneq_h X$. ■

### Préservation de $\omega_1^{ck}$ et $\leq_h$

Notons que dans le théorème précédent nous avons commencé par restreindre notre classe aux éléments $Y$ tels que $\omega_1^Y = \omega_1^{ck}$. La réduction hyperarithmétique cache un phénomène nouveau par rapport à la réduction Turing : $\omega_1^{ck}$, contrairement à $\omega$, est une notion relative. En particulier, il existe des oracles $Y$ tels que $\omega_1^Y > \omega_1^{ck}$, et donc qui « augmentent » la valeur du plus petit ordinal non calculable.

Dans le théorème 2.4, pour obtenir $Y \not\supseteq_h X$, il ne suffit donc pas de s'assurer que $H_a^Y \not\supseteq_T X$ pour tout $a \in O$. Il se peut par exemple qu'il existe un $a \in O^Y \setminus O$ tel que $H_a^Y \supseteq_T X$. Par exemple, si $\omega_1^Y > \omega_1^{ck}$, il existe $a \in O^Y$ tel que $|a| = \omega_1^{ck}$, et $H_a^Y$ permet de calculer $O$, qui peut être vu en quelque sorte comme $\emptyset^{(\omega_1^{ck})}$. Forcer $\omega_1^Y = \omega_1^{ck}$ permet donc de se restreindre aux itérations le long de $\omega_1^{ck}$ et non de $\omega_1^Y$, ce qui simplifie la preuve sachant que $Y$ est en cours de construction.

## 3. L'hypothèse du continu pour les classes $\Sigma_1^1$

Nous avons abordé dans la section 9-4.6.2 la question de Cantor, consistant à savoir s'il existait un ensemble $\mathcal{A} \subseteq \mathbb{R}$ tels que $|\mathbb{N}| < |\mathcal{A}| < |2^\mathbb{N}|$. Bien que la question dans toute sa généralité soit indépendante de ZFC, nous avons prouvé à travers la proposition 8-2.14 que l'hypothèse du continu restreinte aux fermés de l'espace de Cantor était vraie, au sens où si un fermé $\mathcal{F}$ est indénombrable, alors il existe une injection de $2^\mathbb{N}$ dans $\mathcal{F}$, ce qui revient à dire que $\mathcal{F}$ est soit de cardinalité finie, soit dénombrable, soit de cardinalité $|2^\mathbb{N}| = |\mathbb{R}|$. Nous allons maintenant étendre la proposition 8-2.14 aux classes $\Sigma_1^1$.

### 3.1. Les classes $\Sigma_1^1$ indénombrables

Nous avons vu que l'axiome du choix dénombrable était superflu pour les classes $\Sigma_1^1$. Voyons à présent que c'est aussi le cas pour l'hypothèse du continu. Nous commençons par une proposition simple : les singletonns $\Sigma_1^1$ sont $\Delta_1^1$.
**Proposition 3.1.** Soit $\mathcal{A}$ une classe $\Sigma_1^1$ ne contenant qu'un seul élément $X$. Alors, $X$ est $\Delta_1^1$.

PREUVE. L'ensemble $X$ a la description $\Sigma_1^1$ suivante : $n \in X$ ssi $\exists Y \in \mathcal{A}$ tel que $n \in Y$. L'ensemble $\mathbb{N} \setminus X$ a la même description : $n \notin X$ ssi $\exists Y \in \mathcal{A}$ tel que $n \notin Y$. L'ensemble $X$ est donc $\Delta_1^1$.

### Théorème 3.2

Soit $\mathcal{A}$ une classe $\Sigma_1^1$ indénombrable. Alors, il existe une injection $f : 2^{\mathbb{N}} \to \mathcal{A}$ calculable en $\mathcal{O}$.

PREUVE. Étant donné un arbre calculable $T \subseteq \mathbb{N}^{<\mathbb{N}}$, la question de savoir si $[T]$ est non vide est $\Sigma_1^1$, et $\mathcal{O}$ peut donc y répondre. On considère la classe $\mathcal{A}' = \mathcal{A} \cap \{X : X \text{ n'est pas hyperarithmétique}\}$. Nous verrons avec la proposition 4.2 que la classe $\mathcal{A}'$ reste $\Sigma_1^1$. Comme la classe des ensembles hyperarithmétiques est dénombrable, la classe $\mathcal{A}'$ reste indénombrable.

Soit $T$ l'arbre calculable tel que $[T]$ contient des éléments $\langle f, X \rangle$ pour tout $X \in \mathcal{A}'$. À l'aide de $\mathcal{O}$, on cherche

$$ \langle \tau_0, \sigma_0 \rangle \in \mathbb{N}^{<\mathbb{N}} \times 2^{<\mathbb{N}} \quad \text{et} \quad \langle \tau_1, \sigma_1 \rangle \in \mathbb{N}^{<\mathbb{N}} \times 2^{<\mathbb{N}} $$

tels que $\sigma_0$ et $\sigma_1$ sont incomparables et tels que $[T \upharpoonright_{\langle \tau_0, \sigma_0 \rangle}]$ et $[T \upharpoonright_{\langle \tau_1, \sigma_1 \rangle}]$ sont non vides (c'est-à-dire tels que les arbres correspondants sont mal fondés). Puis, inductivement, supposons que $\langle \tau_\rho, \sigma_\rho \rangle$ soient définis et deux à deux incomparables pour toute chaîne $\rho$ de taille $n$, et que $[T \upharpoonright_{\langle \tau_\rho, \sigma_\rho \rangle}]$ soit non vide pour chacune d'entre elles.

Supposons par l'absurde que l'un des $[T \upharpoonright_{\langle \tau_\rho, \sigma_\rho \rangle}]$ ne contienne qu'un seul élément. Alors, d'après la proposition 3.1, cet élément est hyperarithmétique, contredisant le fait que $\mathcal{A}'$ ne contienne aucun élément hyperarithmétique. On peut donc continuer : à l'aide de $\mathcal{O}$, on cherche $\langle \tau_{\rho_0}, \sigma_{\rho_0} \rangle \in \mathbb{N}^{<\mathbb{N}} \times 2^{<\mathbb{N}}$ et $\langle \tau_{\rho_1}, \sigma_{\rho_1} \rangle \in \mathbb{N}^{<\mathbb{N}} \times 2^{<\mathbb{N}}$ tels que $\sigma_{\rho_i} \supseteq \sigma_\rho$, $\tau_{\rho_i} \supseteq \tau_\rho$ pour $i \in \{0, 1\}$, tels que $\sigma_{\rho_0}, \sigma_{\rho_1}$ sont incomparables et tels que $[T \upharpoonright_{\langle \tau_{\rho_0}, \sigma_{\rho_0} \rangle}]$ et $[T \upharpoonright_{\langle \tau_{\rho_1}, \sigma_{\rho_1} \rangle}]$ sont non vides. La bijection est donnée par $f(X)$ comme étant l'unique élément de $\bigcap_{\rho \prec X}[\sigma_\rho]$. On a bien $X \neq Y$ implique $f(X) \neq f(Y)$.

### Corollaire 3.3

L'hypothèse du continu est superflue pour les classes $\Sigma_1^1$.

PREUVE. Toute classe $\Sigma_1^1$ est $\Sigma_1^1(X)$ pour un certain $X$. On relativise le théorème précédent à $X$.
Notons qu'il s'agit ici de l'hypothèse du continu telle que posée initialement par Cantor (par opposition à la version de l'hypothèse du continu faisant intervenir les cardinaux, telle que formulée dans la section 27-4.3) : toute classe $\Sigma_1^1$ est soit finie, soit dénombrable, soit contient une injection de $2^N$ vers elle-même.

## 3.2. Les classes $\Sigma_1^1$ dénombrables

La technique utilisée dans la preuve du théorème 3.2 nous permet en fait de renforcer considérablement la proposition 3.1 :

### Théorème 3.4

*Une classe $\Sigma_1^1$ dénombrable ne contient que des éléments hyperarithmétiques.*

PREUVE. Soit $\mathcal{A}$ une classe $\Sigma_1^1$ dénombrable. Soit

$$ \mathcal{A}' = \mathcal{A} \cap \{X : X \text{ n'est pas hyperarithmétique}\}. $$

Supposons par l'absurde que $\mathcal{A}'$ est non vide. Alors, on recommence la construction du théorème précédent (le théorème 3.2). Si l'on peut me-ner cette construction jusqu'au bout, on a une injection de $2^N$ vers $\mathcal{A}'$, ce qui contredit le fait que $\mathcal{A}'$ soit dénombrable. Sinon, la construction bloque au bout d'un moment : il existe une chaîne $\sigma$ telle que $\mathcal{A}' \cap [\sigma]$ ne contient qu'un seul élément. D'après la proposition 3.1, cet élément est hyperarithmétique, ce qui contredit que $\mathcal{A}'$ ne contient aucun élément hyperarithmétique. Donc, $\mathcal{A}'$ est vide, et donc $\mathcal{A}$ ne contient que des hy-perarithmétiques. ■

Notons que d'après le théorème 29-6.4, on peut donc obtenir, uniformément en un code de classe $\Sigma_1^1$ dénombrable, un code d'ordinal calculable $\alpha$ tel que $\emptyset^{(\alpha)}$ puisse en calculer tous les éléments. Nous finissons cette section en montrant que les classes $\Pi_1^0$ dénombrables de l'espace de Cantor sont déjà suffisantes pour renfermer des éléments hyperarithmétiques de complexité arbitraire.

**Proposition 3.5.** On considère $T \subseteq \mathbb{N}^{<N}$ un arbre calculable. Alors, il existe $\mathcal{F} \subseteq 2^N$ une classe $\Pi_1^0$ dont les éléments sont à encodage calculable près, les éléments de $[T]$, auxquels il faut ajouter des ensembles finis. ★

PREUVE. Il suffit d'encoder chaque élément de $f \in [T]$ comme étant l'ensemble $X_f = 0^{f(0)}10^{f(1)}10^{f(2)}1...$. De la même manière, on peut associer à chaque $\tau \in T$ la chaîne finie $X_\tau = 0^{\tau(0)}10^{\tau(1)}1...10^{\tau(|\tau|-1)}$. Soit $S \subseteq 2^N$ l'arbre calculable défini par $\sigma \in S$ ssi $\sigma < X_\tau$ pour $\tau \in T$. Alors, $[S]$ contient exactement les chemins $X_f$ tels que $f \in [T]$, auxquels il faut rajouter les points limites de suites de tels chemins, qui sont nécessairement des ensembles finis.
Supposons en effet qu'un ensemble infini $X$ appartienne à $S$. Alors, chaque préfixe de la forme $0^{n_0}10^{n_1}...10^{n_k}1$ de $X$ correspond à une chaîne $\tau \in T$ telle que $\tau(0) = n_0, \tau(1) = n_1, ..., \tau(k) = n_k$. Ces préfixes étant tous comparables et de plus en plus longs, $X$ correspond donc à une fonction $f \in [T]$. ■

Il est intéressant d'examiner les différents théorèmes de base des classes $\Pi_1^0$ à la lumière de la proposition précédente. Que ce soit le théorème de base low ou de base calculatoirement dominé —et d'autres encore—, on voit que l'on peut être forcé de choisir des ensembles finis pour les satisfaire, les autres ensembles de la classe pouvant être de n'importe quelle complexité impossible par la puissance définitionnelle $\Sigma_1^1$ —par exemple calculant tous $\emptyset^{(\omega)}$.

**Corollaire 3.6**

Des classes $\Pi_1^0$ dénombrables peuvent contenir des éléments hyperarithmétiques de complexité arbitraire.

# 4. Quelques classes $\Pi_1^1$ emblématiques

Nous commençons cette section par la présentation de quelques classes $\Pi_1^1$ particulières. Outre l'intérêt propre que l'on peut avoir à étudier ces classes naturelles, celles-ci sont également utiles en tant qu'outil d'analyse des classes $\Sigma_1^1$, comme nous l'avons vu avec la section 2.3 à propos de la base d'évitement de cône pour les classes $\Sigma_1^1$, et la section 3 à propos des classes $\Sigma_1^1$ dénombrables.

**Définition 4.1.** On dénote par HYP la classe des ensembles hyperarithmétiques. ◇

Nous allons maintenant voir que la classe HYP est $\Pi_1^1$, autrement dit que la classe des ensembles non hyperarithmétiques est $\Sigma_1^1$. La proposition 4.2 est utile pour retirer d'une classe $\Sigma_1^1$ tous ses membres hyperarithmétiques tout en la conservant $\Sigma_1^1$.

**Proposition 4.2.** La classe HYP est $\Pi_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 $\{Y : \mathcal{P}(a, Y)\}$ est le singleton $H_a$ pour tout $a \in \mathcal{O}$. La classe des ensembles hyperarithmétiques est alors donnée par

$$ \{X : \exists a \in \mathcal{O} \exists Y (\mathcal{P}(a, Y) \rightarrow \forall n \Phi_e(Y, n) \downarrow = X(n))\}. $$

La classe HYP est donc bien $\Pi_1^1$.

■
Nous avons vu avec le théorème 29-6.4 que HYP n’est pas $\Sigma_1^1$. La classe HYP reste toutefois une classe borélienne : comme il n’y a qu’une quantité dénombrable d’éléments hyperarithmétiques et que chacun d’entre eux est un singleton $\Pi_1^0$, la classe des ensembles hyperarithmétiques est donc $\Sigma_2^0$. Elle est en fait $\Sigma_2^0(\mathcal{O})$.

Nous étudions à présent la classe des ensembles permettant de calculer le plus petit ordinal non calculable, et que nous appellerons $\mathcal{S}$ pour cette section.

**Proposition 4.3.** La classe $\mathcal{S} = \{X : \omega_1^X > \omega_1^{ck}\}$ est $\Pi_1^1$.

★

PREUVE. Soit $R$ l’ensemble des codes d’ordres c. e. linéaires. Montrons que l’on a $\omega_1^X > \omega_1^{ck}$ si, et seulement si,

$$ \exists a \in \mathcal{O}^X \ \forall f \in \mathbb{N}^\mathbb{N} \ \forall e \in R $$

« f n’est pas un isomorphisme de l’ordre codé par $a$ vers celui codé par $e$. »

Si $\omega_1^X > \omega_1^{ck}$, soit $a \in \mathcal{O}^X$ tel que $|a| = \omega_1^{ck}$. Alors, pour tout $e$ codant pour un ordre linéaire calculable, soit $e$ correspond à un ordinal $\alpha < \omega_1^{ck}$, soit $e$ correspond à un ordre mal fondé. Dans les deux cas, il n’existe pas d’isomorphisme entre l’ordre codé par $a$ et celui codé par $e$.

À l’inverse, si $\omega_1^X = \omega_1^{ck}$, alors pour tout élément $a \in \mathcal{O}^X$, l’ordre codé par $a$ est isomorphe à un bon ordre calculable. ■

Nous avons vu avec le théorème 2.2 que la classe $\mathcal{S}$ n’est pas $\Sigma_1^1$, et même plus : elle ne contient aucune sous-classe $\Sigma_1^1$ non vide. Toutefois, là en-core, cette classe reste borélienne. En voici une description $\Sigma_{\omega_1^{ck}+2}^0(\mathcal{O})$ par l’existence d’un code $3 \times 5^e \in \mathcal{O}_{=\omega_1^{ck}}^X$ :

$$ \mathcal{S} = \left\{ X : \exists e \left( \begin{array}{l} \forall n \ \Phi_e(X, n) <_o \Phi_e(X, n+1) \\ \wedge \ \forall n \ \exists a \in \mathcal{O} \ \Phi_e(X, n) \in \mathcal{O}_{<|a|}^X \\ \wedge \ \forall a \in \mathcal{O} \ \exists n \ \Phi_e(X, n) \notin \mathcal{O}_{<|a|}^X \end{array} \right) \right\} $$

D’après le théorème 2.2, la classe des $\{X : \Phi_e(X, n) \in \mathcal{O}_{<a}^X\}$ est $\Sigma_{|a|+1}^0$, uniformément en $a \in \mathcal{O}$. On obtient donc bien la complexité $\Sigma_{\omega_1^{ck}+2}^0(\mathcal{O})$. Il est possible de montrer en utilisant le *forcing de Steel* [216] que cette classe n’est pas $\Pi_{\omega_1^{ck}+2}^0$.

**Exercice 4.4. (★★★)** (Sacks [189], Tanaka [221]). D’après l’exercice 29-3.9, toute classe $\Pi_1^1$ est mesurable. Montrer que la classe suivante est de mesure nulle

$$ \mathcal{S} = \{X : \omega_1^X > \omega_1^{ck}\}. $$

◇

**Exercice 4.5. (★★)** (Keckris [110], Hjorth et Nies [92]). Déduire de l’exercice précédent qu’il existe une classe $\Pi_1^1$ de mesure nulle qui contient toutes les classes $\Pi_1^1$ de mesure nulle. ◇
Nous voyons finalement notre troisième exemple de classe $\Pi_1^1$, qui cette fois-ci ne sera pas $\Sigma_1^1$. L'idée est de considérer la classe des $X$ qui sont calculables par $\emptyset^{(\alpha)}$ pour $\alpha < \omega_1^X$. Le problème est que pour $\alpha \ge \omega_1^{ck}$ l'ensemble $\emptyset^{(\alpha)}$ n'est pas bien défini. On pourrait bien sûr itérer la définition de $\emptyset^{(\alpha)}$ pour $\alpha \ge \omega_1^{ck}$, mais sans aide extérieure pour calculer $\alpha$, la puissance de calcul de l'ensemble $\emptyset^{(\alpha)}$ n'est pas claire. Il est par ailleurs exclu d'utiliser l'oracle $X$ lui-même comme aide extérieure, car il est malaisé de spécifier formellement que $X$ ne peut être utilisé que dans le calcul de $\alpha$ et non dans le calcul de lui-même. On introduit alors la notation suivante.

**Notation**

Soit un ordinal $\alpha < \omega_1$. On écrit $X \leq_T \emptyset^{(\alpha)}$ pour signifier

$$ \forall Y (\alpha < \omega_1^Y \rightarrow X \leq_T Y^{(\alpha)}). $$

On définit ci-après notre dernière classe $\Pi_1^1$.

**Définition 4.6.** On définit la classe

$$ C = \{X : \exists \alpha < \omega_1^X X \leq_T \emptyset^{(\alpha)}\}. $$

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

La classe $C$ contient en particulier tous les ensembles hyperarithmétiques, ainsi que par exemple le $O$ de Kleene (voir proposition 6.1 et théorème 5.1) et bien d'autres éléments : tous les ensembles $X$ que l'on peut calculer via une itération $\alpha$ du saut Turing, pour $\alpha$ calculable en $X$. La classe $C$ semble moins naturelle que HYP ou $S$. Nous allons néanmoins voir qu'elle possède des propriétés remarquables, que nous étudierons dans la section suivante. Commençons par montrer que cette classe est $\Pi_1^1$.

**Proposition 4.7.** La classe $C$ est $\Pi_1^1$.

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

**PRÉUVE.** La classe $C$ peut s'exprimer de la manière suivante :

$$ C = \{X : \exists b \in O^X \forall Y (\omega_1^Y \le |b| \text{ ou } \exists a \in O^Y_{=|b|} X \le_T H_a^Y)\}. $$

Le prédicat $b \in O^X$ est $\Pi_1^1(X)$ uniformément en $X$. En reprenant les idées de la proposition 4.3, on montre que pour $b \in O^X$ le prédicat $\omega_1^Y \le |b|$ est $\Pi_1^1(X \oplus Y)$ uniformément en $X$ et $Y$. En effet, en considérant l'ensemble $R^Y$ des codes $Y$-c. e. d'ordres linéaires, on a $\omega_1^Y \le |b|$ ssi

$$ \forall e \in R^Y \forall f \in \mathbb{N}^\mathbb{N} $$

« $f$ n'est pas un isomorphisme de l'ordre codé par $b$ vers celui codé par $e$. »

Le prédicat $\exists a \in O^Y X \le_T H_a^Y$ est quant à lui $\Pi_1^1(X \oplus Y)$ uniformément en $X$ et $Y$. La classe est donc $\Pi_1^1$. ■
# 5. Étude d'une classe $\Pi_1^1$ très spéciale

La classe $\mathcal{C}$ définie précédemment n'est pas une classe $\Sigma_1^1$. Nous le verrons en particulier avec le théorème 5.6. Nous allons voir que $\mathcal{C}$ possède de nombreuses propriétés remarquables, ce qui justifie bien qu'on lui consacre une section.

**Théorème 5.1 (Guaspari [80])**

La classe $\mathcal{C}$ est une base pour les classes $\Pi_1^1 : \text{toute classe } \Pi_1^1 \text{ non vide contient un élément de } \mathcal{C}$.

## PREUVE

Soit $\mathcal{A}$ une classe $\Pi_1^1$ non vide. D'après la démonstration du théorème 29-3.2 il existe un code $e$ qui est pour tout $X$ le code d'un arbre $X$-c. e. bien fondé si, et seulement si, $X \in \mathcal{A}$. En utilisant l'ordre de Kleene-Brouwer sur cet arbre, on obtient un code $e$ qui est pour tout $X$ le code d'un ordre linéaire sur un ensemble d'entiers, et tel que $X \in \mathcal{A}$ ssi $e$ code pour un ordre bien fondé. On note $\langle e \rangle^X$ l'ordre en question, $\text{dom}_e^X$ le domaine de $\langle e \rangle^X$ et $\langle e \rangle^\sigma$ l'ordre $\langle e \rangle$ énuméré avec le « morceau d'oracle » $\sigma$. Si $\langle e \rangle^X$ est bien fondé, on note $|e|^X$ l'ordinal $\langle e \rangle^X$ et, pour $a \in \text{dom}_e^X$, on note $|a|^X$ l'ordinal correspondant à $\langle e \rangle^X$ restreint aux éléments strictement plus petits que $a$.

On commence par construire un arbre $T$ dans l'espace $(\mathbb{N} \times \omega_1 \times 2^{<\mathbb{N}})^{<\mathbb{N}}$ dont les chemins seront des encodages d'éléments de $\mathcal{A}$. Le plus petit chemin de $T$ pour l'ordre lexicographique sera un encodage d'un élément $X \in \mathcal{A} \cap \mathcal{C}$. La technique explicitée dans cette preuve sera réutilisée plusieurs fois dans cette section. On notera $\langle \tau, \rho, (\sigma_1, \dots, \sigma_n) \rangle$ pour $\tau \in \mathbb{N}^{<\mathbb{N}}$ et $\rho \in \omega_1^{<\mathbb{N}}$, avec $|\tau| = |\rho| = n$, les éléments de cet espace pour signifier formellement la concatenation des éléments $(\tau(0), \rho(0), \sigma_1), \dots, (\tau(n-1), \rho(n-1), \sigma_n)$. Étant donné un tel élément $\langle \tau, \rho, (\sigma_1, \dots, \sigma_n) \rangle$, on notera $f_{\tau,\rho}: \mathbb{N} \to \omega_1$ la fonction partielle, de domaine fini, telle que $f_{\tau,\rho}(\tau(i)) = \rho(i)$ pour $i < n$.

Pour commencer, on met dans $T$ des nœuds $\langle a, \alpha, \sigma \rangle$ de taille 1 pour tout ordinal $\alpha < \omega_1$ et tous $a, \sigma$ tels que $a$ est le premier élément énuméré dans l'ordre $\langle e \rangle^\sigma$. Étant donné un nœud $\langle \tau, \rho, (\sigma_1, \dots, \sigma_n) \rangle$ de $T$, avec

$$ \sigma_1 < \dots < \sigma_n, \quad |\tau| = |\rho| = n, $$

on met pour tout $\alpha < \omega_1$ le nœud $\langle \tau a, \rho \alpha, (\sigma_1, \dots, \sigma_n, \sigma_{n+1}) \rangle$ dans $T$ pour $\sigma_{n+1} > \sigma_n$ si $a$ est le $(n+1)$-ième élément énuméré dans $\langle e \rangle^{\sigma_{n+1}}$, répétitions non comprises, tel que $f_{\tau a, \rho \alpha}$ est une fonction qui préserve l'ordre.

On notera $\langle f, X \rangle$ la limite $\langle \tau_1, \rho_1, (\sigma_1) \rangle \prec \langle \tau_2, \rho_2, (\sigma_1, \sigma_2) \rangle \prec \dots$ de $[T]$, où $\sigma_1 \prec \sigma_2 \prec \dots X$ et $f_{\tau_1, \rho_1} \prec f_{\tau_2, \rho_2} \prec \dots f$. Montrons que $\langle f, X \rangle \in [T]$ pour une certaine fonction $f$ si, et seulement si, $X \in \mathcal{A}$.
Soit $\langle f, X \rangle \in [T]$. Alors, $f$ est une fonction de $\text{dom}_e^X$ vers $\omega_1$ qui préserve l'ordre. En particulier, pour $a, b \in \text{dom}_e^X$, on a $a <_e^X b$ ssi $f(a) < f(b)$. Il s'ensuit que $<_e^X$ doit être bien fondé. Donc, $X \in \mathcal{A}$. Réciproquement, si $X \in \mathcal{A}$, alors pour la fonction $f : \text{dom}_e^X \to \omega_1$ telle que $f(a) = |a|^X$ on doit avoir $\langle f, X \rangle \in [T]$. Comme $\mathcal{A}$ est non vide, alors $[T]$ aussi est non vide.

Soit $\langle f, X \rangle$ le plus petit chemin infini de $T$ pour l'ordre lexicographique. Notons que l'on a forcément $f(a) = |a|^X$ pour un tel chemin infini — car il s'agit du plus petit chemin pour l'ordre lexicographique. En particulier, $|<_e^X| < \omega_1^X$. Notons que bien que la construction de $T$ soit intuitive effective, il n'est pas possible de parler de calculabilité de $T$, car on manipule des ordinaux dénombrables arbitraires.

L'objectif est à présent de trouver $\beta < \omega_1^X$ tel que pour tout ensemble $Y$ vérifiant $\beta < \omega_1^Y$, l'ensemble $X$ est calculable en $Y^{(\beta)}$. Soit $\alpha = |<_e^X|$, et soit $Y$ tel que $\alpha < \omega_1^Y$. On recommence alors la construction d'un arbre $T_Y$ dont le but est de recopier $T$, mais avec des codes d'ordinaux de $O_{<\alpha}^Y$ à la place des ordinaux eux-mêmes, et en ne gardant donc que la partie de $T$ dont les nœuds mentionnent des ordinaux inférieurs à $\alpha$. Comme plusieurs éléments de $O_{<\alpha}^Y$ peuvent coder pour le même ordinal, on travaillera avec l'ensemble $O_{1,<\alpha}^Y$ qui ne conserve pour chaque ordinal $\beta < \alpha$ que le plus petit code de $\beta$ (plus petit pour l'ordre sur les entiers). Formellement, $O_{1,<\alpha}^Y = \{b \in O_{<\alpha}^Y : \forall c < b \ c \notin O_{=|b|}^Y\}$. En particulier, $O_{1,<\alpha}^Y$ est un ensemble $\Delta_1^1(Y)$. L'arbre $T_Y$ est alors un sous-ensemble $O_{1,<\alpha}^Y$-calculable de $(\mathbb{N} \times O_{1,<\alpha}^Y \times 2^{<\mathbb{N}})^{<\mathbb{N}}$. Il est clair que le chemin $\langle f, X \rangle$ le plus à gauche de $[T_Y]$ est le même — à encodage près des ordinaux de la fonction $f$ — que le chemin le plus à gauche de $T$. Il est clair également que pour $Y_1, Y_2$ tels que $\alpha \le \omega_1^{Y_1}$ et $\alpha \le \omega_1^{Y_2}$, les arbres $T_{Y_1}$ et $T_{Y_2}$ sont les mêmes, à encodage près des ordinaux.

Dans chaque arbre $T_Y$ (pour $Y$ tel que $\alpha \le \omega_1^Y$), le chemin le plus à gauche est donc le même, et il est calculable en $O^Y$ en réutilisant la technique du théorème 2.2. Ce n'est pas tout à fait suffisant : ce chemin doit être hyperarithmétique en $Y$. Pour le montrer, nous allons passer momentanément par l'arbre $T_X$ pour $X$ tel que $\langle f, X \rangle$ est le chemin le plus à gauche de $[T]$. Notons d'abord que la fonction $f$ est hyperarithmétique en $X$ en tant qu'unique fonction telle que $\langle f, X \rangle \in [T_X]$ et telle que $|a|^X = |f(a)|$ pour tout $a \in \text{dom}_e^X$. Donc, $\langle f, X \rangle$ est hyperarithmétique en $X$. Par ailleurs, chaque nœud situé à gauche de $\langle f, X \rangle$ est le point de départ d'un arbre bien fondé hyperarithmétique en $X$, et donc codant pour un ordinal inférieur à $\omega_1^X$. À présent, il est possible de calculer à partir de $\langle f, X \rangle$ l'ensemble des codes hyperarithmétiques en $X$ de tous les arbres bien fondés se situant à gauche de $\langle f, X \rangle$. Comme $\langle f, X \rangle$ est hyperarithmétique en $X$, d'après la
majoration $\Sigma_1^1$ de Spector (combinée aux théorèmes 28-1.10 et 29-6.1), le supremum $\beta$ des ordinaux codés par ces arbres est inférieur à $\omega_1^X$.

À présent, pour un ensemble $Y$ arbitraire tel que $\max(\alpha, \beta) < \omega_1^Y$, l'ordonnal $\beta$ est aussi le supremum des ordinaux codés par des arbres bien fondés se trouvant à gauche de la branche $\langle f, X \rangle \in [T_Y]$. On peut alors calculer en $T_Y$ et $O_{<\beta}^{T_Y}$ le chemin $\langle f, X \rangle$: étant donné un préfixe $\langle \sigma, \rho \rangle$ de $\langle f, X \rangle$, il suffit de chercher la plus petite extension sous laquelle l'arbre est mal fondé, c'est-à-dire sous laquelle l'arbre ne code pas pour un ordinal de $O_{<\beta}^{T_Y}$.
Avec une version relativisée du théorème 28-1.10, on a $O_{<\beta}^{T_Y} \le T_Y$ ($T_Y^{(\beta+1)}$).
Or, $T_Y \le T_Y$ $O_{1, <\alpha}^Y \le T_Y$ $Y^{(\alpha+1)}$. Donc, $O_{<\beta}^{T_Y} \le T_Y$ $Y^{(\beta+1+\alpha+1)}$. En particulier, $X \le T_Y$ $Y^{(\beta+1+\alpha+1)}$ pour tout $Y$ tel que $\beta+1+\alpha+1 < \omega_1^Y$.
Or, $\beta+1+\alpha+1 < \omega_1^X$. Donc, $X \in C$. ■

## Théorème 5.2

Pour toute classe $\Pi_1^1$ non vide $\mathcal{A}$, on peut trouver uniformément en un code de $\mathcal{A}$ le code d'un singleton $\Pi_1^1$ inclus dans $\mathcal{A}$.

**PREUVE.** Il suffit essentiellement de s'apercevoir que dans la preuve précédente, le calcul de la branche infinie $\langle f, X \rangle$ est uniforme en $Y^{(\beta+1+\alpha+1)}$.
En reprenant les notations de cette preuve-là, soit $T \subseteq (\mathbb{N} \times \omega_1 \times 2^{<\mathbb{N}})^<\mathbb{N}$ l'arbre correspondant à la classe $\mathcal{A}$. Soit $\langle f, X \rangle$ le chemin infini le plus à gauche de $T$ et soit $\alpha = |<_e^X|$ où $e$ est le code utilisé pour construire $T$. Pour $Y$ tel que $\omega_1^Y > \alpha$, soit $T_Y$ défini comme dans la même preuve.

Pour des questions d'uniformité, on a besoin ici de $T_Y^\gamma$, qui est l'arbre $T_Y$ qui recopie $T_Y$ en ne gardant que la partie de $T_Y$ dont les nœuds mentionnent des ordinaux inférieurs à $\gamma$. Chaque chemin infini à droite de $\langle f, X \rangle$ dans $T$ est de la forme $\langle g, Z \rangle$ pour $g \ge f$. En particulier, pour $\gamma < |\alpha|$, l'arbre $T_Y^\gamma$ doit être vide et, pour $\gamma \ge |\alpha|$, les arbres $T_Y^\gamma$ ont tous $\langle f, X \rangle$ comme chemin infini le plus à gauche, et sont tous les mêmes à gauche de $\langle f, X \rangle$ (à codage près des ordinaux).

On a montré dans la preuve précédente que pour un certain $\beta < \omega_1^X$, les arbres — nécessairement bien fondés — se trouvant à gauche de la branche $\langle f, X \rangle \in [T_X^\alpha]$ sont de hauteur au plus $\beta$. L'arbre $T_Y^\alpha$ est calculable en $O_{1, <\alpha}^Y$, lui-même calculable en $Y^{(\alpha+1)}$. Comme $O_{<\beta}^Z \le T_Y$ ($Z^{(\beta+1)}$) pour un oracle $Z$ quelconque, en prenant $Z = O_{1, <\alpha}^Y$, on obtient que les arbres se trouvant à gauche de $\langle f, X \rangle$ dans $T_Y^\alpha$ ont tous un code dans $O_{<\beta}^{Y, <\alpha}$, lui-même calculable en $Y^{(\alpha+1+\beta+1)}$. Comme $O_{<\beta}^{Y, <\alpha} \subseteq O_{<\gamma}^{Y, <\alpha}$ pour $\beta < \gamma$, alors également tout oracle de la forme $Y^{(\alpha+1+\gamma+1)}$ pour $\beta < \gamma$ peut reconnaître uniformément que les arbres à gauche de $\langle f, X \rangle$ sont bien fondés.
On peut alors définir la fonctionnelle $\Phi_e$ qui pour n'importe quel $Y$ tel que $\omega_1^Y \ge \omega_1^X$, pour n'importe quel $\gamma_1$ avec $\alpha \le \gamma_1 < \omega_1^Y$ et pour n'importe quel $\gamma_2$ avec $\beta \le \gamma_2 < \omega_1^Y$ sera telle que $\Phi_e(T_Y^{\gamma_1}, Y^{(\gamma_1+1+\gamma_2+1)})$ calcule le chemin $\langle f, X \rangle$, uniformément en $\gamma_1$ et $\gamma_2$, et pour $\gamma_1 < \alpha$ ou $\gamma_2 < \beta$, le calcul $\Phi_e(T_Y^{\gamma_1}, Y^{(\gamma_1+1+\gamma_2+1)})$ ne produit pas un objet infini (soit l'arbre $T_Y^{\gamma_1}$ n'a pas de chemin infini, soit $Y^{(\gamma_1+1+\gamma_2+1)}$ ne connaît pas assez de codes d'arbres bien fondés et fait partir le calcul à gauche « trop tôt »).

Le singleton $\Pi_1^1 A_1 \subseteq A$ est alors donné par la formule suivante :

$$ \{ X \in A : \forall Y \left( \begin{array}{l} \omega_1^Y < \omega_1^X \text{ ou } \exists \gamma_1, \gamma_2 < \omega_1^Y \text{ t.q. } \Phi_e(T_Y^{\gamma_1}, Y^{(\gamma_1+1+\gamma_2+1)}) \\ \text{calcule un chemin infini } \langle f, Z \rangle \text{ avec } Z=X \end{array} \right) \}. \blacksquare $$

On a pour corollaire une généralisation du théorème 29-4.1, due tout à la fois à Kondô [123] et Addison [4].

**Corollaire 5.3 (Uniformisation des classes $\Pi_1^1$)**

Pour toute classe $\Pi_1^1 A \subseteq 2^N \times 2^N$, il existe $f : 2^N \to 2^N$, une fonction partielle $\Pi_1^1$, telle que pour tout $X$, si $\{Y : (X, Y) \in A\}$ est non vide, alors $(X, f(X)) \in A$.

PREUVE. On définit $f(X) = Y$ si $Y$ appartient au $\Pi_1^1(X)$ singleton inclus dans la classe $\{Y : (X, Y) \in A\}$. ■

**Corollaire 5.4**

L'axiome du choix est superflu pour les classes $\Pi_1^1$.

Conformément au corollaire 5.3, l'axiome du choix est vérifié tant qu'il y a une uniformité dans la présentation de nos classes $\Pi_1^1$.

**Corollaire 5.5**

Soit $X$ un singleton $\Pi_1^1$. Alors, $\exists \alpha < \omega_1^X$ tel que $X \le_T \emptyset^{(\alpha)}$.

Nous reviendrons sur les singletons $\Pi_1^1$ dans la section suivante, et nous nous consacrons pour le moment à terminer notre étude de $C$, en montrant qu'elle ne vérifie pas forcément l'hypothèse du continu, et qu'elle ne contient en particulier aucun fermé parfait. Il s'agit en fait de la plus grosse classe $\Pi_1^1$ ne contenant pas de fermé parfait.

**Théorème 5.6 (Mansfield [147] Solovay [211])**

Soit $A$ une classe $\Pi_1^1$. Alors, $A$ contient un fermé parfait si, et seulement si, elle contient un élément $X \notin C$.
PREUVE. Supposons que $\mathcal{A}$ contient un fermé parfait $T$. D'après la proposition 4.2 la classe $\mathcal{U}$ des éléments de $[T]$ qui ne sont pas $\Delta_1^1(T)$ est une classe $\Sigma_1^1(T)$ indénombrable. D'après la relativisation du théorème 2.2, la classe $\mathcal{U}$ contient un élément $X$ tel que $\omega_1^{X \oplus T} = \omega_1^T$. On a donc $\omega_1^X \le \omega_1^T$. En revanche, $X$ n'est pas hyperarithmétique en $T$. En particulier, $X \notin \mathcal{C}$.

Si $\mathcal{A}$ contient à présent un élément $X \notin \mathcal{C}$, soit $T \subseteq (\mathbb{N} \times \omega_1 \times 2^{<\mathbb{N}})^{<\mathbb{N}}$ l'arbre défini comme dans la preuve du théorème 5.1, c'est-à-dire — en reprenant les notations de la preuve — tel que $X \in \mathcal{A}$ ssi $\langle f, X \rangle \in [T]$ pour une certaine fonction $f : \text{dom}_e^X \to \omega_1$ (où $\text{dom}_e^X$ est défini là encore comme dans la même preuve). Pour un ordinal $\gamma$ et un ensemble $Y$ avec $\omega_1^Y > \gamma$, on note $T_Y^\gamma$ l'arbre $T$ restreint aux nœuds ne mentionnant que des ordinaux plus petits que $\gamma$ et utilisant des codes de $\mathcal{O}_{1, < \gamma}^Y$ pour représenter les ordinaux. Notons qu'à codage près des ordinaux les arbres $T_Y^\gamma$ sont les mêmes pour tout $Y$ vérifiant $\gamma < \omega_1^Y$. Soit $\alpha$ le plus petit ordinal tel que pour tout $Y$ vérifiant $\alpha < \omega_1^Y$ ; l'arbre $T_Y^\alpha$ contient un chemin infini $\langle f, X \rangle$ pour un certain $X \in \mathcal{A} \setminus \mathcal{C}$. Notons que l'on a dans ce cas nécessairement $\alpha < \omega_1^X$.

Soit $U \subseteq \mathbb{N}^{<\mathbb{N}}$ un arbre calculable tel que $X \notin \mathcal{C}$ ssi $\exists f \langle f, X \rangle \in [U]$. Considérons à présent l'arbre $S_Y \subseteq (\mathbb{N}^{<\mathbb{N}} \times \mathbb{N} \times \alpha \times 2^{<\mathbb{N}})^{<\mathbb{N}}$ tel que

$$ \langle (\tau_1, \dots, \tau_n), \tau, \rho, (\sigma_1, \dots, \sigma_n) \rangle \in S $$

ssi $\langle \tau_i, \sigma_i \rangle \in U$ pour tout $i \le n$ et $\langle \tau, \rho, (\sigma_1, \dots, \sigma_n) \rangle \in T_Y^\alpha$. Notons qu'à codage près des ordinaux les arbres $S_Y$ sont les mêmes pour tout $Y$ tel que $\alpha < \omega_1^Y$. Par hypothèse sur $\alpha$, l'arbre $S_Y$ est non vide. On prétend que pour tout nœud

$$ \eta = \langle (\tau_1, \dots, \tau_n), \tau, \rho, (\sigma_1, \dots, \sigma_n) \rangle \in S_Y $$

tel que $[S_Y \upharpoonright_\eta]$ est non vide, il existe deux nœuds

$$ \eta_1 = \langle (\tau_1, \dots, \tau_n, \dots, \tau_{m_1}^1), \tau_1, \rho_1, (\sigma_1, \dots, \sigma_n, \dots, \sigma_{m_1}^1) \rangle \succ \eta $$

$$ \text{et } \eta_2 = \langle (\tau_1, \dots, \tau_n, \dots, \tau_{m_2}^2), \tau_2, \rho_2, (\sigma_1, \dots, \sigma_n, \dots, \sigma_{m_2}^2) \rangle \succ \eta $$

tels que $\sigma_{m_1}^1$ et $\sigma_{m_2}^2$ sont incompatibles et tels que $[S_Y \upharpoonright_{\eta_1}]$ et $[S_Y \upharpoonright_{\eta_2}]$ sont tous les deux non vides. Si tel est bien le cas, on construit une injection de $2^{\mathbb{N}}$ vers les éléments de $\mathcal{A} \setminus \mathcal{C}$, et la proposition est vérifiée. Si ce n'est pas le cas, alors il existe un nœud $\eta \in S_Y$ tel que $[S_Y \upharpoonright_\eta]$ contient au moins un chemin infini et tel que tous les chemins infinis de $[S_Y \upharpoonright_\eta]$ sont de la forme $\langle f', f, X \rangle$ pour un même ensemble $X$. Notons que pour $Y$ tel que $\omega_1^Y > \alpha$ l'arbre $S_Y$ est uniformément $\Delta_1^1(Y)$. Pour $n$ suffisamment grand, on a donc $n \in X$ ssi $\exists f', f, Z \langle f', f, Z \rangle \in [S_Y \upharpoonright_\eta] \wedge n \in Z$ et $n \notin X$ ssi $\exists f', f, Z \langle f', f, Z \rangle \in [S_Y \upharpoonright_\eta] \wedge n \notin Z$. Ainsi, $X$ et $\mathbb{N} \setminus X$ sont $\Sigma_1^1(S_Y)$ et donc $X$ est $\Delta_1^1(S_Y)$, et donc $\Delta_1^1(Y)$. La procédure est pas ailleurs uniforme en $Y$. Donc, pour tout $Y$ tel que $\omega_1^Y > \alpha$ il existe $\beta$ avec $\alpha \le \beta < \omega_1^Y$ tel que $Y^{(\beta)} \ge T_X$. D'après le lemme 29-6.3 relativisé à $X$, on a par
conséquent un ordinal $\beta$ avec $\alpha \le \beta < \omega_1^X$ tel que $Y^{(\beta)} \ge_T X$ pour tout $Y$ vérifiant $\omega_1^Y > \beta \ge \alpha$. Donc, $X \in C$, ce qui est une contradiction. ■

**Corollaire 5.7**

La classe $C$ est la plus grosse classe $\Pi_1^1$ ne contenant pas de fermé parfait.

On ne peut donc pas construire d'injection continue de $2^N$ dans $C$. Mais la classe $C$ est-elle elle-même dénombrable ou indénombrable ? Il n'est en fait pas possible de répondre à cette question. On peut montrer que dans le modèle de ZFC des constructibles de Gödel, tout ensemble $X \in 2^N$ est Turing calculable par un élément de $C$. Dans ce modèle, $C$ est indénombrable et satisfait l'hypothèse du continu (bien que l'on ne puisse pas en rendre compte via une injection continue de $2^N$ vers $C$). Via la technique du forcing de Cohen, on peut construire des modèles de ZFC pour lesquels $C$ peut rester indénombrable et ne pas satisfaire l'hypothèse du continu, ou même devenir dénombrable. On trouvera plus de détails dans la section 4.3 de [35].

# 6. Les singletons $\Pi_1^1$

Par le théorème 5.2, toute classe $\Pi_1^1 \ne \emptyset$ contient un singleton $\Pi_1^1$. On portera donc une attention particulière aux singletons $\Pi_1^1$. En particulier, tout théorème de base pour les $\Pi_1^1$ peut se prouver en se restreignant aux classes singletons. Contrairement aux singletons $\Sigma_1^1$, les singletons $\Pi_1^1$ ne sont pas forcément hyperarithmétiques. On a, à titre d'exemple, ce qui suit.

**Proposition 6.1.** Le $\mathcal{O}$ de Kleene est un singleton $\Pi_1^1$.

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

PREUVE. Il est clair que la classe $\mathcal{A}$ suivante est $\Pi_1^1$ et contient exactement le $\mathcal{O}$ de Kleene :

$$ \left\{ \begin{array}{l} \forall e \in X \ e \in \mathcal{O} \wedge 1 \in X \\ \forall a \in \mathbb{N} \ a \in X \rightarrow 2^a \in X \\ \forall e \in \mathbb{N} \ \left( \begin{array}{l} \forall n \ (\Phi_e(n) \downarrow \in X \wedge \Phi_e(n) <_o \Phi_e(n+1)) \\ \rightarrow 3 \times 5^e \in X \end{array} \right) \end{array} \right\}. $$

Notons que la relation $<_o$ utilisée pour la définition de $\mathcal{A}$ est la relation $\ll$ étendue $\gg$ à tous les éléments de la forme $2^b$ ou $3.5^b$, comme dans la preuve du théorème 29-3.1. ■

On peut en fait montrer que pour tout $\mathcal{A}$ singleton $\Pi_1^1$ l'ensemble $\mathcal{O}^\mathcal{A}$ est lui aussi un singleton $\Pi_1^1$. Nous le verrons formellement dans la prochaine proposition. Ainsi, $\mathcal{O}, \mathcal{O}^\mathcal{O}, \mathcal{O}^{\mathcal{O}\mathcal{O}}, \dots$, sont tous des singletons $\Pi_1^1$. Cette considération nous amène à l'itération transfinie de l'hypersaut. Contrairement à la hiérarchie transfinie du saut, on peut cette fois-ci continuer au-delà de $\omega_1^{ck}$, puisque notre oracle alors décodeur $\omega_1^{ck}$.
**Définition 6.2.** On définit inductivement la hiérarchie des hypersauts.

(1) $J_1 = \emptyset$ et $J_2 = \mathcal{O}$. On définit $1 <_{ho} 2$.

(2) Si $a$ est dans le domaine de $<_{ho}$, alors $J_{2a} = \mathcal{O}^{J_a}$. On définit $a <_{ho} 2^a$ et $b <_{ho} 2^a$ pour tout $b <_{ho} a$.

(3) Si $a$ est dans le domaine de $<_{ho}$ et $e$ est le code d'une fonctionnelle telle que $\Phi_e(J_a, 0) \downarrow = a$ et telle que $\Phi_e(J_a, n) \downarrow <_{ho} \Phi_e(J_a, n+1) \downarrow$ pour tout $n$, alors $J_{3^a \times 5^e} = \bigoplus_{n \in \mathbb{N}} J_{\Phi_e(J_a, n)}$. On définit $b <_{ho} 3^a \times 5^e$ pour tout $b$ tel que $b <_{ho} \Phi_e(J_a, n)$ pour un certain $n$. $\diamond$

Notons la différence avec l'ordre $<_o$: cette fois-ci les éléments limites sont de la forme $3^a \times 5^e$ et non de la forme $3 \times 5^e$, où l'élément $a$ sert comme un code de l'itération de l'hypersaut nécessaire en tant qu'oracle pour déplier l'ordre codé par $e$.

**Proposition 6.3.** Soit $a$ dans le domaine de $<_{ho}$. Alors, $J_a$ est un singleton $\Pi_1^1$. ★

**PREUVE.** La preuve est similaire à celle du théorème 28-2.1 : on utilise le théorème du point fixe pour définir une classe $\Pi_1^1 \mathcal{P} \subseteq \mathbb{N} \times 2^\mathbb{N}$ telle que pour tout code $e$ dans le domaine de $<_{ho}$ la classe $\{X : (e, X) \in \mathcal{P}\}$ est égale à $\{J_e\}$. Soit $\Psi$ la fonctionnelle telle que $\Psi(\mathcal{O}^X) = X$ pour tout $X$. La définition de $\mathcal{P}$ est la suivante : $(b, X) \in \mathcal{P}$ si $b = 1$ et $X = \emptyset$, ou si $b = 2^a$ et (en reprenant les éléments de la preuve de la proposition 6.1) si $X$ est dans la classe suivante :

$$ \left\{ Y : (a, \Psi(Y)) \in \mathcal{P} \wedge \left( \begin{array}{l} \forall e \in Y \ e \in \mathcal{O}^{\Psi(Y)} \wedge 1 \in Y \\ \forall e \in \mathbb{N} \ e \in Y \to 2^e \in Y \\ \forall e \in \mathbb{N} \ \left( \begin{array}{l} \forall n \left( \begin{array}{l} \Phi_e(n) \downarrow \in Y \\ \wedge \ \Phi_e(n) <_o \Phi_e(n+1) \end{array} \right) \\ \to 3 \times 5^e \in Y \end{array} \right) \end{array} \right\} $$

ou si $b = 3^a \times 5^e$ et si $X$ est dans la classe suivante :

$$ \{ \bigoplus_n Y_n : (a, Y_0) \in \mathcal{P} \wedge \forall n (\Phi_e(Y_0, n), Y_n) \in \mathcal{P} \}. $$

Ci-dessus, la relation $<_o$ se calcule à l'aide de l'oracle $\Psi(Y)$.

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

Il est intéressant de se demander jusqu'où va la hiérarchie des hypersauts. L'ordre $<_{ho}$ que l'on a défini conjointement à cette hiérarchie correspond à un bon ordre, qui va bien au-delà de $\omega_1^{ck}$. Quelle est la valeur de cet ordinal ? Pour répondre à cette question, nous introduisons ci-après une hiérarchie d'ordinaux qui va de pair avec celle des hypersauts.
**Définition 6.4.** On définit la hiérarchie d'ordinaux suivante.

1. Soit $\omega_1^{ck}$ le plus petit ordinal non calculable.

2. Supposons $\omega_\alpha^{ck}$ défini pour un ordinal dénombrable $\alpha$. Alors, $\omega_{\alpha+1}^{ck}$ est le plus petit ordinal supérieur à $\omega_\alpha^{ck}$ et de la forme $\omega_1^X$ pour un certain $X$.

3. Supposons $\omega_{\alpha_n}^{ck}$ défini pour $\alpha_0 < \alpha_1 < \dots$. Alors, $\omega_{\sup_n \alpha_n}^{ck} = \sup_n \omega_{\alpha_n}^{ck}$. $\diamond$

En utilisant et en itérant le théorème 29-7.6 on montre facilement que $\omega_2^{ck} = \omega_1^{\mathcal{O}}, \omega_3^{ck} = \omega_1^{\mathcal{O}^\mathcal{O}}, \dots$. Notons que $\omega_\omega^{ck} = \sup_n \omega_n^{ck}$ n'est lui-même pas de la forme $\omega_1^X$ pour un certain $X$ :

**Proposition 6.5.** Supposons $\omega_1^X > \omega_n^{ck}$ pour tout $n$. Alors, $\omega_1^X > \omega_\omega^{ck}$. $\star$

**PREUVE.** On va définir une fonction totale $f : \mathbb{N} \to \mathcal{O}^X$ qui sera $\Pi_1^1(X)$ et telle que $|f(n)| = \omega_n^{ck}$. Comme la fonction est totale sur $\mathbb{N}$ la relation $f(n) = a$ est équivalente à $\forall b \neq a \ f(n) \neq b$. La relation $f(n) = a$ est donc également $\Sigma_1^1(X)$. En particulier, l'image de $f$ est un ensemble $\Sigma_1^1(X)$ inclus dans $\mathcal{O}^X$. D'après le théorème de majoration de Spector, son supremum est donc strictement inférieur à $\omega_1^X$, ce qui nous donne $\omega_1^X > \omega_\omega^{ck}$.

Définissons à présent notre fonction : $f(0) = a$ si

(1) $a \in \mathcal{O}^X$;

(2) pour tout $e$ aucune fonction $g$ n'est un isomorphisme entre l'ordre codé par $a$ et celui codé par $e$;

(3) $\forall b <_o^X a \ \exists c \in \mathcal{O} \ b \in \mathcal{O}_{<c}^X$;

(4) $a$ est le plus petit entier de l'ensemble $\mathcal{O}_{=|a|}^X$.

Chaque condition est $\Pi_1^1(X)$. La première assure que $a$ est bien un ordinal, la deuxième et la troisième que $|a| = \omega_1^{ck}$, et la dernière est là pour l'unicité de $a$. Notons que l'on peut alors définir un code $\Delta_1^1(X)$ pour $\mathcal{O}$ uniformément en $f(0)$. On note alors $H_0$ l'ensemble $\mathcal{O}$.

On définit ensuite inductivement $f(n+1) = a$ si :

(1) $a \in \mathcal{O}^X$;

(2) pour tout $e$ aucune fonction $g$ n'est un isomorphisme entre l'ordre codé par $a$ et celui codé par $e$ avec oracle $H_n$;

(3) $\forall b <_o^X a \ \exists c \in \mathcal{O}^{H_n} \ b \in \mathcal{O}_{<c}^X$;

(4) $a$ est le plus petit entier de l'ensemble $\mathcal{O}_{=|a|}^X$.

On définit enfin inductivement $H_{n+1}$ comme étant l'ensemble $\mathcal{O}^{H_n}$ qui est $\Delta_1^1(X)$ uniformément en $f(n+1)$. Chaque condition est $\Pi_1^1(X)$. Pour la condition (2), $H_n$ est simplement une notation pour un ensemble $\Delta_1^1(X)$ dont on connaît le code uniformément en $f(n)$. Le fait que $f(n+1)$ ait
besoin de réutiliser la valeur $f(n)$ n'est pas un problème pour donner une
définition $\Pi_1^1(X)$ du prédicat $f(n) = a$. On peut par exemple utiliser le
théorème du point fixe pour avoir accès au code du graphe de $f$ dans la
définition de $f$.
■

On peut montrer que pour la plupart des ordinaux limites $\alpha$, l'ordinal $\omega_\alpha^{ck}$ n'est pas de la forme $\omega_1^X$ pour un certain $X$. C'est en fait le cas pour tout ordinal limite $\alpha < \omega_\alpha^{ck}$. Il suffit de répéter la preuve précédente, mais avec une fonction $f : \alpha \to O^X$ — on utilise bien sûr en pratique des codes de $\mathcal{O}_{=\alpha}^X$ à la place de $\alpha$.

**Définition 6.6.** Un ordinal dénombrable $\alpha$ est *récursivement inaccessible* si $\alpha$ est limite et $\omega_\alpha^{ck} = \omega_1^X$ pour un certain $X$. $\diamond$

Notons que par la remarque précédant cette définition, tout ordinal récur-
sivement inaccessible $\alpha$ est tel que $\alpha = \omega_{\alpha}^{ck}$. Il ne s'agit toutefois pas
d'une condition suffisante, et le premier ordinal tel que $\alpha = \omega_{\alpha}^{ck}$ (défini
par $\sup_n f^{(n)}(1)$ où $f(\alpha) = \omega_{\alpha}^{ck}$) n'est pas récursivement inaccessible.

Notons enfin que notre définition d'ordinal récursivement inaccessible n'est
pas la définition originale (dont l'équivalence avec la nôtre découle d'un
théorème de Sacks [191]), qui nécessite de travailler dans l'univers des
constructibles de Gödel et dépasse le cadre de cet ouvrage.

Sacks [190] a montré que le premier ordinal récursivement inaccessible est égal à $|<_{ho}|$, le plus petit ordinal inaccessible par notre hiérarchie des hypersauts. Il est également possible de montrer que le premier ordinal récursivement inaccessible peut être encodé par un singleton $\Pi_1^1$. En particulier, les singletonns $\Pi_1^1$ vont « au-delà » de la hiérarchie des hypersauts.
<figure><img src="image_184.png" /></figure>
Chapitre 31

# Les systèmes ATR₀ et Π₁⁻CA₀

Les mathématiques à rebours possèdent cinq grands systèmes de référence, à savoir RCA₀, WKL₀, ACA₀, ATR₀ et Π₁⁻CA₀, linéairement ordonnés par l'implication logique. Les premiers systèmes, RCA₀, WKL₀ et ACA₀, correspondent à des notions calculatoires connues en calculabilité classique : les ensembles calculables, les complétions de l'arithmétique de Peano, et enfin les ensembles arithmétiques. Nous avions donc les outils nécessaires pour étudier ces systèmes dans le chapitre 22.

Les systèmes ATR₀ et Π₁⁻CA₀, en revanche, font intervenir des itérations transfinies d'opérateurs arithmétiques, et des quantifications du second ordre. Leurs puissances calculatoires correspondantes se situent donc naturellement plutôt au niveau de l'hypercalculabilité. Profitons donc de cette nouvelle connaissance pour revenir sur l'étude de ces deux systèmes en mathématiques à rebours.

## 1. Définitions

Rappelons les définitions formelles des systèmes ATR₀ et Π₁⁻CA₀, telles que présentées dans le chapitre 22.

Le système ATR₀. Le système ACA₀ était caractérisé par l'axiome de compréhension sur les formules Σ₁. Le système ATR₀ est quant à lui caractérisé par un axiome d'existence d'ensemble plus puissant, permettant informellement d'utiliser les définitions mathématiques par récurrence transfinie. L'exemple canonique est l'existence de l'α-itération du saut Turing, pour un ordinal α dans le modèle considéré. La formulation précise de ATR₀
soulève un point important : la notion de bon ordre est une notion *relative* au modèle. Plus précisément, considérons un ordre total strict < sur un ensemble $A \subseteq \mathbb{N}$. L'énoncé ≪ < est bien fondé sur $A \succ$ s'exprime formellement par la formule du second ordre $WO(<, A)$ suivante :

$$ \forall B \subseteq A (B \neq \emptyset \rightarrow \exists x \in B \forall y \in B \ y \prec x). $$

Autrement dit, $WO(<, A)$ signifie que tout sous-ensemble non vide de $A$ possède un plus petit élément au sens de l'ordre $<$. En particulier, un modèle $\mathcal{M}$ satisfait $WO(<, A)$ si tout sous-ensemble non vide $B$ de $A$ présent dans le modèle possède un plus petit élément. Il se peut donc qu'un ordre mal fondé $<$ sur $A$ semble être un bon ordre du point de vue de $\mathcal{M}$, mais ne soit pas un bon ordre en absolu, dans le sens où il existe un sous-ensemble de $A$ sans plus petit élément, mais qu'un tel ensemble ne soit pas dans $\mathcal{M}$.

Soit $\theta(x, X)$ une formule arithmétique contenant notamment les variables libres $x$ et $X$. Cette formule induit un opérateur $\Theta: 2^\mathbb{N} \to 2^\mathbb{N}$ sur les ensembles défini par $\Theta(X) = \{n \in \mathbb{N} : \theta(n, X)\}$. Rappelons le schéma de récursion transfinie présenté dans la section 22-8.3.

## Définition 1.1

Le schéma de récursion transfinie énonce, pour toute formule arithmétique à paramètre $\theta(x, X)$, tout ensemble $A$ et tout ordre total strict $< \subseteq A \times A$ tel que $WO(<, A)$, l'existence d'un ensemble $Y = \bigoplus_{a \in A} Y_a$ défini pour tout $a \in A$ par

$$ Y_a = \Theta\left(\bigoplus_{b<a} Y_b\right). $$

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

Par exemple, si l'on considère la formule $\theta(x, X) = \Phi_x^X(x) \downarrow$ et l'ensemble bien ordonné $(\mathbb{N}, <_\mathbb{N})$, alors l'opérateur $\Theta$ est le saut Turing défini par $\Theta(X) = X'$. On a

$$ Y_0 = \Theta(\emptyset) = \emptyset', \quad Y_1 = \Theta(Y_0) = \emptyset'', \quad Y_2 = \Theta(Y_0 \oplus Y_1) = (\emptyset' \oplus \emptyset'')', $$

et ainsi de suite. L'ensemble $Y$ résultant est de même degré que l'ω-saut Turing de $\emptyset$.

## Notation

Le système ATR₀ est RCA₀ augmenté du schéma de récursion transfinie.

Il est clair, au vu de ce qui précède, que le système ATR₀ implique ACA₀ dans RCA₀. En effet, RCA₀ prouve que l'ordre naturel sur les entiers est un bon ordre. Ainsi, $RCA_0 + ATR_0$ prouve l'existence de $X'$ pour tout ensemble $X$, donc prouve ACA₀, d'après l'exercice 22-6.2.

Le système $\Pi_1^1-CA_0$. Le système $\Pi_1^1-CA_0$ est quant à lui plus simple à définir formellement, à l'aide de formules de l'arithmétique du second
ordre. Rappelons que le schéma de compréhension est donné pour toute
formule $F(x)$ par

$$
\exists X \forall y (y \in X \leftrightarrow F(y)) \qquad (9)
$$

Notation

Le système Π₁⁻·CA₀ est RCA₀ augmenté du schéma de compréhension (9)
pour les formules Π₁ à paramètre.

Commençons par prouver le résultat qui suit.

**Proposition 1.2.** Le système $\Pi_1^1$-CA$_0$ implique le système ATR$_0$.

*

PREUVE. Soit $\theta(x, X)$ une formule arithmétique et soit $< \subseteq A \times A$ un bon ordre sur un ensemble $A$. Précisons ici que la notation $\bigoplus_{b<a} X_b$ pour $a \in A$ désigne l'ensemble $\{\langle b, n \rangle : n \in X_b\}$. Notons par ailleurs que $\Pi_1^1$-CA$_0$ signale le schéma de compréhension pour les formules $\Sigma_1^1$ — la compréhension $\Delta_0$ avec paramètre du second ordre permet de montrer que le complémentaire de chaque ensemble existe).

Considérons la formule arithmétique suivante :

$$
F(a, X) \leftrightarrow \forall b \le a X_b = \{m : \theta(m, \bigoplus_{c<b} X_c)\}, \text{ où } X = \bigoplus_{b<a} X_b.
$$

En supposant Π₁⁻·CA₀, montrons que pour tout $a \in A$ il existe un unique Z tel que $F(a, Z)$. Supposons par l'absurde que cela ne soit pas le cas. Par hypothèse sur notre ordre $< \subseteq A \times A$, il existe un plus petit $a \in A$ tel que ce n'est pas le cas. En particulier, pour tout $b < a$, il existe un unique ensemble $Z^b$ tel que $F(b, Z^b)$. Montrons que l'ensemble $Z = \bigoplus_{b<a} Z^b$ existe. Considérons la formule

$$
F(\langle b, n \rangle) \equiv b < a \wedge \exists Z F(b, Z) \wedge n \in Z.
$$

D'après le schéma de compréhension Σ₁, il existe un ensemble Z tel que

$$
\langle b, n \rangle \in Z \leftrightarrow F(\langle b, n \rangle).
$$

Par hypothèse d'induction, cet ensemble est nécessairement unique et égal
à $\bigoplus_{b<a} Z^b$. Il suffit à présent d'appliquer le schéma d'axiome de compréhens
ion pour les formules arithmétiques pour obtenir l'existence de

$$
Z^a = \{m : \theta(m, \bigoplus_{b<a} Z^b)\},
$$

qui vérifie donc $F(a, Z^a)$, ce qui contredit notre hypothèse sur $a$.

Donc, pour tout $a \in A$, il existe un unique ensemble $Z$ tel que $F(a, Z)$. Pour finir, on montre l'existence de l'ensemble $\bigoplus_{a \in A} Z^a$, en utilisant l'axiome de compréhension $\Sigma_1$ sur la formule

$$
F(\langle a, n \rangle) \equiv a \in A \wedge \exists Z F(a, Z) \wedge n \in Z.
$$

■
## 2. ATR₀ et Π₁¹-CA₀ en hypercalculabilité

Tout comme WKL₀ correspond à l'existence de degrés PA relatifs à tout ensemble, ou ACA₀ à l'existence du saut Turing, les systèmes ATR₀ et Π₁¹-CA₀ ont également des équivalences calculatoires. Informellement, ATR₀ stipule que, pour tout X, l'ensemble $X^{(\alpha)}$ existe pour tout ordinal $\alpha < \omega_1^X$, et Π₁¹-CA₀ stipule quant à lui que $O^X$ existe pour tout X.

Il convient toutefois de faire attention à la manière d'exprimer formellement ces deux axiomes. De la même manière que la notion de bon ordre est relative au modèle, la notion d'ordinal, en tant qu'ensemble bien ordonné, est sujette aux mêmes problématiques : il se peut qu'un entier $a$ ne code pas en absolu pour un ordinal, mais que tous les sous-ensembles de $\{b : b <_o a\}$ présents dans le modèle aient un plus petit élément. Autrement dit, du point de vue du modèle, $a$ sera le code d'un ordinal valide. Nous verrons que l'une des conséquences de ce phénomène est que HYP n'est pas un $\omega$-modèle de ATR₀, et qu'un $\omega$-modèle de Π₁¹-CA₀ ne contient pas nécessairement le $O$ de Kleene. En effet, l'axiome « pour tout $X$ l'ensemble $O^X$ existe » doit être exprimé dans le modèle, et ce sera le $O$ de Kleene du point de vue du modèle qui existera dans le modèle, mais pas nécessairement l'authentique $O$ de Kleene.

Voyons tout cela plus précisément. Remémorons-nous un instant la preuve que $O^X$ est $\Pi_1(X)$ uniformément en $X$. La définition se fait comme la conjonction de deux conditions pour que $a \in O$. La première condition est $\Pi_2^0$: 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 linéaire et 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$.

**Notation**

On notera $L_O(a, X)$ le prédicat (1) relativisé à un oracle $X$, auquel on ajoute la condition que si $b <_o c <_o a$, alors également $2^b \leq_o c$.

**Notation**

On notera $W_O(a, X)$ le prédicat (2) relativisé à un oracle $X$.
Remémorons-nous également $\mathcal{P} \subseteq \mathbb{N} \times 2^{\mathbb{N}} \times 2^{\mathbb{N}}$ la classe $\Pi_2^0$, apparais-
sant dans le théorème 28-2.1, telle que pour tout $X$ et tout $a \in \mathcal{O}^X$
l'ensemble $H_a^X$ est l'unique élément tel que $\mathcal{P}(a, X, H_a^X)$. L'existence de
chaque ensemble $H_a^X$ pour $a \in \mathcal{O}^X$ est l'exemple canonique de l'utilisation
de ATR₀. Bien entendu, si l'on est tout à fait formel, le système ATR₀,
appliqué à la formule $\theta(x, X) = \Phi_x^X(x) \downarrow$, montre l'existence des ensembles
$\emptyset', \emptyset'', (\emptyset' \oplus \emptyset'')'$, ...,

à la place de $\emptyset'$, $\emptyset''$, $\emptyset'''$. Mais, on montre aisément par induction dans $\mathcal{ACA}_0$
que chaque $H_a$ est many-one réductible à l'ensemble $Y_a = \Theta(\bigoplus_{b<a} Y_b)$,
où $\Theta$ est l'opérateur induit par la formule $\theta(x, X) = \Phi_x^X(x) \downarrow$. Réciproque-
ment il est possible de montrer toujours par induction dans $\mathcal{ACA}_0$ que
les ensembles définissables par récursion transfinie sont tous calculables
par une certaine itération transfinie du saut. Tout cela nous amène à la
proposition suivante.

**Proposition 2.1.** Dans $\mathcal{ACA}_0$, le système $\mathrm{ATR}_0$ est équivalent à l'énoncé suivant : « Pour tout $X$ et pour tout $a \in \mathbb{N}$, si $L_{\mathcal{O}}(a, X)$ et $W_{\mathcal{O}}(a, X)$, alors il existe un ensemble $Y$ tel que $\mathcal{P}(a, X, Y)$. »

Le lecteur pourra en trouver une preuve détaillée dans [203]. En ce qui concerne $\Pi_1^1-\mathrm{CA}_0$, la preuve que tout ensemble $\Pi_1^1$ est many-one réductible à $\mathcal{O}$ se fait sans problème dans $\mathrm{ACA}_0$, et l'on a donc là aussi une cáractérisation calculatoire de $\Pi_1^1-\mathrm{CA}_0$.

**Proposition 2.2.** Dans $\mathrm{ACA}_0$, le système $\Pi_1^1-\mathrm{CA}_0$ est équivalent à l'énoncé suivant : « Pour tout $X$, l'ensemble $\{a \in \mathbb{N} : L_{\mathcal{O}}(a, X) \text{ et } W_{\mathcal{O}}(a, X)\}$ existe. »

En particulier, dans chacun des deux cas précédents, le prédicat $W_O(a, X)$ équivalent à : « $\forall B \subseteq \{b : b <_o^X a\}$, si $B$ est non vide, alors $B$ contient un plus petit élément pour $<_o^X$ » doit être interprété dans le modèle, et donc avec la quantification $\forall B$ faite dans le modèle. Ainsi, il se pourrait que $a$ ne soit pas réellement le code d'un ordre bien fondé, mais qu'aucun sous-ensemble $B \subseteq \{b : b <_o^X a\}$ sans plus petit élément n'appartiennent au modèle, et donc que du point de vue du modèle — qui n'a pas assez d'ensembles pour détecter tout ce qui est mal fondé — $a$ soit bien fondé.

Nous allons voir dans la prochaine section une conséquence de ces considéra-
tions : HYP n'est pas un modèle d'ATR₀.

3. HYP n'est pas modèle de ATR₀

Les ensembles hyperarithmétiques sont exactement ceux qui peuvent être
obtenus par récursion transfinie d'un opérateur arithmétique le long d'un
bon ordre calculable.
En particulier, tout $\omega$-modèle de $\mathrm{ATR}_0$ contient tous les ensembles hyperarithmétiques, et l'on pourrait à première vue conjecturer que HYP forme un modèle de $\mathrm{ATR}_0$. Nous allons cependant montrer que ce n'est pas le cas, et que certains $\omega$-modèles de $\mathrm{ATR}_0$ possèdent nécessairement des ordres qui semblent être des bons ordres du point de vue du modèle, mais n'en sont pas en absolu. Les axiomes d'ATR₀ vont donc autoriser l'itération d'opérations arithmétiques le long de ces mauvais ordres, et ainsi impliquer l'existence d'ensembles non hyperarithmétiques. Nous introduisons pour cela la notion de pseudo-bon ordre, c'est-à-dire des ordres qui seraient considérés comme des bons ordres dans le modèle HYP.

**Définition 3.1.** Soit $X \in 2^\mathbb{N}$. On dit que $a$ est un $X$-pseudo bon ordre si $L_O(a, X)$ et si tout sous-ensemble $\Delta_1^1(X)$ de $\{b : b <_o a\}$ possède un plus petit élément. ◇

**Notation**

On note $\mathrm{PBO}^X \subseteq \mathbb{N}$ l'ensemble des $X$-pseudos bons ordres, et l'on note PBO l'ensemble des pseudos bons ordres sans relativisation.

Notons que l'on a $\mathcal{O}^X \subseteq \mathrm{PBO}^X$ pour tout $X$.

**Proposition 3.2.** Pour tout $X$, l'ensemble $\mathrm{PBO}^X$ est $\Sigma_1^1(X)$.

PREUVE. On a $a \in \mathrm{PBO}^X$ si, et seulement si,

$$ \forall n \in \mathbb{N} \ n \notin \mathcal{O}^X \lor \exists Y \left( \mathcal{P}(n, X, Y) \land \begin{array}{l} Y \text{ ne calcule pas de sous-ensemble de } \{b : b <_o a\} \end{array} \right), $$

ce qui est bien un prédicat $\Sigma_1^1(X)$.

Le théorème suivant dû à Harrison, se base sur un simple argument de définissabilité pour montrer l'existence nécessaire de pseudo bons ordres qui ne sont pas des bons ordres, mais le long desquels il existe quand même une hiérarchie de sauts Turing.

**Théorème 3.3 (Harrison [84])**

Pour tout $X$, il existe $a \in \mathrm{PBO}^X \setminus \mathcal{O}^X$ tel qu'il existe $Y$ pour lequel $(a, X, Y) \in \mathcal{P}$.

PREUVE. Soit $X$ un ensemble quelconque. Notons que pour tout $a \in \mathcal{O}^X$ on a bien $L_O(a, X)$ et $\exists Y (a, X, Y) \in \mathcal{P}$. Supposons que cela ne soit le cas pour aucun élément $a \in \mathrm{PBO}^X \setminus \mathcal{O}^X$. Alors, on peut donner la définition $\Sigma_1^1(X)$ de $\mathcal{O}^X$ suivante : $a \in \mathcal{O}^X$ ssi $a \in \mathrm{PBO}^X$ et $\exists Y (a, X, Y) \in \mathcal{P}$. Comme $\mathcal{O}^X$ n'est pas $\Sigma_1^1(X)$, on a là une contradiction. ■
Cela nous amène à la définition suivante.

**Définition 3.4.** Soit $X \in 2^\mathbb{N}$. On dit qu'un code $a$ tel que $L_O(a, X)$ est un support du saut de $X$ si $\{Y : P(a, X, Y)\}$ est non vide. ◇

### Notation

Soit $\text{SUPP}_X \subseteq \mathbb{N}$ l'ensemble des supports du saut de $X$.

Le théorème 3.3 montre donc que l'on a $O^X \subsetneq \text{PBO}^X \cap \text{SUPP}_X$ pour tout ensemble $X$. À quoi ressemble alors un élément $Y$ tel que $(a, X, Y) \in \mathcal{P}$ pour $a \in \text{PBO}^X \setminus O^X$ ? On peut « déplier » $Y$ le long des codes $b <_o a$; soit $Y_b$ l'élément correspondant au code $b$. Si $b = 2^c$, on a alors $Y_b = Y_c'$. Si $b = 3 \times 5^e$, on a alors $Y_b = \bigoplus_n Y_{\Phi_e(n)}$. On voit en particulier que pour tout $b <_o c$, on a $Y_b \leq_T Y_c$. En fait, comme $L_O(a, X)$, alors pour tout $b <_o c <_o a$ on a $2^b \leq_o c$, et donc $Y_b' \leq_T Y_c$. Comme $a \notin O^X$, il doit exister une suite $\dots < a_3 <_o a_2 <_o a_1 <_o a$. Les $Y_{a_n}$, pour $n \in \mathbb{N}$, forment donc une suite descendante dans les sauts Turing, c'est-à-dire que l'on a : $Y_{a_{n+1}}' \leq_T Y_{a_n}$ pour tout $n$. Une telle suite ne peut être hyper-arithmétique, comme le montre le théorème suivant.

### Théorème 3.5 (Enderton, Putnam [56])

Soit une suite $(X_n)_{n \in \mathbb{N}}$ telle que $\forall n, X'_{n+1} \leq_T X_n$. Alors, pour tout $n$, l'ensemble $X_n$ Turing calcule tous les ensembles hyperarithmétiques.

**PREUVE.** Soit $\alpha < \omega_1^{ck}$. Supposons que pour tout $n$ l'ensemble $X_n$ calcule $\emptyset^{(\alpha)}$. Montrons que pour tout $n$ l'ensemble $X_n$ calcule $\emptyset^{(\alpha+1)}$. Fixons $X_n$. Comme $\emptyset^{(\alpha)} \leq_T X_{n+1}$, alors $\emptyset^{(\alpha+1)} \leq_T X'_{n+1}$. Comme $X'_{n+1} \leq_T X_n$, alors $\emptyset^{(\alpha+1)} \leq_T X_n$.

Supposons à présent que pour $\alpha = \sup_n \beta_n$ — pour une suite calculable d'ordinaux $\beta_1 < \beta_2 < \dots$ — on ait $\emptyset^{(\beta_n)} \leq_T X_n$ pour tout $n$. Fixons $X_n$. Notons que $X_{n+2}$ calcule aussi $\emptyset^{(\beta_n)}$ pour tout $\beta_n$. En utilisant $X''_{n+2}$, on peut lister tous les éléments $Y_e$ qui sont calculés par une fonctionnelle $\Phi_e$ totale sur $X_{n+2}$. On peut ensuite décider uniformément en un code de $\beta_n$ en utilisant $Y_e''$ — et donc en utilisant $X''_{n+2}$ — si $Y_e$ est un élément du singleton $\Pi_2^0$ contenant $\emptyset^{(\beta_n)}$. En utilisant $X''_{n+2}$ on peut donc reconstruire petit à petit $\bigoplus_n \emptyset^{(\beta_n)}$. Comme $X''_{n+2} \leq_T X_n$ on en déduit, que $X_n$ calcule $\emptyset^{(\alpha)}$. ■

Le théorème précédent se relativise sans problème à n'importe quel oracle. C'est l'objet du corollaire qui suit.
**Corollaire 3.6**

Soit $X \in 2^N$, et soit $a \in \text{SUPP}_X \setminus \mathcal{O}^X$.

Alors, pour tout $Y \in 2^N$ tel que $\mathcal{P}(a, X, Y)$, l'ensemble $Y$ calcule tous les ensembles hyperarithmétiques en $X$.

PREUVE. Il suffit de remarquer que pour un tel ensemble $Y$ il existe une suite $(Y_n)_{n \in \mathbb{N}}$ telle que $Y'_{n+1} \le T Y_n$ avec $Y_0 = Y$. ■

**Corollaire 3.7 (Enderton, Putnam [56])**

Il existe des ensembles $X$ qui Turing calculent tous les ensembles hyperarithmétiques et avec $\omega_1^X = \omega_1^{ck}$ — en particulier avec $X \not\subseteq_h O$.

PREUVE. Soit $a \in \text{SUPP}_X \setminus \mathcal{O}^X$. Comme la classe $\{Y : \mathcal{P}(a, \emptyset, Y)\}$ est $\Pi_2^0$, et donc $\Sigma_1^1$, elle contient d'après le théorème 30-2.2 un élément $X$ tel que $\omega_1^X = \omega_1^{ck}$. Dans le même temps, $X$ calcule tous les ensembles hyperarithmétiques d'après le corollaire 3.6. ■

Nous avions vu avec le théorème 28-2.1 que pour tout code $a \in \mathcal{O}^X$, la classe $\{Y : \mathcal{P}(a, X, Y)\}$ est un singleton $\Pi_2^0$. La situation est bien différente lorsque $a \in \text{SUPP}_X \setminus \mathcal{O}^X$. Intuitivement, dès lors que $a$ ne code pas pour un ordre bien fondé, il existe une suite infinie décroissante, et il existe de nombreuses possibilités d'itérer le saut Turing le long de cette suite. Le corollaire suivant appuie cette intuition.

**Corollaire 3.8**

Soit $X \in 2^N$, et soit $a \in \text{SUPP}_X \setminus \mathcal{O}^X$. Alors, $\{Y : \mathcal{P}(a, X, Y)\}$ est indénombrable.

PREUVE. Comme la classe $\{Y : \mathcal{P}(a, X, Y)\}$ ne contient que des éléments calculant tous les hyperarithmétiques, elle ne contient donc aucun élément hyperarithmétique. Comme cette classe est $\Sigma_1^1$, elle doit être indénombrable d'après le théorème 30-3.4. ■

**Corollaire 3.9**

La classe HYP n'est pas un modèle de ATR₀.

PREUVE. Soit $X = \emptyset$ et supposons par l'absurde que HYP est un modèle de ATR₀. Au vu du théorème 3.3, il existe un code $a \in \text{PBO}^X \cap \text{SUPP}_X \setminus \mathcal{O}^X$. Comme $a$ est dans $\text{PBO}^X$, du point de vue du modèle HYP, $a$ code bien pour un ordinal. Comme HYP est modèle de ATR₀, il doit forcément exister $Y \in \text{HYP}$ tel que $(a, X, Y) \in \mathcal{P}$. Comme $a \in \text{SUPP}_X$, d'après le théorème 3.5 aucun élément $Y$ tel que $(a, X, Y) \in \mathcal{P}$ n'est hyperarithmétique, ce qui est une contradiction. Donc, HYP n'est pas modèle de ATR₀. ■
# 4. Codes d'ordinaux non standard

L'ensemble PBO \ O est en quelque sorte un ensemble d'ordinaux non standard : il ne s'agit pas de bons ordres, mais il est impossible de s'en apercevoir même avec la puissance de calcul hyperarithmétique. Il s'agit d'une classe d'objets fascinante et qui n'a probablement pas encore révélé tous ses secrets. Voici un petit résumé de ce que l'on a réussi à en observer jusqu'ici.

## Théorème 4.1 (Harrison [84])

Supposons $e \in \text{PBO}^X \setminus \text{O}^X$. Alors, le type d'ordre de $e$ est $\omega_1^X + \omega_1^X \nu + \alpha$, pour $\nu$ le type d'ordre de $\mathbb{Q}$ et $\alpha < \omega_1^X$.

PREUVE. Nous montrons le théorème pour $X = \emptyset$; il se relativise sans problème à n'importe quel ensemble $X$. Soit $e \in \text{PBO} \setminus \mathcal{O}$. Pour $a <_o e$, soient $A_{<a} = \{b : b <_o a\}$ et $A_{>a} = \{b : a <_o b <_o e\}$. Pour $a <_o b <_o e$, soit $A_{[a,b]} = \{c : a <_o c <_o b\}$. Si $A_{[a,b]}$ est bien ordonné, on note $|A_{[a,b]}|$ l'ordinal qui lui correspond.

Fait 1. Soit $a <_o e$ tel que $A_{>a}$ n'est pas bien ordonné pour $<_o$. Montrons que $\omega_1^{ck} = \sup\{|A_{[a,b]}| : b \in A_{>a}\}$ tel que $A_{[a,b]}$ est bien ordonné}.

Supposons que l'ensemble $A_{>a}$ ne soit pas bien ordonné pour $<_o$. Soit alors $\alpha = \sup\{|A_{[a,b]}| : b \in A_{>a}\}$ tel que $A_{[a,b]}$ est bien ordonné}. Notons que l'on a nécessairement $\alpha \le \omega_1^{ck}$, car dans le cas inverse on aurait un élément $b$ tel que $A_{[a,b]}$ est bien ordonné et tel que $|A_{[a,b]}| = \omega_1^{ck}$, ce qui donnerait un calcul de $\omega_1^{ck}$. Montrons que l'on a nécessairement $\alpha = \omega_1^{ck}$. Supposons par l'absurde $\alpha < \omega_1^{ck}$. Les deux ensembles

$$Z = \{b \in A_{>a} : A_{[a,b]} \text{ est bien ordonné}\},$$

$$Z_1 = \{b \in A_{>a} : \text{il existe un morphisme de } |A_{[a,b]}| \text{ vers } \alpha\}$$

sont égaux. L'ensemble $Z_1$ a une définition $\Sigma_1^1$, tandis que l'ensemble $Z$ a une définition $\Pi_1^1$ naturelle, et est donc $\Delta_1^1$. On peut à présent calculer via $Z$ un ensemble mal fondé d'éléments de $A_{>a}$ : il suffit de prendre un élément $c_0$ tel que $A_{[a,c_0]}$ est mal fondé, puis de chercher un élément $c_1 <_o c_0$ tel que $a <_o c_1$ et $c_1 \notin Z$, puis de chercher $c_2 <_o c_1$ tel que $a <_o c_2$ et $c_2 \notin Z$, etc. Comme $Z$ est hyperarithmétique, cela contredit $e \in \text{PBO}$. Donc, $\alpha = \omega_1^{ck}$. Cela termine la preuve du fait 1.

On peut à présent appliquer cela à l'ordinal 1 codant pour le plus petit élément de $e$. On a ainsi

$$\omega_1^{ck} = \sup\{|A_{1,b}| : b \in A_{>1}\} \text{ tel que } A_{1,b} \text{ est bien ordonné}\}.$$

L'ordre de $e$ commence donc par un segment initial bien fondé de taille $\omega_1^{ck}$.
Fait 2. Soit $a <_o e$, Montrons que l'ensemble

$$Z = \{b : A_{[b,a[} \text{ est bien ordonné}\}$$

possède un plus petit élément. Supposons par l'absurde que ce n'est pas le cas. On définit à présent l'ensemble Π₁¹

$$B = \{(n, b) : n, b \in Z \text{ et } b <_o n <_o a\}.$$

En utilisant le théorème 29-4.1 d'uniformisation Π₁¹, soit $g$ une fonction partielle Π₁¹ telle que si $\{b : (n, b) \in B\}$ est non vide, alors $(n, g(n)) \in B$. On définit alors une fonction Π₁¹ totale $f$, avec $f(0)$ un élément de $Z$ quel-conque, puis $f(n+1) = g(f(n))$. On a alors $f(n+1) <_o f(n)$ pour tout $n$. Comme $f$ est totale, elle est donc $\Delta_1^1$ d'après la proposition 29-4.2. Son image est donc $\Delta_1^1$, ce qui contredit $e \in \text{PBO}$. Donc, pour tout $a <_o e$, l'ensemble $Z = \{b : A_{[b,a[} \text{ est bien ordonné}\}$ possède un plus petit élément. Cela prouve le fait 2.

Pour $a <_o e$, soit $b_a$ un tel élément. Si $A_{>b_a}$ est bien ordonné, alors il s'agit d'un ordinal calculable $\alpha$, ce qui correspond au segment final de l'ordre. Si-non, pour tout $a <_o e$, on a $\omega_1^{ck} = \sup_{b \in A} \{|A_{[b,a[} : A_{[b_a,b[} \text{ est bien ordonné}\}$.
Fait 3. Soient $a_1 <_o a_2 < e$, chacun étant les débuts d'une partie bien fondée (c'est-à-dire de la forme $b_a$ pour un certain $a$). Montrons qu'il existe un $c <_o a_2$ tel que $c \notin \{b : A_{[b_a,b[} \text{ est bien ordonné}\}$.

Sachant que $a_1 <_o a_2$ sont les débuts d'une partie bien fondée, on a forcément $a_2 \notin \{b : A_{[a_1,b[} \text{ est bien ordonné}\}$. Alors, de même, on a forcément $c <_o a_2$ tel que $c \notin \{b : A_{[a_1,b[} \text{ est bien ordonné}\}$, car sinon $a_2$ permettrait de calculer $\omega_1^{ck}$ étant donné que $a_1$ démarre une partie bien fondée de taille $\omega_1^{ck}$.

Le fait 1 montre que le type d'ordre de $e$ commence par $\omega_1^{ck}$. Les faits 1 et 2 ensemble montrent que chaque élément est soit dans un sous-ordre de type $\omega_1^{ck}$, soit appartient à la partie finale $\alpha < \omega_1^{ck}$. Enfin, le fait 3 montre qu'entre deux copies de $\omega_1^{ck}$, ou entre une copie de $\omega_1^{ck}$ et $\alpha$, il existe une autre copie de $\omega_1^{ck}$. Le type d'ordre de $e$ est donc $\omega_1^{ck} + \omega_1^{ck}\nu + \alpha$. ■

### Corollaire 4.2 (Feferman et Spector [58])

Il existe un ensemble $O_1 \subseteq O$ qui est $\Pi_1$ et bien ordonné par $<_o$, et dont le supremum est $\omega_1^{ck}$.

PREUVE. Soit $e \in \text{PBO}^X \setminus O^X$. Alors, en reprenant les notations du théorème précédent, on a $O_1 = \{b <_o e : A_{[1,b[} \text{ est bien fondé}\}$. ■

L'ensemble $O_1$ peut être utile pour s'abstraire encore plus des systèmes de codage : au lieu de considérer que l'on travaille avec le code d'un ordinal $\alpha$, on peut alors faire comme si l'on travaillait directement avec l'ordinal $\alpha$ lui-même, via son unique code dans $O_1$. Nous voyons à présent un
théorème remarquable sur la relation entre les ensembles PBO<sup>X</sup> et SUPP<sup>X</sup>. Nous allons voir en particulier que si un ordre mal fondé est le support d'une hiérarchie de saut, alors nécessairement cet ordre ne contient pas de sous-ensemble hyperarithmétique sans plus petit élément. En d'autres termes, SUPP<sup>X</sup> ⊆ PBO<sup>X</sup>. Nous utilisons pour cela le lemme suivant.

**Lemme 4.3 (Steel).** Soit $\Phi$ une fonctionnelle calculable. Alors, il n'existe aucune suite $(X_n)_{n\in\mathbb{N}}$ telle que $\Phi(X_n) = X'_{n+1}$ pour tout $n$. ★

**PREUVE.** Soit $(X_n)_{n\in\mathbb{N}}$ une suite telle que $\Phi(X_n) = X'_{n+1}$ pour tout $n$. On construit facilement une fonctionnelle $\Psi$ telle que $\Psi(X_n, m) = X'_{n+m}$ pour tous $n, m \in \mathbb{N}$ avec $m > 0$. En utilisant le théorème du point fixe, soit $e$ le code d'un programme qui s'arrête sur l'oracle $X$ si $\exists m > 0 e \notin \Psi(X, m)$. Supposons $e \notin X'_0$. Alors, pour tout $m > 0$ on a $e \in \Psi(X_0, m)$ c'est-à-dire $e \in X'_m$ pour tout $m > 0$. En particulier, on a $e \in X'_1$, et donc $\exists k > 0$ tel que $e \notin \Psi(X_1, k)$. On a donc $e \notin X'_{1+k}$, ce qui contredit $e \in X'_m$ pour tout $m > 0$.

Supposons à présent $e \in X'_0$. Alors, $\exists m > 0$ tel que $e \notin \Psi(X_0, m)$ et donc tel que $e \notin X'_m$. On peut donc répéter l'argument précédent mais avec la suite $Y_0 = X_m, Y_1 = X_{m+1}, \dots$ On aboutit dans tous les cas à une contradiction. ■

On peut à présent montrer le résultat attendu.

**Théorème 4.4 (Friedman [68])**

Pour tout oracle $X$, on a $\text{SUPP}^X \subseteq \text{PBO}^X$.

**PREUVE.** On montre le résultat pour $X = \emptyset$, la preuve se relativisant sans problème à tout oracle $X$. Supposons que la classe $\{Y : \mathcal{P}(e, \emptyset, Y)\}$ soit non vide pour $e \notin \mathcal{O}$, et soit $Y$ l'un de ses membres. Supposons par l'absurde qu'il existe un ensemble hyperarithmétique $Z \subseteq \{a : a <_o e\}$ ne possédant pas de plus petit élément. On va alors construire une suite d'ensembles $(X_n)_{n\in\mathbb{N}}$ et une fonctionnelle $\Phi$ telle que $\Phi(X_n'') = X'''_{n+1}$. Il suffira d'appliquer le lemme 4.3 à la suite $(X_n'')_{n\in\mathbb{N}}$ pour obtenir une contradiction.

On peut déplier l'ensemble $Y$ le long des codes $a <_o e$. Soit $Y_a$ l'ensemble correspondant au code $a$. D'après le théorème 3.5, chaque ensemble $Y_a$ pour $a \in Z$ calcule tous les hyperarithmétique,s et donc en particulier $Z$. Soit $a \in \mathcal{O}$ tel que $\Psi(H_a) = Z$ pour une fonctionnelle $\Psi$. La fonctionnelle $\Phi$ procède comme suit : sur un oracle de la forme $(1^b 0 Y_b)''$ pour $b \in Z$, la fonctionnelle liste toutes les fonctions totales pour $Y_b$ et regarde si le résultat du calcul est bien un membre de la classe $\{X : \mathcal{P}(a, \emptyset, X)\}$, auquel cas il s'agit nécessairement de $H_a$. Une fois $H_a$ identifié, la fonctionnelle s'en sert pour calculer $Z$, puis pour chercher $c \in Z$ avec $c <_o b$ et tel que $2^c \leqslant_o b$.
Une fois cet élément trouvé, la fonctionnelle peut alors calculer $Y_{2^c} = Y'_c$ à partir de $Y_b$, puis calculer $(1^c 0 Y_c)' \leq_T Y'_c \leq_T Y_b$ puis finalement ren-voyer $(1^c 0 Y_c)'''$ en utilisant $Y_b''$. ■

A-t-on égalité entre SUPP<sup>X</sup> et PBO<sup>X</sup>? Friedman [66] a montré que ce n'était pas le cas, en construisant un élément $e \in \text{PBO} \setminus \text{SUPP}$.

**Théorème 4.5 (Friedman)**

Pour tout oracle X, on a $\text{SUPP}^X \subsetneq \text{PBO}^X$.

PREUVE. On montre le théorème pour $X = \emptyset$, la preuve se relativisant sans problème à tout oracle X. Soit $f$ une fonction totale calculable, définie à l'aide du théorème 27-5.10 et de la proposition 27-5.18 telle que $e \in \mathcal{T}$ ssi $f(e) \in \mathcal{O}$. Soit $g$ la fonction totale calculable qui sur le code $e$ d'un arbre c. e. $T_e \subseteq \mathbb{N}^<\mathbb{N}$ renvoie le code de l'arbre $T_{g(e)}$ de l'espace de Baire qui encode les éléments de la classe $\Pi_2^0$ suivante :

$$ \{X : L_{\mathcal{O}}(f(e), \emptyset) \text{ et } (f(e), \emptyset, X) \in \mathcal{P}\}. $$

Expliquons un peu plus concrètement l'arbre $T_{g(e)}$ : étant donné $\bigcap_n U_n$ une description $\Pi_2^0$ de la classe $\{X : (f(e), \emptyset, X) \in \mathcal{P}\}$ et $\bigcap_n A_n$ une description $\Pi_2^0$ de l'ensemble $\{a : L_{\mathcal{O}}(a, \emptyset)\}$, on procède ainsi : supposons un nœud $\rho$ de taille $n + 1$ énuméré dans $T_{g(e)}$ et correspondant à des chaînes $\sigma_0 < \dots < \sigma_n$, où $\sigma_i$ est énuméré dans $U_i$. Avant d'énumérer des fils de $\rho$ dans $T_{g(e)}$, on cherche si $f(e) \in A_{n+1}$. Si cela est bien vérifié, on énumère $\rho m$ dans $T_{g(e)}$ pour tout $m$ correspondant à une extension $\sigma_{n+1} \supseteq \sigma_n$ avec $\sigma_{n+1}$ énuméré dans $U_{n+1}$. Il est clair que

$$ L_{\mathcal{O}}(f(e), \emptyset) \text{ et } \{X : (f(e), \emptyset, X) \in \mathcal{P}\} $$

est non vide si, et seulement si, l'arbre $T_{g(e)}$ a un chemin infini, auquel cas les chemins infinis de $T_{g(e)}$ sont exactement les encodages des éléments de $\{X : (f(e), \emptyset, X) \in \mathcal{P}\}$.

À l'aide du théorème du point fixe, soit à présent $e$ tel que $T_e = T_{g(e)}$. Supposons par l'absurde que $T_e$ ne contienne pas de chemin infini. Alors, $f(e) \in \mathcal{O}$ et dans ce cas l'arbre $T_{g(e)}$ doit contenir un chemin infini, ce qui est une contradiction. Donc, $T_e$ est mal fondé. Comme $T_{g(e)}$ est mal fondé, on en déduit $L_{\mathcal{O}}(f(e), \emptyset)$ et $\{X : (f(e), \emptyset, X) \in \mathcal{P}\}$ non vide, ce qui implique $f(e) \in \text{SUPP} \setminus \mathcal{O}$. En particulier, $f(e) \in \text{PBO}$. Notons que tout élément X tel que $(f(e), \emptyset, X) \in \mathcal{P}$ calcule un élément de $[T_e]$ — sa propre représentation —, et donc calcule un sous-ensemble de $Z_X \subseteq \{a : a <_o f(e)\}$ qui n'a pas de plus petit élément. Considèrons à présent l'ordre $f(e) +_o f(e)$. La preuve que l'on a $L_{\mathcal{O}}(f(e) +_o f(e), \emptyset)$ est laissée aux bons soins du lecteur. Tout élément $a <_o f(e)$ possède son analogue $f(e) +_o a$ qui est tel que $f(e) <_o f(e) +_o a <_o f(e) +_o f(e)$.
Réciproquement, pour tout élément $a$ tel que $f(e) <_o a <_o f(e) +_o f(e)$, on peut chercher un élément $b <_o a$ tel que $a = f(e) +_o b$. Il est clair que $f(e) +_o f(e) \in \text{PBO} : \text{en effet, tout sous-ensemble } \Delta_1^1$

$$Z \subseteq \{a : a <_o f(e) +_o f(e)\}$$

et sans plus petit élément est cofini dans $\{a : a <_o f(e)\}$ — auquel cas $f(e) \notin \text{PBO}$— ou cofini dans $\{a : a <_o f(e) +_o f(e)\}$ auquel cas $Z$ peut calculer son analogue sous $f(e)$, et là encore $f(e) \notin \text{PBO}$. On prétend qu’en revanche $f(e) +_o f(e) \notin \text{SUPP}$. Supposons par l’absurde qu’il existe un ensemble $Y$ tel que $(f(e) +_o f(e), \emptyset, Y) \in \mathcal{P}$. On peut alors « déplier » $Y$ le long des codes de pseudo ordinaux et pour $a <_o f(e) +_o f(e)$ on note $Y_a$ l’ensemble correspondant à $a$ dans ce dépliage. Notons que $Y_{f(e)}$ — qui est tel que $(f(e), \emptyset, Y_{f(e)}) \in \mathcal{P}$ — calcule l’ensemble $Z_{Y_{f(e)}} \subseteq \{a : a <_o f(e)\}$ sans plus petit élément, et donc un ensemble $Z \subseteq \{a : f(e) <_o a <_o f(e) +_o f(e)\}$ sans plus petit élément. On va alors définir une fonction calculable $\Phi$ et une suite $(X_n)_{n \in \mathbb{N}}$ qui seront telles que $\Phi(X_n) = X'_n$, en contradiction avec le lemme 4.3. La suite $(X_n)_{n \in \mathbb{N}}$ est simplement donnée par $X_n = 1^{a_n} 0 Y_{a_n}$ pour une suite $\cdots < a_3 <_o a_2 < a_1 \in Z$. La fonctionnelle $\Phi$ agit comme suit sur l’ensemble $1^{a_n} 0 Y_{a_n}$ avec $f(e) <_o a_n$ et $a_n \in Z$ : elle calcule $Y_{f(e)}$ à partir de $Y_{a_n}$ et de la connaissance de $a_n$, puis elle calcule $Z$ à partir de $Y_{f(e)}$ et enfin elle cherche $a_{n+1} \in Z$ avec $a_{n+1} <_o a_n$ tel que $2^{a_{n+1}} \leq_o a_n$. Notons que l’on a $Y_{2^{a_{n+1}}} = Y'_{a_{n+1}}$. À partir de $Y_{a_n}$, la fonctionnelle peut donc calculer $Y'_{a_{n+1}}$ puis calculer et renvoyer l’ensemble $(1^{(a_{n+1})} 0 Y_{a_{n+1}})'$. On a alors une contradiction avec le lemme 4.3. Il s’ensuit que notre hypothèse est fausse, et donc que $f(e) +_o f(e) \notin \text{SUPP}$. ■

Nous terminons cette section par un théorème d’Harrington : PBO et SUPP sont tous les deux $\Sigma_1^1$-complets.

**Théorème 4.6 (Harrington (non publié))**

Soit $A$ un ensemble $\Sigma_1^1$ tel que $O \subseteq A \subseteq \text{PBO}$. Alors, $A$ est $\Sigma_1^1$-complet.

PREUVE. Nous établissons d'abord le résultat pour l'ensemble $\mathcal{T}$ des codes c. e. d'arbres bien fondés de l'espace de Baire, et pour l'ensemble PBT des codes c. e. d'arbres sans chemins infinis hyperarithmétiques.

On suppose donc que $A$, ensemble $\Sigma_1^1$, vérifie $\mathcal{T} \subseteq A \subseteq \text{PBT}$. Montrons alors que l’on peut réduire par une réduction many-one l’ensemble des codes c. e. d’arbres mal fondés à $A$. Comme $A$ est $\Sigma_1^1$, il existe une fonction $f$ telle que $n \in A$ ssi $f(n)$ est un code d’arbre c. e. mal fondé. En utilisant le théorème du point fixe, on définit une fonction $g$ telle que pour tout $e$, la valeur $g(e)$ est l’arbre c. e. des morphismes (voir la définition 29-5.6) de l’arbre c. e. codé par $e$ vers celui codé par $f(g(e))$.
Montrons d'abord que $g(e)$ code pour tout $e$ pour un arbre mal fondé. Supposons par l'absurde que $g(e)$ code pour un arbre bien fondé. Alors, $g(e)$ appartient à $A$, et donc $f(g(e))$ code pour un arbre mal fondé. Il existe alors nécessairement un morphisme de l'arbre codé par $e$ vers celui codé par $f(g(e))$, et donc $g(e)$ — qui code pour l'ensemble de ces morphismes — doit être mal fondé.

Montrons à présent que $g$ est la réduction attendue, c'est-à-dire telle que $e$ code pour un arbre mal fondé ssi $g(e) \in A$. Supposons que $e$ code pour un arbre mal fondé. Comme $g(e)$ code toujours pour un arbre mal fondé, il existe un morphisme de l'arbre codé par $e$ vers celui codé par $f(g(e))$. Donc, $f(g(e))$ code aussi pour un arbre mal fondé, et donc $g(e) \in A$ par définition de $f$. Supposons à présent que $e$ code pour un arbre bien fondé. Soit $\alpha < \omega_1^{ck}$ la hauteur de cet arbre. Nous savons qu'il existe un morphisme de l'arbre codé par $e$ vers celui codé par $f(g(e))$, car $g(e)$ code pour un arbre mal fondé. D'après la proposition 28-1.7, l'ensemble $\emptyset^{(\alpha+1)}$ peut obtenir uniformément en $\beta \le \alpha$ l'ensemble $T_{<\beta}$ des codes d'arbre c. e. bien fondés et de hauteur inférieure à $\beta$. On peut alors à l'aide de $\emptyset^{(\alpha+1)}$ calculer un tel morphisme : il suffit d'envoyer des nœuds commençant des arbres de hauteurs $\beta$ vers des nœuds de même taille commençant des arbres qui ne sont pas de hauteur inférieure à $\beta$ (tout en restant cohérent avec la partie du morphisme déjà définie). La connaissance de l'ensemble des codes d'arbres de hauteurs $\beta \le \alpha$ est donc suffisante. L'arbre codé par $g(e)$ contient ainsi des chemins infinis hyarithmétiques, si bien qu'il n'appartient alors pas à PBO, et donc pas non plus à $A$.

Pour obtenir le résultat pour un $A$ ensemble $\Sigma_1^1$, avec $O \subseteq A \subseteq \text{PBO}$, il suffit à présent de considérer avec l'aide du théorème 27-5.10 et de la proposition 27-5.18 une fonction calculable $f$ telle que $e$ est un code c. e. pour un arbre bien fondé — c'est-à-dire $e \in T — \text{ssi } f(e) \in O$, et de considérer l'ensemble $B = \{e \in N : f(e) \in A\}$. Un tel ensemble est $\Sigma_1^1$. Il est clair par définition de $f$ que $T \subseteq B$ puisque $O \subseteq A$. De plus, on montre facilement que si $e$ code pour un arbre avec un chemin hyperarithmétique, alors si l'on a $L_\infty(f(e), \emptyset)$, l'ensemble $\{a : , a <_o f(e)\}$ contient un sous-ensemble hyperarithmétique qui n'a pas de plus petit élément. On a donc $e \notin \text{PBT implique } f(e) \notin \text{PBO}$, donc $f(e) \in \text{PBO implique } e \in \text{PBT}$. Comme $A \subseteq \text{PBO}$, alors $B \subseteq \text{PBT}$. On réduit alors tout ensemble $\Sigma_1^1$ à $B$, qui lui-même se réduit à $A$ via la fonction $f$. ■

**Corollaire 4.7**

Les ensembles PBO et SUPP sont $\Sigma_1^1$-complets.

PREUVE. Nous avons vu avec la proposition 3.2 que l'ensemble PBO est $\Sigma_1^1$. L'ensemble SUPP est également $\Sigma_1^1 : a \in \text{SUPP ssi } \exists Y P(a, \emptyset, Y)$. Ils sont donc tous les deux $\Sigma_1^1$-complets. ■
# 5. Séparation entre ATR₀ et Π₁⁻¹-CA₀

Si certains modèles d'ATR₀ et de Π₁⁻¹-CA₀ peuvent être complexes à apprê-
hender en raison d'ordres qu'ils ne peuvent détecter comme étant mal
fondés, il ne doit pas forcément en être ainsi. On peut tout à fait définir
des modèles qui reflètent bien ce qu'il se passe à l'extérieur d'eux-mêmes.

**Définition 5.1.** Soit $\mathcal{M} \subseteq 2^\mathbb{N}$. Alors, $\mathcal{M}$ est un $\beta$-modèle si pour tout $X$ dans $\mathcal{M}$ et pour tout $A$ une classe $\Sigma_1^1(X)$ non vide, il existe $Y \in A \cap \mathcal{M}$. $\diamond$

Notons que l'on suppose implicitement que les $\beta$-modèles sont toujours
des $\omega$-modèles, pour lesquels on ne spécifie donc que la partie du second
ordre.

**Proposition 5.2.** Soit $\mathcal{M}$ un $\beta$-modèle clos par jointure Turing. Alors, $\mathcal{M}$ est un modèle de ATR$_0$. $\star$

PREUVE. Pour chaque $X \in \mathcal{M}$ et chaque $Y \leq_T X$, l'élément $Y$ est un singleton $\Pi_1^0(X)$, et donc $Y \in \mathcal{M}$. Ainsi, $\mathcal{M}$ est clos par jointure et par réduction Turing, donc est un idéal Turing. On a donc $\mathcal{M} \models \text{RCA}_0$. Par ailleurs, pour tout $X \in \mathcal{M}$ la classe $\{X'\}$ est $\Sigma_1^1(X)$, donc $X' \in \mathcal{M}$. Ainsi, $\mathcal{M} \models \text{ACA}_0$.

Par la proposition 2.1, il suffit de montrer que si $X \in \mathcal{M}$ et $a \in \mathbb{N}$ est tel que $L_{\mathcal{O}}(a, X)$ et $W_{\mathcal{O}}(a, X)$, alors il existe un $Y \in \mathcal{M}$ tel que $(a, X, Y) \in \mathcal{P}$. Soit $X \in \mathcal{M}$, et soit $a \in \mathbb{N}$ tel que $L_{\mathcal{O}}(a, X)$ et $W_{\mathcal{O}}(a, X)$. Montrons alors que $a \in \mathcal{O}^X$. Si $a \notin \mathcal{O}^X$, la classe des sous-ensembles de $\{b : b <_o a\}$ sans plus petit élément est en effet un $\Sigma_1^1(X)$ non vide, et il existe donc un témoin de ce fait dans $\mathcal{M}$, donc $\mathcal{M} \not\models W_{\mathcal{O}}(a, X)$, contradiction. Si $a \in \mathcal{O}^X$, la classe $\{Y : (a, X, Y) \in \mathcal{P}\}$ est alors le singleton $\Pi_2^0 H_a^X$, et donc $H_a^X \in \mathcal{M}$, car $\mathcal{M}$ est un $\beta$-modèle. $\blacksquare$

**Proposition 5.3.** Il existe un $\beta$-modèle minimal de $\Pi_1^1$-CA$_0$ : la classe des éléments Turing réductibles à une itération finie de l'hypersaut. $\star$

PREUVE. Par la proposition 2.2, n'importe lequel des $\beta$-modèles de $\Pi_1^1$-CA$_0$ contient le vrai $\mathcal{O}$ de Kleene, et par conséquent $\mathcal{O}^{\mathcal{O}}$, $\mathcal{O}^{\mathcal{O}^{\mathcal{O}}}$, et ainsi de suite. Comme il est clos par réduction Turing, il contient tous les ensembles Turing réductibles à une itération finie de l'hypersaut.

Réciproquement, soit $\mathcal{M}$ le modèle des éléments Turing réductibles à une itération finie de l'hypersaut. Montrons alors que $\mathcal{M}$ est un idéal Turing. Pour tout $X \in \mathcal{M}$, il existe un $n$ tel que $X \leq_T J_n$, où $J_n$ est la $n$-ième itération de l'hypersaut. Si $Y \leq_T X$, alors $Y \leq_T J_n$, donc $Y \in \mathcal{M}$. De plus, pour tous $X, Y \in \mathcal{M}$, on a $X \leq_T J_n$ et $Y \leq_T J_m$ pour $n, m \in \mathbb{N}$, et donc $X \oplus Y \leq_T J_{\max(n,m)}$. Ainsi, $X \oplus Y \in \mathcal{M}$. On a donc, $\mathcal{M} \models \text{RCA}_0$.
Montrons que pour tout $X \in \mathcal{M}, \mathcal{O}^X \in \mathcal{M}$. Par définition de $\mathcal{M}$, il existe un $n \in \mathbb{N}$ tel que $X \leq_T J_n$. En particulier, $\mathcal{O}^X \leq_T J_{n+1}$, et donc $\mathcal{O}^X \in \mathcal{M}$. Ainsi, $\mathcal{M} = \Pi_1^1-\text{CA}_0$. Notons au passage que $\mathcal{M}$ est un $\beta$-modèle, car pour une classe $\Sigma_1^1(X)$ non vide, un élément de cette classe est d'après le théorème 30-2.2 calculable à l'aide de $\mathcal{O}^X$, et donc appartient à $\mathcal{M}$. ■

On montre à présent notre théorème de séparation entre ATR₀ et Π₁¹-CA₀.

### Théorème 5.4

Il existe des $\beta$-modèles d'ATR₀ ne contenant pas $\mathcal{O}$.

PREUVE. Soit $e_1, e_2, \dots$ une suite, où $e_i$ est un code de classe $\Sigma_1^1$ et où chaque code possible est répété une infinité de fois. À l'étape $n$, supposons que l'on dispose de $n$ ensembles $X_1, \dots, X_n$ avec $\mathcal{O}^{X_1 \oplus \dots \oplus X_n} \leq_T \mathcal{O}$ et tels que $X_{i+1}$ est un élément de la classe $\Sigma_1^1(X_1 \oplus \dots \oplus X_i)$ de code $e_{i+1}$ pour tout $i < n$, si cette classe est non vide. On considère alors la classe $\Sigma_1^1(X_1 \oplus \dots \oplus X_n)$ de code $e_{n+1}$. Si celle-ci est non vide, on définit à l'aide du théorème 30-2.2 $X_{n+1}$ comme étant un élément de cette classe tel que $\mathcal{O}^{X_1 \oplus \dots \oplus X_n \oplus X_{n+1}} \leq_T \mathcal{O}$. Si cette classe est vide, on définit $X_{n+1} = \emptyset$. Notre modèle $\mathcal{M}$ est donné par $\{X_n : n \in \mathbb{N}\}$.

Il est clair que $\mathcal{M}$ ne contient que des éléments $X$ tels que $\mathcal{O}^X \leq_T \mathcal{O}$, et ne contient donc pas $\mathcal{O}$. De plus, $\mathcal{M}$ est un $\beta$-modèle, car pour $X_n \in \mathcal{M}$ et une classe $\Sigma_1^1(X_n)$, il existe un code $e_m$ pour $m > n$ tel que $e_m$ correspond avec un oracle $X_1 \oplus \dots \oplus X_n \oplus \dots \oplus X_{m-1}$ à la classe $\Sigma_1^1(X_n)$ (et ce indépendamment de $m$). Pour un tel $e_m$, on aura donc un élément $X_m$ de cette classe dans notre modèle $\mathcal{M}$. Enfin, $\mathcal{M}$ est clos par jointure Turing, car pour tous $n_1, n_2$ il existe un code $e_m$ pour $m > n_1, n_2$ tel que $X_{n_1} \oplus X_{n_2}$ est le seul élément de la classe $\Sigma_1^1(X_1 \oplus \dots \oplus X_{n_1} \oplus \dots \oplus X_{n_2} \oplus \dots \oplus X_{m-1})$ de code $e_m$. D'après la proposition 5.2, $\mathcal{M}$ est donc un $\beta$-modèle de ATR₀. ■

### Corollaire 5.5

Le système ATR₀ n'implique pas $\Pi_1^1-\text{CA}_0$.

PREUVE. On a un $\beta$-modèle d'ATR₀ ne contenant pas $\mathcal{O}$. Comme il s'agit d'un $\beta$-modèle, il ne peut être modèle de $\Pi_1^1-\text{CA}_0$, car tout $\beta$-modèle de $\Pi_1^1-\text{CA}_0$ contient $\mathcal{O}$. ■

Il est tentant de faire un parallèle entre les systèmes ATR₀ et WKL₀ ainsi qu'entre les systèmes ACA₀ et Π₁¹-CA₀. Là où ACA₀ affirme l'existence du saut Turing de tout ensemble, Π₁¹-CA₀ asserte l'existence de l'hypersaut Turing pour tout ensemble.
Là où l'on sépare WKL₀ de ACA₀ en construisant un modèle de WKL₀ ne contenant pas le saut, on sépare ATR₀ de Π₁⁻CA₀ en construisant un β-modèle d'ATR₀ ne contenant pas l'hypersaut.

La correspondance a toutefois ses limites. Il est ainsi possible de construire un modèle dénombrable de WKL₀ dont la représentation est low, mais il est impossible de construire un β-modèle dénombrable d'ATR₀ qui soit hyperlow.

**Définition 5.6.** Un ensemble $M \subseteq \mathbb{N}$ est un code d'une classe dénombrable $\mathcal{M} = \{X_n : n \in \mathbb{N}\}$ si $M = \bigoplus_n X_n$. ◇

Notons qu'une même classe dénombrable possède une infinité de codes, car l'ordre de ses éléments n'est pas fixé.

**Théorème 5.7**

Soit $\mathcal{M}$ un β-modèle dénombrable du système ATR₀ codé par $M$. Alors, $\mathcal{O} \leq_T \mathcal{M}''$.

**PREUVE.** Il est facile de donner une définition arithmétique en $\mathcal{M}$, de l'ensemble des codes d'arbres mal fondés. Il s'agit de l'ensemble des codes $e$ codant pour un arbre $T_e$ tel qu'il existe $X \in \mathcal{M}$ appartenant à $[T_e]$. La quantification existentielle du second ordre sur $X$ se transforme en quantification existentielle du premier ordre $M$. Le prédicat $X \in [T_e]$ est quant à lui $\Pi_1^0(X)$, et donc $\Pi_1^0(M)$. Ainsi, l'ensemble des codes d'arbres mal fondés est calculable en $M''$. On en déduit $\mathcal{O} \leq_T \mathcal{M}''$. ■

Nous terminons ce chapitre en montrant finalement que les modèles de ATR₀ ou Π₁⁻CA₀ ne sont pas nécessairement des β-modèles.

**Théorème 5.8**

Il existe des modèles de Π₁⁻CA₀ ne contenant pas $\mathcal{O}$.

**PREUVE.** Il suffit de considérer la classe des ensembles $X$ qui codent pour des modèles dénombrables de Π₁⁻CA₀. Les quantifications universelles ou existentielles du second ordre se transforment en quantifications du premier ordre sur les éléments $X_1 \oplus X_2 \oplus \dots$ qui sont codés par $X$. Il s'agit donc d'une classe arithmétique, et en particulier $\Sigma_1^1$. Comme il existe des modèles dénombrables de Π₁⁻CA₀, cette classe est non vide. D'après le théorème 30-2.2, elle contient un élément $X$ tel que $\omega_1^X = \omega_1^{ck}$. Il s'ensuit que $X$ code pour un modèle dénombrable de Π₁⁻CA₀ ne pouvant pas contenir $\mathcal{O}$.
**Corollaire 5.9**

Il existe des modèles de Π₁¹-CA₀ — et donc aussi de ATR₀ — qui ne sont pas des β-modèles.

PREUVE. Le modèle du théorème précédent ne peut pas être un $\beta$-modèle, d'après la proposition 5.3. ■
Annexe A

Correction des exercices

Chapitre 2

**Solution 3.4.** On définit $g : \mathbb{N} \to \mathbb{N}$ de la manière suivante : $g(0)$ est le plus petit entier $x$ tel que $f(x) \in B$. Supposons $g(n)$ défini. Alors, on définit $g(n+1)$ comme étant le plus petit entier $x$ strictement plus grand que $g(n)$ et tel que $f(x) \in B$. Comme $B$ est infini alors $g$ est bien défini partout. On définit alors

$$h(n) = f(g(n)).$$

Par construction, $h$ est bijective.

**Solution 3.7.**

1. Montrons que $(x_1, y_1) \neq (x_2, y_2)$ implique $\alpha_2(x_1, y_1) \neq \alpha_2(x_2, y_2)$. Supposons $(x_1, y_1) \neq (x_2, y_2)$. Supposons d'abord que $x_1 + y_1 < x_2 + y_2$ (le cas $x_2 + y_2 < x_1 + y_1$ étant symétrique). Alors,

$$ 
\begin{array}{lclcl}
 & (\sum_{i=0}^{x_1+y_1} i) + x_1 + y_1 + 1 & \le & \sum_{i=0}^{x_2+y_2} i \\
\rightarrow & y_1 + \sum_{i=0}^{x_1+y_1} i & < & \sum_{i=0}^{x_2+y_2} i \\
\rightarrow & y_1 + \sum_{i=0}^{x_1+y_1} i & < & y_2 + \sum_{i=0}^{x_2+y_2} i \\
\rightarrow & \alpha_2(x_1, y_1) & < & \alpha_2(x_2, y_2).
\end{array}
$$

Supposons à présent que $x_1 + y_1 = x_2 + y_2$. Notez que l'on a alors $y_1 = y_2$ implique $x_1 = x_2$. Comme $(x_1, y_1) \neq (x_2, y_2)$, alors nécessairement $y_1 \neq y_2$. On a donc :

$$ 
\begin{array}{rclcl}
 & (\sum_{i=0}^{x_1+y_1} i) & = & \sum_{i=0}^{x_2+y_2} i \\
\rightarrow & y_1 + (\sum_{i=0}^{x_1+y_1} i) & \neq & y_2 + \sum_{i=0}^{x_2+y_2} i \\
\rightarrow & \alpha_2(x_1, y_1) & \neq & \alpha_2(x_2, y_2).
\end{array}
$$
Montrons à présent que $\alpha_2$ est surjective. Pour cela, montrons d'abord que :

$$ 
\begin{align*} 
\alpha_2(x-1, y+1) - \alpha_2(x, y) &= 1 \quad \text{pour } x > 0 \\ 
\alpha_2(y+1, 0) - \alpha_2(0, y) &= 1. 
\end{align*} 
$$

Dans le premier cas, on a :

$$ 
\begin{align*} 
\alpha_2(x-1, y+1) - \alpha_2(x, y) &= (y+1 + \sum_{i=0}^{x-1+y+1} i) - (y + \sum_{i=0}^{x+y} i) \\ 
&= (y+1 + \sum_{i=0}^{x+y} i) - (y + \sum_{i=0}^{x+y} i) \\ 
&= 1. 
\end{align*} 
$$

Dans le deuxième cas, on a :

$$ 
\begin{align*} 
\alpha_2(y+1, 0) - \alpha_2(0, y) &= (\sum_{i=0}^{y+1} i) - (y + \sum_{i=0}^{y} i) \\ 
&= (y+1 + \sum_{i=0}^{y} i) - (y + \sum_{i=0}^{y} i) \\ 
&= 1. 
\end{align*} 
$$

Montrons à présent par récurrence que pour tout $n$, il existe $(x, y)$ tel que

$$ \alpha_2(x, y) = n. $$

On a bien $\alpha_2(0, 0) = 0$.

Supposons à présent que $\alpha_2(x, y) = n$. Si jamais $x > 0$, alors on a donc

$$ \alpha_2(x-1, y+1) = n+1. $$

Si jamais $x = 0$, on a donc $\alpha_2(y+1, 0) = n+1$. On en déduit que $\alpha_2$ est surjective.

2. Trivial.

**Solution 3.9.** On vérifie sans peine que $f : \mathbb{N} \to \mathbb{Z}$ donnée par $f(2n) = n$ et $f(2n+1) = -n-1$ est une bijection. On en déduit à l'aide du corollaire 3.8 que $\mathbb{Z} \times \mathbb{Z}$ est dénombrable.

On dispose d'une injection de $\mathbb{Q}$ vers $\mathbb{Z} \times \mathbb{Z}$ en assignant à $r \in \mathbb{Q}$ le couple $(p, q)$ avec $p \in \mathbb{Z}$ et $q \in \mathbb{N}^*$, et où $p/q$ est la fraction réduite égale à $r$. On en déduit donc que $|\mathbb{Q}| \le |\mathbb{Z} \times \mathbb{Z}|$. Comme $\mathbb{Z} \times \mathbb{Z}$ est dénombrable, on a aussi $|\mathbb{Z} \times \mathbb{Z}| \le |\mathbb{N}|$. Comme $\mathbb{Q}$ est infini, $|\mathbb{N}| \le |\mathbb{Q}|$, ce qui donne $|\mathbb{Q}| = |\mathbb{N}|$ par le théorème 2.3 de Cantor-Bernstein.

**Solution 3.10.** Soit $g : A \to \mathbb{N}$ la fonction qui à $y \in A$ associe le plus petit élément $n$ tel que $f(n) = y$. La fonction $g$ est injective, car si $x \ne y \in A$, alors $\{n : f(n) = x\} \cap \{n : f(n) = y\} = \emptyset$, donc $g(x) \ne g(y)$. Ainsi, $A$ est subpotent à $\mathbb{N}$. Comme $A$ est infini, par la proposition 3.2, $\mathbb{N}$ est subpotent à $A$, donc par le théorème 2.3 de Cantor-Bernstein, $A$ et $\mathbb{N}$ sont équipotents.

Question cachée : la proposition 3.2 utilise l'axiome du choix. Comment peut-on résoudre l'exercice de manière constructive, sans faire appel à la proposition 3.2 ?

**Solution 3.11.** On définit la fonction $h : \mathbb{N} \times \mathbb{N} \to B$ par $h(n, m) = f_n(m)$. La fonction est clairement surjective (bijective si les ensembles $B_n$ sont deux à deux disjoints). Par la proposition 3.5, il existe une bijection $b : \mathbb{N} \to \mathbb{N} \times \mathbb{N}$. La fonction $h \circ b : \mathbb{N} \to B$ est donc une fonction surjective. Comme $B$ est infini, l'exercice précédent permet de conclure.
# Chapitre 3

**Solution 2.3.** D'après l'exercice 2-3.7, la bijection de couplage et ses inverses peuvent se calculer de la manière suivante.

```c
int couplage(int a, int b) {
    return (a+b+1)(a+b)/2;
}

int invere1(int c) {
    for (int i = 0; i <= c; i = i + 1)
        for (int j = 0; j <= c; j = j + 1)
            if (couplage(i,j) == c)
                return i;
}

int invere2(int c) {
    for (int i = 0; i <= c; i = i + 1)
        for (int j = 0; j <= c; j = j + 1)
            if (couplage(i,j) == c)
                return j;
}
```

**Solution 2.4.**

```c
int A(int a, int b) {
    // Fonction pour calculer A
}

int ins1(int x, int y) {
    for (int i = 0; i < y; i = i + 1)
        if (A(x, i) == 0)
            return 0;
    return 1;
}

int ins2(int x, int y) {
    for (int i = 0; i < y; i = i + 1)
        if (A(x, i) == 1)
            return 1;
    return 0;
}
```
**Solution 6.4.**

1. Soient $x_1 \in A$ et $x_2 \notin A$. On définit $f$ par $f(x) = x_2$ si $x \in A$, et $f(x) = x_1$ sinon.

2. D'après le théorème du point fixe, il existe $e$ tel que $\Phi_{f(e)} = \Phi_e$.

3. Trivial.

4. Trivial.

**Solution 7.3.** Soit $A$ un ensemble calculable. Alors, on définit le code d'une fonction $e$ qui s'arrête sur son entrée $x$ si $x \in A$, et qui fait une boucle infinie si $x \notin A$.

**Solution 7.9.** On crée le programme qui sur une entrée $n$, énumère $A$ jusqu'à ce qu'un élément plus grand que $n$ soit énuméré dans $A$. Comme $A$ est infini, cela arrivera nécessairement. À ce moment, si $n$ fait partie des éléments énumérés dans $A$, alors $n \in A$, sinon $n \notin A$ (car seuls des éléments strictement supérieurs à $n$ seront énumérés par la suite).

**Solution 7.10.** Soit $A$ est un ensemble c. e. infini. On définit un ensemble c. e. $B$ vérifiant $B \subseteq A$ et que l'on énumère dans l'ordre, de la manière suivante : on énumère $x_0$ dans $B$ pour $x_0$ le premier élément énuméré dans $A$. Supposons que $x_0 < x_1 < \dots < x_n$ aient été énumérés dans $B$, alors l'élément $x_{n+1}$ énuméré dans $B$ sera le prochain élément énuméré dans $A$ qui est plus grand que $x_{n+1}$. Comme $A$ est infini, cela arrive forcément.

**Solution 7.11.** À l'étape de calcul $t$, pour tout $e \le t$ tel que $e$ n'est énuméré ni dans $A$ ou $B$, si $\Phi_e(e)[t] \downarrow \in \{0,1\}$, alors on énumère $e$ dans $A$ si $\Phi_e(e)[t] = 0$ et l'on énumère $e$ dans $B$ si $\Phi_e(e)[t] \downarrow = 1$. Ainsi, si $\Phi_e$ calcule un ensemble $C$, alors soit $A \not\subseteq C$, soit $C \cap B \ne \emptyset$.

**Solution 7.12.** Soit $C$ un ensemble c. e. Nous allons énumérer dans l'ordre deux ensembles $A, B$ (qui seront donc calculables) tels que $x \in C$ ssi $2^x \in D_{A,B}$.

Supposons $A_t, B_t$ énumérés à l'étape $t$. Soit $x$ un nouvel élément énuméré dans $C$ à l'étape $t+1$. Soit $k$ le plus petit entier tel que $2^k > x$ et tel que $2^k$ est plus grand que tous les éléments de $A_t$ et $B_t$. On énumère alors $2^{k+1}$ dans $A$ et $2^{k+1} - x$ dans $B$. On a bien $2^{k+1} - (2^{k+1} - x) = x$ dans l'ensemble $D_{A,B}$. De plus, les autres éléments rajoutés dans $D_{A,B}$ à cette occasion sont de la forme $2^{k+1} - b$ pour $b \in B_t$ et de la forme $a - (2^{k+1} - x)$ pour $a \in A_t$. Comme $b < 2^k$, on a $2^k < 2^{k+1} - b < 2^{k+1}$. Donc, $2^{k+1} - b$ n'est pas une puissance de 2. Comme $a, x < 2^k$, alors $a - (2^{k+1} - x)$ est négatif, et n'appartient donc pas à $D_{A,B}$. Les seuls éléments de $D_{A,B}$ qui sont des puissances de 2 encodent alors les éléments de $C$. Donc, $D_{A,B}$ permet de calculer $C$, et donc si $D_{A,B}$ était calculable, $C$ le serait aussi.

**Solution 7.13.** Montrons que le processus uniforme donné dans l'indication existe. Si $W_e$ énumère un premier élément $a_0$, alors on énumère $[0, a_0]$ dans $W_d$.
Puis, pour tout $n$, si $W_e$ énumère un élément $a_{n+1} > a_n$, on énumère $]a_n, a_{n+1}[$ dans $W_d$. Cela termine la description de $W_d$. Si $W_e$ est fini, l'ensemble $W_d$ est fini aussi, et donc de complémentaire infini. Si $W_e$ est infini, la suite $(a_n)_{n \in \mathbb{N}}$ telle que $a_n < a_{n+1}$ est bien définie, et l'ensemble $W_d$ consiste alors exactement en le complémentaire de cette suite (le complémentaire de $W_d$ est donc bien infini). Il est clair que si $W_d \subseteq W_e$ et $W_e$ est infini, alors $W_e = \mathbb{N}$.

On dira que $\ll R_e$ est satisfait $\gg$ si l'ensemble $W_d$ énuméré vérifie bien

$$W_d \subseteq W_e \rightarrow (|\mathbb{N} \setminus W_e| < \infty \lor |W_e \setminus W_d| < \infty).$$

La difficulté consiste à présent en la coordination de différentes stratégies afin que chaque $R_e$ soit satisfait pour le même ensemble $W_d$. L'idée est la suivante : on effectue bien le processus décrit plus haut pour construire $W_d$ de manière à satisfaire $R_0$. Ce processus énumère une suite d'entiers $a_0^0 < a_1^0 < \dots < a_n^0$ qui va constituer le complémentaire de $W_d$ pour le moment. Il y a deux possibilités.

▷ Cas 1. La suite $(a_n^0)_{n \in \mathbb{N}}$ est infinie, auquel cas on satisfait $R_1$ de la même manière en considérant $(a_n^0)_{n \in \mathbb{N}}$ comme notre nouvel espace de travail.

▷ Cas 2. Il existe un élément $a_k^0$ maximal, auquel cas on peut satisfaire $R_1$ en considérant $\{m : m > a_k^0\}$ comme notre nouvel espace de travail. Le problème est que l'on doit satisfaire $R_1$ uniformément, et que l'on ne sait pas si la satisfaction de $R_0$ va déboucher sur le cas $\ll \text{infini} \gg$ ou sur le cas $\ll \text{fini} \gg$. L'idée est alors de traiter les deux possibilités simultanément. Pour satisfaire $R_1$, on considère la possibilité $\ll \text{finie} \gg$, et ainsi pour chaque $a_k^0$ qui est le plus grand élément pour le moment, on construit pour satisfaire $R_1$ des éléments $a_0^1 < a_1^1 < \dots < a_n^1$ à l'intérieur de $\{m : m > a_k^0\}$. Notons que cela impacte le travail pour satisfaire $R_0$, car la satisfaction de $R_1$ contribue aussi à l'énumération de $W_d$; en pratique, ce n'est pas un problème. Dans le même temps, on va considérer pour satisfaire $R_1$ la possibilité $\ll \text{infinie} \gg$ et tenter, à mesure de l'énumération de $a_0^0 < a_1^0 < \dots < a_n^0$, de travailler dans cet espace. Il faut alors itérer cette idée pour satisfaire chaque $R_e$.

La formalisation de l'argument ci-dessus se fait naturellement via une méthode de priorité avec blessures infinies, comme exposé de manière détaillée dans le chapitre 13. Toutefois, pour cette construction précise, il est possible de donner un algorithme étonnamment simple qui implémente $\ll \text{automatiquement} \gg$, ce qui a été expliqué. Étant donné $x$, on note $\sigma_e(x)[s]$ le nombre $\sum_{i \le e, x \in W_i[s]} 2^{e-i}$. L'idée est que $\sigma_e(x)[s]$ est un poids que l'on donne à $x$, qui augmente à mesure que $x$ appartient à de plus en plus d'ensembles $W_i$ pour $i \le e$. De plus, l'appartenance de $x$ à $W_i$ a plus de valeur que l'appartenance de $x$ à l'ensemble des $W_j$ pour $i < j \le e$. L'algorithme est le suivant. À l'étape 0, soit $a_n^0 = n$ pour tout $n$. À l'étape $s+1$, on définit $a_0^{s+1}$ comme le plus petit entier $x \in [0, s+1] \cap \overline{W_d}$ tel que $\sigma_e(x)[s]$ est maximal — ici, $\overline{W_d}$ dénote le complémentaire de $W_d$ à cette étape de calcul — et l'on énumère $[0, a_0^{s+1}]$ [dans $W_d$. Puis, inductivement, si $a_e^{s+1}$ est défini, on définit $a_{e+1}^{s+1}$ comme le plus petit entier $x \in ]a_e^{s+1}, s+1] \cap \overline{W_d}[s]$, s'il existe, tel que $\sigma_e(x)[s]$ est maximal, puis on énumère $]a_e^{s+1}, a_{e+1}^{s+1}[$ dans $W_d$. Cela conclut la construction.
Notons que, pour tout $e, x$, on a $\sigma_e(x)[s] \le \sigma_e(x)[s+1]$. Il y a par ailleurs $e$ valeurs possibles pour $\sigma_e(x)[s]$. Donc, $\lim_s \sigma_e(x)[s]$ existe. On en déduit que $a_0 = \lim_s a_0^s$ existe aussi, et par induction que $a_e = \lim_s a_e^s$ existe pour tout $e$. Il est alors clair que $W_d$ est le complémentaire de $(a_e)_{e \in \mathbb{N}}$, et que $\overline{W_d}$ est donc infini. Supposons par l'absurde qu'il existe $e$ tel que $W_d \subseteq W_e$, $|W_e \setminus W_d| = \infty$ et $|\mathbb{N} \setminus W_e| = \infty$. Soit $e$ le plus petit de ces entiers. En particulier, il existe un entier $a_n$ à partir duquel pour tout $i < e$, soit $a_m \in W_i$ pour tout $m > n$, soit $a_m \notin W_i$ pour tout $m > n$. Soit $a_{m_3} > a_{m_2} > a_{m_1} > a_n$ tels que $a_{m_2} \notin W_e$ et $a_{m_1}, a_{m_3} \in W_e$. Alors, $\sigma_{m_2}(a_{m_2}) < \sigma_{m_2}(a_{m_3})$ (souvenons-nous que l'appartenance de $a_{m_3}$ à $W_e$ a plus de poids que son appartenance ou non à $W_i$ pour $e < i \le m_2$). En particulier, à un certain moment on devrait énumérer $]a_{m_1}, a_{m_3}[$ dans $W_d$, ce qui est une contradiction.

# Chapitre 4

**Solution 4.3.** Si $Y(n) = \Phi_a(X, n)$ pour tout $n$ et $Z(n) = \Phi_b(Y, n)$ pour tout $n$, alors on peut créer la fonctionnelle $\Phi_e$ qui à partir de l'oracle $X$, cherche pour tout entier $n$ une chaîne $\sigma$ telle que $\sigma(i) = \Phi_a(X, i)$ pour $i < |\sigma|$ et telle que $\Phi_b(\sigma, n) \downarrow$.

**Solution 5.3.** Trivial d'après l'exercice 4.3.

**Solution 5.4.** Supposons $Y =^* X$. Pour calculer $Y$ à partir de $X$, il suffit d'encoder les variations de $X \llcorner$ en dur $\gg$ dans un programme (une suite finie d'instructions), qui sur l'oracle $X$ va répéter en sortie son oracle, sauf pour le nombre fini d'éléments spécifiés dans le programme lui-même.

**Solution 5.8.** Soit $e_1, e_2$ tels que $\Phi_{e_1}(Y, n) \downarrow= X(n)$ et $\Phi_{e_2}(B, n) \downarrow= A(n)$. Alors, on définit la fonctionnelle $\Phi_e$ telle que $\Phi_e(Z_0 \oplus Z_1, 2n) = \Phi_{e_1}(Z_0, n)$ et telle que $\Phi_e(Z_0 \oplus Z_1, 2n + 1) = \Phi_{e_2}(Z_1, n)$.

**Solution 6.2.** Soit $\Psi$ la fonctionnelle telle que $\Psi(Y, n) \downarrow= X(n)$ pour tout $n$. On note $\Psi(Y)$ pour l'ensemble $\{n \in \mathbb{N} : \Psi(Y, n) \downarrow= 1\}$. Soit $f: \mathbb{N} \to \mathbb{N}$ la fonction calculable telle que $\Phi_{f(n)}(Y, m) = \Phi_n(\Psi(Y), n) \downarrow$ pour tout $m$. En particulier, $f(n) \in Y'$ ssi $n \in X'$. Donc, $X' \le_T Y'$.

**Solution 6.4.** Soit $g: \mathbb{N} \to \mathbb{N}$ définie comme dans la preuve de la proposition 6.3. La fonctionnelle $\Phi_e$, sur l'oracle $Z$ et l'entrée $n$, regarde simplement si $g(n) \in Z$. Si c'est le cas, alors elle renvoie 1, sinon elle renvoie 0.

**Solution 7.5.** Clairement, $\emptyset''$ est $\emptyset'$-c. e. et $\emptyset'$ est $\emptyset$-c. e., mais $\emptyset''$ n'est pas est $\emptyset$-c. e. car tout ensemble $\emptyset$-c. e. est calculable à la limite et donc calculable en $\emptyset'$, mais d'après la proposition 6.3 $\emptyset''$ n'est pas calculable en $\emptyset'$.
**Solution 7.8.** Soit $f: \mathbb{N} \to \mathbb{N}$ telle que $f(n) \ge \mu_A(n)$. Pour calculer $A(n)$, on lance l'énumération de $A$ jusqu'à l'étape $f(n)$. On a alors $A_{f(n)}(n) = A(n)$.

**Solution 10.5.** Il suffit de répéter la même preuve, mais en changeant la condition (P2) comme suit :

$$ \forall (x, y) \in \text{dom } h \setminus \text{dom } g, \quad x < m \Rightarrow h(x, y) = B(x). $$

**Solution 10.6.** La construction de la proposition 10.2 est calculable en $\emptyset''$; on peut toutefois utiliser le fait que $\emptyset''$ soit calculatoirement énumérable en $\emptyset'$ pour que la construction devienne effective en $\emptyset'$. À une étape $t$, on satisfait le contrat $S_e$ à partir d'un couple $(g, e)$ pour une fonction partielle $g$, sur la base de ce que l'on croit être le préfixe correct de $\emptyset''$ de taille $e$ à l'étape $t$.

Quand $\emptyset'$ détecte que $k$ est énuméré dans $\emptyset''$ pour un certain $k$, les contrats $S_e$ pour $e \ge k$ deviennent caduques, car ils étaient satisfaits sur la base d'un mauvais préfixe. On peut toutefois re-satisfaire ces contrats autant de fois que nécessaire, en utilisant le fait que l'énumération de $\emptyset''$ converge petit à petit.

**Solution 10.7.** Il suffit de répéter la preuve de la proposition 8.1, mais avec une quantité dénombrable d'ensembles : supposons qu'à l'étape $t$ on ait défini des préfixes $\sigma_{0,t}, \dots, \sigma_{t,t}$ de $A_0, \dots, A_t$, tout en s'assurant qu'aucune fonctionnelle $\Phi_e$ pour $e \le t$ ne puisse calculer $\sigma_{i,t}$ à partir de $\sigma_{j,t}$ pour $i \ne j \le t$. À l'étape $t+1$, on définit des extensions $\sigma_{i,t+1}$ de chaque $\sigma_{i,t}$, ainsi qu'une extension $\sigma_{t+1,t+1}$ du mot vide, de manière à ce que pour tout $e \le t+1$, la fonctionnelle $\Phi_e$ ne puisse calculer $\sigma_{i,t+1}$ à partir de $\sigma_{j,t+1}$ pour $i \ne j \le t+1$. Les extensions se font petit à petit en diagonalisant sur les fonctionnelles $\Phi_e$ pour $e \le t+1$ et sur tous les couples $(i, j)$ possibles pour $i, j \le t+1$.

# Chapitre 5

**Solution 1.8.** Il n'existe qu'un nombre dénombrable d'ensembles dans la hiérarchie arithmétique, donc il existe des ensembles non $\Sigma_n^0$. Soit $A$ un tel ensemble. En particulier $A = \bigcup_{n \in A} \{n\}$. Chaque singleton étant calculable, et $a$ fortiori $\Sigma_n^0$, $A$ est une réunion dénombrable d'ensembles $\Sigma_n^0$, mais n'est pas $\Sigma_n^0$.

**Solution 5.7.** Pour la direction $X \equiv_T Y \to X' \equiv_m Y'$, il suffit de reprendre l'exercice 4-6.2 et de s'apercevoir que la réduction définie est en fait une réduction many-one.

Supposons à présent $X' \ge_m Y'$. Soit $e_{n,0}$ et $e_{n,1}$ les codes des programmes qui s'arrêtent sur leur entrées si respectivement $Z(n) = 0$ ou $Z(n) = 1$ pour l'oracle courant $Z$. En particulier, pour n'importe quel oracle $Z$ on a $Z'(e_{n,0}) \ne Z'(e_{n,1})$ et au moins une des deux valeurs est à 1. À présent, à partir de $X$ et de la fonction $f$ telle que $x \in Y'$ ssi $f(x) \in X$, sur une entrée $n$, on énumère $X'$
jusqu'à trouver $f(e_{n,0}) \in X'$ ou $f(e_{n,1}) \in X'$ si le premier événement arrive alors $Y(n) = 0$ et sinon $Y(n) = 1$.

**Solution 7.2.** On a $e \in \text{TOT ssi } \forall n \exists t \Phi_e(n)[t] \downarrow$, ce qui est un prédicat $\Pi_2^0$. Soit à présent un ensemble $\Pi_2^0$

$$A = \{n \in \mathbb{N} : \forall x_1 \exists x_2 R(n, x_1, x_2)\},$$

où $R$ est un prédicat calculable. Étant donné $n$, on définit la fonctionnelle $e_n$ telle que $\Phi_{e_n}(m)$ s'arrête si $\exists t R(n, m, t)$. Il est clair que $e_n \in \text{TOT ssi } n \in A$.

**Solution 7.5.** Si c'était le cas, l'arrêt serait calculable.

**Solution 7.9.** Trivial.

**Solution 7.10.** Il suffit de créer à l'aide du théorème du point fixe le code $e$ d'une fonctionnelle qui calcule un ensemble $X$ en ne choisissant que des 0 pour les premiers bits de $X$, jusqu'à ce que $f(e)$ renvoie une valeur : si cette valeur est 0 le code $e$ décide de mettre un des bits encore non calculé à 1, sinon il continue de ne mettre que des 0. Plus formellement, soit $g$ la fonction calculable telle que :

1. $\Phi_{g(e)}(t) = 1$, si $t$ est le plus petit tel que $f(e)[t] \downarrow$ et si $f(e)[t] \downarrow = 0$;

2. $\Phi_{g(e)}(t) = 0$, sinon.

D'après le théorème du point fixe, il existe un code $a$ tel que $\Phi_a = \Phi_{g(a)}$. Notons que $g(e)$ est toujours le code $\Delta_1^0$ d'un ensemble fini. C'est donc le cas pour $g(a)$, et donc aussi pour $a$. Par hypothèse sur $f$, on doit donc avoir $f(a) \downarrow = n$ pour un certain $n$. Si $n = 0$, alors $e$ code pour un ensemble à un élément. Dans le cas contraire, $e$ code pour l'ensemble vide.

**Solution 7.11.** Soit $b$ un entier tel que, pour tout oracle $X$, on a $\Phi_b(X, b) \downarrow$ ssi $X$ est non vide, et tel que $\Phi_b(X, b) \uparrow$ sinon. On définit la fonction $g : \mathbb{N} \to \mathbb{N}$ telle que :

1. $\Phi_{g(e)}(\emptyset', t) = 0$ si $\Phi_{f(e)}(\emptyset', b)[t] \uparrow$;

2. $\Phi_{g(e)}(\emptyset', t) = 1$ si $\Phi_{f(e)}(\emptyset', b)[t] \downarrow = 0$;

3. $\Phi_{g(e)}(\emptyset', t) = 0$ si $\Phi_{f(e)}(\emptyset', b)[t] \downarrow = 1$.

D'après le théorème du point fixe, il existe un code $a$ tel que $\Phi_{g(a)} = \Phi_a$. Notons que $g(e)$ code toujours pour une fonction totale en $\emptyset'$, et est donc un code $\Delta_2^0$. Par conséquent, $g(a)$ et $a$ le sont également. Notons enfin que l'ensemble de code $a$ est soit vide, soit n'a qu'un nombre fini de 0. Il est donc calculable, et en particulier low. Donc, par hypothèse sur $f$, $f(a)$ est un code $\Delta_2^0$, et donc $\Phi_{f(a)}$ est totale sur l'oracle $\emptyset'$ et il existe $t$ tel que $\Phi_{f(a)}(\emptyset', b)[t] \downarrow = i$. Si $i = 0$, alors $a$ code pour un ensemble $X$ non vide, et l'on devrait avoir $X'(b) = 1 \neq \Phi_{f(a)}(\emptyset', b)$. Si $i = 1$, alors $a$ code pour un ensemble $X$ vide, et $X'(b) = 0 \neq \Phi_{f(a)}(\emptyset', b)$ comme il se devrait.
Exercice caché : donner à présent une description informelle de la procédure décrite ci-dessus, comme celle de la solution précédente.

# Chapitre 6

**Solution 3.10.** Soit $m$ tel que notre programme utilise au plus les registres

$R_0, \dots, R_m.$

Il suffit de recopier au début du programme les registres de $R_1$ à $R_m$ dans les registres de $R_{m+1}$ à $R_{m+m}$. Ensuite, le programme est le même en remplaçant tous les registres $R_i$ par $R_{i+m}$ pour $i > 0$, puis enfin en ajoutant des instructions à la fin qui remettent à zéro tous les registres de $R_{m+1}$ à $R_{m+m}$.

**Solution 3.12.** L'addition est définie en utilisant les schémas de composition et récursion primitive. La multiplication et l'exponentielle en utilisant le schéma de récursion primitive.

Addition :

$$ \text{add}(a, 0) = p_1^2(a, 0) $$

$$ \text{add}(a, b+1) = \text{succ}(p_2^2(a, \text{add}(a, b))) $$

Multiplication :

$$ \text{mult}(a, 0) = 0 $$

$$ \text{mult}(a, b+1) = \text{add}(a, \text{mult}(a, b)) $$

Exponentielle :

$$ \text{exp}(a, 0) = 1 $$

$$ \text{exp}(a, b+1) = \text{mult}(a, \text{exp}(a, b)) $$

**Solution 3.13.** Les fonctions sont définies en utilisant le schéma de récursion primitive.

Prédécesseur :

$$ \text{pred}(0) = 0 $$

$$ \text{pred}(n+1) = p_1^2(n, \text{pred}(n)) $$

Soustraction :

$$ -(a, 0) = p_1^2(a, 0) $$

$$ -(a, b+1) = \text{pred}(p_2^2(a, -(a, b))) $$

**Solution 3.14.** Les fonctions sont définies à l'aide du schéma de récursion primitive.

sg :

$$ \text{sg}(0) = 0 $$

$$ \text{sg}(x+1) = c_1^2(x, \text{sg}(x)) $$

$\overline{\text{sg}} :$

$$ \overline{\text{sg}}(0) = 1 $$

$$ \overline{\text{sg}}(x+1) = c_0^2(x, \overline{\text{sg}}(x)) $$

**Solution 3.19.** Soient $P_1, P_2 \subseteq \mathbb{N}^n$ des prédicats primitifs récursifs. Alors,

$$ P_1(a_1, \dots, a_n) \wedge P_2(a_1, \dots, a_n) = P_1(a_1, \dots, a_n) \times P_2(a_1, \dots, a_n) $$

$$ P_1(a_1, \dots, a_n) \vee P_2(a_1, \dots, a_n) = \text{sg}(P_1(a_1, \dots, a_n) + P_2(a_1, \dots, a_n)) $$

$$ \neg P_1(a_1, \dots, a_n) = \overline{\text{sg}}(P_1(a_1, \dots, a_n)). $$
Soit $P \subseteq \mathbb{N}^{n+1}$ un prédicat primitif récursif. Alors,

$$ \exists y \leq z P(x_1, \dots, x_n, y) = Q_1(x_1, \dots, x_n, z) $$

$$ \forall y \leq z P(x_1, \dots, x_n, y) = Q_2(x_1, \dots, x_n, z) $$

où

$$ Q_1(x_1, \dots, x_n, 0) = P(x_1, \dots, x_n, 0) $$

$$ Q_1(x_1, \dots, x_n, z + 1) = P(x_1, \dots, x_n, \text{succ}(z)) \lor Q_1(x_1, \dots, x_n, z) $$

$$ Q_2(x_1, \dots, x_n, 0) = P(x_1, \dots, x_n, 0) $$

$$ Q_2(x_1, \dots, x_n, z + 1) = P(x_1, \dots, x_n, \text{succ}(z)) \land Q_2(x_1, \dots, x_n, z). $$

**Solution 3.20.** On utilise le schéma de récursion primitive, la définition par cas et la clôture des prédicats primitifs récursifs par conjonction et quantification bornée :

$$ \begin{aligned} g(x_1, \dots, x_p, 0) &= 0 \\ g(x_1, \dots, x_p, n+1) &= \begin{cases} \text{succ}(n) & \text{si } f(x_1, \dots, x_p, \text{succ}(n)) = 0 \\ & \text{et } \forall t \leq n \ f(x_1, \dots, x_p, t) \neq 0 \\ & g(x_1, \dots, x_p, n) \end{cases} \end{aligned} $$

**Solution 3.23.** L'ensemble $A$ peut être défini de manière calculable par récurrence. On pose $A_0 = \{e_0\}$, où $e_0$ est le code de la fonction successeur. Supposons $A_n$ défini avec $n = (k, a)$. Alors, $A_{n+1}$ est l'ensemble $A_n$ auquel on ajoute un code pour toutes les possibilités d'application du schéma de composition et de récursion primitive des codes de $A_n$, ainsi que des codes pour la fonction constante $f(x_1, \dots, x_k) = a$ et pour la projection $f(x_1, \dots, x_k) = x_a$ dans le cas où $a \leq k$. On prendra bien garde à ce que les nouveaux codes de $A_{n+1}$ soient tous supérieurs aux codes de $A_n$, via le lemme de remplissage. L'ensemble $A = \cup_n A_n$ est alors calculable.

Par diagonalisation, en utilisant le fait qu'une fonction primitive récursive est toujours totale; on calcule alors une fonction $\Phi_e$ qui n'a pas de code dans $A$. Soient $a_0 < a_1 < a_2 < \dots$ les éléments de $A$ codant pour des fonctions prenant exactement un paramètre. On peut alors par exemple définir $\Phi_e(n) = 0$ si $\Phi_{a_n}(n) \neq 0$, et $\Phi_e(n) = 1$ sinon. Notons qu'il est nécessaire pour tout $n$ de lancer l'exécution de $\Phi_{a_n}(n)$ jusqu'à ce qu'elle s'arrête (ce qui arrive nécessairement car $a_n$ code pour une fonction primitive récursive).

**Solution 3.25.**

(1) On a $A_0(x)=2^x>x$, donc (1) est vrai pour $A_0$. Supposons (1) pour $A_n$, et montrons (1) pour $A_{n+1}$. On procède par récurrence sur $x$. On a $A_{n+1}(0)=1>0$. Supposons $A_{n+1}(x) > x$ pour $x$. Alors, $A_{n+1}(x+1) = A_n(A_{n+1}(x))$. Comme (1) est vrai pour $A_n$, alors $A_n(A_{n+1}(x)) > A_{n+1}(x)$. Par hypothèse de récurrence, $A_{n+1}(x) > x$. Donc, $A_{n+1}(x+1) > x+1$.

(2) La fonction $A_0$ est clairement strictement croissante. Ensuite, pour tout $n$, on a $A_{n+1}(x+1) = A_n(A_{n+1}(x))$. En utilisant (1), on a $A_n(A_{n+1}(x)) > A_{n+1}(x)$, et donc $A_{n+1}(x+1) > A_{n+1}(x)$. Donc, pour tout $n$, la fonction $A_{n+1}$ est strictement croissante.
(3) Pour $x=0$, pour tout $n$ on a $A_{n+1}(0)=1$ et $A_n(0)=1$. Donc, $A_{n+1}(0)\ge A_n(0)$. Pour $x>0$, on a $A_{n+1}(x) = A_n(A_{n+1}(x-1))$.

D'après (1), on a $A_{n+1}(x-1) > x-1$, donc $A_{n+1}(x-1) \ge x$. Aussi, comme la fonction $A_n$ est croissante, on a $A_n(A_{n+1}(x-1)) \ge A_n(x)$. On a donc $A_{n+1}(x) \ge A_n(x)$, ce qui implique que la fonction $n \mapsto A_n(x)$ est croissante.

(4) Par récurrence sur $y$. Pour $y=0$, on a $A_{n+1}(x) \ge x$, d'après (1). Supposons (4) pour $y$, afin de le montrer pour $y+1$. On a

$$A_{n+1}(x + y + 1) = A_n(A_{n+1}(x + y)).$$

Par l'hypothèse de récurrence, $A_{n+1}(x+y) \ge A_n^{(y)}(x)$. On a donc

$$A_{n+1}(x + y + 1) \ge A_n(A_n^{(y)}(x)) = A_n^{(y+1)}(x),$$

car $A_{n+1}$ est croissante.

(5) D'après (4), on a $A_{n+1}(2(x+1)) \ge A_n^{(x+1)}(x+1)$.

Il suffit de montrer $A_{n+1}(x) > A_n(2(x+1))$ pour presque tout $x$ pour avoir (5). Par (3), pour tout $n \in \mathbb{N}$, on a $A_{n+1}(x) \ge A_0(x) = 2^x > 2x+3$ pour presque tout $x$. Par définition, pour tout $n \in \mathbb{N}$, on a

$$A_{n+1}(x) = A_n(A_{n+1}(x-1)) \ge A_n(2(x-1)+3),$$

pour presque tout $x$ (car $n \mapsto A_n$ est croissante par (3)).

(6) Pour les fonctions primitives récursives de base (projections, fonctions constantes et successeur), $P(f)$ est clairement vérifié. Supposons que l'on ait $P(h)$ et $P(g_1), \dots, P(g_n)$ pour les fonctions primitives récursives $h : \mathbb{N}^n \to \mathbb{N}$ et $g_1, \dots, g_n : \mathbb{N}^m \to \mathbb{N}$. Montrons $P(f)$ pour la fonction

$$f(x_1, \dots, x_m) = h(g_1(x_1, \dots, x_m), \dots, g_n(x_1, \dots, x_m)).$$

Il existe $k \in \mathbb{N}$ tel que

$$h(x_1, \dots, x_n) < A_k(\max(x_1, \dots, x_n)) \text{ et } g_i(x_1, \dots, x_m) < A_k(\max(x_1, \dots, x_m))$$

presque partout et pour tout $i \le n$. Comme $A_k$ soit croissante, on a

$$h(g_1(x_1, \dots, x_m), \dots, g_n(x_1, \dots, x_m)) \le A_k(A_k(\max(x_1, \dots, x_m))).$$

D'après (5), pour presque tout $x_1, \dots, x_m$, on a

$$A_k^{(2)}(\max(x_1, \dots, x_m)) < A_{k+2}(\max(x_1, \dots, x_m)).$$

Donc, $P(f)$ est vérifié.

Supposons à présent que $P(h)$ et $P(g)$ soit vrais pour les fonctions primitives récursives $h : \mathbb{N}^{n+2} \to \mathbb{N}$ et $g : \mathbb{N}^n \to \mathbb{N}$. Montrons que $P(f)$ est vrai pour la fonction

$$\begin{aligned} f(x_1, \dots, x_n, 0) &= g(x_1, \dots, x_n) \\ f(x_1, \dots, x_n, x+1) &= h(x_1, \dots, x_n, x, f(x_1, \dots, x_n, x)). \end{aligned}$$

En particulier, il existe $k$ tel que

$$g(x_1, \dots, x_n) < A_k(\max(x_1, \dots, x_n)) \text{ et } h(x_1, \dots, x_n, z, x) < A_k(\max(x_1, \dots, x_n, z, x)) \text{ pour presque tous } x_1, \dots, x_n, z, x. \text{ On laisse au lecteur le soin de montrer par récurrence sur } x \text{ que l'on a } f(x_1, \dots, x_n, x) < A_k^{(x+1)}(\max(x_1, \dots, x_n)) \text{ pour}$$
tout $x$. On a également

$$A_k^{(x+1)}(\max(x_1, \dots, x_n)) \le A_k^{(\max(x_1, \dots, x_n, x+1))}(\max(x_1, \dots, x_n, x+1));$$

or,

$$A_k^{(\max(x_1, \dots, x_n, x+1))}(\max(x_1, \dots, x_n, x+1)) \le A_{k+2}(\max(x_1, \dots, x_n, x))$$

pour presque tout $x_1, \dots, x_n, x$ (d'après (5)).

Ainsi, $\forall^\infty x f(x_1, \dots, x_n, x) < A_{k+2}(\max(x_1, \dots, x_n, x))$, et donc $P(f)$. On a dès lors $P(f)$ pour toute fonction primitive récursive $f$. On en déduit que la fonction d'Arckermann domine presque partout toutes les fonctions récursives.

# Chapitre 7

**Solution 1.5.** Si un ensemble $A$ n'est pas immune il contient un ensemble infini c. e. $x_0, x_1, \dots$. On peut supposer sans perte de généralité $x_i \neq x_j$ pour $i \neq j$ et en posant $F_i = \{x_i\}$ on obtient un tableau c. e. $F_0, F_1, \dots$ pour lequel $A \cap F_n \neq \emptyset$ pour tout $n$. Donc, $A$ n'est pas hyperimmune.

**Solution 2.2.** Soit $X$ un ensemble calculant une fonction DNC $f: \mathbb{N} \to \mathbb{N}$. Par le lemme de remplissage, il existe un ensemble infini calculable $A = \{e_0 < e_1 < \dots\}$ de codes de la fonction définie nulle part. Soit $g: \mathbb{N} \to \mathbb{N}$ la fonction définie par $g(x) = f(x)$ si $x \notin A$, et $g(e_n) = X(n)$ sinon. La fonction $g$ est X-calculable. Inversement, on peut re-calculer $X$ à partir de $g$ en regardant les valeurs de $g$ aux positions de $A$. Ainsi, $g$ est dans le degré de $X$. Montrons que $g$ est DNC. Si $x \notin A$, alors $g(x) = f(x) \neq \Phi_x(x)$. Si $x \in A$, alors $\Phi_x$ n'est définie nulle part, donc $g(x) \neq \Phi_x(x)$.

**Solution 2.9.** On construit un ensemble $A$ comme limite de chaînes

$$\sigma_0 < \sigma_1 < \sigma_2 < \dots,$$

via une construction calculable en $\emptyset'$. La manière de rendre $A$ non calculable est identique à celle de la preuve de la proposition 4-9.1.

Pour obtenir $A$ non DNC, étant donné une fonctionnelle $\Phi$ et une chaîne $\sigma_n$, soit il existe $m \in \mathbb{N}$ tel que $\Phi(\sigma_n\tau, m)\uparrow$ pour toute chaîne $\tau$, auquel cas $\Phi(A, m)$ sera partielle, soit pour tout $m$ on a $\Phi(\sigma_n\tau, m)\downarrow$ pour une chaîne $\tau$, auquel cas on peut calculer la fonction totale $f(m) = \Phi(\sigma_n\tau, m)$ pour la première chaîne $\tau$ trouvée telle que $\Phi(\sigma_n\tau, m)\downarrow$. Il existe alors $a$ tel que $\Phi_a(a)\downarrow= f(a)$. On choisit $\sigma_{n+1} = \sigma_n\tau$ pour $\tau$ telle que $\Phi(\sigma_n\tau, a)\downarrow= f(a) = \Phi_a(a)$, et l'on aura $\Phi(A, a)\downarrow= \Phi_a(a)\downarrow$.

**Solution 3.2.** On procède comme dans l'indication. Soit il existe $n$ tel que la fonction $m \mapsto g(a_{n,m})$ est DNC relativement à $C$, soit pour tout $n$, il existe $m$ tel que $\Phi_m(C, m)\downarrow= g(a_{n,m})$. On définit alors la fonction $g \oplus C$-calculable $f: \mathbb{N} \to \mathbb{N}$ telle que $f(n)$ renvoie le plus petit $s$ tel que $\Phi_m(C, m)[s]\downarrow= g(a_{n,m})$ pour $m \le s$. Supposons par l'absurde qu'il existe $n$ tel que $\emptyset'(n) = 1$ et tel que $\emptyset'(n)[f(n)] = 0$. Alors, $g(a_{n,m}) = \Phi_{a_{n,m}}(a_{n,m})$, ce qui contredit que $g$ est DNC. Donc, $f$ borne le temps d'entrée de $n$ dans $\emptyset'$.
**Solution 4.2.** Une direction est triviale. Pour l'autre direction, supposons qu'il existe une fonction calculable $g$ et un entier $y$ pour lesquels $g(x) > f(x)$ pour tout $x \ge y$. Alors, la fonction $g'(x)$ définie par $g'(x) = f(x) + 1$ si $x < y$, et par $g'(x) = g(x)$ sinon, est calculable et domine $f$ partout. Donc, $f$ n'est pas hyperimmune.

**Solution 4.5.** Soit $X \ge T$ avec $f$ hyperimmune. Alors, $X \ge T g$ avec $g: \mathbb{N} \to \mathbb{N}$ définie par $g(n) = \langle f(n), X(n) \rangle$. Comme on a $g > f$, alors $g$ est hyperimmune, et il est clair que $g$ calcule $X$.

**Solution 4.6.** Soit $(f_n)_{n \in \mathbb{N}}$ une énumération des fonctions calculables totales. On définit $\sigma_0 = \epsilon$. Supposons $\sigma_n$ défini. Alors, on définit $\sigma_{n+1}$ comme étant $\sigma_n 0^{f_n(n)+1} 1$. L'ensemble $\{X\} = \bigcap_n[\sigma_n]$ est hyperimmune via la fonction qui à $n$ associe le $n$-ième élément de $X$.

**Solution 5.8.** Supposons $T(\sigma)$ défini pour toute chaîne $\sigma$ de taille $n$, telle que pour tout $e \le n$ on a $\Phi_e(T(\sigma)) \not\supseteq T(\tau)$. Pour tous $\sigma, \tau$ de taille $n$. Soit $(\sigma_{j,0})_{j \le 2^{n+1}}$ une énumération des chaînes de la forme $T(\sigma)i$ pour une chaîne $\sigma$ de taille $n$ et $i \in \{0,1\}$. Soit $((a_j, b_j))_{j \in k}$ une énumération des couples distincts d'éléments inférieurs à $2^{n+1}$. Supposons $(\sigma_{j,t})_{j \le 2^{n+1}}$ défini à l'étape $t$. À l'étape $t+1$, on définit $\sigma_{a_{t+1},t+1}$ et $\sigma_{b_{t+1},t+1}$ comme étant des extensions de $\sigma_{a_{t+1},t}$ et $\sigma_{b_{t+1},t}$ telles que $\Phi_{n+1}(\sigma_{a_{t+1},t+1}) \not\supseteq \sigma_{b_{t+1},t+1}$. On définit $\sigma_{c,t+1} = \sigma_{c,t}$ pour $c \ne a_{t+1}$ et $c \ne b_{t+1}$. Une fois que tous les couples $((a_j, b_j))_{j \in k}$ ont été considérés, on définit finalement $T(\sigma i)$ comme étant la chaîne $\sigma_{j,k}$ qui étend $T(\sigma)i$ pour $i \in \{0,1\}$.

**Solution 6.3.** Montrons (1) ⇒ (2). Soit $f: \mathbb{N} \to \mathbb{N}$ une fonction qui domine presque partout toute fonction calculable. On procède comme dans (2) ⇒ (3) de le théorème 6.2, mais pour les fonctionnelles à valeur dans $\mathbb{N}$.

Montrons (2) ⇒ (3). On transforme la liste $(f_n)_{n \in \mathbb{N}}$ en remplaçant chaque fonction $f$ telle que $f(n) < f(n+1)$ par l'ensemble $X$ tel que $f(n)$ est le $n$-ième élément de $X$.

Si pour une fonction $f$ on s'aperçoit à un moment $f(n+1) \le f(n)$, on complète alors l'ensemble $X$ correspondant par un ensemble calculable infini fixé à l'avance.

Montrons (3) ⇒ (1). Il suffit de calculer la fonction $g: \mathbb{N} \to \mathbb{N}$ définie par $g(n)$ comme étant la somme des $n$-ième éléments des ensembles $X_i$ pour $i \le n$.

**Solution 6.5.** Soit $f: \mathbb{N} \to \mathbb{N}$ la fonction $X$-calculable qui à $n$ associe le plus petit $m$ tel que $\mathbb{N} \setminus X$ contienne $2n$ éléments plus petits que $m$. Supposons par l'absurde qu'il existe une fonction calculable $g$ telle que $\exists^\infty n g(n) > f(n)$. On peut supposer sans perte de généralité que $g(n) < g(n+1)$.

Montrons tout d'abord qu'il existe une infinité de valeurs $n$ telles que $\mathbb{N} \setminus X$ contient au moins deux éléments dans $[g(n), g(n+1)]$. En effet, dans le cas contraire, soit $n_0$ le plus petit entier tel que pour tout $n \ge n_0$, $[g(n), g(n+1)]$ contienne au plus un élément de $\mathbb{N} \setminus X$. Soit $k$ le nombre d'éléments de $\mathbb{N} \setminus X$
inférieurs à $g(n_0)$. Pour tout $n > n_0$, le nombre d'éléments de $\mathbb{N} \setminus X$ inférieurs à $g(n)$ est au plus $k+n-n_0$. Pour $n$ suffisamment grand, on a $k+n-n_0 < 2n$, autrement dit il existe moins de $2n$ éléments plus petits que $g(n)$, donc $g(n) < f(n)$, ce qui contredit notre hypothèse.

Montrons maintenant qu'il existe un ensemble c. e. $Y \supseteq X$ tel que $Y \setminus X$ et $\mathbb{N} \setminus Y$ sont tous les deux infinis. On recopie $X$ dans $Y$, et en plus de cela à chaque temps de calcul $s$ on énumère dans $Y$ le plus petit entier de l'intervalle $[g(n), g(n+1)]$ (pour $n \le s$) qui n'est pas énuméré dans $X$ à l'étape $s$. Notons que pour chaque intervalle $[g(n), g(n+1)]$ contenant au moins deux éléments de $\mathbb{N} \setminus X$, on énumèrera un élément dans $Y$ qui n'est pas dans $X$, et l'on gardera un élément de $\mathbb{N} \setminus X$ hors de $Y$. Le complémentaire de $Y$ sera donc infini, et une infinité d'éléments de $Y$ ne seront pas dans $X$, ce qui contredit l'hypothèse de maximalité sur $X$. Donc, $X$ est high.

# Chapitre 8

**Solution 1.7.** Trivial.

**Solution 1.8.** Une fois un nœud $\sigma_n \in T$ calculé, ce nœud a au moins un extension dans $T$. On calcule alors $\sigma_{n+1}$ comme étant l'extension la plus à gauche de $\sigma_n$ dans $T$ (c'est-à-dire $\sigma_n 0$ si $\sigma_n 0 \in T$, et $\sigma_n 1$ sinon).

**Solution 4.2.** À l'aide de $\emptyset'$, on peut calculer le sous-arbre $T' \subseteq T$ des nœuds extensibles de $T$. D'après l'exercice 1.8, cet arbre contient un chemin calculable en l'arbre et donc $\emptyset'$-calculable.

**Solution 5.2.** Pas de difficulté particulière : il s'agit de dupliquer la construction faite dans la preuve du théorème 7-5.6, de la même manière que la construction d'un degré calculatoirement dominé dans une classe $\Pi_1^0$ est dupliquée dans la preuve du théorème 5.1.

**Solution 5.3.** En reprenant les éléments de la preuve du théorème 5.1, à une étape $n$, on a pour chaque chaîne $\sigma \in 2^{<\mathbb{N}}$ de taille $n$ des classes $\Pi_1^0$ deux à deux disjointes et non vides $P_\sigma \subseteq P$. Soit $\Phi_n$ la fonctionnelle de code $n$, et soient $\sigma_0, \sigma_1$ deux chaînes distinctes de taille $n$.

Soit il existe $X$ tel que $\Phi_n(Y) = X$ pour tout $Y \in P_{\sigma_0}$, auquel cas $X$ est calculable et donc $\Phi_n(Y) \notin P_{\sigma_1}$ pour tout $Y \in P_{\sigma_0}$, soit il existe $m$ tel que

$$ \{Y \in P_0 : \Phi_n(Y, m) \uparrow \neq 0\} \neq \emptyset \quad \text{et} \quad \{Y \in P_0 : \Phi_n(Y, m) \uparrow \neq 1\} \neq \emptyset. $$

Au moins une des deux classes parmi $\{Y \in P_1 : Y(m)=0\}$ et $\{Y \in P_1 : Y(m)=1\}$ est non vide. On peut donc toujours trouver deux classes $\Pi_1^0$ non vides $P'_{\sigma_0} \subseteq P_{\sigma_0}$ et $P'_{\sigma_1} \subseteq P_{\sigma_1}$ telles que $\Phi_n(Y) \notin P'_{\sigma_1}$ pour tout $Y \in P'_{\sigma_0}$.

Il suffit d'itérer cette idée pour toutes les paires $\sigma_0, \sigma_1$ de taille $n$, et de recommencer en alternant ces étapes avec celles de la preuve du théorème 5.1, pour diagonaliser contre toutes les fonctionnelles $\Phi_n$.
**Solution 5.4.** La différence est que l'on n'a ici pas d'effectivité. On montre le lemme suivant : étant donné deux chaînes $\sigma$ et $\tau$ qui sont chacune respectivement le premier nœud branchant de $f$-arbres $S_\sigma$ et $S_\tau$, et étant donné une fonctionnelle $\Phi_e$, il existe des extensions $\sigma' \supseteq \sigma$, $\tau' \supseteq \tau$ et un sous-f-arbre $S'_\sigma \subseteq S_\sigma$ dont $\sigma'$ est le premier nœud branchant, et tel que $\Phi_e(X) \nsubseteq \tau'$ pour tout $X \in [S'_\sigma]$.

Soient $\rho_0, \rho_1$ telle que $\tau\rho_0, \tau\rho_1 \in \text{Im } S_\tau$ sont incompatibles. Alors, on a deux possibilités. Soit il existe $\sigma' \supseteq \sigma$ avec $\sigma' \in \text{Im } S_\sigma$ telle que $\Phi_e(\sigma') \supseteq \tau\rho_0$; dans ce cas, on trouve un sous-arbre de $S_\sigma$ tel qu'aucun de ses nœuds qui étend $\sigma'$ n'est envoyé vers $\tau\rho_1$. Soit pour tout $\sigma' \supseteq \sigma$ on a $\Phi_e(\sigma') \nsubseteq \tau\rho_0$; dans ce cas, aucun nœud de $S_\sigma$ qui étend $\sigma$ n'est envoyé vers $\tau\rho_0$.

À présent, étant donné un f-arbre quelconque $T$, il suffit de construire un sous-f-arbre $S$ de $T$ en itérant petit à petit le lemme sur chaque feuille du morceau fini de $S$ que l'on est en train de construire.

**Solution 5.5.** Soit $T \subseteq 2^{<\mathbb{N}}$ un arbre calculable tel que $\mathcal{P} = [T]$. À l'aide de l'arrêt, on calcule l'ensemble $T' \subseteq T$ des nœuds extensibles de $T$. On peut ensuite trouver un chemin de $[T']$ en diagonalisant contre tous les ensembles calculables (sachant que $\emptyset'$ peut lister uniformément tous les ensembles calculables).

**Solution 6.10.** Étant donné $n$, on définit le code $e_n$ de la fonctionnelle telle que $\Phi_{e_n}(e_n) = 0$ si $n \in A$ et $\Phi_{e_n}(e_n) = 1$ si $n \in B$. Si aucun des deux cas ne se produit, alors $\Phi_{e_n}(e_n) \uparrow$. Soit à présent $f: \mathbb{N} \to \{0, 1\}$ une fonction $X$-calculable telle que $f(n) \neq \Phi_n(n)$ pour tout $n$. On calcule alors $C(n) = f(e_n)$.

**Solution 7.6.** Si $Y$ un ensemble $\text{PA}(X)$, il peut calculer un chemin dans toute classe $\Pi_1^0(X)$ non vide, et donc en particulier dans une classe $\Pi_1^0(X)$ ayant $X$ pour seul chemin.

**Solution 7.11.** La clôture par préfixe d'un ensemble de chaînes est un arbre. Si cet ensemble de chaînes est infini, il s'agit alors d'un arbre infini, qui admet un chemin par le lemme faible de König.

**Solution 7.12.** Soit $\sigma_t = \emptyset^t[t]_t$ et $S = \{\sigma_t : t \in \mathbb{N}\}$. Alors, l'unique chemin de la clôture par préfixe de $S$ est $\emptyset^t$.

**Solution 7.13.** Soit $f: 2^{<\mathbb{N}} \times \mathbb{N} \to \{0, 1\}$ une approximation $\Delta_2^0$ de $T$, c'est-à-dire telle que pour tout $\sigma \in 2^{<\mathbb{N}}$, $\lim_y f(\sigma, y)$ existe, et $\lim_y f(\sigma, y) = 1$ ssi $\sigma \in T$. On supposera de plus que pour tout $y$, $\{\sigma \in 2^{<\mathbb{N}} : f(\sigma, y) = 1\}$ est clos par préfixe et infini.

Nous allons définir une suite calculable de chaînes $\sigma_0, \sigma_1, \dots$ telle que $|\sigma_n| = n$ et telle que l'ensemble des chemins infinis de sa clôture par préfixe est $[T]$. Initiallement, $\sigma_0 = \epsilon$. Supposons que l'on a défini $\sigma_0, \dots, \sigma_n$.
Pour toute chaîne $\tau$ de longueur au plus $n$, on définit son *ancienneté* $\mu_n(\tau)$ à l'étape $n$ comme le plus grand entier $s \le n$ tel que $\tau \preceq \sigma_s$ s'il existe.SION, $\mu_n(\tau) = 0$. Soit $\sigma_{n+1}$ une chaîne de longueur $n+1$ telle que $f(\sigma_{n+1}, n+1) = 1$, et telle que pour tout $s \le n$, $\sigma_{n+1} \upharpoonright_s$ est d'ancienneté minimale parmi

$$ \{\rho \in 2^{\mathbb{N}} : |\rho| = s \wedge \rho \upharpoonright_{s-1} = \sigma_{n+1} \upharpoonright_{s-1}\}. $$

Soit $S = \{\sigma_n : n \in \mathbb{N}\}$. Montrons que $[\hat{S}] \subseteq [T]$. Soit $P \in [\hat{S}]$, et soit $\tau < P$. Alors, il existe une infinité de $n$ tels que $\tau < \sigma_n$.

Comme $f(\sigma_n, n) = 1$ et $\{\rho \in 2^{<\mathbb{N}} : f(\rho, n) = 1\}$ est clos par préfixes, il existe une infinité de $n$ tels que $f(\tau, n) = 1$, donc $\lim_n f(\tau, n) = 1$, autrement dit $\tau \in T$. Comme tout segment initial de $P$ est dans $T$, $P \in [T]$.

Montrons que $[T] \subseteq [\hat{S}]$. Soit $P \in [T]$. Supposons par l'absurde que $P \notin [\hat{S}]$, et soit $\tau < P$ de longueur minimale tel que $[\tau] \cap [\hat{S}] = \emptyset$. Soit $n_0$ tel que

(1) pour tout $n > n_0$, $\sigma_n \upharpoonright_{|\tau|}$ est extensible en un chemin infini dans $\hat{S}$;

(2) pour tout $\rho \in 2^{<\mathbb{N}}$ de longueur $|\tau|$ extensible en un chemin infini dans $\hat{S}$, il existe $n < n_0$ tel que $\rho < \sigma_n$;

(3) pour tout $n > n_0$, $f(\tau, n) = 1$.

Par minimalité de $\tau$, il existe $n > n_0$ tel que $\tau \upharpoonright_{|\tau|-1} < \sigma_n$. Par le choix de $\sigma_n$, $\sigma \upharpoonright_{|\tau|}$ est une chaîne étendant $\sigma \upharpoonright_{|\tau|-1}$ d'ancienneté minimale. Par (2), toutes les chaînes de longueur $|\tau|$ extensibles dans $\hat{S}$ sont d'ancienneté strictement positive; par (3), il existe une chaîne étendant $\sigma \upharpoonright_{|\tau|-1}$ d'ancienneté 0; et, par (1), $\sigma \upharpoonright_{|\tau|}$ est extensible en un chemin infini. On obtient une contradiction. Donc, $P \notin [\hat{S}]$.

# Chapitre 10

**Solution 2.8.** Supposons que $U^<)$ soit dense dans $2^{<\mathbb{N}}$. Soit $\sigma \in 2^{<\mathbb{N}}$. Montrons que $[\sigma] \cap \bigcup_{\tau \in U}[\tau] \neq \emptyset$. Par densité de $U^<$, il existe $\rho \succeq \sigma$ tel que $\rho \in U^<$. Il existe donc un préfixe $\rho' \preceq \rho$ tel que $\rho' \in U$. Soit $\sigma \preceq \rho'$ auquel cas $[\rho'] \subseteq [\sigma]$, soit $\rho' \preceq \sigma$ auquel cas $[\sigma] \subseteq [\rho']$. Dans tous les cas, $[\rho'] \cap [\sigma] \neq \emptyset$, et donc $[\sigma] \cap \bigcup_{\tau \in U}[\tau] \neq \emptyset$.

Supposons maintenant que l'ouvert $\bigcup_{\tau \in U}[\tau]$ soit dense dans l'espace de Cantor. Soit $\sigma \in 2^{<\mathbb{N}}$. En particulier, $[\sigma] \cap \bigcup_{\tau \in U}[\tau] \neq \emptyset$, donc il existe $A \in [\sigma] \cap \bigcup_{\tau \in U}[\tau]$. Soit $\tau \in U$ tel que $A \in [\tau]$. Soit $n > \max(|\sigma|, |\tau|)$. En particulier, $A \upharpoonright_n \succeq \tau$, donc par la clôture par suffixe de $U^<$, $A \upharpoonright_n \in U^<$, et $A \in [\sigma]$, donc $A \upharpoonright_n \succeq \sigma$. La chaîne $\sigma$ a donc une extension dans $U^<$.

**Solution 2.12.** Par l'exercice 2.8, pour tout $n$, comme $W_n^<$ est dense dans $2^{<\mathbb{N}}$ et clos par suffixe, alors $[W_n]$ est dense dans l'espace de Cantor. Ainsi, $\bigcap_n [W_n]$ est une intersection dénombrable d'ouverts denses, et la classe est donc co-maigre.

**Solution 2.13.** Soit $G$ un ensemble $\tilde{W}$-générique. En particulier, $G$ rencontre $W_n$ pour tout $n$, et il existe donc $\sigma < G$ tel que $\sigma \in W_n$; par suite, $G \in [W_n]$, et donc $G \in \bigcap_n [W_n]$. Inversement, soit $G \in \bigcap_n [W_n]$. Alors, pour tout $n$, $G \in [W_n]$,
et il existe donc $\sigma \prec G$ tel que $\sigma \in W_n$. Autrement dit, $G$ rencontre $W_n$ pour tout $n$, de sorte que $G$ est $\tilde{W}$-générique.

**Solution 3.5.** Comme dans (3) $\to$ (2) du théorème 3.2, mais relativisé à A.

**Solution 3.6.** Soit $f \leq_T G$ une fonction égale infiniment souvent à toute fonction A-calculable. Alors, $f+1$ est infiniment souvent au-dessus de toute fonction A-calculable.

**Solution 3.11.** La construction est similaire à celle de la preuve du théorème 3.9. On construit pour tout $e$ une fonction $\emptyset''$-calculable $f_e$, qui différera de $\Phi_e(X)$ pour tout $X$ dans un arbre $T: \mathbb{N}^{<\mathbb{N}} \to \mathbb{N}^{<\mathbb{N}}$, que l'on construit petit à petit.

Supposons à l'étape $s-1$ que $T$ est déjà défini sur les chaînes $\sigma_0, \dots, \sigma_s$, et que l'on a des réservoirs c. e. infinis $V_{t,s} \subseteq \mathbb{N}^{<\mathbb{N}}$ pour $t \leqslant s$. À l'étape $s = (e, i)$, à la sous-étape $t \leqslant s$, on demande à $\emptyset''$ s'il existe une infinité de chaînes $\mu \in V_{t,s}$ ayant une extension $\mu' \supseteq \mu$ pour laquelle $\Phi_e(\mu', i) \downarrow$ est égale à un nombre dont le $t$-ième bit est 0. Si la réponse est oui, alors $V_{t,s+1}$ est l'ensemble de ces extensions, et sinon $V_{t,s+1}$ est l'ensemble $V_{t,s}$ auquel on retire un nombre fini d'éléments de manière à ce que toutes les extensions possibles $\mu'$ restantes sur lesquelles $\Phi_e(\mu', i)$ s'arrête soient envoyées sur un nombre dont le $t$-ième bit est 1. Une fois la réponse obtenue pour tout $t \leqslant s$, on construit un nombre de $s$ bits qui diffère de tous les calculs possibles par un oracle de notre arbre. On définit alors $f_e(i)$ comme étant ce nombre.

**Solution 3.22.** Soit A un ensemble calculable, et soit W l'ensemble $\Sigma_1^0$

$$ \{(A \upharpoonright_n) \frown (1 - A(n)) : n \in \mathbb{N}\}. $$

Par construction, A ne possède aucun segment initial dans W, mais aucun segment initial de A n'évite W non plus. Ainsi, A ne possède pas de segment initial dans $W \cup W^{\perp}$, et A n'est donc pas 1-générique.

**Solution 3.23.** Étant donné une chaîne $\sigma$ et un ensemble c. e. $U \subseteq 2^{<\mathbb{N}}$, l'arrêt $\emptyset'$ peut répondre à la question de savoir si $\sigma$ a une extension dans $U$ est $\Sigma_1^0$. On construit ainsi aisément un ensemble générique $G \emptyset'$-calculable. Comme $G$ est 1-générique, alors $G' \leq_T G \oplus \emptyset' \equiv \emptyset'$. Donc, $G$ est low.

**Solution 3.25.** Rappelons que la fonction principale d'un ensemble infini $X$ donné par $\{a_0 < a_1 < \dots\}$ est la fonction $p_X$ qui à $i$ associe $a_i$. Soit $\Phi_e$ une fonctionnelle, et $i$ un entier. Considérons l'ouvert

$$ U_{e,i} = \left\{ \bigoplus_{n \in \mathbb{N}} X_n : \exists m \; \Phi_e \left( \bigoplus_{j \neq i} X_j, m \right) \downarrow < p_{X_i}(m) \right\}. $$

Supposons qu'il existe une chaîne $\sigma$ telle que $[\sigma] \cap U_{e,i} = \emptyset$. Montrons que l'on a nécessairement un entier $m$ tel que $\Phi_e(\bigoplus_{j \neq i} X_j, m) \uparrow$ pour tout $X = \bigoplus_{n \in \mathbb{N}} X_n$ tel que $\sigma \prec X$. Supposons, par l'absurde, le contraire. Soit $m > |\sigma|$. Alors, il existe $X = \bigoplus_{n \in \mathbb{N}} X_n$ avec $\sigma \prec X$ tel que $\Phi_e(\bigoplus_{j \neq i} X_j, m) \downarrow = k \in \mathbb{N}$.
Comme $[\sigma] \cap \mathcal{U}_{e,i} = \emptyset$, on a nécessairement $p_{X_i}(m) \le k$. Il suffit à présent de considérer $Y = \bigoplus_{n \in \mathbb{N}} Y_n$ tel que $Y_j = X_j$ pour $j \ne i$, $Y_i(m') = 0$ si $m \le m' \le k$, et $Y_i(m') = X_i(m')$ sinon. On a alors $\Phi_e(\bigoplus_{j \ne i} Y_j, m) \downarrow = k < p_{Y_i}(m)$, donc $Y \in \mathcal{U}_{e,i}$, et comme $Y \succ \sigma$, cela contredit notre hypothèse sur $\sigma$.

Ainsi, si $G = \bigoplus_{n \in \mathbb{N}} G_n$ est 1-générique, soit $G \in \mathcal{U}_{e,i}$, soit il existe un préfixe $\sigma < G$ tel que $[\sigma] \cap \mathcal{U}_{e,i} = \emptyset$, auquel cas il existe $m$ tel que $\Phi_e(\bigoplus_{j \ne i} G_j, m) \uparrow$.

**Solution 3.26.** La preuve est une adaptation de la direction (1) → (3) du théorème 3.2. Pour tout $i \in \mathbb{N}$, soit $f_i$ la fonction principale de $X_i$, c'est-à-dire la fonction qui à $n$ associe le $n$-ième élément de $X_i$. Notons que $f_i$ est croissante, et hyperimmune relativement à $\bigoplus_{j \ne i} X_j$. On calcule à partir de $X$ un ensemble 1-générique $G \in 2^{\mathbb{N}}$. Soit $(W_e)_{e \in \mathbb{N}}$ une énumération des sous-ensembles $\Sigma_1^0$ de $2^{\mathbb{N}}$. On construit $G$ par approximations successives $\sigma_0 \preceq \sigma_1 \preceq \sigma_2 \preceq \dots$.

On décrit d'abord une procédure récursive à effectuer à chaque fois que l'on veut
concaténer une chaîne $\tau$ à une chaîne $\sigma$ que l'on a jusqu'à présent calculé. Cette
procédure, que nous nommerons $R$, prend un troisième paramètre : un entier $e$
qui correspond au plus petit entier tel que $\sigma\tau$ est énuméré dans $W_e$ à l'étape de
calcul $f_e(|\sigma|)$. On notera $R(\sigma, \tau, e)$ pour le résultat de l'appel à cette procédure.
Notons enfin que certains entiers sont marqués comme $\ll$ satisfaits $\gg$ au moment
où la procédure est appelée : ce sont les entiers $e$ tels que $\sigma$ étend une chaîne
de $W_e$ à l'étape de calcul courante.

La procédure $R(\sigma, \tau, e)$ fait la chose suivante : pour chaque préfixe $\tau' \preceq \tau$ dans l'ordre, elle cherche le plus petit entier $e' < e$ qui n'est pas satisfait et tel qu'une chaîne de la forme $\sigma\tau'\rho$ soit énumérée dans $W_{e'}[f_{e'}(|\sigma\tau'|)]$. Si un tel entier est trouvé, la procédure renvoie alors le résultat de l'appel récursif à $R(\sigma\tau', \rho, e')$. Sinon, elle renvoie $\sigma\tau$. Notons que la diminution de la valeur du dernier paramètre dans les appels récursifs fait que la procédure s'arrête nécessairement.

À l'étape 0, on définit $\sigma_0 = \epsilon$. Supposons $\sigma_t$ défini à l'étape $t$. À l'étape $t+1$, on cherche le plus petit entier $e \le t+1$ non satisfait tel qu'une chaîne de la forme $\sigma_t\tau$ soit énumérée dans $W_e[f_e(|\sigma_t|)]$. Si l'on trouve un tel entier $e$, on définit $\sigma_{t+1}$ comme étant $R(\sigma_t, \tau, e)$. Sinon, $\sigma_{t+1}$ comme étant $\sigma_0$. Cela conclut la construction.

Supposons par l'absurde que $G$ n'est pas 1-générique. Soit $e$ le plus petit entier tel que $W_e$ est un ensemble dense le long de $G$. Dans ce cas, la fonction $f_e$ n'a aucun impact sur la construction, qui est alors $\bigoplus_{j \ne e} X_j$-calculable. En particulier, $f_e$ est $G$-hyperimmune. Soit $h$ la fonction totale $G$-calculable qui à $n$ associe le plus petit temps de calcul $t$ tel que $W_e$ énumère une chaîne étendant $G \upharpoonright_n$. Comme $f_e$ est $G$-hyperimmune, il existe une infinité de valeurs $n$ telles que $f_e(n) > h(n)$.

Soit $t$ tel que tous les entiers $e' < e$ qui sont satisfaits à un moment de la construction sont satisfaits au temps $t$. Soit $n$ le plus petit entier supérieur ou égal à $|\sigma_t|$ tel que $f_e(n) > h(n)$. Soit $s \ge t$ le plus petit entier tel que $|\sigma_s| \le n < |\sigma_{s+1}|$. Si $|\sigma_s| = n$, alors par minimalité de $e$ l'algorithme définit $\sigma_{s+1} = \sigma_s\tau$ avec $\sigma_s\tau$ dans $W_e[f_e(n)]$. Sinon, alors par construction au moment de définir $\sigma_{s+1} = \sigma_s\tau$
pour une certaine chaîne $\tau$, l'algorithme vérifie pour tout préfixe $\tau' \preceq \tau$, que l'on n'a pas une extension de $\sigma_s\tau'$ énumérée dans $W_e[f_e(|\sigma_s\tau'|)]$, et en particulier pour le préfixe $\tau'$ tel que $|\sigma_s\tau'| = n$. Si c'est le cas, l'algorithme est relancé sur cette extension. Comme c'est effectivement le cas par hypothèse, et par minimalité de $e$, on aura en fait $\sigma_s\tau \in W_e[f_e(n)]$ pour $\sigma_{s+1} = \sigma_s\tau$. On en conclut que $W_e$ n'est pas dense le long de $G = \sigma_0 < \sigma_1 < \sigma_2 < \dots$, donc que l'ensemble $G$ est bien 1-générique.

**Solution 3.30.** Montrons qu'il existe un ensemble faiblement 1-générique relativement à $A$ et approchable par la gauche relativement à $A$. Soit $(W_n)_{n \in \mathbb{N}}$ une énumération des ensembles de chaînes $\Sigma_1^0(A)$.

À l'étape $s$, on calcule à l'aide de $A$ une chaîne $\sigma_{n,s}$ pour tout $n \le s$, telle que $\sigma_{n,s} < \sigma_{n+1,s}$ pour tout $n < s$ et telle que $\sigma_{n,s-1}$ est lexicographiquement plus petit ou égal à $\sigma_{n,s}$. À l'étape $s=0$, on définit $\sigma_{0,0}$ comme étant la chaîne $0$. Supposons $\sigma_{n,s}$ défini à l'étape $s$ pour tout $n \le s$. À l'étape $s+1$, soit $n \le s$ le plus petit tel que $\sigma_{n,s}$ est de la forme $\tau 0$ et tel qu'il existe une extension $\tau 1 \rho$ de $\tau 1$ dans $W_n[s+1]$. Si aucun tel entier $n$ n'existe, alors $\sigma_{n,s+1} = \sigma_{n,s}$ pour $n \le s$, et l'on définit $\sigma_{s+1,s+1} = \sigma_{s,s+1}0$.

Sinon, on définit $\sigma_{i,s+1} = \sigma_{i,s+1}$ pour $i < n$, $\sigma_{n,s+1} = \tau 1 \rho$ et $\sigma_{i+1,s+1} = \sigma_{i,s+1}0$ pour $s+1 \ge i \ge n$. On laisse au lecteur le soin de vérifier que $\lim_{s \to +\infty} \sigma_{n,s} = \sigma_n$ est bien défini et que l'unique élément $G \in \bigcap_n[\sigma_n]$ est bien approchable par la gauche relativement à $A$ et faiblement 1-générique relativement à $A$.

Montrons qu'aucun ensemble faiblement 1-générique relativement à $A$ n'est approchable par la gauche relativement à $A$. Soit $(X_s)_{s \in \mathbb{N}}$ une approximation par la gauche relativement à $A$ d'un ensemble $X$. On peut supposer sans perte de généralité $X_s \ne X_{s+1}$. Pour tout $s$, soit $n_s$ le plus petit entier tel que

$$X_s \upharpoonright_{n_s+1} \ne X_{s+1} \upharpoonright_{n_s+1}.$$

Notons que l'on a nécessairement $X_s(n_s) = 0$ et $X_{s+1}(n_s) = 1$. On énumère dans $W$ — un ensemble A-c. e. — la chaîne $X_s \upharpoonright_{n_s+1}$ pour tout $s$. On laisse au lecteur le soin de vérifier que $W$ est dense le long de $G$ sans jamais rencontrer $G$.

# Chapitre 11

**Solution 1.7.** Soit $Q = \{d \in \mathbb{P} : d \text{ et } c \text{ sont incompatibles}\}$. Montrons que $D \cup Q$ est dense. Soit $d \in \mathbb{P}$.

Cas 1. Les conditions $d$ et $c$ sont incompatibles, auquel cas $d \in Q$.

Cas 2. Il existe $d' \le d, c$. Sachant que $D$ est dense sous $c$, il existe $e \le d'$ tel que $e \in D$. En particulier, $e \le d$ et $e \in D \cup Q$. Ainsi, $D \cup Q$ est dense. Sachant que $F$ est suffisamment générique, il intersecte $D \cup Q$. S'il contient $c$, alors par définition d'un filtre, tous les éléments de $F$ sont compatibles avec $c$, donc $F \cap Q = \emptyset$. Il s'ensuit que $F$ intersecte $D$.
**Solution 2.4.** Soit $F$ un filtre suffisamment générique contenant $c$, et soit
$$D = \{d \in \mathbb{P} : d \text{ force } \mathcal{R}\}.$$

Par l'exercice 1.7, $F$ intersecte l'ensemble $D$, donc $\dot{F}$ satisfait $\mathcal{R}$. Il s'ensuit que $c$ force $\mathcal{R}$.

**Solution 2.8.** Par induction sur la complexité de $\mathcal{R}$.

Cas 1. Le contrat $\mathcal{R}$ est $\Sigma_1^0$ ou $\Pi_1^0$. Par définition, pour tout $X \in [c]$, $\mathcal{R}(X)$ est vrai. Comme $d \le c$, alors $[d] \subseteq [c]$, donc pour tout $X \in [d]$, $\mathcal{R}(X)$ est vrai. Ainsi, $d \Vdash^* \mathcal{R}$.

Cas 2. Le contrat $\mathcal{R}$ est de la forme $\exists x \mathcal{S}(x)$ où $\mathcal{S}(x)$ est $\Pi_k^0$ pour $k \ge 1$. Par définition, il existe $n \in \mathbb{N}$ tel que $c \Vdash^* \mathcal{S}(n)$. Par hypothèse d'induction, $d \Vdash^* \mathcal{S}(n)$, donc $d \Vdash^* \exists x \mathcal{S}(x)$.

Cas 3. Le contrat $\mathcal{R}$ est de la forme $\forall x \mathcal{S}(x)$, où $\mathcal{S}(x)$ est $\Sigma_k^0$ pour $k \ge 1$. Alors, $c \Vdash^* \mathcal{R}$ implique $\forall e \le c \ exists \ \neg \mathcal{R}$ implique $\forall e \le d \ exists \ \neg \mathcal{R}$ implique $d \Vdash^* \mathcal{R}$.

**Solution 2.9.** Par induction sur la complexité de $\mathcal{R}$, et soit
$$U = \{c \in \mathbb{P} : c \Vdash^* \mathcal{R} \text{ ou } c \Vdash^* \neg \mathcal{R}\}.$$

On peut supposer que $\mathcal{R}$ est $\Sigma_n^0$ (sinon, on répète l'argument avec $\neg \mathcal{R}$ à la place de $\mathcal{R}$). Étant donné une condition $c$, soit il existe une extension de $d \le c$ telle que $d \Vdash^* \mathcal{R}$, soit $\forall d \le c \ d \ exists \ \neg \mathcal{R}$ auquel cas $c \Vdash^* \neg \mathcal{R}$.

**Solution 2.10.** Par induction sur la complexité de $\mathcal{R}$.

Cas 1. Le contrat $\mathcal{R}$ est $\Sigma_1^0$ ou $\Pi_1^0$. Supposons que $c \Vdash^* \mathcal{R}$. Pour tout filtre maximal $F$ contenant $c$, comme $\dot{F} \in [c]$, alors $\dot{F}$ satisfait $\mathcal{R}$, donc $c \Vdash \mathcal{R}$.

Cas 2. Le contrat $\mathcal{R}$ est de la forme $\exists x \mathcal{S}(x)$. Supposons que $c \Vdash^* \exists x \mathcal{S}(x)$. Par définition, il existe un $n \in \mathbb{N}$ tel que $c \Vdash^* \mathcal{S}(n)$. Par hypothèse d'induction, $c$ force $\mathcal{S}(n)$, donc $c \Vdash \exists x \mathcal{S}(x)$.

Cas 3. Le contrat $\mathcal{R}$ est de la forme $\forall x \mathcal{S}(x)$. Supposons que $c \Vdash^* \forall x \mathcal{S}(x)$. Par définition, pour tout $d \le c$ et $n \in \mathbb{N}$, $d \Vdash^* \neg \mathcal{S}(n)$. Par l'exercice 2.9, pour tout $n$, l'ensemble $\{d \in \mathbb{P} : d \Vdash^* \mathcal{S}(n)\}$ est dense sous $c$. Soit $F$ un filtre suffisamment générique contenant $c$. En particulier, pour tout $n \in \mathbb{N}$, il existe $d \in F$ tel que $d \Vdash^* \mathcal{S}(n)$. Par hypothèse d'induction, $d \Vdash \mathcal{S}(n)$, donc $\dot{F}$ satisfait $\mathcal{S}(n)$. Il s'ensuit que $\dot{F}$ satisfait $\forall x \mathcal{S}(x)$, donc $c \Vdash \forall x \mathcal{S}(x)$.

**Solution 3.3.** Il suffit de montrer que $G$ est différent d'un ensemble $A$ quelconque fixé à l'avance. Soit $T: 2^{<\mathbb{N}} \to 2^{<\mathbb{N}}$ un f-arbre calculable. En particulier, $T(0)$ et $T(1)$ sont incomparables, donc il existe $i < 2$ tel que $T(i)$ est incomparable avec $A$. Le f-arbre $S: 2^{<\mathbb{N}} \to 2^{<\mathbb{N}}$ défini par $S(\sigma) = T(i\sigma)$ est un sous-f-arbre calculable de $T$ tel que pour tout $P \in [S]$, $P \ne A$.

**Solution 3.5.** Soit $T: 2^{<\mathbb{N}} \to 2^{<\mathbb{N}}$ une condition du forcing de Sacks et soit $\Phi_e$ une fonctionnelle. Supposons que pour tout $n$ il existe $i_n$ tel que pour tout $\sigma \in$
$2^{<\mathbb{N}}$, on a $\Phi_e(T(\sigma), n) \downarrow \Phi(T(\sigma), n) \downarrow= i_n$. Alors, si $\Phi_e$ est totale sur $X \in [T]$, on a nécessairement $\Phi_e(X) = Y$, avec $Y(n) = i_n$ pour tout $n$. Un tel ensemble $Y$ est calculable, car il suffit pour connaître $Y(n)$ de chercher $\sigma \in 2^{<\mathbb{N}}$ tel que $\Phi_e(T(\sigma), n) \downarrow$. Donc, $\Phi_e(X) \neq A$. En particulier, $\Phi_e(X) \neq A$, pour tout $X \in [T]$.

Sinon, il existe $n$ et $\sigma_1, \sigma_2 \in 2^{<\mathbb{N}}$ tels que $\Phi_e(T(\sigma_1), n) \downarrow \neq \Phi_e(T(\sigma_2), n) \downarrow$. On peut considérer sans perte de généralité $\Phi_e(T(\sigma_1), n) \downarrow \neq A(n)$. On prend alors l'extension $S \leq T$ définie par $S(\tau) = T(\sigma_1\tau)$.

L'ensemble des conditions $T$ telles que

$$T \Vdash^* \exists n \Phi_e(G, n) \uparrow \text{ ou } \exists n T \Vdash^* \Phi_e(G, n) \downarrow \neq A(n)$$

est dense. Donc, si $G$ est suffisamment générique pour le forcing de Sacks, il ne calcule pas $A$.

### Solution 3.6.

1. Soit $T: 2^{<\mathbb{N}} \to 2^{<\mathbb{N}}$ une condition du forcing de Sacks et soit $\Phi_e$ une fonctionnelle. Si $\exists n \exists \sigma \forall \tau \supseteq \sigma \Phi_e(T(\tau), n) \uparrow$, on considère l'extension $S \leq T$ définie par $S(\rho) = T(\sigma\rho)$. On force ainsi la partialité de $\Phi_e$.

Sinon, $\forall n \forall \sigma \exists \tau \supseteq \sigma \Phi_e(T(\tau), n) \downarrow$, on construit une condition $S \leq T$ telle que $\Phi_e(S(\sigma), |\sigma|) \downarrow$ pour tout $\sigma \in 2^{<\mathbb{N}}$. La taille de l'ensemble $T_n$ des valeurs calculées par des chaînes $S(\sigma)$, pour $\sigma$ de taille $n$, est bornée par $2^n$.

2. Soit $X$ calculatoirement traçable avec borne calculable $h$. Soit $h'$ comme dans l'énoncé. Soit $(A_n)_{n \in \mathbb{N}}$ une suite d'intervalle consécutifs formant une partition de $\mathbb{N}$ et telle que $h(\min A_n) < h'(\max A_n)$. On note $\langle f(x) \rangle_{x \in A_n}$ pour l'entier $\langle f(x_0), \dots, f(x_k) \rangle$, où $x_0, \dots, x_k$ sont les éléments de $A_n$.

Étant donné $f \leq_T X$, on considère $g \leq_T f$ défini par $g(n) = \langle f(x) \rangle_{x \in A_n}$. Soit $(T_n)_{n \in \mathbb{N}}$ une trace de $g$ avec $|T_n| \leq h(n)$. On peut décomposer la trace $(T_n)_{n \in \mathbb{N}}$ en une trace $(S_n)_{n \in \mathbb{N}}$ pour la fonction $f$ qui sera alors telle que $|S_n| \leq h'(n)$ pour $n > 0$ (car on a $h(\min A_n) < h'(\max A_n)$).

3. Pour chaque condition $T$, l'ensemble $[T]$ des chemins de $T$ contient des fonctions $f: \mathbb{N} \to \mathbb{N}$ avec $f(n) < 2^n$. L'objectif est de montrer que si une telle fonction $g$ est suffisamment générique, alors elle sera calculatoirement dominée, et pour toute trace $(T_n)_{n \in \mathbb{N}}$ telle que $|T_n| \leq n$, on aura $g(m) \notin T_m$ pour un certain $m$. D'après (2), cela est suffisant pour montrer que l'ensemble $X_g \in 2^\mathbb{N}$ qui encode $g$ n'est pas calculatoirement traçable, car $X_g$ calcule $g$ qui n'admet de pas trace $(T_n)_{n \in \mathbb{N}}$ avec $|T_n| \leq n$.

La manière de forcer l'ensemble à être calculatoirement dominé est similaire à celle du forcing de Sacks : soit il existe $n \in \mathbb{N}$ et il existe $\sigma \in T$ tels que $\forall \tau \supseteq \sigma$ avec $\tau \in T$ on a $\Phi_e(\tau, n) \uparrow$, auquel cas $S=T\uparrow_\sigma$ est une extension qui force la partialité, soit pour tout $n \in \mathbb{N}$ et pour tout $\sigma \in T$ il existe $\tau \supseteq \sigma$ avec $\tau \in T$ tel que $\Phi_e(\tau, n) \downarrow$. Dans ce cas, pour tout nœud $\sigma \in T$ à branchement maximal on peut trouver pour tout $i < 2^{|\sigma|}$ des extensions $\tau_i \supseteq \sigma i$ telles que $\Phi_e(\tau_i, n) \downarrow$. On utilise cela pour construire une extension $S \subseteq T$ telle que $\Phi_e$ est totale sur les chemins de $[S]$, ainsi qu'une fonction calculable bornant $n \mapsto \Phi(X, n)$ pour tout $X \in [S]$.
Par nature des conditions de forcing, étant donné une trace calculable $(T_n)_{n \in \mathbb{N}}$ avec $|T_n| \le n$, on a une chaîne $\tau \in T$ telle que $\tau i \in T$ et $i \notin T|_{\tau}|$. On peut alors étendre $T$ en la condition $S \subseteq T$ des éléments de $T$ compatibles avec $\tau i$, afin de forcer à ne pas être tracé par $(T_n)_{n \in \mathbb{N}}$.

**Solution 4.4.** (a) Soit $T \in \mathbb{P}$ et soit $\sigma \in 2^{<\mathbb{N}}$ tels que $[T] \cap [\sigma] \neq \emptyset$. Soit $S = \{\tau \in T : \tau \supseteq \sigma \lor \tau \prec \sigma\}$. Alors, $S$ est une extension de $T$ telle que $[S] \subseteq [\sigma]$. Ainsi, $(\mathbb{P}, \leqslant)$ est un forcing de Cantor.

(b) Montrons que pour tout filtre $F \subseteq \mathbb{P}$ suffisamment générique pour $\mathbb{P}$, le filtre $\widehat{F} = \{[T] : T \in F\}$ est suffisamment générique pour le forcing de Jockusch-Soare. Soit $\widehat{D}$ un ensemble dense dans le forcing de Jockusch-Soare. Montrons que $D = \{T \in \mathbb{P} : [T] \in \widehat{D}\}$ est dense dans $\mathbb{P}$. Soit $T \in \mathbb{P}$. Par densité de $\widehat{D}$, il existe une classe $\Pi_1^0 C \subseteq [T]$ telle que $C \in \widehat{D}$. Par la proposition 8-3.3, il existe un arbre infini calculable $S \subseteq 2^{<\mathbb{N}}$ tel que $[S] = C$. Notons que $S \cap T$ est également un arbre infini calculable tel que $[S \cap T] = C$ et tel que $S \cap T$ est une extension de $T$. Donc, $D$ est dense dans $\mathbb{P}$. Il s'ensuit que tout ensemble suffisamment générique pour $\mathbb{P}$ est suffisamment générique pour le forcing de Jockusch-Soare.

Montrons que pour tout filtre $\widehat{F}$ suffisamment générique pour le forcing de Jockusch-Soare, $F = \{T \in \mathbb{P} : [T] \in \widehat{F}\}$ est suffisamment générique pour $\mathbb{P}$. Soit $D \subseteq \mathbb{P}$ un ensemble dense pour $\mathbb{P}$. Montrons que $\widehat{D} = \{[T] : T \in D\}$ est dense pour le forcing de Jockusch-Soare. Soit $C \subseteq 2^{<\mathbb{N}}$ une classe $\Pi_1^0$ non vide. Par la proposition 8-3.3, il existe un arbre infini calculable $T \subseteq 2^{<\mathbb{N}}$ tel que $[T] = C$. Par densité de $D$, il existe une extension $S$ de $T$ dans $D$. En particulier, $[S]$ est une extension de $C$ dans $\widehat{D}$, donc $\widehat{D}$ est dense. Il s'ensuit que tout ensemble suffisamment générique pour le forcing de Jockusch-Soare est suffisamment générique pour $\mathbb{P}$.

(c) Soit $T \in \mathbb{P}$ un arbre calculable infini, et soit $S = \{\sigma \in T : \forall n < |\sigma| \Phi(\sigma, n) \uparrow\}$. Si $S$ est infini, alors $S$ est une extension de $T$ tel que $S|^{\prec\circ} \forall n \Phi(G, n) \uparrow$. Si $S$ est fini, soit $t$ suffisamment grand tel qu'aucune chaîne de longueur $t$ est dans $S$. Alors, pour tout $\sigma \in T$ de longueur $t$, $\exists n < t \Phi(\sigma, t) \downarrow$, donc $T|^{\prec\circ} \exists n \Phi(G, n) \downarrow$.

(d) Immédiat.

**Solution 4.7.**

1. Nous allons définir à chaque étape $s$ un arbre parfait $T_s \subseteq 2^{<\mathbb{N}}$ calculable uniformément en $s$, avec $T_{s+1} \subseteq T_s$. Étant donné un arbre parfait $T$, on définit $T|_n$ comme étant la clôture par préfixe de l'ensemble des chaînes $\sigma \in T$ ayant exactement $n$ préfixes branchants dans $T$. Ainsi, $T|_n$ est un arbre fini avec $2^n$ feuilles.

Soit $(P_e)_{e \in \mathbb{N}}$ une énumération des classes $\Pi_1^0$. À l'étape 0, on définit $T_0 = 2^{<\mathbb{N}}$. Supposons $T_s$ défini à l'étape $s$. À l'étape $s+1$, on considère le plus petit entier $e \le s+1$ tel que pour une feuille $\sigma \in T_s|_e$ on a $P_e[s+1] \cap [\sigma] \neq \emptyset$ et $P_e[s+1] \cap [\sigma] \subsetneq [T_s] \cap [\sigma]$. Si un tel $e$ et une telle chaîne $\sigma$ existent, on définit alors $\tau$ comme étant une extension de $\sigma$ appartenant à $T_s$ et telle que $P_e[s+1] \cap [\tau] = \emptyset$, puis on définit $T_{s+1}$ comme la réunion de toutes les
chaînes de $T_s$ incomparables avec $\sigma$, et de toutes les chaînes de $T_s$ comparables avec $\tau$. On dit alors que $\ll T_s$ est modifié à cause de $\mathcal{P}_e$. Cela conclut la construction.

Étant donné un entier $n$, on notera $s_n$ le plus petit temps de calcul tel que $T_{s_n} \upharpoonright_n = T_t \upharpoonright_n$ pour tout $t \ge s_n$. Montrons par induction sur $n$ que $s_n$ existe pour tout $n$. Une seule modification peut arriver à cause de $\mathcal{P}_0$: celle du premier nœud branchant $\sigma \in T_t \upharpoonright_0$. Si la modification arrive bien à une étape $t$, on a alors $\mathcal{P}_0[t+1] \cap [\sigma] = \emptyset$ pour $\sigma$ l'unique feuille de $T_{t+1} \upharpoonright_0$, et par construction aucune autre modification n'arrivera à cause de $\mathcal{P}_0$, parce que $\mathcal{P}_0[t] \cap [\sigma] = \emptyset$. De plus, une modification due à $\mathcal{P}_e$ pour $e > 0$ se fait sur des feuilles de $T_t \upharpoonright_e$, et laisse donc $T_t \upharpoonright_0$ inchangé. Donc, $s_0 = t + 1$. En itérant cette idée et en utilisant le fait que $\mathcal{P}_e$ ne peut apporter au plus que $2^e$ modifications sur $T_t \upharpoonright_e$ pour $t \ge s_{e-1}$, on arrive à la conclusion. On en déduit que $T = \bigcap_s T_s$ est un arbre parfait, et que $[T]$ est donc une classe $\Pi_1^0$ parfaite.

Montrons que $[T]$ est fine. Soit $\mathcal{P}_e$ une classe $\Pi_1^0$ telle que $\mathcal{P}_e \subseteq [T]$. Supposons par l'absurde $\mathcal{P}_e \cap [\sigma_i] \ne \emptyset$ et $\mathcal{P}_e \cap [\sigma_i] \subsetneq [T] \cap [\sigma_i]$ pour un certain $\sigma_i \in T \upharpoonright_e$. Alors, cela doit être détecté à une certaine étape $t > s_e$, auquel cas par construction $T_{t+1} \upharpoonright_e \ne T_t \upharpoonright_e$, ce qui contredit la définition de $s_e$.

2. Soit $\mathcal{P}$ une classe $\Pi_1^0$ fine, et soit $X \in \mathcal{P}$. Étant donné une fonctionnelle $\Phi_e$ soit $Q = \{Y \in \mathcal{P} : \Phi_e(Y, e) \upharpoonright\}$. À l'aide de $\emptyset'$, on détermine d'abord si $Q$ est vide. Si c'est bien le cas, alors $e \in Y'$. Sinon, on cherche à l'aide de $\emptyset''$ des chaînes $\sigma_0, \dots, \sigma_n$ telles que $Q = \mathcal{P} \cap ([\sigma_0] \cup \dots \cup [\sigma_n])$. Une fois de telles chaînes trouvées, on vérifie si l'une d'elles est un préfixe de $Y$. Si c'est le cas, alors $e \notin Y'$, sinon $e \in Y$.

**Solution 4.8.** Notons d'abord que toute classe de contenant que des aléatoires de Martin-Löf est de mesure positive. L'idée est de répéter la preuve du théorème 4.6 en utilisant le lemme 18-3.3, afin de construire dans toute classe $\Pi_1^0$ $\mathcal{P}$ de mesure positive une sous-classe $\Pi_1^0 S \subseteq \mathcal{P}$ parfaite telle que, pour toute chaîne $\sigma$ pour laquelle $S \cap [\sigma] \ne \emptyset$, il existe $\tau \supseteq \sigma$ pour laquelle $S \cap [\tau] = \emptyset$ et $\mathcal{P} \cap [\tau] \ne \emptyset$.

**Solution 4.17.** Montrons que $c?\vdash \mathcal{R}$ satisfait les propriétés (1) et (2) de la définition d'une question de forcing.

(1) Cette propriété est vérifiée par définition de $c?\vdash \mathcal{R}$.

(2) Si $c?\nvdash \mathcal{R}$, alors pour toute extension $d \le c$, il vient $d \not\vdash \mathcal{R}$. Comme l'ensemble $\{d : d \vdash \mathcal{R} \text{ ou } d \vdash \neg \mathcal{R}\}$ est dense, il existe une extension $d \le c$ telle que $d \vdash \neg \mathcal{R}$. Autrement dit, $c?\vdash \neg \mathcal{R}$.

**Solution 4.26.** La preuve est exactement celle de la proposition 4.25, où l'on ne se restreint plus aux fonctions à valeurs dans $\{0, 1\}$. On évite donc de calculer une fonction DNC à valeurs arbitraires. Dans le cas 1, on se retrouve avec une quantité dénombrable de propriétés $\neg(\Phi_e^{G^{(n)}}(m) \downarrow = v)$ pour $v \in \mathbb{N}$ à forcer simultanément, ce qui est possible, car la question de forcing est $\Pi_\omega$-fusionnable.
# Chapitre 14

**Solution 1.10.** Il suffit de considérer le chemin $X$ le plus à gauche de la classe. Ce chemin-ci est approchable par la gauche, et il permet de calculer l'ensemble c. e. $\{\sigma \in 2^{<N} : \sigma$ est lexicographiquement à gauche de $X\}$. Notons que cet ensemble permet de recalculer $X$. Si une classe $\Pi_1^0$ ne contient que des ensembles de degrés minimaux, alors son chemin le plus à gauche est non calculable, et permet donc de calculer un ensemble c. e. non calculable, qui n'est alors pas de degré minimal : contradiction !

**Solution 1.12.** Il suffit de considérer la classe

$$ \{X \oplus Y : \forall t \forall e \Phi_e(e)[t] \neq X(e) \wedge \Phi_e(Y,e)[t] \neq Y(e)\}. $$

Les membres $X \oplus Y$ de cette classe sont tous ceux tels que $X$ est de degré $\text{DNC}_2$ et $Y$ de degré $\text{DNC}_2$ relativement à $X$. En particulier, par l'exercice 8-7.6, $Y \geq_T X$, mais $X \not\leq_T Y$.

# Chapitre 16

**Solution 1.7.** Il s'agit d'un cas particulier du lemme 4-7.2 de Schoenfield, mais appliqué à des fonctions plutôt que des ensembles d'entiers.

**Solution 1.9.** Soit $f \geq \Sigma$. Alors, $U(\sigma) \downarrow$ ssi $U(\sigma)[f(|\sigma|)] \downarrow$. Donc, $f$ permet de calculer $U$, et donc aussi $\emptyset'$.

**Solution 1.10.** Montrons que pour $n$ suffisamment grand, il existe une chaîne de taille $2n$, de complexité inférieure à $2n$ mais telle qu'aucun programme de taille inférieure à $2n$ ne peut la calculer en un temps inférieur à $\Sigma(n)$. Étant donné $n$, soit $\sigma_n$ le « castor affairé » pour $n$, c'est-à-dire avec $|\sigma_n| \leq n$ et $\Sigma(n) = t$, où $t$ est le plus petit temps de calcul tel que $U(\sigma_n)[t] \downarrow$. Pour $n$ fixé, on considère la plus petite chaîne $\tau_n$ correspondant au programme qui cherche le plus petit temps de calcul $t$ tel que $U(\sigma_n)[t] \downarrow$, qui calcule $U(\rho)[t]$ pour toute chaîne $\rho$ de taille strictement inférieure à $2n$, et écrit finalement une chaîne de taille $2n$ qui n'est pas produite par un tel programme. Comme $\sum_{i<2n} 2^i = 2^{2n} - 1$, une telle chaîne de taille $2n$ existe nécessairement.

Pour $n$ suffisamment grand, la taille de $\tau_n$ est plus petite que $2n$, puisque l'information nécessaire pour ce programme est une chaîne de taille inférieure ou égale à $n$, la connaissance de $n$ qui est de l'ordre de $\log_2(n)$, et le reste du programme qui est constant pour tout $n$. En particulier, pour $\sigma$ tel que $U(\tau_n) \downarrow= \sigma$, on a donc $C(\sigma) < 2n$. Aussi, par construction, aucun programme de taille inférieure à $2n$ ne peut produire $\sigma$ en temps de calcul inférieur à $\Sigma(n)$. On peut donc calculer une borne de $\Sigma(n)$ à partir de la connaissance de $C$, en regardant pour tout $n$ suffisamment grand la complexité de toutes les chaînes de taille $2n$, en cherchant pour chacune d'entre elles le plus petit programme permettant de les produire,
puis en considérant le plus petit temps de calcul utilisé alors. Ce temps de calcul
borne nécessairement $\Sigma(n)$. Par (1), on peut donc calculer $U$.

**Solution 1.11.** Soit $c$ la constante telle que $C(\sigma) \le |\sigma| + c$, pour toute chaîne $\sigma$. Il suffit alors d'utiliser le théorème de la base low sur la classe $\Pi_1^0$ suivante :

$$
\mathcal{P} = \{I : 2^{<\mathbb{N}} \to 2^{<\mathbb{N}} : (\forall \sigma |I(\sigma)| \le |\sigma| + c) \wedge (\forall t \forall \sigma |I(\sigma)| \le C(\sigma)[t])\}.
$$

Notons que la condition $\forall \sigma |I(\sigma)| \le |\sigma| + c$ n'est pas en soi absolument nécessaire,
mais il s'agit d'insister sur le fait que l'arbre calculable dont les chemins infinis
sont les éléments de $\mathcal{P}$ est calculatoirement borné (voir la définition 8-7.7).

**Solution 1.14.** Soit $M$ le programme qui sur une chaîne $\sigma$ renvoie la chaîne $\sigma'U(\sigma)$, où $\sigma'$ est la représentation binaire de $|U(\sigma)|$, et soit $c$ tel que $C(\sigma) < C_M(\sigma) + c$ pour toute chaîne $\sigma$. Soit $d$ tel que $C(\sigma) \le |\sigma| + d$ pour toute chaîne $\sigma$.

Soit $\sigma$ une chaîne de taille supérieure à $c+d+k+2^{k+c+d}$, et soit $\tau \prec \sigma$ un préfixe de taille $c+d+k$. Soit $n$ l'entier codé par $\tau$. Soit $\rho$ de taille $n$ tel que $\tau\rho \preceq \sigma$. Alors, $C_M(\tau\rho) = C(\rho) \le |\rho| + d = (|\tau\rho| - k - c - d) + d = |\tau\rho| - k - c$. Donc, $C(\tau\rho) \le |\tau\rho| - k$.

**Solution 1.15.** Fixons $k$, et trouvons des chaînes $\sigma, \tau$ telles que

$$
C(\tau\rho) \ge C(\tau) + C(\rho) + k.
$$

Soit $c$ la constante telle que $C(\sigma) \le |\sigma| + c$, pour toute chaîne $\sigma$. Considérons alors une chaîne $\sigma$ telle que $C(\sigma) \ge |\sigma|$ et pour laquelle on a un préfixe $\tau$ tel que $C(\tau) \le |\tau| - k - c$, et soit $\rho$ tel que $\sigma = \tau\rho$. On a alors

$$
C(\tau\rho) \ge |\sigma| = |\tau| + |\rho| \ge (C(\tau) + k + c) + C(\rho) - c = C(\tau) + C(\rho) + k.
$$

Enfin, il est clair que $C(\langle\tau, \rho\rangle) \ge^+ C(\tau\rho)$ pour toutes chaînes $\sigma, \tau$. Donc, également pour tout $k$ il existe des chaînes $\tau, \rho$ telles que $C(\langle\tau, \rho\rangle) \ge C(\tau) + C(\rho) + k$.

**Solution 2.3.** On définit la machine $M$ telle que $M(\sigma) = f(U(\sigma))$. Ainsi,

$$
K(f(\tau)) \le {}^+ K_M(f(\tau)) \le {}^+ K(\tau),
$$

pour toute chaîne $\tau$.

**Solution 2.6.** On définit la machine $M$ telle que $M(\sigma)$ cherche $\tau, \rho$ pour les quelles $\tau\rho = \sigma$ et telles que $U(\tau) = |\rho|$. La machine renvoie alors $\rho$. Notons que si de telles chaînes $\tau, \rho$ existent, elles sont uniques, car $U$ est sans préfixe. La machine $M$ est elle aussi sans préfixe : si $M(\tau\rho) \downarrow$, cela signifie $U(\tau) = |\rho|$. Si à présent $M(\tau\rho') \downarrow$ pour $\rho' \prec \rho$ ou $\rho \prec \rho'$, cela signifierait aussi $U(\tau) = |\rho'| \neq |\rho|$, ce qui est impossible. On obtient enfin l'inégalité $K(\sigma) \le^+ |\sigma| + K(|\sigma|)$ via la machine $M$.

Soit $\log_2^{(n)}(\sigma)$ l'application $n$ fois de $\log_2$ à $\sigma$. Si l'on répète l'inégalité récursive-
ment, alors pour tout $n$ on a $K(\sigma) \le^+ |\sigma| + \sum_{k=1}^n \log^{(n)}(|\sigma|) + K(\log^{(n)}(|\sigma|)),$
pour tout $\sigma$. Pour $n = 1$, cela nous donne

$$ 
\begin{aligned}
K(\sigma) &\leq^{+} |\sigma| + \log_2(|\sigma|) + K(\log_2(|\sigma|)) \\
&\leq^{+} |\sigma| + \log_2(|\sigma|) + \log_2(\log_2(|\sigma|)) + 2\log_2(\log_2(\log_2(|\sigma|))),
\end{aligned}
$$

ce qui est bien une amélioration.

**Solution 2.7.** Supposons $K(\sigma) < |\sigma| + c$, pour toute chaîne $\sigma$. Pour $n$ fixé, on a $\sum_{|\sigma|=n} 2^{-K(\sigma)} > \sum_{|\sigma|=n} 2^{-|\sigma|-c} = 2^{-c} \sum_{|\sigma|=n} 2^{-|\sigma|} = 2^{-c}$. Pour $n = 2^c+1$, on a alors $\sum_{|\sigma|\le n} 2^{-K(\sigma)} = n2^{-c} > 1$, ce qui est une contradiction.

**Solution 2.11.** Soit $T$ un arbre calculable tel que $[T]$ sont les chemins de $\mathcal{P}$. Alors, le plus petit chemin de $[T]$ pour l'ordre lexicographique est approchable par la gauche : il est approximé par $\sigma_t 0^\infty$ pour $\sigma_t$ le nœud de taille $t$ le plus à gauche de $T$.

**Solution 4.7.** Cela découle simplement de la proposition 2.4, qui implique

$$ K(\sigma_0 \oplus \sigma_1) =^+ K(\langle \sigma_0, \sigma_1 \rangle) \leq^+ K(\sigma_0) + K(\sigma_1), $$

pour toutes chaînes $\sigma_0, \sigma_1$.

# Chapitre 17

**Solution 3.4.** On définit la fonction $f: \mathbb{N} \to \mathbb{N}$ qui sur $\langle n, i, e \rangle$ pour $n \ge 2$ renvoie $\langle n, 1-i, e' \rangle$ où $e'$ est tel que $W_{e'} = \{f(a) : a \in W_e\}$, et qui sur $\langle 1, i, e \rangle$ renvoie $\langle 1, 1-i, e \rangle$.

**Solution 3.6.** Un examen attentif de la preuve montre que l'on a l'uniformité.

**Solution 3.9.** Il suffit de voir que toute classe $\Pi_2^0(\emptyset')$ dense contient un ensemble low, par la méthode des extensions finies.

**Solution 3.10.** Considérons un ouvert $U = \bigcup_{\tau \in W}[\tau]$ contenant tous les éléments qui ne sont pas des sauts Turing, et des chaînes $\sigma, \tau$ telles que $X' \supseteq \sigma$ pour tout $X \supseteq \tau$. Montrons qu'il existe une extension $\sigma^* \supseteq \sigma$, avec $\sigma^* \in W$, et une extension $\tau^* \supseteq \tau$ telle que $X' \supseteq \sigma^*$ pour tout $X \supseteq \tau^*$.

Soit $V_m$ une suite décroissante de classes $\Sigma_1^0$ telle que $\bigcap_m V_m$ est vide et telle que $V_m \cap [\tau]$ est non vide pour tout $m$. Soit $a_m > |\sigma|$ le code de la machine qui s'arrête sur l'entrée $a_m$ ssi son oracle appartient à $V_m$.

Soient $\sigma_0 = \sigma$ et $W_0 = [\tau]$. Soit aussi $e = |\sigma|$. Supposons définies des chaînes $\sigma_n \supseteq \dots \supseteq \sigma_0 = \sigma$ telles que $|\sigma_i| = |\sigma| + i$, ainsi que des ouverts $W_i$ pour $i < n$ tels que $W_{i+1} = \{X : \Phi_{e+i}(X, e+i) \downarrow\}$ si $\sigma_n(e+i) = 1$, et tels
que $W_{i+1} \subseteq \{X : \Phi_{e+i}(X, e+i) \uparrow\}$ si $\sigma_n(e+i) = 0$. Notons que $\bigcap_{k \le n} W_k$ ne contient que des éléments $X$ tels que $\sigma_n < X'$. Supposons aussi que

(1) la classe $(\bigcap_{k \le n} W_k) \cap V_m$ est non vide pour tout $m$.

Notons que (1) est vérifié pour $n = 0$. Construisons $\sigma_{n+1}$ et $W_{n+1}$. Si $e+n$ est égal à $a_m$ pour un certain $m$, alors $\sigma_{n+1} = \sigma_n 1$ et

$$W_{n+1} = V_m = \{X : \Phi_{e+n}(X, e+n) \downarrow\}.$$

On vérifie facilement (1). Sinon, on a deux possibilités :

▷ si $\{X : \Phi_{e+n}(X, e+n) \downarrow\} \cap \bigcap_{k \le n} W_k \cap V_m$ est non vide pour tout $m$, alors $\sigma_{n+1} = \sigma_n 1$, $W_{n+1} = \{X : \Phi_{e+n}(X, e+n) \downarrow\}$, et (1) est toujours vérifié;

▷ sinon, cela signifie $\bigcap_{k \le n} W_k \cap V_m \subseteq \{X : \Phi_{e+n}(X, e+n) \uparrow\}$ pour un certain $m$. On définit alors $\sigma_{n+1} = \sigma_n 0$ et $W_{n+1} = \bigcap_{k \le n} W_k \cap V_m$, et l'on a toujours (1).

Soit $Y = \sigma_1 < \sigma_2 < \dots$. Montrons que $Y$ n'est pas un saut Turing. Supposons que $Y = X'$ pour un ensemble $X$. Soit $m \in \mathbb{N}$. Comme $Y(a_m) = 1$, alors $\Phi_{a_m}(X, a_m) \downarrow$, et donc $X \in V_m$. Il s'ensuit que $X \in \bigcap_m V_m$, mais $\bigcap_m V_m = \emptyset$, ce qui amène à une contradiction. Donc, $Y \in \mathcal{U}$ par hypothèse sur $\mathcal{U}$. On a ainsi un préfixe $\sigma_n < Y$ tel que $\sigma_n \in W$. Par (1), la classe $\bigcap_{k \le n} W_k \subseteq [\tau]$ est non vide. Elle est aussi ouverte, et il existe donc une extension $\tau_n \supseteq \tau$ telle que $X' \supseteq \sigma_n$ pour tout $X \supseteq \tau_n$.

Pour finir, soit $\bigcap_n \mathcal{U}_n$ une classe $\Pi_2^0$ contenant tous les éléments qui ne sont pas des sauts Turing. En utilisant ce qui précède, on construit alors aisément par extension finie des éléments $X, Y$ tels que $Y \in \bigcap_n \mathcal{U}_n$ et tels que $Y = X'$. Donc, $\bigcap_n \mathcal{U}_n$ contient aussi des éléments qui sont des sauts Turing, et la classe de tous les éléments qui ne sont pas des sauts n'est donc pas $\Pi_2^0$.

**Solution 3.11.** Introduisons quelques notations. Pour une chaîne $\sigma$, on écrira $r(\sigma)$ pour désigner le ratio de 1 dans $\sigma$ par rapport à sa taille. On notera $P_m(\sigma, \varepsilon)$ le prédicat $\ll r(\sigma |_n) < \varepsilon$ pour tout $n$ tel que $m < n \le |\sigma| \gg$.

Soit $\bigcup_n \mathcal{F}_n$ une classe $\Sigma_2^0$ contenant tous les éléments de densité supérieure positive, et soit $\bigcap_n \mathcal{U}_n$ le complémentaire de $\bigcup_n \mathcal{F}_n$. Soit $\sigma$ une chaîne quelconque et soit $\varepsilon$ un rationnel. Montrons qu'il doit exister une extension $\tau \supseteq \sigma$ et un entier $n$ tels que :

(1) $P_{|\sigma|}(\tau, \varepsilon)$;

(2) $\{X \supseteq \tau : \forall m > |\sigma| \ P_{|\sigma|}(X \upharpoonright_m, \varepsilon)\} \subseteq \mathcal{F}_n$.

On fixe pour cette preuve un autre rationnel $\varepsilon' < \varepsilon$. Soit $\tau_0 = \sigma$. Notons que l'on a (1) avec $\tau_0$. Donc, si l'on a (2) avec $\tau_0$ et $n = 0$, alors c'est terminé. Sinon, il doit exister $X \in \mathcal{U}_0$, avec $X \supseteq \tau_0$ tel que $\forall m > |\sigma| \ P_{|\sigma|}(X \upharpoonright_m, \varepsilon)$. Soit $\tau_0 \le \rho_0 < X$ tel que $[\rho_0] \subseteq \mathcal{U}_0$. Supposons $\tau_n, \rho_n$ définis. Alors, on trouve une extension $\tau_{n+1} \supseteq \tau_n$ telle que $P_{|\sigma|}(\tau_{n+1}, \varepsilon)$ et telle que $r(\tau_{n+1}) > \varepsilon'$. Si l'on a (2) avec $\tau_{n+1}$ et $n+1$, alors c'est terminé. Sinon, il doit exister $X \in \mathcal{U}_{n+1}$, avec $X \supseteq \tau_{n+1}$ tel que $\forall m > |\sigma| \ P_{|\sigma|}(X \upharpoonright_m, \varepsilon)$. Soit $\tau_{n+1} \le \rho_{n+1} < X$ tel que $[\rho_{n+1}] \subseteq \mathcal{U}_{n+1}$. Supposons que l'on ne soit jamais dans le cas (2). Alors, on construit une suite $Y = \tau_0 < \tau_1 < \dots$ telle que $Y \in \bigcap_n \mathcal{U}_n$ et telle que $r(\tau_n) > \varepsilon'$
pour tout $n$. En particulier, la suite $Y$ est de densité supérieure positive, et donc $Y \in \bigcup_n \mathcal{F}_n$, ce qui est une contradiction. On arrive donc nécessairement dans le cas (2), ce qui conclut notre démonstration intermédiaire.

Soit à présent $\bigcap_k \bigcup_n \mathcal{F}_{k,n}$ une classe $\Pi_3^0$ contenant tous les éléments de densité supérieure positive. Soit $\sigma_0$ tel que $P_0(\sigma_0, 2^{-1})$, et soit $n_0$ tel que

$$ \{X \succeq \sigma_0 : \forall m > 0 P_0(X \upharpoonright_m, 2^{-1})\} \subseteq \mathcal{F}_{0,n_0}. $$

Supposons la chaîne $\sigma_k$ et l'entier $n_k$ définis. Alors, on définit $\sigma_{k+1} \succeq \sigma_k$ et $n_{k+1}$ tels que $P_{|\sigma_k|}(\sigma_{k+1}, 2^{-k-2})$ et tels que

$$ \{X \succeq \sigma_{k+1} : \forall m > |\sigma_k| P_{|\sigma_k|}(X \upharpoonright_m, 2^{-k-2})\} \subseteq \mathcal{F}_{k+1, n_{k+1}}. $$

Soit $Y = \sigma_0 \preceq \sigma_1 \preceq \dots$. Pour tout $k$, on a par construction

$$ \forall m > |\sigma_k| P_{\sigma_k}(Y \upharpoonright_m, 2^{-k-1}). $$

Par ailleurs, $Y \in \mathcal{F}_{n_k}$ pour tout $k$. Ainsi, $Y \in \bigcap_k \bigcup_n \mathcal{F}_{k,n}$. Il est de plus clair que la densité supérieure de $Y$ est 0. Par suite, $\bigcap_k \bigcup_n \mathcal{F}_{k,n}$ contient aussi des éléments de densité supérieure 0, et la classe des éléments de densité supérieure positive n'est donc pas $\Pi_3^0$.

**Solution 4.7.** Pour tout $n$, l'ensemble $\emptyset^{(n)}$ est $\Sigma_n^0$. Considérons la classe générée par la réunion des cylindres $[0^m1]$ pour $m \in \emptyset^{(n)}$. Il s'agit un ouvert qui admet une description effective $\Sigma_n^0$ et dont la représentation binaire de la mesure est égale à $\emptyset^{(n)}$.

## Chapitre 18

**Solution 1.3.** En utilisant l'indication, pour $q = n$ et pour $a < 2^n$, l'ensemble des $X \in q^N$ tels que la limite inférieure de la fréquence d'apparition de $a$ dans ses préfixes ne converge pas vers $1/q$ est égale à $\bigcup_\epsilon \bigcap_n \bigcup_{m \ge n} C_{\epsilon,m}^{q,a}$. D'après l'inégalité de Hoeffding, pour chaque $\epsilon$, la classe $\bigcap_n \bigcup_{m \ge n} C_{\epsilon,m}^{q,a}$ est une classe $\Pi_2^0$ de mesure 0, et telle que la mesure de chaque composante $\bigcup_{m \ge n} C_{\epsilon,m}^{q,a}$ est bornée par $2a_n/(1-a_1)$, où $a_m = e^{-2m\epsilon^2}$ (voir le développement fait au début du chapitre 18).

## Chapitre 19

**Solution 3.3.** Dans une direction, il suffit de transformer une classe $\Pi_2^0(\emptyset^{(n)})$ en une classe $\Pi_{n+2}^0$. Chaque ouvert $\Sigma_1^0(\emptyset^{(n)})$ est décrit par un ensemble de chaînes $\Sigma_1^0(\emptyset^{(n)})$ qui est aussi $\Sigma_{n+1}^0$, d'après le théorème 5-5.5. On peut donc transformer chaque ouvert uniformément en classe $\Sigma_{n+1}^0$, l'intersection étant alors $\Pi_{n+2}^0$.
Pour l'autre direction, il suffit d'appliquer le théorème 17-4.4.

**Solution 3.6.** Étant donné une classe $\Pi_1^0 \mathcal{P}$ et une fonctionnelle $\Phi_e$, on définit à l'aide du théorème du point fixe le code $a_e$ de la fonction $\emptyset'{-}$calculable qui fait la chose suivante : cherche une chaîne $\sigma$ telle que $\mathcal{P} \cap [\sigma] \neq \emptyset$ et telle que $\Phi_e(\sigma, a_e) \downarrow$. Si une telle chaîne $\sigma$ est trouvée, alors $a_e$ code pour la fonction telle que $\Phi_{a_e}(\emptyset', a_e) = \Phi_e(\sigma, a_e) \downarrow$. Sinon, $a_e$ reste partielle. Notons que le code $a_e$ lui-même est uniformément calculable, et cela sans l'aide de $\emptyset'$.

Dans le même temps, et cette fois-ci sans l'aide de $\emptyset'$, on cherche la première chaîne $\sigma$ telle que $\mathcal{P} \cap [\sigma]$ est pour le moment non vide et telle que $\Phi_e(\sigma, a_e) \downarrow$, et l'on énumère dans une classe $\Sigma_2^0$ le code de la classe $\Pi_1^0 \mathcal{P} \cap [\sigma]$. Si l'on s'aperçoit que $\mathcal{P} \cap [\sigma] = \emptyset$, on cherche une autre chaîne $\sigma$ telle que $\mathcal{P} \cap [\sigma]$ est pour le moment non vide et telle que $\Phi_e(\sigma, a_e) \downarrow$, etc. Entre chaque énumération de codes de la forme $\mathcal{P} \cap [\sigma]$, on énumère dans notre classe $\Sigma_2^0$ un code correspondant à la classe $\mathcal{P}$, mais que l'on videra complètement une fois la prochaine chaîne $\sigma$ trouvée. Il y a plusieurs deux possibilités :

▷ soit $\Phi(X, a_e) \uparrow$ pour tout $X \in \mathcal{P}$, auquel cas on arrivera à un moment où aucune chaîne $\sigma$ ne sera trouvée, et notre classe $\Sigma_2^0$ contiendra un code de $\mathcal{P}$ qui ne sera jamais vidé;

▷ soit $\Phi(X, a_e) \downarrow$ pour un élément $X \in \mathcal{P}$, auquel cas on finira par trouver une chaîne $\sigma$ telle que $\mathcal{P} \cap [\sigma]$ est non vide et telle que $\Phi(\sigma, a_e) \downarrow$. Il suffit alors de synchroniser notre recherche avec le calcul effectué à l'aide de l'arrêt pour s'assurer que $\Phi_{a_e}(\emptyset', a_e) = \Phi_e(\sigma, a_e) \downarrow$ pour la même chaîne $\sigma$. À ce moment notre classe $\Sigma_2^0$ ne contient plus que des codes de classes vides, ainsi que le code d'une sous-classe $\Pi_1^0 \mathcal{P}$ telle que $\Phi_e(X, a_n) \downarrow = \Phi_{a_e}(\emptyset', a_e)$ pour tout $X$ dans cette sous-classe.

On construit de cette manière pour tout $e$ une classe $\Sigma_2^0$ qui intersecte chaque classe $\Pi_1^0$ non vide (et qui contient donc tous les ensembles calculatoirement dominés) et telle que pour tout $X$ dans cette classe, soit $\Phi(X, a_e) \uparrow$, soit $\Phi(X, a_e) \downarrow = \Phi_{a_e}(a_e)$. L'intersection de ces classes $\Sigma_2^0$ contient tous les ensembles calculatoirement dominés, et aucun d'entre eux n'est degré DNC($\emptyset'$).

**Solution 4.9.** Soit $\mathcal{F}$ une classe $\Pi_1^0$ de mesure positive, et soit $X \in \mathcal{F}$ un ensemble pour lequel il existe $n$ et $\varepsilon < 1$ tels que pour tout $m \ge n$ on a

$$ \lambda(\mathcal{F} | [X \upharpoonright_m]) < 1 - \varepsilon. $$

On définit le test suivant. Soit $U_0 = \{X \upharpoonright_n\}$ et supposons $U_k \subseteq 2^{<\mathbb{N}}$ défini tel qu'un préfixe de $Y$ est dans $U_k$. Pour tout $\sigma \in U_k$, on cherche $t$ tel que $\lambda(\mathcal{F}[t] | [\sigma])$ soit $< 1 - \varepsilon$. Si cela arrive, on énumère dans $U_{k+1}$ un ensemble fini de chaînes générant l'ouvert/fermé $\mathcal{F}[t] \cap [\sigma]$. Par induction, un préfixe de $X$ est nécessairement dans $U_{k+1}$ et, par définition, $\lambda([U_{k+1}]) < (1-\varepsilon)\lambda([U_k])$. Donc, $X$ est capturé par $\bigcap_k [U_k]$, qui est un test de Martin-Löf.