Une intuition que nous allons étayer dans les développements à venir est que les classes maigres sont « petites » et les classes co-maigres sont « grosses ». Il ne faut pas prendre l'attribution de ces adjectifs comme étant absolue. Il y a d'autres manières de juger de la taille des classes, qui ne coïncident en rien avec le fait que les maigres soit petites et les co-maigres grosses. On peut par exemple trouver des classes maigres de mesure 1 et des classes co-maigre de mesure 0 (voir la partie II).

Ce qu'il faut comprendre plutôt, c'est que les classes co-maigres sont suffisamment grosses pour toujours être stables par intersection dénombrable, et dans le même temps toujours denses, et même dans un sens fort : si $\mathcal{B}$ est une classe co-maigre, alors $\mathcal{B} \cap [\sigma]$ est indénombrable pour tout cylindre $[\sigma]$. Il s'agit en fait d'un renforcement du théorème 2.4. Pour s'en convaincre, se souvenir du fait suivant démontré avec la proposition 8-2.3 et la proposition 8-3.2.

**Fait**

L'intersection d'un nombre fini d'ouverts est un ouvert. Par conséquent, on peut toujours supposer qu'une intersection dénombrable d'ouverts $\cap_n U_n$ est décroissante. Par passage au complémentaire, on peut toujours supposer qu'une réunion dénombrable de fermés est croissante.

Rappelons qu'une classe $\mathcal{F} \subseteq 2^\mathbb{N}$ est parfaite si elle est l'image d'une injection continue de $2^\mathbb{N}$ vers $2^\mathbb{N}$ (voir la section 8-2.4), c'est-à-dire que $\mathcal{F}$ est de la forme $[T]$ pour un f-arbre $T : 2^{<\mathbb{N}} \to 2^{<\mathbb{N}}$ (voir la section 7-5). Le lemme suivant montre qu'une classe co-maigre a la puissance du continu.

**Lemme 2.14.** Une classe co-maigre de l'espace de Cantor contient une sous-classe parfaite de points dans chaque cylindre $[\sigma]$.

**PREUVE.** Soit $\mathcal{B}$ une classe co-maigre, et soit $\cap_n U_n \subseteq \mathcal{B}$ une intersection d'ouverts denses. On peut supposer sans perte de généralité que $U_{n+1} \subseteq U_n$. Le lecteur peut s'aider de la figure 2.2 pour une représentation graphique de la construction qui suit.

Soit $\sigma \in 2^{<\mathbb{N}}$. Comme l'ouvert $U_0$ est dense, $U_0 \cap [\sigma 0]$ est non vide, et il y a donc une chaîne $\sigma_0 \supsetneq \sigma 0$ telle que $[\sigma_0] \subseteq U_0$. De la même manière il y a une chaîne $\sigma_1 \supsetneq \sigma 1$ telle que $[\sigma_1] \subseteq U_0$. Supposons que pour toute chaîne $\tau$ de taille $n+1$ on ait défini des chaînes $\sigma_\tau \supseteq \sigma$ deux à deux incomparables et telles que $[\sigma_\tau] \subseteq U_n$. Pour chacune de ces chaînes $\tau$ et pour chaque $i \in \{0, 1\}$, on définit $\sigma_{\tau i}$ comme étant une chaîne qui étend $\sigma_\tau i$ et telle que $[\sigma_{\tau i}] \subseteq U_{n+1}$, ce qui est possible car $U_{n+1}$ est dense.

Il est clair que pour tout ensemble $X$ la classe $\cap_{\tau < X} [\sigma_\tau] \subseteq \cap_n U_n$ contient un unique élément $Y_X \in [\sigma] \cap \cap_n U_n$. On vérifie sans peine que la fonction $T : 2^{<\mathbb{N}} \to 2^{<\mathbb{N}}$ définie par $T(\tau) = \sigma_\tau$ est un f-arbre dont les chemins sont les éléments $Y_X = T(\sigma_0) < T(\sigma_1) < \dots$ pour $X = \sigma_0 < \sigma_1 < \dots$.
<figure><img src="image_73.png" /><figcaption>FIGURE 2.15 – Illustration de la construction d'une sous-classe parfaite de points dans $[\sigma] \cap \bigcap_n U_n$. Comme chaque ouvert $U_n$ est dense, on peut trouver pour toute chaîne $\sigma_\tau i$ une extension $\sigma_{\tau i} \supseteq \sigma_\tau i$ telle que $[\sigma_{\tau i}] \subseteq U_n$.</figcaption></figure>

Ainsi, $\mathcal{B}$ contient une sous-classe parfaite de points dans le cylindre $[\sigma]$, ce qui achève la démonstration du lemme 2.14. ■

Notons en particulier comme conséquence du lemme précédent qu'une réunion dénombrable de fermés d'intérieur vide est d'intérieur vide : si une telle réunion de fermés contenait un cylindre $[\sigma]$, son complémentaire — une classe co-maigre — ne pourrait contenir de point dans $[\sigma]$, ce qui serait une contradiction.

Nous voyons à présent l'équivalent topologique de la définition 2.1 de forcing pour les contrats $\Sigma_1^0$ et $\Pi_1^0$.

**Définition 2.16.** Soit $\mathcal{R}$ un contrat $\Sigma_1^0$ ou $\Pi_1^0$. Soit $\mathcal{B}_\mathcal{R}$ la classe des éléments qui satisfont $\mathcal{R}$. Alors, $\sigma$ force $\mathcal{R}$ ssi $[\sigma] \subseteq \mathcal{B}_\mathcal{R}$. Notons que si $\mathcal{R}$ est $\Sigma_1^0$, alors $\mathcal{B}_\mathcal{R}$ est un ouvert effectif, et que si $\mathcal{R}$ est $\Pi_1^0$, alors $\mathcal{B}_\mathcal{R}$ est un fermé effectif. ◇

Notons par exemple que si la classe des éléments satisfaisant un contrat $\Pi_1^0$ est d'intérieur vide, alors aucune chaîne ne force ce contrat : la classe des éléments ne satisfaisant pas le contrat est un ouvert dense, et contiendra tout élément suffisamment générique. Cela nous amène à l'étude des ensembles qui sont dans « suffisamment d'ouverts denses » : les 1-génériques et les faiblement 1-génériques, que nous voyons à présent.
# 3. Généricité effective

Jockusch fut sans doute l'un des premiers à comprendre l'utilité que pouvaient avoir les idées de Cohen en calculabilité, et il initia l'étude d'une version effective des concepts de Cohen, avec les notions de 1-généricité et 1-généricité faible, résultant de l'application du forcing à tous les contrats $\Sigma_1^0$ et $\Pi_1^0$.

La généricité peut être vue à la fois comme une notion de force et de faiblesse. Un ensemble suffisamment générique sera par exemple toujours de degré hyperimmune. En revanche, nous verrons que les ensembles suffisamment génériques ne peuvent pas calculer l'arrêt, ni même de fonction DNC. De manière générale, la méthode des extensions finies satisfait des propriétés de force et de faiblesse de la même manière : en prouvant la densité de certains ensembles bien choisis.

## 3.1. Ensembles faiblement 1-génériques

Nous commençons par présenter les ensembles faiblement 1-génériques, introduits par Kurtz durant sa thèse de doctorat, effectuée sous la direction de Jockusch.

**Définition 3.1 (Kurtz [126]).** Un ensemble $G \in 2^N$ est faiblement 1-générique s'il est générique pour tous les ensembles c. e. denses. Autrement dit, $G$ est faiblement 1-générique si $G$ appartient à toutes les classes $\Sigma_1^0$ denses de l'espace de Cantor. ◇

Notons qu'il n'existe qu'une quantité dénombrable de classes $\Sigma_1^0$ denses. La notion d'ensemble faiblement 1-générique s'avère n'être pas assez restrictive pour receler des propriétés normalement inhérentes aux génériques, mais en termes de degré Turing, la notion présente un certain intérêt, notamment via la caractérisation suivante.

**Théorème 3.2 (Kurtz [126])**

Soit $G \subseteq N$. Les énoncés suivants sont équivalents.

(1) $G$ est de degré hyperimmune.

(2) $G$ calcule une fonction qui est égale infiniment souvent à toute fonction calculable.

(3) $G$ calcule un ensemble faiblement 1-générique.

*PREUVE.* Montrons d'abord (1) $\rightarrow$ (3), l'implication la plus difficile. Soit $f \le_T G$ une fonction qui n'est bornée par aucune fonction calculable. On suppose sans perte de généralité que $f$ est croissante. Notons que pour toute fonction calculable $g$, il y a une infinité de valeurs $n$ telles
que $f(n) > g(n)$. On calcule à partir de la fonction $f$ un ensemble $G \in 2^N$
qui appartient à toute classe $\Sigma_1^0$ dense. Soit $(W_e)_{e \in N}$ une énumération
des sous-ensembles $\Sigma_1^0$ de $2^N$. On construit $G$ par approximations suc-
cessives $\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 concatené 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(|\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 « satisfaits » 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(|\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(|\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.

Notons que si $W_e$ décrit un ouvert dense, alors la fonction $f_e$ qui à $n$ associe
le plus petit temps de calcul $t$ tel que toutes les chaînes de taille $n$ ont une
extension dans $W_e[t]$ est une fonction calculable et totale. On a en particulier
$f_e(n) < f(n)$ pour une infinité de valeurs $n$. Supposons que $W_e$ décrit un
ouvert dense, que $e$ n'est pas satisfait au temps $t$ et que tous les $e' < e$ qui
sont satisfait à 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(n) > f_e(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 \in W_e[f(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(|\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(n)]$ pour $\sigma_{s+1} = \sigma_s\tau$. On en
conclut que l'ensemble $G = \sigma_0 < \sigma_1 < \sigma_2 < \dots$ appartient à tous les
ouverts denses.
Montrons l'implication (3) → (2).

Soit $G$ un ensemble faiblement 1-générique. Notons que si $f$ est une fonction totale calculable alors l'ensemble $W_f = \{\sigma 0 f(|\sigma|) 1 : \sigma \in 2^{<\mathbb{N}}\}$ décrit une classe $\Sigma_1^0$ dense. On calcule à partir de $G$ la fonction $g$ qui à $n$ associe le nombre maximal $g(n)$ de 0 tel que $G \upharpoonright_n 0^{g(n)} \prec G$. Comme pour toute fonction totale calculable $f$ l'ensemble $G$ appartient à $W_f$, il est clair que $g$ est égale au moins une fois à toute fonction calculable. Si $g$ n'était égale qu'un nombre fini de fois à une fonction calculable donnée, on pourrait modifier un nombre fini de valeurs de cette fonction pour avoir une fonction calculable qui n'est jamais égale à $g$. Donc, $g$ est égale infiniment souvent à toute fonction calculable.

Montrons enfin (2) → (1).

Soit $f$ une fonction égale infiniment souvent à toute fonction calculable. Alors, $f+1$ est infiniment souvent au-dessus de toute fonction calculable. ■

On peut relativiser la notion de 1-généricité faible à n'importe quel oracle.

**Définition 3.3 (Kurtz [126]).** Soit $A \in 2^{<\mathbb{N}}}$. Un ensemble $G$ est faiblement 1-générique relativement à $A$ si $G$ rencontre $W$ pour tout ensemble de chaînes $\Sigma_1^0(A)$ dense $W$. ♦

La hiérarchie des sauts Turing permet de définir une hiérarchie de généricité comme suit.

**Définition 3.4 (Kurtz [126]).** Un ensemble $G \in 2^{<\mathbb{N}}$ est faiblement $n$-générique s'il est faiblement 1-générique relativement à $\emptyset^{(n-1)}$, c'est-à-dire s'il rencontre tous les ensembles de chaînes $\Sigma_1^0(\emptyset^{(n-1)})$ denses, ou encore tous les ensembles de chaînes $\Sigma_n^0$ denses. ♦

Certaines implications du théorème 3.2 se généralisent à tout oracle $A$.

**Exercice 3.5.** Montrer que tout ensemble $G$ faiblement 1-générique relativement à $A$ calcule une fonction $g : N \to N$ qui est égale infiniment souvent à toute fonction $A$-calculable. ♦

**Exercice 3.6.** Soit $n \ge 1$, et soit $G \in 2^{<\mathbb{N}}}$. Montrer que si $G$ calcule une fonction qui est égale infiniment souvent à toutes les fonctions $A$-calculables, alors $G$ calcule une fonction $A$-hyperimmune. ♦

La direction (1) → (3) du théorème 3.2 ne se généralise pas en règle générale. Dans la hiérarchie des sauts Turing, cela fonctionne uniquement à la première étape.
**Proposition 3.7 (Andrews, Gerdes et Miller [7]).**

Toute fonction hyperimmune relativement à $\emptyset'$ calcule un ensemble faiblement 2-générique. ★

L'idée pour montrer la proposition précédente est d'utiliser le fait que les objets $\emptyset'$-calculables sont calculables à la limite. En revanche, à partir de $n \ge 3$, les ensembles faiblement $n$-génériques ne peuvent plus être construits simplement à l'aide de fonctions échappant à des collections de fonctions, au sens suivant.

**Définition 3.8.** Soit $\mathcal{F}$ une collection de fonctions $N \to N$. Une fonction $f$ est $\mathcal{F}$-échappante si pour tout $g \in \mathcal{F}$, il existe un entier $n$ tel que $f(n) > g(n)$. ♦

Le théorème suivant exprime une profonde différence structurelle entre les fonctions échappantes et les degrés génériques, au sens où quel que soit un oracle $A$, il existe une fonction $A$-hyperimmune qui ne calcule pas d'ensemble faiblement 3-générique.

**Théorème 3.9 (Andrews, Gerdes et Miller [7])**

*Pour toute collection dénombrable de fonctions $\mathcal{F}$, il existe une fonction $\mathcal{F}$-échappante qui n'est pas de degré faiblement 3-générique.*

**PREUVE.** Nous utiliserons une variante de la notion de f-arbre définie dans la section 7-5. Nous allons définir une fonction $\Delta_3^0$ totale $T: \mathbb{N}^{<\mathbb{N}} \to \mathbb{N}^{<\mathbb{N}}$ telle que :

(1) dom $T$ (le domaine de $T$) est un ensemble clos par préfixe;

(2) pour tous $\sigma, \tau \in \text{dom } T$, $\sigma \preceq \tau$ si et seulement si $T(\sigma) \preceq T(\tau)$;

(3) pour tout $\sigma \in \mathbb{N}^{<\mathbb{N}}$ et $n \in \mathbb{N}$, il existe un $m \ge n$ tel que $T_s(\sigma n)$ étend $T_s(\sigma)m$.

La fonction $T$ s'étend en une fonction de $\mathbb{N}^\mathbb{N}$ vers $\mathbb{N}^\mathbb{N}$, en définissant pour tout $X \in \mathbb{N}^\mathbb{N}$, $T(X)$ comme l'unique élément de la classe $\bigcap_{\sigma<\chi} [T(\sigma)]$. Un chemin de $T$ est une suite $P \in \mathbb{N}^\mathbb{N}$ dont une infinité de segments initiaux appartiennent à $\text{Im } T$. Autrement dit, un chemin est une suite $P \in 2^\mathbb{N}$ de la forme $P = T(X)$ pour un $X \in \mathbb{N}^\mathbb{N}$. On notera $[T]$ l'ensemble des chemins de $T$. Par (3), pour toute collection dénombrable de fonctions $\mathcal{F}$, il existe un chemin $f \in [T]$ qui est $\mathcal{F}$-échappant. Nous allons construire $T$ de telle sorte que pour tout chemin $f \in [T]$, $f$ n'est pas de degré faiblement 3-générique.

Le lecteur peut s'aider de la figure 3.10 pour comprendre la construction qui suit. Soit $(\sigma_s)_{s \in \mathbb{N}}$ une énumération calculable de $\mathbb{N}^{<\mathbb{N}}$ qui ne fait aparaître chaque chaîne qu'après avoir énuméré ses préfixes. En particulier, $\sigma_0 = \epsilon$. Au début de l'étape $s$, nous aurons déjà défini $T$ sur $\sigma_0, \dots, \sigma_s$.
Nous supposerons également défini pour chaque $t \le s$, un réservoir c. e. in-
fini $V_{t,s} \subseteq \mathbb{N}^{<\mathbb{N}}$ de chaînes étendant $T(\sigma_s)$. Nous allons nous assurer que
pour tout $n \in \mathbb{N}$, $T(\sigma_s n)$ étend une chaîne de $V_{t,s}$. Simultanément, nous
allons créer pour chaque $e$ un ensemble $\Sigma_1^0(\emptyset'')$ dense $U_e \subseteq 2^{<\mathbb{N}}$ tel que
si $\Phi_e^P$ est totale pour un chemin $P \in [T]$, alors $P$ ne rencontre pas $U_e$.
Ainsi, quel que soit le chemin $P \in [T]$, $\Phi_e^P$ ne sera pas un ensemble faible-
ment 3-générique.

Initialement, $f(\epsilon) = \epsilon$ et $V_{0,0} = \mathbb{N}$. À l'étape $s = \langle e, i \rangle$, nous allons nous assurer que toute chaîne de longueur $i$ a une extension dans $U_e$. L'ensemble $\{\sigma_t : t \le s\}$ forme un arbre fini, et pour chaque feuille $\tau$ de cet arbre, $\Phi_e^{T(\tau)}$ peut avoir des valeurs différentes. L'ensemble $U_e$ doit donc ajouter des extensions à toutes les chaînes de longueur $i$, tout en s'assurant qu'elle évitera $\Phi_e^{T(\sigma_t)}$ pour tout $t \le s$. Nous fixons donc une longueur suffisamment grande, $k = i+s+1$, de telle sorte que si l'on construit un ensemble de chaînes binaires $\ll$ interdites $\gg \rho_0, \dots, \rho_s$ chacune de longueur $k$, toute chaîne binaire de longueur $i$ admet une extension de longueur $k$ évitant les chaînes interdites.

Pour chaque $t \le s$, on demande à $\emptyset''$ s'il existe une chaîne $\rho_s$ de taille $k$
telle qu'il existe une infinité de chaînes binaires $\mu \in V_{t,s}$ ayant une exten-
sion $\mu' \supseteq \mu$ pour laquelle $\Phi_e^{\mu'} \upharpoonright_k = \rho_s$. Si c'est le cas, on définit $V_{t,s+1}$ comme
l'ensemble de ces $\mu'$. Notons que $V_{t,s+1}$ est alors encore calculatoirement
énumérable. Sinon, pour toute chaîne $\rho$ de taille $k$, seul un nombre fini de
chaînes de $V_{t,s}$ possède une extension qui sera envoyée vers une extension
de $\rho$ via $\Phi_e$. En particulier, on peut enlever un nombre fini de chaînes de $V_{t,s}$
de manière à ce qu'aucune extension des chaînes restantes ne sera jamais
envoyé vers une chaîne de taille plus grande que $k$. On prend alors une
chaîne $\rho_s$ arbitraire, et l'on définit $V_{t,s+1}$ comme la restriction de $V_{t,s}$ aux
chaînes $\mu$ qui n'ont pas d'extension $\mu'$ envoyée vers une chaîne de taille plus
grande que $k$ via $\Phi$. Comme nous retirons un nombre fini de chaînes, $V_{s,t+1}$
est encore c. e.

Nous nous retrouvons donc avec un ensemble de chaînes binaires $\rho_0, \dots, \rho_s$,
chacune de longueur $k$, de telle sorte que pour tout chemin $P \in [T]$, si $\Phi_e^P$
est total, alors $\Phi_e^P \upharpoonright_k = \rho_t$ pour un $t \le s$. On énumère dans $U_e$ toutes
les chaînes de longueur $k$ autres que $\rho_0, \dots, \rho_s$. En excluant ces chaînes,
on s'assure que pour tout chemin $P \in [T]$, si $\Phi_e^P$ est total, alors il ne
rencontrera pas $U_e$. La longueur $k$ étant suffisamment grande, toute chaîne
de longueur $i$ a une extension dans $U_e$.

Enfin, nous définissons $T(\sigma_{s+1})$. Supposons que $\sigma_{s+1} = \sigma_{t,n}$ pour un $t \le s$
et $n \in \mathbb{N}$. On choisit $\tau \in V_{t,s+1}$, on le retire de $V_{t,s+1}$, et l'on pose $T(\sigma_{s+1}) = \tau$.
Enfin, on définit $V_{s+1,s+1} = \{\tau m : m \in \mathbb{N}\}$. Cela termine la preuve du
théorème 3.9.

■
Ci-dessous, l'énumération $(\sigma_s)_{s \in \mathbb{N}}$ commence par $\epsilon, 0, 1, 2, 00, 01, 10, 11, \dots$

<figure><img src="image_74.png" /><figcaption>FIGURE 3.10 – Illustration de la preuve : à l'étape 8, on va restreindre chacun des réservoirs de $V_{0,7}$ à $V_{7,7}$ en supprimant certaines de leurs branches, et en étendant d'autres, de manière à ce que la fonctionnelle courante $\Phi_e$ évite, pour chacune des branches des réservoirs $V_{i,8}$, un ouvert dense que l'on est en train d'énumérer à l'aide du double saut. Une fois les réservoirs restreints, on complète notre arbre en prenant une extension dans chacun d'entre eux, ce qui crée pour chaque extension un nouveau réservoir, et ainsi de suite.</figcaption></figure>

**Exercice 3.11. (★★)** Modifier la preuve du théorème précédent pour montrer que pour toute collection dénombrable de fonctions $\mathcal{F}$, il existe une fonction $\mathcal{F}$-échappante qui ne calcule aucune fonction qui est égale infiniment souvent à toute fonction $\emptyset''$-calculable. ◇

## 3.2. Ensembles 1-génériques

Nous voyons à présent la 1-généricité, une notion un peu plus forte et beaucoup plus riche que la 1-généricité faible. Les ensembles faiblement 1-génériques sont ceux résultant du forcing pour les contrats $\Sigma_1^0$ denses. Mais qu'en est-il des contrats $\Sigma_1^0$ qui ne sont pas denses ?

La 1-généricité correspond au premier niveau de forcing permettant de s'attaquer aux contrats $\Sigma_1^0/\Pi_1^0$ quelconques, via le théorème suivant, qui sera démontré à la fin de la sous-section qui suit (nous renvoyons le lecteur à la définition 2.1 pour la notation $\Vdash^*$).

### Théorème 3.12

Soit $G$ un ensemble 1-générique. Soit $\mathcal{R}$ un contrat $\Sigma_1^0$ ou $\Pi_1^0$. Alors, $G$ satisfait $\mathcal{R}$ si, et seulement si, il existe un préfixe $\sigma \prec G$ tel que $\sigma \Vdash^* \mathcal{R}$.
### 3.2.1. Nature des ensembles 1-génériques

**Définition 3.13.** Une chaîne $\sigma \in 2^{<N}$ évite un ensemble $W \subseteq 2^{<N}$ (noté $\sigma \perp W$) si non seulement $\sigma \notin W$, mais également aucune extension de $\sigma$ n'est dans $W$. ◇

**Notation**

On note $W^{\perp} = \{\tau \in 2^{<N} : \tau \perp W\}$.

**Lemme 3.14.** Soit $W \subseteq 2^{<N}$ un ensemble arbitraire. Alors, l'ensemble $W \cup W^{\perp}$ est dense. ★

**PREUVE.** Soit $\sigma \in 2^{<N}$. Soit $\sigma$ possède une extension dans $W$, et donc dans $W \cup W^{\perp}$, soit $\sigma$ évite $W$, auquel cas $\sigma \in W^{\perp}$. ■

Notons que si $W$ est un ensemble dense, alors $W^{\perp} = \emptyset$. Souvenons-nous que la densité d'un ensemble de chaînes $W$ clos par suffixe sur $2^{<N}$ correspond à la densité sur $2^N$ de son ouvert correspondant $[W] = \cup_{\sigma \in W}[\sigma]$. L'ensemble $W^{\perp}$ correspond également à un ouvert : l'intérieur du complémentaire de l'ensemble $[W]$, c'est-à-dire la réunion de tous les cylindres $[\sigma]$ inclus dans le complémentaire de $[W]$.

Si on le reformule dans l'espace de Cantor, le lemme 3.14 énonce que pour n'importe quelle classe ouverte $\mathcal{U} \subseteq 2^N$, la classe $\mathcal{U} \cup \text{int}(2^N \setminus \mathcal{U})$ est un ouvert dense. Si $\mathcal{U}$ est à la base dense, alors $\text{int}(2^N \setminus \mathcal{U}) = \emptyset$, sinon on << densifie >> $\mathcal{U}$ en y ajoutant l'intérieur de son complémentaire. Nous sommes maintenant prêts à définir la notion d'ensemble 1-générique.

**Définition 3.15 (Jockusch [100]).** Un ensemble $G \in 2^N$ est 1-générique s'il est $\{W_e \cup W_e^{\perp} : e \in \mathbb{N}\}$-générique, où $W_e$ est l'ensemble de chaînes calculatoirement énumérable de code $e$. De manière équivalente, $G$ est 1-générique si $G \in \mathcal{U} \cup \text{int}(2^N \setminus \mathcal{U})$ pour toute classe $\Sigma_1^0 \mathcal{U}$. ◇

Comme signalé plus haut, si $W \subseteq 2^{<N}$ est un ensemble dense, alors $W^{\perp} = \emptyset$. Il s'ensuit que tout ensemble 1-générique rencontre tout ensemble $\Sigma_1^0$ dense, et est donc faiblement 1-générique. En particulier, les degrés des ensembles faiblement 1-génériques coïncidant avec les degrés hyperimmunes, tout ensemble 1-générique est de degré hyperimmune, et donc non calculable.

Si l'on regarde la contraposée de la notion de 1-généricité, un ensemble $G$ n'est pas 1-générique s'il existe un ensemble c. e. $W \subseteq 2^{<N}$ ne contenant aucun préfixe de $G$ et tel que $W$ << est dense le long de $G$ >>, c'est-à-dire que pour tout $\sigma \prec G$ il existe $\tau \succeq \sigma$ avec $\tau \in W$ et $\tau \precneq G$. Cette idée est illustrée dans la figure 3.16.
<figure><img src="image_75.png" /><figcaption>FIGURE 3.16 – Une illustration d’un ensemble G qui n’est pas 1-générique : on peut énumérer des chaînes $\sigma_0, \sigma_1, \dots$ densément le long de G, et sans jamais énumérer un préfixe de G.</figcaption></figure>

Nous voyons à présent formellement pourquoi le théorème 3.12 annoncé est vrai.

**Proposition 3.17.** Soit $\mathcal{R}_e$ un contrat $\Sigma_1^0$. Alors, l'ensemble $W \subseteq 2^{<\mathbb{N}}$ des chaînes forçant $\mathcal{R}_e$ est $\Sigma_1^0$. De plus, $W^{\perp}$ est l'ensemble des chaînes forçant $\neg \mathcal{R}_e$ et il est $\Pi_1^0$. $\star$

**PREUVE.** Le contrat $\mathcal{R}_e$ étant $\Sigma_1^0$, il peut s'écrire de la forme $\Phi(G, 0)\downarrow$ pour une fonctionnelle $\Phi$. Une chaîne $\sigma$ force $\mathcal{R}_e$ si $\Phi(X, 0)\downarrow$ pour tout $X \in [\sigma]$. Par le lemme de König, $\sigma$ force $\mathcal{R}_e$ s'il existe une longueur $n$ telle que pour tout $\tau \succeq \sigma$ de longueur $n$, $\Phi(\tau, 0)\downarrow$. L'ensemble

$$W = \{\sigma \in 2^{<\mathbb{N}} : \exists n \ \forall \tau \in 2^n \ (\tau \succeq \sigma \rightarrow \Phi(\tau, 0)\downarrow)\}$$

est $\Sigma_1^0$ (où $2^n$ désigne l'ensemble des chaînes de taille $n$).

Montrons que $W^{\perp}$ est l'ensemble des chaînes $\sigma$ qui forcent $\neg \mathcal{R}_e$. Si $\sigma$ ne force pas $\neg \mathcal{R}_e$, alors il existe un $X \in [\sigma]$ tel que $\Phi(X, 0)\downarrow$. Par la propriété de l'usage, pour $n$ suffisamment grand et pour tout $Y \in [X \upharpoonright_n]$, $\Phi(Y, 0)\downarrow$. On peut supposer $n \ge |\sigma|$. Soit $\tau = X \upharpoonright_n$. Alors, $\tau \in W$, donc $\sigma \notin W^{\perp}$. Par contraposée, si $\sigma \in W^{\perp}$, alors $\sigma$ force $\neg \mathcal{R}_e$. Supposons maintenant que $\sigma \notin W^{\perp}$. Alors, il existe $\tau \succeq \sigma$ tel que $\tau \in W$. En particulier, il existe un $X \in [\tau] \subseteq [\sigma]$ tel que $\Phi(X, 0)\downarrow$. Il s'ensuit que $\sigma$ ne force pas $\neg \mathcal{R}_e$.

Comme l'ensemble $W$ est $\Sigma_1^0$, il est clair que l'ensemble $W^{\perp}$ est $\Pi_1^0$. $\blacksquare$

**Corollaire 3.18**

Soit $\mathcal{R}_e$ un contrat $\Sigma_1^0$. Alors, l'ensemble $D$ des chaînes qui forcent $\mathcal{R}_e$ ou qui forcent $\neg \mathcal{R}_e$ est dense.

**PREUVE.** Immédiat par le lemme 3.14 et la proposition 3.17. $\blacksquare$
Notons que tout ensemble satisfait la formule $\ll \mathcal{R}_e \lor \neg \mathcal{R}_e \gg$, et donc que toute chaîne force $\ll \mathcal{R}_e \lor \neg \mathcal{R}_e \gg$. En revanche, il est beaucoup plus fort pour une chaîne $\sigma$ de forcer $\mathcal{R}_e$ ou de forcer $\neg \mathcal{R}_e$, car tout ensemble $A \in [\sigma]$ doit avoir le même comportement vis-à-vis de $\mathcal{R}_e$.

On peut à présent montrer le théorème 3.12 annoncé : si $G$ est un ensemble 1-générique et $\mathcal{R}$ un contrat $\Sigma_1^0$ ou $\Pi_1^0$, alors $G$ satisfait $\mathcal{R}$ ssi il existe un préfixe $\sigma \prec G$ tel que $\sigma \models^* \mathcal{R}$.

**PREUVE DU THÉORÈME 3.12.** Soit $G$ un ensemble 1-générique. Soit $\mathcal{R}$ un contrat $\Sigma_1^0$. Si un préfixe $\sigma \prec G$ force $\mathcal{R}$ ou $\neg \mathcal{R}$, alors par définition $G$ satisfait respectivement $\mathcal{R}$ ou $\neg \mathcal{R}$.

Réciproquement, supposons que $G$ satisfasse $\mathcal{R}$. Soit $W$ l'ensemble c. e. des chaînes qui forcent $\mathcal{R}$. Comme $G$ est 1-générique, il rencontre $W \cup W^{\perp}$. Si $G$ rencontre $W^{\perp}$, alors $\sigma$ force $\neg \mathcal{R}$ pour un préfixe $\sigma \prec G$, et $G$ satisfait donc $\neg \mathcal{R}$, ce qui est une contradiction. Ainsi, $G$ rencontre $W$, et un préfixe $\sigma \prec G$ force donc $\mathcal{R}$.

Symétriquement, si $G$ satisfait $\neg \mathcal{R}$, alors un préfixe $\sigma \prec G$ force $\neg \mathcal{R}$.

### 3.2.2. Propriétés des ensembles 1-génériques

De manière générale, la fonction qui à $X$ associe $X'$ n'est pas continue. En effet, il est parfois nécessaire de connaître une infinité de bits de $X$ pour savoir si $n \in X'$. René Baire a montré — sous une autre forme bien sûr — que cette fonction était en revanche continue sur une classe co-maigre de points. La 1-généricité est le niveau de généricité requis pour rendre compte de ce théorème.

**Définition 3.19.** Un ensemble $G \in 2^{\mathbb{N}}$ est low généralisé si

$$G' \preceq_T G \oplus \emptyset' \diamond$$

Si un ensemble $G$ est low généralisé, alors non seulement la fonction qui à $X$ associe $X'$ est continue en $G$, mais plus encore elle est calculable en $G \oplus \emptyset'$. Un ensemble quelconque n'a *a priori* aucune raison d'être low généralisé. À titre d'exemple, $\emptyset'$ ne l'est pas, mais c'est le cas pour les ensembles 1-génériques.

**Théorème 3.20**

Les ensembles 1-génériques sont low généralisés.

**PREUVE.** Pour tout entier $e$, on définit la classe $U_e = \{X : \Phi_e(X, e) \downarrow\}$. Soit $W_e \subseteq 2^{<\mathbb{N}}$ un ensemble $\Sigma_1^0$ qui représente $U_e$, c'est-à-dire tel que

$$[W_e] = U_e, \quad \text{où} \quad [W_e] = \bigcup_{\sigma \in W_e} [\sigma].$$
Notons que $e \in G'$ ssi $G \in \mathcal{U}_e$. On a par ailleurs $G \in \mathcal{U}_e$ ssi il existe $\tau \preceq G$ tel que $\tau \in W_e$, et par définition de la 1-généricité de $G$ on a $G \notin \mathcal{U}_e$ ssi il existe $\tau \preceq G$ tel que $\sigma \notin W_e$ pour tout $\sigma$ comparable avec $\tau$. La question de savoir si $\sigma \notin W_e$ pour tout $\sigma$ comparable avec $\tau$ est $\Pi_1^0$ uniformément en $\tau$, et donc peut être posée à $\emptyset'$. Pour savoir si $e \in G'$, il suffit donc de chercher un préfixe $\tau$ de $G$ tel que l'on est dans un cas ou dans l'autre, ce qui arrivera nécessairement. ■

Nous avons vu que tout ensemble 1-générique était de degré hyperimmune, et donc non calculable. Il ne s'agit donc pas d'une propriété de faiblesse. Nous allons maintenant voir que ce n'est pas non plus une notion de force, au sens où certaines puissances calculatoires ne pourront jamais être atteintes par les degrés 1-génériques. En particulier, aucun degré 1-générique ne calcule $\emptyset'$.

**Théorème 3.21 (Demuth et Kučera [45])**

*Un ensemble 1-générique n'est pas de degré DNC.*

PREUVE. Supposons que $n \mapsto \Phi(G, n)$ soit une fonction DNC. On considère la classe $\mathcal{U} = \{X : \exists n \ \Phi(X, n) \downarrow = \Phi_n(n) \downarrow\}$. Par hypothèse, $G \notin \mathcal{U}$. Considérons une chaîne $\sigma$. On définit par le théorème de point fixe de Kleene le code $e_\sigma$ de la fonction qui l'entrée $e_\sigma$ cherche une extension $\tau_\sigma \supseteq \sigma$ telle que $\Phi(\tau_\sigma, e_\sigma) \downarrow$ et assigne $\Phi(\tau_\sigma, e_\sigma)$ à $\Phi_{e_\sigma}(e_\sigma)$. Le processus étant uniforme, on énumère toutes les chaînes de la forme $\tau_\sigma$ dans un ensemble c. e. W.

Notons que pour tout $\sigma < G$ la fonction de code $e_\sigma$ s'arrête sur l'entrée $e_\sigma$, car il existe au moins une extension de $\sigma$ — à savoir $G$ lui-même — pour laquelle $\Phi$ s'arrête sur l'entrée $e_\sigma$. Comme $n \mapsto \Phi(G, n)$ est DNC, on a dès lors $\Phi(G, e_\sigma) \neq \Phi_{e_\sigma}(e_\sigma)$, et donc $\sigma < \tau_\sigma \not< G$.

On a ainsi un ensemble c. e. W dont aucun élément n'est un préfixe de G, mais qui contient une extension de chaque préfixe de G. Il s'ensuit que G n'est pas 1-générique. ■

La restriction de la généricité permet de construire des ensembles bénéficiant de certains avantages de la généricité tout en n'étant pas trop complexes d'un point de vue calculatoire.

**Exercice 3.22.** (⋆) Montrer par un argument direct qu'aucun ensemble 1-générique n'est calculable. ◇

**Exercice 3.23.** (⋆) Montrer qu'il existe un ensemble 1-générique $\Delta_2^0$. En déduire qu'il existe un ensemble 1-générique de degré low. ◇
Nous allons voir dans la section suivante avec le corollaire 3.34 qu'il existe aussi des ensembles 1-génériques de degrés high. Terminons par un exercice intéressant, qui demande d'élaborer sur les techniques du théorème 3.28, et qui utilise la notion de jointure effective de la définition 4-5.6, mais étendue à une suite dénombrable d'ensembles :

**Définition 3.24.** La jointure effective $\bigoplus_{n \in \mathbb{N}} A_n$ d'une suite $(A_n)_{n \in \mathbb{N}}$ d'ensembles est l'ensemble $Y$ tel que $\langle n, m \rangle \in Y$ ssi $m \in A_n$. ◇

Dans les exercices qui suivent, la notation $\bigoplus_{j \neq i} G_j$ correspond donc à la jointure effective de la suite $(G_n)_{n \in \mathbb{N}}$ de laquelle on enlève l'ensemble $G_i$.

**Exercice 3.25. (★★)** Soit $G = \bigoplus_{n \in \mathbb{N}} G_n$ un ensemble 1-générique. Montrer que $G_i$ est hyperimmune relativement à $\bigoplus_{j \neq i} G_j$ pour tout $i \in \mathbb{N}$. ◇

**Exercice 3.26. (★★)** (Miller). Soit $X = \bigoplus_{n \in \mathbb{N}} X_n$ un ensemble tel que $X_i$ est hyperimmune relativement à $\bigoplus_{j \neq i} X_j$ pour tout $i \in \mathbb{N}$. Montrer que $X$ calcule un ensemble 1-générique. ◇

### 3.2.3. Relativisation des ensembles 1-génériques

Tout comme on a relativisé la 1-généricité faible, on relativise à présent la 1-généricité.

**Définition 3.27 (Jockusch [100]).** Soit $A \in 2^{\mathbb{N}}$. Un ensemble $G \in 2^{\mathbb{N}}$ est 1-générique relativement à $A$ si $G \in \mathcal{U} \cup \text{int}(2^{\mathbb{N}} \setminus \mathcal{U})$ pour toute classe $\mathcal{U}$ qui est $\Sigma_1^0(A)$. On dira que $G$ est $n$-générique s'il est 1-générique relativement à $\emptyset^{(n-1)}$, ou de manière équivalente s'il rencontre $W \cup W^{\perp}$ pour tout $W$ ensemble de chaîne $\Sigma_n^0$. ◇

Nous étudierons cette relativisation plus en détail dans la section 5. Voyons pour le moment un premier théorème clef.

**Théorème 3.28**

Soit $X$ non calculable, et soit $G$ un ensemble 1-générique relativement à $X$. Alors, $G \not\subset_T X$.

**PREUVE.** Soit $\Phi$ une fonctionnelle Turing. Nous construisons $\mathcal{U}$, une classe $\Sigma_1^0(X)$ telle que $Y \in \mathcal{U} \cup \text{int}(\mathbb{N} \setminus \mathcal{U})$ implique $\Phi(Y) \neq X$.

On énumère simplement dans l'ensemble $X$-c. e. qui décrit $\mathcal{U}$, toutes les chaînes $\sigma$ telles que $\exists n \Phi(\sigma, n) \downarrow \neq X(n)$. Supposons à présent que $\tau$ est une chaîne pour laquelle $[\tau] \subseteq \mathbb{N} \setminus \mathcal{U}$, c'est-à-dire qu'aucune extension $\sigma \supseteq \tau$ ne soit telle que $\exists n \Phi(\sigma, n) \downarrow \neq X(n)$. Montrons alors que, pour tout $Y \supseteq \tau$,
on a $∃n Φ(Y, n)↑$. Supposons que ce ne soit pas le cas. Alors, on peut
calculer $X$ de la manière suivante : pour connaître $X(n)$, il suffit de chercher
une extension $\sigma \supseteq \tau$ telle que $Φ(\sigma, n)↓$. Par hypothèse, une telle extension
existe, et toujours par hypothèse, elle est telle que $Φ(\sigma, n)↓= X(n)$. Comme
c'est vrai pour tout $n$, cela contredit le fait que $X$ est incalculable. Donc,
si $[\tau] \subseteq \mathbb{N} \setminus U$, alors pour tout $Y \supseteq \tau$ on a $∃n Φ(Y, n)↑$. On en déduit que,
pour tout $Y \in U \cup \text{int}(\mathbb{N} \setminus U)$, on a $Φ(Y) \neq X$. Comme $G$ est 1-générique
relativement à $X$, alors $G \in U \cup \text{int}(\mathbb{N} \setminus U)$, et la même chose est vrai pour
toute fonctionnelle $Φ$. Donc, $G \not\subseteq_T X$.
$\blacksquare$

Voyons à présent les différentes implications entre les notions de *n-généricité*
et *n-généricité faible*.

**Proposition 3.29.** Soit $G$ un ensemble. Alors, pour tout $n > 0$, $G$ faiblement (n + 1)-générique implique $G$ n-générique, lequel implique à son tour $G$ faiblement n-générique. Les implications sont strictes. ★

PREUVE. Si $G$ est faiblement $(n+1)$-générique, il rencontre tout ensemble $\Sigma_1^0(\emptyset^{(n)})$ dense. Pour tout ensemble $\Sigma_1^0(\emptyset^{(n-1)})$ $W$, la réunion $W \cup W^\perp$ est dense et $\Sigma_1^0(\emptyset^{(n)})$, donc rencontre $G$. Ainsi, $G$ est n-générique. Si $G$ est n-générique, alors pour tout ensemble $\Sigma_1^0(\emptyset^{(n-1)})$, $G$ rencontre $W \cup W^\perp$. Si $W$ est dense, alors $W^\perp = \emptyset$, donc $G$ rencontre $W$. Ainsi, $G$ est faiblement n-générique.

Pour voir que la première implication est stricte, il suffit de construire un
ensemble *n*-générique $\emptyset^{(n)}$-calculable et de voir qu'aucun ensemble faible-
ment (*n* + 1)-générique n'est $\emptyset^{(n)}$-calculable, car {σ : σ ≁ X} est un
ensemble de chaînes $\Sigma_{n+1}^0$ dense pour tout ensemble X qui est $\Delta_{n+1}^0$. On
pourra consulter l'exercice 3.30 pour un exemple d'ensemble *n*-générique
qui n'est pas faiblement *n*-générique.
$\blacksquare$

**Exercice 3.30. (★★)** Un ensemble $X$ est *approchable par la gauche* relativement à $A$ s'il existe une suite $A$-calculable d'ensembles $(X_s)_{s \in \mathbb{N}}$ telle que $X_s$ est lexicographiquement plus petit que $X_{s+1}$ pour tout $s$, et tel que $\lim_s X_s = X$.

Montrer que pour tout $A$ il existe un ensemble faiblement 1-générique relativement à $A$ et approchable par la gauche relativement à $A$. Montrer qu'aucun ensemble 1-générique relativement à $A$ n'est approchable par la gauche relativement à $A$.
$\diamond$
### 3.3. Théorème de Posner/Robinson

Dans un article de 1981, Posner et Robinson étudient les degrés strictement sous l'arrêt, mais dont la jointure permet de calculer l'arrêt. Une version généralisée et moderne de leur théorème principal est la suivante : pour tout ensemble $A$ non calculable — et en particulier aussi « faible » que possible calculatoirement —, il existe un ensemble $G$ tel que $A \oplus G \geq_T G'$. Informellement, il existe toujours un ensemble $G$ dont la distance calculatoire entre lui-même et son saut est « réduite » à $A$, et ce pour n'importe quel $A$.

La présentation moderne du théorème est celle de Jockusch et Shore, qui montrent quelque chose de plus général :

**Théorème 3.31 (Jockusch et Shore [102])**

Soient $A, Z$ des ensembles non calculables. Il existe un ensemble 1-générique $G$ tel que $A \oplus G \geq_T Z$. De plus, on peut obtenir $G$ de manière calculable à partir de $A \oplus Z \oplus \emptyset'$.

**PREUVE.** L'idée est de construire un ensemble 1-générique $G$, qui va encoder $Z$, de manière à ce que $G$ et $A$ permettent de retrouver le déroulement de la construction. La construction elle-même sera calculable en $A \oplus Z \oplus \emptyset'$. On peut supposer sans perte de généralité que $A$ n'est pas un ensemble c. e. (dans le cas contraire, on remplace $A$ par son complémentaire). Soit $(W_e)_{e \in \mathbb{N}}$ une énumération des sous-ensembles $\Sigma_1^0$ de $2^{<\mathbb{N}}$.

On définit $\sigma_0 = \epsilon$, le mot vide. Supposons $\sigma_e$ défini. On considère l'ensemble

$$D_e = \{m : \exists \tau \text{ tel que } \sigma_e Z(e) 0^m 1 \tau \in W_e\}.$$

Notons que $D_e$ est un ensemble c. e. En particulier, comme $A$ n'est pas c. e., il existe $m \in D_e$, avec $m \notin A$, ou alors il existe $m \notin D_e$ avec $m \in A$. On considère le plus petit $m$ tel que l'on est dans un cas ou dans l'autre. Notons que $\emptyset' \oplus A$ permet de trouver uniformément cet entier $m$.

Dans le premier cas, on définit $\sigma_{e+1}$ comme étant $\sigma_e Z(e) 0^m 1 \tau$ pour la première chaîne $\tau$ telle que $\sigma_e Z(e) 0^m 1 \tau$ est énumérée dans $W_e$. Dans le deuxième cas, on définit $\sigma_{e+1}$ comme étant $\sigma_e Z(e) 0^m 1$. Notons que dans ce cas aucune chaîne de $W_e$ ne peut étendre $\sigma_{e+1}$. On définit $G$ comme étant $\sigma_0 \preceq \sigma_1 \preceq \sigma_2 \preceq \dots$. Cela termine la construction.

Il est clair que $G$ est 1-générique et calculable en $A \oplus Z \oplus \emptyset'$. Comment fait-on à présent pour calculer $Z$ à partir de $G \oplus A$ ? Supposons que l'on connaisse la chaîne $\sigma_e$. On connaît alors nécessairement le $e$-ième bit de $Z$: il s'agit du bit $i$ tel que $\sigma_e i \prec G$. On peut ensuite trouver $\sigma_{e+1}$ de la manière suivante : on regarde le nombre $m$ de 0 qui suit $\sigma_e i$ dans $G$.
Si $m \in A$, cela signifie que $\sigma_{e+1} = \sigma_e i 0^m 1$. Si $m \notin A$, cela signifie que $\sigma_{e+1} = \sigma_e i 0^m 1 \tau$ pour la première chaîne $\tau$ que l'on trouve dans $W_e$. Trouver $\tau$ est alors un procédé calculable. On peut donc dans tous les cas trouver $\sigma_{e+1}$, et en répétant le processus, calculer $Z$ à partir de $A \oplus G$. ■

**Corollaire 3.32 (Posner et Robinson [180])**

Soit $A$ un ensemble non calculable. Il existe un ensemble $G$ tel que

$$A \oplus G \geq_T G'$$

Si $A$ est $\Delta_2^0$, on a alors $A \oplus G \equiv_T G'$.

**PREUVE.** On applique le théorème précédent avec $Z = \emptyset'$. On a donc un ensemble 1-générique $G$ tel que $G \leq_T \emptyset' \oplus A$ et tel que $G \oplus A \geq_T \emptyset'$. En utilisant le fait que les 1-génériques sont low généralisés, on a donc

$$G \oplus A \geq_T G \oplus \emptyset' \equiv_T G'$$

Il est clair que si $A$ est $\Delta_2^0$, alors $A \oplus G \equiv_T G'$.

Un autre corollaire intéressant est le théorème d'inversion du saut : tout ensemble qui calcule l'arrêt peut être vu comme le degré Turing du saut d'un ensemble.

**Corollaire 3.33 (Théorème d'inversion du saut, Friedberg [62])**

Soit $Z \geq_T \emptyset'$. Il existe un ensemble $G$ tel que $Z \equiv_T G'$.

**PREUVE.** On applique le théorème précédent avec $Z$ et $A = \emptyset'$. On a donc un ensemble 1-générique $G$ tel que

$$G \oplus \emptyset' \leq_T Z \oplus \emptyset' \equiv_T Z \quad \text{et tel que} \quad G \oplus \emptyset' \geq_T Z.$$

Usant du fait que les 1-génériques sont low généralisés, on a donc $G' \equiv_T Z$. ■

Le théorème 3.31 permet également de déduire l'existence d'ensembles high et non Turing complets, et même non DNC.

**Corollaire 3.34**

Il existe un ensemble high, non DNC et en particulier non Turing complet.

**PREUVE.** Il suffit d'appliquer le théorème 3.31 pour trouver un ensemble 1-générique $G$ tel que $\emptyset' \oplus G \geq_T \emptyset''$, ce qui implique $G' \geq_T \emptyset''$. Notons que comme $G$ est 1-générique, il n'est pas de degré DNC, et ne calcule en particulier pas $\emptyset''$. ■
**3.4. Maigreur/co-maigreur des propriétés calculatoires**

Revenons un moment aux notions topologiques de classes maigres et de classes co-maigres introduites par Baire. Nous avons déjà mentionné que toute classe n’était pas forcément maigre ou co-maigre. C’est en revanche le cas pour les classes ayant de bonnes propriétés de clôture, et en particulier pour toutes celles dites boréliennes (nous définirons précisément ce terme dans le chapitre 17) et closes par équivalence Turing. Ce sera en particulier le cas de toutes les notions de calculabilité que nous verrons, et nous nous poserons la question de savoir si ces dernières sont maigres ou co-maigres. Aussi une classe est-elle sans perte de généralité co-maigre si elle contient tout élément *suffisamment générique*. En pratique, la 1-généricité est suffisante pour les différentes propriétés calculatoires vues jusqu’ici.

Nous avons les degrés high — les low en tant que classe dénombrable ne nous intéressent pas — les degrés calculatoirement dominés vs hyperimmunes, et enfin les degrés DNC et PA. La classe des ensembles de chacun de ces degrés est-elle maigre ou co-maigre ? Nous avons déjà la réponse en ce qui concerne les degrés calculatoirement dominés et hyperimmunes.

**Proposition 3.35.** La classe des ensembles calculatoirement dominés est maigre. Celle des ensembles hyperimmunes est co-maigre. ★

PREUVE. D’après le théorème 3.2, si $G$ est faiblement 1-générique, alors il n’est pas de degré calculatoirement dominé. ■

**Proposition 3.36.** La classe des ensembles DNC est maigre, ainsi bien sûr que la classe des ensembles PA. ★

PREUVE. D’après le théorème 3.21, si $X$ est 1-générique, alors il n’est pas de degré DNC, hors la classe des ensembles 1-génériques est co-maigre. ■

Nous nous attaquons à présent aux degrés high. Nous utilisons pour cela notre théorème 3.28 d’évitement de cône.

**Proposition 3.37.** Si $X$ est non calculable, alors la classe des ensembles qui calculent $X$ est maigre. ★

PREUVE. La classe des ensembles 1-génériques relativement à $X$ est une intersection d’ouverts denses, et est donc co-maigre. Par le théorème 3.28, aucun d’entre eux ne calcule $X$, et la classe des ensemble calculant $X$ est donc dans son complémentaire, une classe maigre. ■

Nous pouvons finalement montrer, en combinant ce que nous avons vu, que la classe des ensembles high est elle aussi maigre.
**Proposition 3.38.** La classe des ensembles high est maigre.

★

PREUVE. On utilise pour cela une version relativisée du théorème 3.28 : si $X$ n'est pas $\emptyset$-calculable, alors pour tout ensemble $G$ qui est 1-générique relativement à $X \oplus \emptyset'$ on a $G \oplus \emptyset' \not\ge_T X$. Cette version relativisée se montre de la même manière et ne présente pas de difficulté particulière.

On utilise à présent le théorème 3.20 : si l'ensemble $G$ est 1-générique, on a alors $G' \le_T G \oplus \emptyset'$. On en déduit que si $G$ est 1-générique, alors $G$ est high ssi $G \oplus \emptyset' \ge_T \emptyset$'$. Par ailleurs, d'après la version relativisée du théorème 3.28, aucun 1-générique relativement à $\emptyset$' n'est tel que $G \oplus \emptyset' \ge_T \emptyset$'$. Comme tout ensemble 1-générique relativement à $\emptyset$' est aussi 1-générique, on a donc qu'aucun 1-générique relativement à $\emptyset$' n'est high. La classe des ensembles high est donc maigre.

■

## 4. Forcing $\Sigma_n^0/\Pi_n^0$

Le concept de 1-généricité peut être vu comme un cadre formel effectif autour de la méthode des extensions finies, qui permet pour résumer de contrôler l'arrêt ou non de fonctionnelles, c'est-à-dire de contrôler la valeur de vérité de prédicats $\Sigma_1^0$ ou $\Pi_1^0$. Il s'agit d'un premier niveau de forcing : étant donné $\mathcal{R}_e$ un contrat $\Sigma_1^0$ ou $\Pi_1^0$, d'après le corollaire 3.18 toute chaîne $\sigma$ admet une extension $\tau \succeq \sigma$ telle que tout ensemble $X \in [\tau]$ satisfait $\mathcal{R}_e$ ou telle que tout ensemble $X \in [\tau]$ satisfait $\neg \mathcal{R}_e$.

À partir du niveau $\Sigma_2^0/\Pi_2^0$, les choses deviennent plus complexes et la méthode des extensions finies ne peut plus fonctionner de la même manière, comme en témoigne l'exemple suivant.

**Exemple 4.1.** Considérons le contrat $\mathcal{R} : \langle \exists x \forall y \ge x G(y) = 0 \rangle$, qui exprime la finitude de l'ensemble $G$. Pour tout $\sigma \in 2^{<\mathbb{N}}$, $[\sigma]$ contient à la fois un ensemble fini et un ensemble infini. Il n'existe donc aucun cylindre dont tous les éléments satisfont $\mathcal{R}$ ou dont tous les éléments satisfont $\neg \mathcal{R}$.

### Point sur les contrats

Nous nous attaquons à présent aux contrats $\Sigma_n^0$ (resp. $\Pi_n^0$) c'est-à-dire aux contrats portant sur un ensemble $G$ et qui s'expriment par une formule $\Sigma_n^0$ (resp. $\Pi_n^0$) de l'arithmétique du second ordre, avec $G$ comme variable d'ensemble libre. De manière équivalente, un contrat est $\Sigma_n^0$ s'il existe une fonctionnelle $\Phi_e(G, x_1, \dots, x_{n-1})$ telle que les ensembles $G$ satisfaisant le contrat sont ceux tels que :

$\exists x_1 \forall x_2 \dots \forall x_{n-1} \Phi_e(G, x_1, x_2, \dots, x_{n-1}) \downarrow$ pour $n$ impair

$\exists x_1 \forall x_2 \dots \exists x_{n-1} \Phi_e(G, x_1, x_2, \dots, x_{n-1}) \uparrow$ pour $n$ pair.
Les contrats $\Pi_n^0$ ont l'équivalence analogue en commençant par une quantification universelle. Par convention, la négation $\neg\mathcal{R}$ devant une formule $\Sigma_n^0$ (resp. $\Pi_n^0$) ne sera pas considérée comme un symbole du langage, mais comme une opération de transformation $\mathcal{R}$, qui inverse les quantificateurs, et remplace le prédicat $\Delta_0^0$ final par sa négation, pour faire de $\neg\mathcal{R}$ une formule $\Pi_n^0$ (resp. $\Sigma_n^0$).

Nous devons donc abstraire un peu les choses afin de donner une définition plus générale du forcing permettant de contrôler la valeur de vérité de prédicats de complexité arbitraire. Introduisons avant de commencer une définition qui sera utilisée dans les preuves à venir.

**Définition 4.2.** Un ensemble $D \subseteq 2^{<N}$ est dense sous la chaîne $\sigma$ si pour tout $\tau \supseteq \sigma$, il existe un $\rho \supseteq \tau$ tel que $\rho \in D$. ◇

**4.1. L'approche sémantique**

La relation de forcing sera définie par induction sur $n$, entre les chaînes finies et les prédicats $\Sigma_n^0$. Un des objectifs sera alors de conserver la propriété suivante.

(D) : L'ensemble des chaînes forçant $\mathcal{R}$ ou forçant $\neg\mathcal{R}$ est dense.

Afin d'examiner ce dont nous avons besoin, reprenons l'exemple précédent, à savoir un contrat $\mathcal{R} \Sigma_2^0$ arbitraire $\ll \exists x \Phi(G, x) \uparrow \gg$, et regardons ce qui ne fonctionne pas quand on essaye de prouver la densité de l'ensemble $Q \subseteq 2^{<N}$ des chaînes dont tous les éléments satisfont $\mathcal{R}$ ou dont tous les éléments satisfont $\neg\mathcal{R}$.

Soit $\sigma \in 2^{<N}$ une chaîne. Faisons une analyse de cas.

▷ Cas 1. Il existe une extension $\tau \supseteq \sigma$ et un entier $x \ge 1$ tel que pour tout $\rho \supseteq \tau$, $\Phi(\rho, x) \uparrow$. Dans ce cas, par la propriété de l'usage, pour tout $A \in [\tau]$, $\Phi(A, x) \uparrow$. Il s'ensuit que $\mathcal{R}$ est satisfait pour tout $A \in [\tau]$, donc que $\tau \in Q$.

▷ Cas 2. Pour toute extension $\tau \supseteq \sigma$ et tout $x \in \mathbb{N}$, il existe une chaîne $\rho \supseteq \tau$ telle que $\Phi(\rho, x) \downarrow$. C'est dans ce cas que notre tentative échoue. Pourtant, intuitivement, dans ce cas, nous devrions être capables de poursuivre la construction d'une suite tout en s'assurant que l'ensemble résultant satis-fasse $\neg\mathcal{R}$. En effet, quel que soit l'état d'avancement de la construction, nous nous retrouvons avec une chaîne $\tau \supseteq \sigma$, donc par hypothèse, pour tout $x \in \mathbb{N}$, il est toujours possible de trouver une extension $\rho \supseteq \tau$ telle que $\Phi(G, x) \downarrow$ pour tout $G \in [\rho]$ : pour tout $x$, l'ensemble $Q_x$ des chaînes $\rho$ telles que $\Phi(\rho, x) \downarrow$ est dense sous $\sigma$, c'est-à-dire que pour tout $\tau \supseteq \sigma$ il
existe $\rho \succeq \tau$ telle que $\rho \in Q_x$. Par conséquent, si un ensemble suffisamment générique $G$ étend $\sigma$, alors il rencontrera chacun des $Q_x$. On aura donc $\forall x \Phi(G, x) \downarrow$, autrement dit $G$ satisfera $\neg R$.

Cette analyse motive donc la définition suivante pour le forcing de Cohen.

**Définition 4.3.** Une chaîne $\sigma$ force sémantiquement un contrat $\mathcal{R}$, auquel cas on notera $\sigma \Vdash \mathcal{R}$, si tout ensemble << suffisamment générique >> qui étend $\sigma$ satisfait $\mathcal{R}$ : il existe une suite dénombrable d'ensembles de chaînes denses $(W_n)_{n \in \mathbb{N}}$ telle que si $G \in [\sigma]$ rencontre chaque $W_n$, alors le contrat sera satisfait pour $G$. ◇

Notons que la relation $\Vdash$ est plus générale que la relation $\Vdash^*$ pour les contrats $\Sigma_1^0$ et $\Pi_1^0$. Par exemple, la chaîne vide $\epsilon$ force sémantiquement le contrat $\mathcal{R} : \llcorner \exists x G(x) = 1 \rrcorner$, car l'ensemble des chaînes contenant un 1 est dense, et donc tout ensemble suffisamment générique satisfera $\mathcal{R}$. En revanche, la suite infinie de zéros $0^\infty$ appartient à $[\epsilon]$ et ne satisfait pas le contrat $\mathcal{R}$.

## 4.2. L'approche syntaxique

La définition 4.3 est simple à exprimer dans le langage naturel, mais sort de la hiérarchie arithmétique : une traduction directe demande de quantifier existentiellement sur toutes les suites dénombrables d'ensembles de chaînes denses, puis de quantifier universellement sur les ensembles génériques pour ces ensembles de chaînes. Nous allons définir une relation beaucoup plus simple syntaxiquement parlant, qui permettra de raisonner plus facilement et notamment de prouver les propriétés essentielles que l'on attend de la relation de forcing, à savoir qu'elle soit close par extension et que l'ensemble des chaînes forçant un contrat ou sa négation soit dense.

Définissons à présent une relation syntaxique de forcing pour tout contrat arithmétique, par induction sur ses quantifications. Le premier niveau sera celui auquel nous sommes déjà habitué : soit $\mathcal{R}$ un contrat $\Sigma_1^0$ — et donc de la forme $\Phi_e(G) \downarrow —$, alors une chaîne $\sigma$ force $\mathcal{R}$ si $\Phi_e(\sigma) \downarrow$, et donc si tout $X \in [\sigma]$ satisfait le contrat. Il en va de même pour les contrats $\Pi_1^0$.

**Définition 4.4**

(1) $\sigma \Vdash^* \mathcal{R}$ pour $\mathcal{R}$ un contrat $\Sigma_1^0$ ou $\Pi_1^0$ ssi tout $X \in [\sigma]$ satisfait $\mathcal{R}$.

(2) $\sigma \Vdash^* \exists x \mathcal{R}(x)$ pour $\mathcal{R}(x)$ un contrat $\Pi_k^0$ pour $k > 0$ avec variable libre $x$ ssi il existe un $n \in \mathbb{N}$ tel que $\sigma \Vdash^* \mathcal{R}(n)$.

(3) $\sigma \Vdash^* \forall x \mathcal{R}(x)$ pour $\mathcal{R}(x)$ un contrat $\Sigma_k^0$ pour $k > 0$ avec variable libre $x$ ssi pour tout $\tau \succeq \sigma$ et tout $n \in \mathbb{N}$, $\tau \Vdash^* \neg \mathcal{R}(n)$. ◇
Avant toute chose, remarquons que (3) de la définition précédente admet une formulation équivalente, parfois plus adaptée à ce que l'on veut démontrer.

**Lemme 4.5.** Soit $\mathcal{R}$ un contrat $\Pi_n^0$, on a $\sigma \Vdash^* \mathcal{R}$ ssi $\forall \tau \succeq \sigma \tau \Vdash^* \neg \mathcal{R}$. ★

*PREUVE.* Il s'agit d'une simple reformulation de la définition.

Cas 1. Le contrat $\mathcal{R}$ est $\Pi_1^0$, de la forme $\Phi(G)\uparrow$. Alors, $\sigma \Vdash^* \mathcal{R}$ ssi $\Phi(X)\uparrow$ pour tout $X \in [\sigma]$ ssi $\Phi(X)\uparrow$ pour tout $\tau \succeq \sigma$ et tout $X \in [\tau]$ ssi pour tout $\tau \succeq \sigma$, il existe $X \in [\tau]$ tel que $\Phi(X)\uparrow$ (par la propriété de l'usage) ssi pour tout $\tau \succeq \sigma$, $\tau \Vdash^* \Phi(G)\downarrow$.

Cas 2. Le contrat $\mathcal{R}$ est $\Pi_{k+1}^0$, de la forme $\forall x Q(x)$ pour $Q(x)$ un contrat $\Sigma_k^0$ pour $k \ge 1$. Alors, $\sigma \Vdash^* \mathcal{R}$ ssi pour tout $\tau \succeq \sigma$ et tout $n \in \mathbb{N}$, $\tau \Vdash^* \neg Q(n)$ ssi $\forall \tau \succeq \sigma \tau \Vdash^* \exists x \neg Q(x)$ ssi $\forall \tau \succeq \sigma \tau \Vdash^* \neg \mathcal{R}$. ■

La première propriété que l'on attend d'une relation de forcing est sa clôture par extension. En effet, $\llcorner \sigma \urcorner$ force $\mathcal{R} \urcorner$ signifie que la propriété $\mathcal{R}$ est déjà décidée sur l'objet final construit, ce qui ne doit pas changer au cours des étapes suivantes de la construction.

**Proposition 4.6.** Soient $\sigma, \tau \in 2^{<\mathbb{N}}$ et soit $\mathcal{R}$ un contrat arithmétique. Si $\sigma \Vdash^* \mathcal{R}$ et $\sigma \preceq \tau$, alors $\tau \Vdash^* \mathcal{R}$. ★

*PREUVE.* Par induction sur la complexité arithmétique du contrat.

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

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

Cas 3. Le contrat $\mathcal{R}$ est de la forme $\forall x S(x)$ pour $S(x)$ un contrat $\Sigma_k^0$ pour $k > 0$. D'après le lemme 4.5, $\sigma \Vdash^* \mathcal{R}$ implique $\forall \rho \succeq \sigma \rho \Vdash^* \neg \mathcal{R}$. Si $\tau \succeq \sigma$, alors on a aussi $\forall \rho \succeq \tau \rho \Vdash^* \neg \mathcal{R}$, ce qui encore d'après le lemme 4.5 implique $\tau \Vdash^* \mathcal{R}$. ■

La seconde propriété, et peut-être la plus importante, est la densité de l'ensemble des chaînes forçant un contrat ou sa négation. La proposition 4.7 signifie en particulier que la valeur de vérité de tout contrat arithmétique sera décidée au bout d'un moment fini de la construction. C'est ce qui donne toute la puissance de la relation de forcing.
**Proposition 4.7.** Soit $\mathcal{R}$ un contrat arithmétique. L'ensemble

$$ \{\sigma \in 2^{<\mathbb{N}} : \sigma \Vdash^* \mathcal{R} \text{ ou } \sigma \Vdash^* \neg \mathcal{R}\} $$

est dense.

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

**PREUVE.** On peut supposer sans perte de généralité que $\mathcal{R}$ est $\Sigma_n^0$ (dans le cas inverse, on répète l'argument avec $\neg \mathcal{R}$). Soit $\sigma$ une chaîne. D'après le lemme 4.5, soit $\tau \Vdash^* \mathcal{R}$ pour une extension $\tau \supseteq \sigma$, soit $\sigma \Vdash^* \neg \mathcal{R}$. ■

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

Une dernière propriété que l'on attend également est bien entendu la validité de la définition de la relation de forcing, c'est-à-dire que si une chaîne $\sigma$ force un contrat, alors ce contrat sera effectivement satisfait pour n'importe quel ensemble suffisamment générique qui étend $\sigma$. Insistons encore sur ce que signifie être << suffisamment générique >> dans ce contexte : il existe une suite dénombrable d'ensembles de chaînes denses $(W_n)_{n \in \mathbb{N}}$ telle que si $G \in [\sigma]$ rencontre chaque $W_n$, alors le contrat sera satisfait pour G.

**Proposition 4.8.** Soit $\mathcal{R}$ un contrat arithmétique et soit $\sigma \in 2^{<\mathbb{N}}$.

Si $\sigma \Vdash^* \mathcal{R}$, alors $\sigma \Vdash \mathcal{R}$ : si $G \in [\sigma]$ est suffisamment générique, alors $\mathcal{R}$ est satisfait pour G. ★

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

**PREUVE.** Par induction sur la complexité arithmétique du contrat.

Cas 1. Le contrat $\mathcal{R}$ est $\Sigma_1^0$ ou $\Pi_1^0$. Supposons que $\sigma \Vdash^* \mathcal{R}$. Par définition, tout ensemble $G \in [\sigma]$ satisfait $\mathcal{R}$, donc a fortiori tout ensemble suffisamment générique $G \in [\sigma]$. Ainsi, $\sigma \Vdash \mathcal{R}$.

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

Cas 3. Le contrat $\mathcal{R}$ est de la forme $\forall x S(x)$ pour $S(x)$ un contrat $\Sigma_k^0$ pour $k > 0$. Supposons que $\sigma \Vdash^* \forall x S(x)$. Par définition, pour tous $\tau \supseteq \sigma$ et $n \in \mathbb{N}$, $\tau \Vdash^* \neg S(x)$. Par la proposition 4.7, pour tout $n$, l'ensemble

$$ D_n = \{\tau \in 2^{<\mathbb{N}} : \tau \Vdash^* S(n)\} $$

est dense sous $\sigma$: pour tout $\tau \supseteq \sigma$ il existe $\rho \supseteq \tau$ tel que $\rho \Vdash^* S(n)$. Soit $G$ un ensemble suffisamment générique étendant $\sigma$. On suppose en particulier que le niveau de généricité de $G$ garanti qu'il rencontre chaque ensemble $D_n$. Donc, pour tout $n$, il existe un préfixe $\tau_n \prec G$ tel que $\tau_n \Vdash^* S(n)$. Pour une telle chaîne $\tau_n$, par hypothèse d'induction, il existe une suite dénombrable d'ensemble de chaînes dense $(D_{n,m})_{m \in \mathbb{N}}$ telle que si $G \in [\tau_n]$ rencontre chaque $D_{n,m}$, alors il satisfait $S(n)$. On a bien $G \in [\tau_n]$, et comme $G$ est suffisamment générique, il rencontre chaque $D_{n,m}$, et satisfait donc $S(n)$. Comme c'est le cas pour tout $n$, alors $G$ satisfait $\forall x S(x)$, donc $\sigma \Vdash \forall x S(x)$. ■
Le cœur du forcing se trouve sans doute dans la précédente proposition, et en particulier dans le cas 3 de sa preuve : c'est là que s'exerce le mécanisme de la relation $\sigma \Vdash^* \mathcal{R}$, qui garantit que si $G$ appartient à $[\sigma]$ et si $G$ est suffisamment générique, alors le contrat $\mathcal{R}$ sera satisfait pour $G$. Il s'agit en réalité d'une modification sophistiquée de la méthode des extensions finies, le point clef étant le suivant : peu importe le préfixe $\sigma$ de $G$ que l'on a construit jusqu'ici, on peut étendre $\sigma$ pour rencontrer n'importe quel ensemble de chaînes dense fixé à l'avance.

Nous voyons à présent dans la section suivante que cette idée n'est pas nouvelle : le mathématicien René Baire avait déjà formalisé l'ensemble de ces mécanismes au début du XXᵉ siècle, notamment via le théorème suivant : « toute classe borélienne a la propriété de Baire. »

### 4.3. L'approche topologique : la propriété de Baire

Une technique importante pour l'étude d'objets complexes en mathématiques consiste à se ramener à des objets plus simples tout en contrôlant la marge d'erreur d'approximation. En particulier, dans l'étude des ensembles, que cela soit du point de vue de la théorie de la mesure ou de la théorie des catégories, il existe un certain nombre de théorèmes de la forme « tout ensemble complexe est équivalent à un ensemble simple modulo une quantité négligeable d'éléments ». En théorie de la mesure par exemple, nous avons les trois principes de Littlewood [145], qui énoncent que tout ensemble mesurable est « presque » une réunion finie d'intervalle, toute fonction est « presque » continue, et toute suite convergente est « presque » uniformément convergente. Dans ce contexte « presque » signifie : « sauf sur un ensemble de mesure inférieure à $\varepsilon$ pour $\varepsilon$ aussi petit que l'on souhaite. »
La propriété de Baire exprime le fait qu'une classe $S$ est « presque » ouverte, où presque signifie dans ce contexte : « sauf sur une classe maigre. »

**Définition 4.9.** Une classe $\mathcal{B} \subseteq 2^\mathbb{N}$ a la propriété de Baire s'il existe un ouvert $U \subseteq 2^\mathbb{N}$ tel que $\mathcal{B}\Delta U$ est une classe maigre. Ici, $\mathcal{B}\Delta U$ est la classe des éléments sur lesquels $\mathcal{B}$ et $U$ ne coïncident pas, c'est-à-dire que

$$ (\mathcal{B} \setminus U) \cup (U \setminus \mathcal{B}). \quad \diamond $$

Considérons un contrat $\mathcal{R}$, et soient $\mathcal{B}_\mathcal{R}$ et $\mathcal{B}_{\mathcal{R}}$ les classes des éléments qui respectivement satisfont et ne satisfont pas ce contrat (en particulier, $\mathcal{B}_\mathcal{R} \cap \mathcal{B}_{\mathcal{R}} = \emptyset$ et $\mathcal{B}_\mathcal{R} \cup \mathcal{B}_{\mathcal{R}} = 2^\mathbb{N}$). Supposons que $\mathcal{B}_\mathcal{R}$ et $\mathcal{B}_{\mathcal{R}}$ aient tous les deux la propriété de Baire, et fixons deux ouverts $U_\mathcal{R}$ et $U_{\mathcal{R}}$ tels que $\mathcal{B}_\mathcal{R}\Delta U_\mathcal{R}$ et $\mathcal{B}_{\mathcal{R}}\Delta U_{\mathcal{R}}$ soient tous les deux maigres. Cela signifie qu'il existe une réunion dénombrable de fermés d'intérieur vide contenant $\mathcal{B}_\mathcal{R}\Delta U_\mathcal{R}$ et $\mathcal{B}_{\mathcal{R}}\Delta U_{\mathcal{R}}$. Par passage au complémentaire, il existe une
intersection dénombrable d'ouverts denses $\bigcap_n U_n$ telle que pour tout $X$ qui
lui appartient, on a d'un côté $X \in \mathcal{B}_R$ ssi $X \in \mathcal{U}_R$, et de l'autre $X \in \mathcal{B}_{\neg R}$
ssi $X \in \mathcal{U}_{\neg R}$.

En particulier, $X \in \mathcal{B}_R$ ssi il existe un préfixe $\sigma \prec X$ tel que $[\sigma] \subseteq \mathcal{U}_R$. On dira alors que $\sigma$ force le contrat $\mathcal{R}$. Notons que si $X \notin \mathcal{B}_R$, alors $X \in \mathcal{B}_{\neg R}$ et il existe à ce moment un préfixe $\sigma \prec X$ tel que $[\sigma] \subseteq \mathcal{U}_{\neg R}$. À ce moment, $\sigma$ force le contrat $\neg \mathcal{R}$. La définition suivante est simplement une reformulation de la définition 4.3 qui définit le forcing sémantique.

**Définition 4.10.** Soit $\mathcal{R}$ un contrat. On dit que $\sigma$ force sémantiquement
le contrat $\mathcal{R}$, et l'on écrit $\sigma \Vdash \mathcal{R}$ si $[\sigma] \setminus \mathcal{B}_{\mathcal{R}}$ est une classe maigre, où $\mathcal{B}_{\mathcal{R}}$
est la classe des éléments qui satisfont $\mathcal{R}$.
♦

Comme mentionné précédemment, la propriété fondamentale que l'on attend de la relation de forcing pour un contrat est la suivante.

(D) : L'ensemble des chaînes forçant $\mathcal{R}$ ou forçant $\neg \mathcal{R}$ est dense.

Nous commençons donc par une caractérisation des contrats pour lesquels
cette propriété est vraie, à l'aide de la propriété de Baire.

**Proposition 4.11.** Soit $\mathcal{R}$ un contrat, et soit $\mathcal{B}_R$ la classe des éléments qui satisfont $\mathcal{R}$. Les énoncés suivants sont équivalents :

(1) $\mathcal{B}_R$ a la propriété de Baire ;

(2) $\{\sigma \in 2^{<N} : \sigma \Vdash \mathcal{R} \text{ ou } \sigma \Vdash \neg \mathcal{R}\}$ est dense.

PREUVE. Soient $U_R = \{\sigma \in 2^{<N} : \sigma \Vdash \mathcal{R}\}$ et $U_{\neg R} = \{\sigma \in 2^{<N} : \sigma \Vdash \neg \mathcal{R}\}$.

(1) ⇒ (2). Supposons que $\mathcal{B}_R$ ait la propriété de Baire. Soit $\mathcal{U}$ un ouvert tel que $\mathcal{B}_R \Delta \mathcal{U}$ est maigre. En particulier, $\mathcal{U} \setminus \mathcal{B}_R$ est maigre, donc $\mathcal{U} \subseteq [U_R]$. De plus, $\mathcal{B}_R \setminus \mathcal{U} = (2^N \setminus \mathcal{U}) \setminus \mathcal{B}_{\neg R}$ est maigre, donc $\text{int}(2^N \setminus \mathcal{U}) \setminus \mathcal{B}_{\neg R}$ est maigre. Il s'ensuit que $\text{int}(2^N \setminus \mathcal{U}) \subseteq [U_{\neg R}]$. Comme $\mathcal{U} \cup \text{int}(2^N \setminus \mathcal{U})$ est dense dans $2^N$, il en est de même de $[U_R] \cup [U_{\neg R}]$, donc par l'exercice 2.8, $U_R \cup U_{\neg R}$ est dense dans $2^{<N}$.

(2) ⇒ (1). Supposons que $U_R \cup U_{\neg R}$ soit dense dans $2^{<N}$. Par densité, le complémentaire de $[U_R] \cup [U_{\neg R}]$ est un fermé d'intérieur vide, donc maigre. Montrons que $\mathcal{B}_R \Delta [U_R]$ est maigre. Par définition, pour tout $\sigma \in U_R$, la classe $[\sigma] \setminus \mathcal{B}_R$ est maigre, donc $[U_R] \setminus \mathcal{B}_R$ est réunion dénombrable de classes maigres, donc est maigre. Par le même raisonnement, si $\mathcal{B}_{\neg R}$ est la classe des éléments qui satisfont $\neg \mathcal{R}$, alors $[U_{\neg R}] \setminus \mathcal{B}_{\neg R}$ est maigre. Comme $[U_{\neg R}] \setminus \mathcal{B}_{\neg R}$ et $\mathcal{B}_R \cap [U_{\neg R}]$ sont égaux, et comme le complémentaire de $[U_R] \cup [U_{\neg R}]$ est maigre, alors $\mathcal{B}_R \setminus [U_R]$ est maigre. Ainsi, $\mathcal{B}_R \Delta [U_R]$ est maigre. $\blacksquare$

La relation de forcing syntaxique impliquant la relation sémantique, nous pouvons en déduire la densité de la relation de forcing sémantique pour les contrats arithmétiques.
**Lemme 4.12.** Soit $\mathcal{R}$ est un contrat arithmétique. L'ensemble

$$ \{\sigma \in 2^{<\mathbb{N}} : \sigma \Vdash \mathcal{R} \lor \sigma \Vdash \neg \mathcal{R}\} $$

est dense.

*

**PREUVE.** Pour tout $\sigma$, il existe une extension $\tau \succeq \sigma$ telle que $\tau \Vdash^* \mathcal{R}$ ou telle que $\tau \Vdash^* \neg \mathcal{R}$. Si $\tau \Vdash^* \mathcal{R}$, alors $\tau \Vdash \mathcal{R}$, et si $\tau \Vdash^* \neg \mathcal{R}$, alors $\tau \Vdash \neg \mathcal{R}$. ■

Le corollaire suivant découle directement de la caractérisation des classes ayant la propriété de Baire.

**Corollaire 4.13**

Soit $\mathcal{R}$ est un contrat arithmétique. La classe $\mathcal{B}_{\mathcal{R}}$ des éléments qui satis-
font $\mathcal{R}$, a la propriété de Baire.

**PREUVE.** Immédiat par le lemme 4.12 et la proposition 4.11.

■

Nous développerons dans le chapitre 17 et la section 27-3.1 la théorie des classes boréliennes, qui formalise et généralise la notion de contrats arithmétiques, et qui ont toutes la propriété de Baire.

Terminons cette section en clarifiant les liens entre la relation de forcing sémantique et la relation syntaxique $\Vdash^*$, que nous avons définies plus haut.

**Théorème 4.14**

Soit $\mathcal{R}$ un contrat arithmétique. Alors, $\sigma \Vdash \mathcal{R}$ si, et seulement si, l'ense-
semble $\{\tau \in 2^{<\mathbb{N}} : \tau \Vdash^* \mathcal{R}\}$ est dense sous $\sigma$.

Pour montrer le théorème, nous utiliserons deux lemmes. Le premier cor-
respond à la proposition 4.6 pour la relation $\Vdash^*$.

**Lemme 4.15.** Supposons $\sigma \Vdash \mathcal{R}$ pour une chaîne $\sigma$ et un contrat $\mathcal{R}$.
Si $\tau \succeq \sigma$, alors $\tau \Vdash \mathcal{R}$.

*

**PREUVE.** Soit $\mathcal{B}_{\mathcal{R}}$ la classe des éléments qui satisfont $\mathcal{R}$. On a visiblement $[\tau] \setminus \mathcal{B}_{\mathcal{R}} \subseteq [\sigma] \setminus \mathcal{B}_{\mathcal{R}}$. Donc, si $[\sigma] \setminus \mathcal{B}_{\mathcal{R}}$ est maigre, alors $[\tau] \setminus \mathcal{B}_{\mathcal{R}}$ est maigre. ■

■

**Lemme 4.16.** Supposons $\sigma \Vdash \mathcal{R}$ pour une chaîne $\sigma$ et un contrat $\mathcal{R}$.
Alors, $\sigma \Vdash \neg \mathcal{R}$

*

**PREUVE.** Soit $\mathcal{B}_{\mathcal{R}}$ la classe des éléments qui satisfont $\mathcal{R}$, et soit $\mathcal{B}_{\neg \mathcal{R}}$ la classe des éléments qui satisfont $\neg \mathcal{R}$. Supposons par l'absurde $\sigma \Vdash \mathcal{R}$ et $\sigma \Vdash \neg \mathcal{R}$. Alors, les classes $[\sigma] \setminus (\mathcal{B}_{\mathcal{R}} \cap [\sigma])$ et $[\sigma] \setminus (\mathcal{B}_{\neg \mathcal{R}} \cap [\sigma])$ sont toutes deux maigres. Par ailleurs, $([\sigma] \setminus (\mathcal{B}_{\mathcal{R}} \cap [\sigma])) \cup ([\sigma] \setminus (\mathcal{B}_{\neg \mathcal{R}} \cap [\sigma])) = [\sigma]$, ce qui contredit le fait que la réunion de deux classes maigres soit maigre et donc d'intérieur vide. ■
PREUVE DU THÉORÈME 4.14. Rappelons la proposition 4.8 : pour tout contrat $\mathcal{R}$ arithmétique et pour tout $\sigma$, si $\sigma \Vdash^* \mathcal{R}$, alors $\sigma \Vdash \mathcal{R}$.

Montrons que si $\{\tau \in 2^{<\mathbb{N}} : \tau \Vdash^* \mathcal{R}\}$ est dense sous $\sigma$, alors $\sigma \Vdash \mathcal{R}$.
D'après la proposition 4.8, $A = \{\tau \in 2^{<\mathbb{N}} : \tau \Vdash \mathcal{R}\}$ est dense sous $\sigma$. La classe $\{X \in [\sigma] : \forall n X \upharpoonright_n \mathcal{W} \mathcal{R}\}$ est donc un fermé d'intérieur vide, que l'on notera $\mathcal{F}$. Soit $\mathcal{B}_{\mathcal{R}}$ la classe des éléments qui satisfont $\mathcal{R}$. Par définition de $A$, pour tout $\tau \in A$, la classe $M_{\tau} = [\tau] \setminus (\mathcal{B}_{\mathcal{R}} \cap [\tau])$ est maigre. Il s'ensuit que la classe $[\sigma] \setminus (\mathcal{B}_{\mathcal{R}} \cap [\sigma])$ est incluse dans la réunion de $\mathcal{F}$ et de toutes les classes $M_{\tau}$. Elle est donc maigre.

Montrons enfin que si $\sigma \Vdash \mathcal{R}$, alors $\{\tau \in 2^{<\mathbb{N}} : \tau \Vdash^* \mathcal{R}\}$ est dense sous $\sigma$. Par contraposée, supposons qu'il existe $\tau \supseteq \sigma$ tel que pour tout $\rho \supseteq \tau$ on a $\rho \Vdash^* \mathcal{R}$. Au vu de la proposition 4.7, il doit alors exister $\rho \supseteq \tau$ tel que $\rho \Vdash^* \neg \mathcal{R}$. Et, par la proposition 4.8, on a alors $\rho \Vdash \neg \mathcal{R}$. D'après le lemme 4.16, $\rho \Vdash^* \mathcal{R}$, et l'on a donc d'après le lemme 4.15 $\sigma \Vdash^* \mathcal{R}$. ■

# 5. Ensembles arbitrairement génériques

La généricité peut être vue comme une notion de « typicité », au sens où tout ce qui peut arriver infiniment souvent finira par arriver. Dans le cas du forcing de Cohen, un ensemble dense a infiniment souvent la possibilité d'être rencontré, et cela arrivera si un ensemble est typique, ce qui correspond à la notion d'ensemble générique.

Nous avons vu les relativisations des ensembles faiblement 1-génériques et 1-génériques, et notamment les concepts de *n*-générique et faiblement *n*-générique. Nous étudions dans cette section les propriétés des ensembles typiques, c'est-à-dire les propriétés que vont avoir les ensembles suffisamment génériques.

Notons que si une propriété est vérifiée par tout ensemble suffisamment générique, elle est sans perte de généralité vérifiée pour tout ensemble faiblement 1-générique relativement à A pour un certain oracle A suffisamment puissant : il suffit que A encode l'intersection d'ouverts denses correspondant au niveau de généricité requis. On s'attachera donc à déterminer « le bon niveau » de généricité nécessaire pour satisfaire telle ou telle propriété. En pratique, cela correspondra souvent à être *n*-générique pour un certain *n*.

## 5.1. Propriétés des ensembles suffisamment génériques

Nous avons vu que la 1-généricité était le niveau de généricité correspondant au forcing des contrats $\Sigma_1^0/\Pi_1^0$. Sans surprise, nous voyons à présent que la *n*-généricité est le niveau de généricité correspondant au forcing des contrats $\Sigma_n^0/\Pi_n^0$, et nous allons montrer le théorème suivant.
**Théorème 5.1**

Soit $G$ un ensemble $n$-générique. Soit $\mathcal{R}$ un contrat $\Sigma_n^0$ ou $\Pi_n^0$. Alors, $G$ satisfait $\mathcal{R}$ si, et seulement si, il existe un préfixe $\sigma < G$ tel que $\sigma \Vdash^* \mathcal{R}$.

Notons que cette itération n’est pas triviale : il faut faire appel pour cela aux développements de la relation de forcing des sections précédentes.

Nous allons maintenant passer à la preuve du théorème 5.1 en exploitant la simplicité définitionnelle de la relation de forcing syntaxique. Commençons par la proposition suivante.

**Proposition 5.2.** Soit $\mathcal{R}$ un contrat arithmétique.

(1) Si $\mathcal{R}$ est $\Sigma_n^0$, alors le prédicat $\sigma \Vdash^* \mathcal{R}$ est $\Sigma_n^0$.

(2) Si $\mathcal{R}$ est $\Pi_n^0$, alors le prédicat $\sigma \Vdash^* \mathcal{R}$ est $\Pi_n^0$.

*

**PREUVE.** Nous allons prouver (1) et (2) simultanément par induction sur la complexité arithmétique du contrat. Le cas $\Sigma_1^0$ et $\Pi_1^0$ a déjà été traité avec la proposition 3.17.

Si $\mathcal{R}$ est $\Sigma_{m+1}^0$ avec $m > 0$, alors il peut s'exprimer sous la forme $\exists x \mathcal{S}(x)$, où $\mathcal{S}$ est un contrat $\Pi_m^0$. On a $\sigma \Vdash^* \mathcal{R}$ si, et seulement si, il existe un $n \in \mathbb{N}$ tel $\sigma \Vdash^* \mathcal{S}(n)$. Par hypothèse d'induction, le prédicat $\sigma \Vdash^* \mathcal{S}(n)$ est $\Pi_m^0$, et le prédicat $\sigma \Vdash^* \mathcal{R}$ est donc $\Sigma_{m+1}^0$.

Si $\mathcal{R}$ est $\Pi_{m+1}^0$ avec $m > 0$, alors il peut s'exprimer sous la forme $\forall x \mathcal{S}(x)$ où $\mathcal{S}$ est un contrat $\Sigma_m^0$. On a $\sigma \Vdash^* \mathcal{R}$ ssi pour tout $\tau \ge \sigma$ et tout $n$ dans $\mathbb{N}$, $\tau \Vdash^* \neg \mathcal{S}(n)$. En particulier, $\neg \mathcal{S}(n)$ est $\Pi_m^0$, donc par hypothèse d'induction, le prédicat $\tau \Vdash^* \neg \mathcal{S}(n)$ est $\Pi_m^0$, donc $\tau \Vdash^* \neg \mathcal{S}(n)$ est $\Sigma_m^0$, et le prédicat $\sigma \Vdash^* \mathcal{R}$ est $\Pi_{m+1}^0$. $\blacksquare$

Nous voyons à présent le niveau de généricité requis pour rendre vraie la proposition 4.8.

**Proposition 5.3.** Soit $\mathcal{R}$ un contrat arithmétique tel que $\sigma \Vdash^* \mathcal{R}$ pour $\sigma$ dans $2^{<\mathbb{N}}$.

(1) Si $\mathcal{R}$ est $\Sigma_n^0$, alors $\mathcal{R}$ est satisfait pour tout faiblement $(n-2)$-générique qui étend $\sigma$.

(2) Si $\mathcal{R}$ est $\Pi_n^0$, alors $\mathcal{R}$ est satisfait pour tout faiblement $(n-1)$-générique qui étend $\sigma$.

*

**PREUVE.** Par la définition de la relation de forcing, si $\mathcal{R}$ est $\Sigma_1^0$ ou $\Pi_1^0$, alors il est satisfait pour tout ensemble qui étend $\sigma$. Supposons la proposition vraie pour $n$. Soit $\mathcal{R} = \exists x \mathcal{Q}(x)$ un contrat $\Sigma_{n+1}^0$, avec $\mathcal{Q}(x)$ un contrat $\Pi_n^0$. On a $\sigma \Vdash^* \mathcal{R}$ si, et seulement si, il existe $m \in \mathbb{N}$ tel que $\sigma \Vdash^* \mathcal{Q}(m)$. Par hypothèse d'induction, $\mathcal{Q}(m)$ est satisfait pour tout ensemble $(n-1)$-générique qui étend $\sigma$, et il en est donc de même pour $\mathcal{R}$.
Supposons à présent que $\mathcal{R} = \forall x Q(x)$ est un contrat $\Pi_{n+1}^0$, avec $Q(x)$ un contrat $\Sigma_n^0$. On a $\sigma \Vdash^* \mathcal{R}$ si, et seulement si, pour tout $m \in \mathbb{N}$ et pour tout $\tau \succeq \sigma$,
$$ \tau \Vdash^* \neg Q(m). $$

D'après la proposition 5.7, cela signifie que pour $m$ entier fixé l'ensemble $A_m = \{\tau \cdot \tau \Vdash^* Q(m)\}$ est dense sous $\sigma$. D'après la proposition 5.2, chaque ensemble $A_m$ est $\Sigma_n^0$. En particulier, si $G$ est faiblement $n$-générique et étend $\sigma$, alors $G$ rencontre $A_m$. Par hypothèse d'induction, si $G$ rencontre $A_m$ et est $n$-générique, alors $Q(m)$ est vrai pour $G$. Comme c'est le cas pour tout $m$, alors $\mathcal{R}$ est vrai pour tout ensemble $n$-générique $G$ qui étend $\sigma$. ■

Nous pouvons finalement montrer le théorème 5.1.

**PREUVE DU THÉORÈME 5.1.** Le cas $\Sigma_1^0/\Pi_1^0$ a déjà été traité au moyen du théorème 3.12. Soit $n > 1$. On peut supposer sans perte de généralité que $\mathcal{R}$ est $\Sigma_n^0$. Dans le cas inverse, on reproduit l'argument suivant avec $\neg \mathcal{R}$ à la place de $\mathcal{R}$.

Soit $U = \{\sigma \in 2^{<\mathbb{N}} : \sigma \Vdash^* \mathcal{R}\}$. D'après le lemme 4.5,

$$ U^{\perp} = \{\sigma \in 2^{<\mathbb{N}} : \sigma \Vdash^* \neg \mathcal{R}\}. $$

D'après la proposition 5.2, l'ensemble $U$ est $\Sigma_n^0$, et l'ensemble $U^{\perp}$ est $\Pi_n^0$. Notons que comme $G$ est $n$-générique, il rencontre $U \cup U^{\perp}$.

Supposons que $\mathcal{R}$ soit satisfait sur $G$. Alors, $G$ ne peut pas rencontrer $U^{\perp}$, car on aurait dans ce cas un préfixe $\sigma \prec G$ tel que $\sigma \Vdash^* \neg \mathcal{R}$ et, par la proposition 5.3, $\neg \mathcal{R}$ serait donc satisfait sur $G$, ce qui contredit le fait que $\mathcal{R}$ soit satisfait sur $G$. Donc, $G$ rencontre $U$, et l'on a un préfixe $\sigma \prec G$ tel que $\sigma \Vdash^* \mathcal{R}$.

Supposons que $\neg \mathcal{R}$ soit satisfait sur $G$. Symétriquement, $G$ rencontre nécessairement $U^{\perp}$, et l'on a un préfixe $\sigma \prec G$ tel que $\sigma \Vdash^* \mathcal{R}$.

Réciproquement, si un préfixe $\sigma \prec G$ est tel que $\sigma \Vdash^* \mathcal{R}$ ou $\sigma \Vdash^* \neg \mathcal{R}$, alors respectivement $\mathcal{R}$ ou $\neg \mathcal{R}$ est satisfait sur $G$, d'après la proposition 5.3. ■

## 5.2. Degré Turing des ensembles suffisamment générique

Récapitulons d'abord un résultat que nous avons déjà établi : étant donné un ensemble $A$, si $G$ est suffisamment générique, alors $A$ ne calcule pas $G$ et $G$ ne calcule pas $A$.
**Théorème 5.4**

Soit $A \in 2^N$ un ensemble non calculable. Si $G$ est 1-générique relative à $A$, alors $A$ et $G$ sont dans des degrés Turing incomparables.

**PREUVE.** D'après l'exercice 3.5 et l'exercice 3.6, si $G$ est faiblement 1-générique relativement à $A$, il est de degré $A$-hyperimmune, et ne peut donc être calculé par $A$. D'après le théorème 3.28, si $G$ est 1-générique relativement à $A$, il ne calcule pas $A$. ■

Notons que le théorème 5.4 peut être généralisé pour montrer que pour toute suite dénombrable d'ensembles fixée à l'avance $A_0, A_1, \dots$, tout ensemble $G$ suffisamment générique pour le forcing de Cohen est incomparable avec les éléments de cette liste. En effet, si $G$ est suffisamment générique, il sera 1-générique relativement à $A_i$ pour tout $i$. Ce résultat, malgré sa simplicité, admet plusieurs conséquences intéressantes.

**Corollaire 5.5**

Soit $G$ un ensemble suffisamment générique pour le forcing de Cohen. Alors, $G$ n'est pas arithmétique et ne calcule aucun ensemble arithmétique non calculable.

Voyons à présent comment renforcer et itérer le théorème 5.4 : pour $A$ non $\emptyset^{(n)}$-calculable, si un ensemble $G$ est suffisamment générique, non seulement il ne calculera pas $A$, mais aussi son $n$-ième saut Turing ne calculera pas $A$. Nous allons en fait voir quelque chose d'un peu plus précis : si $A$ n'est pas $\Sigma_n^0$ et si $G$ est suffisamment générique, alors $A$ ne sera pas $\Sigma_n^0(G)$. Assurons-nous d'abord de la complexité du contrat $a \in G^{(n)}$, via le lemme suivant.

**Lemme 5.6.** Pour tout $a \in \mathbb{N}$, le contrat $a \in X^{(n)}$ est $\Sigma_n^0$ uniformément en $a$. ★

**PREUVE.** Pour le cas $n = 1$, on a $a \in X'$ ssi $\Phi_a(X, a) \downarrow$, ce qui est bien un contrat $\Sigma_1^0$. Au cas $n$, supposons que $F_n(G, x)$ soit une formule $\Sigma_n^0$ de l'arithmétique du second ordre telle que pour tout $X \in 2^N$ et pour tout $a \in \mathbb{N}$, la formule $F(X, a)$ est vraie ssi $a \in X^{(n)}$. On a alors :

$$ 
\begin{align*}
a \in X^{(n+1)} &\iff \exists \sigma \ \forall i < |\sigma| \left( \bigvee \begin{array}{@{}l@{}} (\sigma(i)=0 \land i \notin X^{(n)}) \\ (\sigma(i)=1 \land i \in X^{(n)}) \end{array} \right) \land \Phi_a(\sigma, a) \downarrow \\
&\iff \exists \sigma \ \forall i < |\sigma| \left( \bigvee \begin{array}{@{}l@{}} (\sigma(i)=0 \land \neg F_n(X, i)) \\ (\sigma(i)=1 \land F_n(X, i)) \end{array} \right) \land \Phi_a(\sigma, a) \downarrow.
\end{align*}
$$

En utilisant le fait que $\neg F_n(G, x)$ et $F_n(G, x)$ sont toutes les deux des formules $\Sigma_{n+1}^0$, et en utilisant la clôture des formules $\Sigma_{n+1}^0$ par quantifi-
cation bornée, réunion finie et intersection finie, on peut définir une formule $\Sigma_{n+1}^0 H(G, \tau)$ telle que

$$H(X, \sigma) \leftrightarrow \forall i < |\sigma| ((\sigma(i) = 0 \land \neg F_n(X, i)) \lor (\sigma(i) = 1 \land F_n(X, i))).$$

Alors,

$$a \in X^{(n+1)} \leftrightarrow \exists \sigma H(X, \sigma) \wedge \Phi_a(\sigma, a)\downarrow,$$

ce qui est bien une formule $\Sigma_{n+1}^0$.

### Théorème 5.7

Soit A un ensemble non $\Sigma_{n+1}^0$ pour un entier $n \ge 0$. Alors, pour tout ensemble G 1-générique relativement à $A \oplus \emptyset^{(n)}$, A n'est pas $\Sigma_{n+1}^0(G)$.

PREUVE. Soit G un ensemble 1-générique relativement à $A \oplus \emptyset^{(n+1)}$. Il s'agit de montrer que pour tout $e$ l'ensemble $A$ est différent de $W_e^{G^{(n)}}$, l'ensemble $G^{(n)}$-c. e. de code $e$. Soit

$$U = \{\sigma : \exists m \notin A \sigma \Vdash^* m \in W_e^{G^{(n)}}\}.$$

D'après le lemme 5.6, le contrat $m \in W_e^{G^{(n)}}$ est $\Sigma_{n+1}^0$. Par suite, d'après la proposition 5.2, l'ensemble $U$ est $\Sigma_1^0(A \oplus \emptyset^{(n)})$. Si $G$ rencontre $U$, alors d'après la proposition 5.3 il existe $m \notin A$ tel que $m \in W_e^{G^{(n)}}$, et $A \ne W_e^{G^{(n)}}$. Si $G$ ne rencontre pas $U$, comme l'ensemble $G$ est 1-générique relativement à $A \oplus \emptyset^{(n+1)}$, $G$ rencontre $U^\perp = \{\sigma : \forall m \notin A \forall \tau \succeq \sigma \tau \Vdash^* m \in W_e^{G^{(n)}}\}$. D'après le lemme 4.5, on a

$$U^\perp = \{\sigma : \forall m \notin A \sigma \Vdash^* m \notin W_e^{G^{(n)}}\}.$$

Soit $\sigma \in U^\perp$ une chaîne fixée. Alors, l'ensemble

$$D_\sigma = \{m : \sigma \Vdash^* m \notin W_e^{G^{(n)}}\}$$

est un ensemble $\Pi_{n+1}^0$, qui par hypothèse contient $\mathbb{N} \setminus A$. Comme $\mathbb{N} \setminus A$ n'est pas $\Pi_{n+1}^0$, il y a forcément un élément $m \in A$ tel que $m \in D_\sigma$. Donc,

$$U^\perp \subseteq \{\sigma : \exists m \in A \sigma \Vdash^* m \notin W_e^{G^{(n)}}\}.$$

Alors, d'après la proposition 5.3, on aura $m \notin W_e^{G^{(n)}}$ pour $m \in A$, et donc $A \ne W_e^{G^{(n)}}$. ■

### Corollaire 5.8

Soit A un ensemble non $\emptyset^{(n)}$-calculable pour $n \ge 0$. Alors, si $G$ est 1-générique relativement à $A \oplus \emptyset^{(n)}$, l'ensemble A n'est pas $G^{(n)}$-calculable.

PREUVE. Comme A n'est pas $\emptyset^{(n)}$-calculable, il n'est pas $\Delta_{n+1}^0$. Comme A n'est pas $\Delta_{n+1}^0$, soit A n'est pas $\Sigma_{n+1}^0$, soit $\bar{A}$ n'est pas $\Sigma_{n+1}^0$. Par le
théorème 5.7, pour tout ensemble $G$ 1-générique relativement à $A \oplus \emptyset^{(n)}$, l'ensemble $A$ n'est pas $\Sigma_{n+1}^0(G)$ dans le premier cas, et $\bar{A}$ n'est pas $\Sigma_{n+1}^0(G)$ dans le second cas. Dans tous les cas, $A$ n'est pas $\Delta_{n+1}^0(G)$, et il n'est donc pas $G^{(n)}$-calculable. ■

Nous avons vu avec le théorème 3.20 que le saut Turing était une fonction continue sur la classe des ensembles 1-génériques : les 1-génériques sont tous low généralisé. Ce résultat se relativise : le n-ième saut Turing est une fonction continue sur la classe des ensembles n-génériques.

**Théorème 5.9**

Soit $G$ un ensemble n-générique. Alors, $G^{(n)} \leq_T G \oplus \emptyset^{(n)}$.

PREUVE. Soit $n > 0$, et soit $G$ un ensemble n-générique. Soit

$$U_e = \{\sigma : \sigma \Vdash^* e \in G^{(n)}\}.$$

D'après le lemme 5.6, le contrat $e \in G^{(n)}$ est $\Sigma_n^0$, et $U_e$ est donc un ensemble $\Sigma_n^0$. Considérons $U_e^{\perp} = \{\sigma : \forall \tau \supseteq \sigma \ \tau \Vdash^* e \in G^{(n)}\}$. En particulier, $U_e^{\perp}$ est un ensemble $\Pi_n^0$. D'après le lemme 4.5,

$$U_e^{\perp} = \{\sigma : \sigma \Vdash^* e \notin G^{(n)}\}.$$

Comme $G$ est n-générique, il rencontre $U_e \cup U_e^{\perp}$. Il suffit à l'aide de $\emptyset^{(n)}$ de chercher un préfixe de $G$ dans $U_e$ ou $U_e^{\perp}$. D'après la proposition 5.3, on a dans le premier cas $e \in G^{(n)}$, et dans le second $e \notin G^{(n)}$. ■

Notons que le corollaire 5.8 se déduit aussi du théorème précédent et d'une version relativisée du théorème 3.28. Attention ! Dans la littérature, la notion de low$_n$-généralisé ne correspond pas à la propriété du théorème 5.9.

**Définition 5.10.** Un ensemble $G \in 2^\mathbb{N}$ est low$_n$ généralisé si

$$G^{(n)} \leq_T (G \oplus \emptyset')^{(n-1)}. \diamond$$

Notons que si $X$ est low$_n$ généralisé, il est aussi low$_{n+1}$ généralisé. Chaque ensemble n-générique est bien low$_n$ généralisé, mais le théorème 5.9 prouve quelque chose de plus fort.
<figure><img src="image_79.png" /></figure>
Chapitre 11

Forcing effectif

Fort des intuitions créées avec l'étude du forcing de Cohen, nous pouvons
alors introduire les notions abstraites de forcing sur un ordre partiel arbi-
traire, et développer toute la machinerie associée.

1. Fondements du forcing

Maintenant que nous nous sommes familiarisés avec les notions de densité
et de généricité sur l'ordre partiel des chaînes binaires, muni de la rela-
tion d'extension, nous sommes prêts à aborder les concepts du forcing dans
toute leur généralité, tout en conservant les intuitions de la méthode des ex-
tensions finies. Les bénéfices de cette abstraction n'apparaîtront qu'à partir
de l'introduction de la relation de forcing, qui donne toute sa puissance au
formalisme. Jusqu'ici, nous avons vu la notion de généricité dans l'ordre
partiel des chaînes binaires comme une systématisation des constructions
avec la méthode des extensions finies.

**Ordre partiel.** Dans toute sa généralité, une notion de forcing est tout simplement un ordre partiel ($\mathbb{P}$, $\leqslant$), dont les éléments sont appelés *condi-tions*. Une condition représente intuitivement une approximation de l'objet que l'on est en train de construire. Une *extension* de $c \in \mathbb{P}$ est une condi-tion $d \leqslant c$.

Remarque

Attention, pour des raisons historiques, la relation d'ordre du forcing est
inversée. Une extension d'une condition *c* est donc une condition *d* plus
petite. L'idée sous-jacente vient du fait que *d* est une approximation plus
précise que *c*, et qu'ainsi l'ensemble des objets « candidats » que l'on
est en train de construire est un sous-ensemble des candidats de $c$, car plus l'on ajoute de contraintes, plus l'on exclut des candidats.

**Filtre.** Dans le cas de la méthode des extensions finies, l'objet construit est un élément de $2^N$, à l'aide d'une suite infinie strictement croissante de chaînes. Dans le langage d'un ordre partiel arbitraire, nous allons construire une suite infinie décroissante de conditions. L'objet produit est un filtre maximal.

**Définition 1.1.** Deux conditions $c_0, c_1$ sont compatibles s'il existe une condition $d$ qui étend à la fois $c_0$ et $c_1$. Dans le cas contraire, $c_0$ et $c_1$ sont incompatibles. Un filtre est un ensemble $F \subseteq \mathbb{P}$ clos par le haut, tel que pour tous $c_0, c_1 \in F$, il existe une condition $d \in F$ telle que $d \le c_0, c_1$. Un filtre est maximal s'il n'est pas inclus dans un filtre strictement plus grand. ◇

Si l'on considère l'ordre partiel sur les chaînes, muni de la relation de suffice, les filtres maximaux sont en correspondance bijective avec l'espace de Cantor. En effet, pour tout $X \in 2^N$, l'ensemble $\{X \upharpoonright_n : n \in \mathbb{N}\}$ est un filtre maximal, et tout filtre maximal est inversement de cette forme.

Dans le cadre d'un ordre partiel dénombrable, il peut être plus intuitif de se représenter un filtre comme la clôture par le haut d'une suite infinie décroissante de conditions. En particulier, pour toute chaîne infinie décroissante de conditions $c_0 \ge c_1 \ge c_2 \ge \dots$, l'ensemble

$$F = \{d \in \mathbb{P} : \exists n \ c_n \le d\}$$

est un filtre. Cette intuition correspond plus à la construction de la méthode des extensions finies.

**Notation**

Comme expliqué, une condition $c \in \mathbb{P}$ peut être vue comme une approximation de l'objet que l'on construit, à savoir un filtre maximal. On peut donc associer à chaque condition l'ensemble $[c]_\epsilon$ des filtres maximaux contenant $c$, représentant les objets candidats. En particulier, suivant l'intuition, si $d \le c$, alors l'approximation $d$ est plus précise que l'approximation $c$, réduisant ainsi le nombre de candidats. On a dont $[d]_\epsilon \subseteq [c]_\epsilon$.

Remarquons que pour tout filtre maximal $F$, $\bigcap_{c \in F} [c]_\epsilon = \{F\}$. Autrement dit, $F$ est l'unique candidat de toutes les conditions du filtre simultanément. Nous avons déjà rencontré plusieurs notions de forcing au cours des chaînes précédents. En voici quelques-uns. Nous allons voir que pour chacune de ces notions de forcing, les filtres maximaux peuvent être interprétés comme des ensembles d'entiers.
**Exemple 1.2.**

1. Le forcing de Cohen est l'ordre partiel des chaînes muni de sa relation de suffixe ($2^{<\mathbb{N}}$, $\succeq$). Pour tout $\sigma \in 2^{<\mathbb{N}}$, $[\sigma]_\infty$ est en bijection avec l'ensemble $[\sigma] = \{X \in 2^{\mathbb{N}} : \sigma \prec X\}$, par la fonction qui à $F \in [\sigma]_\infty$ associe l'unique élément de $\bigcap_{\sigma \in F}[\sigma]$.

2. Le forcing de Jockusch-Soare est l'ordre partiel des classes $\Pi_1^0$ non vides, ordonnés par la relation d'inclusion. Pour toute classe $\Pi_1^0 \mathcal{P}$, l'ensemble $[\mathcal{P}]_\infty$ est en bijection avec $\mathcal{P}$. Un filtre maximal $F$ contenant $\mathcal{P}$ peut donc être vu comme l'unique élément de $\bigcap_{Q \in F} Q$, qui est un membre de $\mathcal{P}$.

3. Le forcing de Sacks est l'ordre partiel des f-arbres calculables, ordonnées par la relation de sous-f-arbre. Pour tout f-arbre calculable $T$, l'ensemble $[T]_\infty$ est en bijection avec l'ensemble

$$[T] = \{ \bigcup_n T(X \upharpoonright_n) : X \in 2^{\mathbb{N}} \} = \{ Y \in 2^{\mathbb{N}} : \exists n \ Y \upharpoonright_n \in \text{Im} T \}.$$

Dans chacun des exemples précédents, pour tout filtre maximal $F$, on note $\tilde{F}$ l'élément de $2^{\mathbb{N}}$ correspondant. On a donc pour chacune de ces notions de forcing l'égalité $[c] = \{\tilde{F} : F \in [c]_\infty\}$.

**Densité, généricité.** Rappelons que dans la méthode des extensions finies, les contrats peuvent être représentés comme l'ensemble des chaînes qui les forcent. Cette représentation a l'avantage de s'abstraire de la notion de contrat et se généralise à tout ordre partiel.

**Définition 1.3.** Soit $(\mathbb{P}, \leqslant)$ un ordre partiel. Un ensemble $D \subseteq \mathbb{P}$ est dense dans $(\mathbb{P}, \leqslant)$ si, pour tout $c \in \mathbb{P}$, il existe un $d \leqslant c$ tel que $d \in D$. $\diamond$

L'intuition qu'il est utile de conserver avec la notion de densité est que si un ensemble $D$ est dense, alors quel que soit le morceau fini de la suite décroissante de conditions que l'on a déjà construit, il n'est jamais trop tard pour intégrer un élément de $D$ dans la suite.

**Définition 1.4.** Soit $\tilde{D} = (D_n)_{n \in \mathbb{N}}$ une collection d'ensembles de conditions. Un filtre $F \subseteq \mathbb{P}$ est $\tilde{D}$-générique s'il intersecte l'ensemble $D_n$ pour tout $n \in \mathbb{N}$. $\diamond$

La proposition suivante montre que si les ensembles de conditions sont denses, il existe un filtre générique pour ces ensembles. La preuve de cette proposition correspond à la construction par la méthode des extensions finies d'une suite infinie croissante de chaînes satisfaisant chaque contrat.
**Proposition 1.5.** Soit $\tilde{D} = (D_n)_{n \in \mathbb{N}}$ une collection d'ensembles denses et soit $c \in \mathbb{P}$ une condition. Il existe un filtre $\tilde{D}$-générique contenant $c$. ★

PREUVE. Définissons inductivement une suite infinie décroissante de conditions $c_0 \ge c_1 \ge c_2 \ge \dots$ comme suit : $c_0 = c$. Si $c_n$ est défini, $c_{n+1} \le c_n$ est une condition appartenant à $D_n$. Une telle extension de $c_n$ existe par densité de l'ensemble $D_n$. Soit $F = \{d \in \mathbb{P} : \exists n \ d \ge c_n\}$. L'ensemble $F$ est un filtre contenant $c$ et rencontrant $D_n$ pour tout $n$. ■

Comme expliqué dans la section 10-2, il existe en général une quantité indénombrable d'ensembles denses, et un filtre $F$ ne peut pas être générique pour tous ces ensembles simultanément. La notion de généricité est donc dépendante d'une collection $\tilde{D}$ dénombrable d'ensembles denses. Nous dirons que tout filtre *suffisamment générique* pour une notion de forcing satisfait telle propriété s'il existe une collection dénombrable d'ensembles denses $\tilde{D}$ telle que tout filtre $\tilde{D}$-générique satisfait cette propriété.

**Définition 1.6.** Soit $(\mathbb{P}, \leqslant)$ un ordre partiel, et soient $c \in \mathbb{P}$ et $D \subseteq \mathbb{P}$ un ensemble. On dit que $D$ est dense sous $c$ si pour tout $d \leqslant c$, il existe un $e \leqslant d$ tel que $e \in D$. ◇

L'exercice suivant sera utile dans la suite de ce développement.

**Exercice 1.7.** Supposons qu'un ensemble $D \subseteq \mathbb{P}$ est dense sous $c \in \mathbb{P}$. Montrer que tout filtre $F$ suffisamment générique contenant la condition $c$ intersecte $D$. ◇

## 2. Relation de forcing

Jusqu'ici, nous avons développé des notions s'exprimant purement en termes d'ordre partiel, à savoir, les notions de densité, de filtre et de généricité. Nous allons maintenant définir une généralisation de la relation de forcing introduite dans la section 10-4. Pour cela, nous allons nous restreindre à des notions de forcing produisant des ensembles d'entiers.

**Définition 2.1.** Un forcing de Cantor est un ordre partiel $(\mathbb{P}, \leqslant)$ muni d'une fonction $F \mapsto \dot{F}$ des filtres maximaux vers l'espace de Cantor $2^\mathbb{N}$, telle pour tout $c \in \mathbb{P}$, et tout $\sigma \in 2^{<\mathbb{N}}$ pour lequel $[c] \cap [\sigma] \neq \emptyset$, il existe une condition $d \leqslant c$ telle que $[d] \subseteq [\sigma]$. Ici, la notation $[c]$ désigne l'ensemble $\{\dot{F} : F \in [c] \in \emptyset\}$. ◇
### 2.1. Relation sémantique de forcing

Par abus de langage, on dira qu'un ensemble $G \in 2^N$ est suffisamment générique pour un forcing de Cantor s'il est de la forme $\dot{F}$ pour un filtre suffisamment générique.

**Définition 2.2.** Une condition $c$ force sémantiquement un contrat $\mathcal{R}$, auquel cas l'on note $c \Vdash \mathcal{R}$ si $\dot{F}$ satisfait $\mathcal{R}$ pour tout filtre maximal $F$ suffisamment générique et contenant $c$. ◇

Cette définition sémantique nous donne << gratuitement >> certaines propriétés de la relation.

**Proposition 2.3.** Soit $(\mathbb{P}, \leqslant)$ un forcing de Cantor, et soient $c, d \in \mathbb{P}$. Soit $\mathcal{R}$ un contrat.

(1) Si $c \Vdash \mathcal{R}$ et $d \leqslant c$, alors $d \Vdash \mathcal{R}$.

(2) Si $c \Vdash \mathcal{R}$, alors $c \nVdash \neg \mathcal{R}$.

*

**PREUVE.** (1) Soit $F$ un filtre suffisamment générique contenant $d$. Par clôture par le haut des filtres, $c \in F$, et comme $c$ force $\mathcal{R}$, $\dot{F}$ satisfait donc $\mathcal{R}$. Il s'ensuit que $d$ force $\mathcal{R}$.

(2) Si $c$ force $\mathcal{R}$ et $\neg \mathcal{R}$, alors pour tout filtre $F$ suffisamment générique contenant $c$, $\dot{F}$ satisfait $\mathcal{R}$ et $\neg \mathcal{R}$, contradiction. ■

**Exercice 2.4.** Soit $(\mathbb{P}, \leqslant)$ un forcing de Cantor, et soit $c \in \mathbb{P}$. Soit $\mathcal{R}$ un contrat. Montrer que si $\{d \in \mathbb{P} : d \Vdash \mathcal{R}\}$ est dense sous $c$, alors $c \Vdash \mathcal{R}$. ◇

En revanche, certaines propriétés sont beaucoup moins évidentes à prouver. Nous allons voir par exemple que pour tout contrat arithmétique $\mathcal{R}$, l'ensemble des conditions qui forcent $\mathcal{R}$ ou qui forcent $\neg \mathcal{R}$ est dense. Tout comme dans le cas du forcing de Cohen avec l'ordre partiel des chaînes $(2^{<N}, \succeq)$, nous allons définir une relation de forcing syntaxique qui nous permettra de rendre compte de ce phénomène.

Nous insistons auparavant sur les trois propriétés fondamentales que doit avoir une relation de forcing syntaxique.

**Définition 2.5 (Relation de forcing).** Étant donné $(\mathbb{P}, \leqslant)$ un forcing de Cantor, on appelle relation de forcing une relation $\Vdash^\circ$ satisfaisant les propriétés suivantes pour tous $c, d \in \mathbb{P}$ et tout contrat arithmétique $\mathcal{R}$.

(1) Si $c \Vdash^\circ \mathcal{R}$, alors $c \Vdash \mathcal{R}$.
(2) Si $c \Vdash^\circ \mathcal{R}$ et $d \leqslant c$, alors $d \Vdash^\circ \mathcal{R}$.

(3) L'ensemble $\{c \in \mathbb{P} : c \Vdash^\circ \mathcal{R} \text{ ou } c \Vdash^\circ \neg \mathcal{R}\}$ est dense. ◇

Les propriétés (1-3) correspondent aux propositions 10-4.8, 10-4.6 et 10-4.7 pour le forcing de Cohen. Il découle immédiatement de (1) que si $c \Vdash^\circ \mathcal{R}$, alors $c \Vdash^\circ \neg \mathcal{R}$. Rappelons qu'un ensemble $S \subseteq \mathbb{P}$ est dense sous $c \in \mathbb{P}$ si pour tout $d \leqslant c$, il existe un $e \leqslant d$ tel que $e \in S$.

**Proposition 2.6.** Soit $(\mathbb{P}, \leqslant)$ un forcing de Cantor, et soit $c \in \mathbb{P}$. Soient $\mathcal{R}$ un contrat arithmétique et $\Vdash^\circ$ une relation de forcing. Alors,

$c \Vdash \mathcal{R}$ si, et seulement si, $\{d \in \mathbb{P} : d \Vdash^\circ \mathcal{R}\}$

est dense sous $c$. ★

**PREUVE.** Supposons que $c \Vdash^\circ \mathcal{R}$. Soit $d \leqslant c$. Par la définition 2.5(3), il existe un $e \leqslant c$ tel que $e \Vdash^\circ \mathcal{R}$ ou $e \Vdash^\circ \neg \mathcal{R}$. Si le second cas se présente, alors par la définition 2.5(1), $e \Vdash \neg \mathcal{R}$. On a donc $e \Vdash \mathcal{R}$ et $e \Vdash \neg \mathcal{R}$, ce qui contredit la proposition 2.3(2). Le premier cas se présente donc. Nous avons montré la densité de l'ensemble $\{d \in \mathbb{P} : d \Vdash^\circ \mathcal{R}\}$ sous $c$.

Réciproquement, supposons que l'ensemble $\{d \in \mathbb{P} : d \Vdash^\circ \mathcal{R}\}$ soit dense sous $c$. Soit $F$ un filtre suffisamment générique contenant $c$. Par généricité, il existe $d \in F$ tel que $d \Vdash^\circ \mathcal{R}$, et par la définition 2.5(1), $d \Vdash \mathcal{R}$, donc $\dot{F}$ satisfait $\mathcal{R}$. Il s'ensuit que $c \Vdash \mathcal{R}$. ■

## 2.2. Relation syntaxique de forcing

Nous définissons à présent notre relation syntaxique de forcing $\Vdash^*$, qui généralise directement la relation $\Vdash^*$ définie dans la section 10-4 pour le forcing de Cohen. Tout comme pour le forcing de Cohen, l'intérêt de la relation $c \Vdash^* \mathcal{R}$ est qu'elle est simple à définir : relativement à $\mathbb{P}$, elle a la même complexité arithmétique que celle du contrat $\mathcal{R}$. Nous verrons dans les sections suivantes que $\mathbb{P}$ en tant qu'ordre partiel est malheureusement rarement calculable, ce qui amène à des complexités calculatoires supplémentaires qui doivent être traitées au cas par cas.

**Définition 2.7.** Soit $(\mathbb{P}, \leqslant)$ un forcing de Cantor. On définit la relation $\Vdash^*$ pour tout $c \in \mathbb{P}$ et tout contrat arithmétique $\mathcal{R}$ :

(1) $c \Vdash^* \mathcal{R}$ pour $\mathcal{R}$ un contrat $\Sigma_1^0$ ou $\Pi_1^0$ ssi tout $X \in [c]$ satisfait $\mathcal{R}$;

(2) $c \Vdash^* \exists x \mathcal{R}(x)$ pour $\mathcal{R}(x)$ un contrat $\Pi_k^0$ avec $k \geqslant 1$ ssi il existe un $n \in \mathbb{N}$ tel que $c \Vdash^* \mathcal{R}(n)$;

(3) $c \Vdash^* \forall x \mathcal{R}(x)$ pour $\mathcal{R}(x)$ un contrat $\Sigma_k^0$ avec $k \geqslant 1$ ssi pour tout $d \leqslant c$ et tout $n \in \mathbb{N}$, $d \Vdash^* \neg \mathcal{R}(n)$. ◇
Notons que tout comme dans le cas du forcing de Cohen, on a $c \Vdash^* \forall x \mathcal{R}(x)$ ssi $\forall d \le c \ d \Vdash^* \exists x \neg \mathcal{R}(x)$. Nous laissons en exercice la preuve que la relation $\Vdash^*$ respecte les points (1-3) d'une relation de forcing de la définition 2.5. Il s'agit à chaque fois de simples preuves par induction sur la complexité des contrats.

**Exercice 2.8.** $(\star)$ Soit $(\mathbb{P}, \le)$ un forcing de Cantor, et soient $c, d \in \mathbb{P}$. Soit $\mathcal{R}$ un contrat arithmétique. Montrer que si $c \Vdash^* \mathcal{R}$ et $d \le c$, alors $d \Vdash^* \mathcal{R}$. $\diamond$

**Exercice 2.9.** $(\star)$ Soit $(\mathbb{P}, \le)$ un forcing de Cantor et soit $\mathcal{R}$ un contrat arithmétique. Montrer que $\{c \in \mathbb{P} : c \Vdash^* \mathcal{R} \text{ ou } c \Vdash^* \neg \mathcal{R}\}$ est dense. $\diamond$

**Exercice 2.10.** $(\star)$ Soit $(\mathbb{P}, \le)$ un forcing de Cantor, et soit $c \in \mathbb{P}$. Soit $\mathcal{R}$ un contrat arithmétique. Montrer que si $c \Vdash^* \mathcal{R}$, alors $c \Vdash \mathcal{R}$. $\diamond$

### La complexité de $\Vdash$

La complexité de $\Vdash^*$ a des conséquences sur la complexité de la relation sémantique de forcing $\Vdash$. D'après les exercices précédents, $\Vdash^*$ respecte bien les points (1-3) de la définition 2.5. Donc, d'après la proposition 2.6, la relation $c \Vdash \mathcal{R}$ est équivalente à $\forall d \le c \exists e \le d \ e \Vdash^* \mathcal{R}$, ce qui par exemple pour un contrat $\Sigma_n^0$ sera un prédicat $\Pi_{n+1}^0(\mathbb{P})$. Il s'agit d'une simplification considérable de la relation sémantique, mais qui reste — relativement à $\mathbb{P}$ — de complexité arithmétique supérieure à celle des contrats qu'elle force, ce qui nous fera préférer la relation $\Vdash^*$.

# 3. Forcing avec des arbres

Le forcing à base d'arbres est une des grandes familles de forcing. Nous en détaillons ici deux exemples, déjà rencontrés dans les chapitres précédents : le forcing de Jockusch-Soare et le forcing de Sacks calculable. Ces notions ont été au départ créées pour contrôler le simple saut via le forcing de contrats $\Sigma_1^0/\Pi_1^0$, ou le double saut via le forcing de contrats $\Sigma_2^0/\Pi_2^0$. Nous en rediscuterons dans la section 4, et nous nous contentons pour le moment de voir en quoi ces forcings ont été utilisés implicitement à plusieurs reprises dans ce livre.

## 3.1. Forcing de Jockusch-Soare

Le forcing de Jockusch-Soare correspond à l'ordre partiel des classes $\Pi_1^0$ non vides, partiellement ordonnées par la relation d'inclusion. On peut associer à tout filtre maximal $F$ sur cet ordre un ensemble d'entiers $\tilde{F} \in 2^N$ qui est
l'élément du singleton $\cap_{P \in \mathcal{F}} \mathcal{P}$. Muni de cette interprétation des filtres, le forcing de Jockusch-Soare est un forcing de Cantor (voir la définition 2.1).

Nous avons déjà rencontré plusieurs utilisations du forcing de Jockusch-Soare dans le chapitre 8 sur les classes $\Pi_1^0$ et les degrés PA. Voici une reformulation des théorèmes de base calculatoirement dominée et de base d'évitement de cône, via le vocabulaire du forcing.

Théorème (reformulation des th. 8-4.5 et 8-4.7)

Soit A un ensemble non calculable et soit G un ensemble suffisamment générique pour le forcing de Jockusch-Soare. Alors, G est calculatoirement dominé et ne calcule pas A.

PREUVE. Soit $(\mathbb{P}, \leqslant)$ le forcing Jockusch-Soare, c'est-à-dire l'ensemble des classes $\Pi_1^0$ non vides ordonnées pas l'inclusion. La preuve du théorème 8-4.5 montre la chose suivante : pour toute fonctionnelle $\Phi_e$ et tout $c \in \mathbb{P}$, il existe $d \leqslant c$ tel que $d \Vdash^* \exists n \Phi_e(G, n) \uparrow$ ou il existe $d \not\leqslant c$ et une fonction calculable $f : \mathbb{N} \to \mathbb{N}$ telle que $d \Vdash^* \Phi_e(G, n) \downarrow< f(n)$ pour tout $n$. Donc, l'ensemble $C_e$ des conditions qui forcent $\Phi_e$ à être partielle ou bien bornée par une fonction calculable est dense. Tout filtre suffisamment générique contient une condition dans chacun des $C_e$. Si $G \in 2^{\mathbb{N}}$ est donc suffisamment générique, il est calculatoirement dominé.

La preuve du théorème 8-4.7 quant à elle montre la chose suivante : pour toute fonctionnelle $\Phi_e$ l'ensemble $D_e = \{c \in \mathbb{P} : c \Vdash^* \exists n \Phi_e(G, n) \uparrow$ ou $\exists n c \Vdash^* \Phi_e(G, n) \downarrow\neq A(n)\}$ est dense. Si $G$ est donc suffisamment générique, il ne calcule pas A.

En ce qui concerne le théorème de la base low, les choses sont différentes : c'est bien le forcing de Jockusch-Soare que nous utilisons pour construire un ensemble low, mais il s'agit d'une utilisation effective de ce forcing, où l'on contrôle à l'aide de $0'\emptyset$ le passage d'une étape $n$ à une étape $n+1$. Il ne s'agit donc pas à proprement parler d'un résultat de forcing, dans le sens où ce n'est pas une propriété satisfaite par tout ensemble suffisamment générique, mais au contraire par une petite classe dénombrable d'ensembles qui sont peu génériques.

Nous avons vu avec le forcing de Cohen que tout ensemble suffisamment générique différait d'une quantité dénombrable d'ensembles fixés à l'avance (voir le théorème 10-5.4). En particulier, aucun ensemble suffisamment générique pour le forcing de Cohen n'est arithmétique. Ce n'est pas le cas du forcing de Jockusch-Soare. En effet, pour tout $X$ calculable, le singleton $\{X\}$ est une classe $\Pi_1^0$ et l'unique filtre contenant $\{X\}$ — à savoir le filtre de toutes les classes $\Pi_1^0$ ayant $X$ comme chemin infini — est maximal. L'ensemble $X$ est donc aussi générique que l'on veut sous la condition $\{X\}$.
Il est toutefois possible de modifier légèrement le forcing de Jockusch-Soare afin d'éviter les éléments calculables.

**Proposition 3.2.** Soit $(\mathbb{P}, \leqslant)$ l'ordre partiel des classes $\Pi_1^0$ non vides sans élément calculable, ordonnées par l'inclusion. Soit $(A_n)_{n \in \mathbb{N}}$ une suite quelconque d'ensembles. Alors, si $G \in 2^\mathbb{N}$ est suffisamment générique pour $\mathbb{P}$, il est différent de chaque $A_n$. ⋆

**PREUVE.** Fixons un ensemble $A$ quelconque et montrons que si $G$ est suffisamment générique, il est différent de $A$. Le résultat suivra automatiquement pour la suite $(A_n)_{n \in \mathbb{N}}$.

Soit $D \subseteq \mathbb{P}$ l'ensemble des classes $\Pi_1^0$ de $\mathbb{P}$ ne contenant pas $A$. Montrons que $D$ est dense dans $\mathbb{P}$. Soit $\mathcal{P} \in \mathbb{P}$. Par la proposition 8-3.6, la classe $\mathcal{P}$ contient au moins deux éléments. Soit $B \in \mathcal{P}$ tel que $B \neq A$, et soit $n \in \mathbb{N}$ tel que $A(n) \neq B(n)$. Alors, la classe $Q = \{X \in \mathcal{P} : X(n) = B(n)\}$ est une classe $\Pi_1^0$ non vide incluse dans $\mathcal{P}$ et telle que $Q \in D$. Donc, $D$ est dense. ■

La modification du forcing de Jockusch-Soare de la proposition précédente peut se décliner de multiples manières pour obtenir différents résultats : on peut considérer l'ordre partiel des classes $\Pi_1^0$ non vides ne contenant que des degrés PA, ou encore celles des classes $\Pi_1^0$ non vides ne contenant que des ensembles aléatoires au sens de Martin-Löf (voir le chapitre 18).

## 3.2. Le forcing de Sacks calculable

Le forcing de Sacks désigne de manière générale l'ordre partiel des arbres parfaits de $2^{<\mathbb{N}}$, sans restriction particulière d'effectivité. Nous nous restreignons en calculabilité aux arbres parfaits calculables, qui ont déjà été abordés via la notion de f-arbre.

Rappelons qu'un f-arbre est une fonction totale $T : 2^{<\mathbb{N}} \to 2^{<\mathbb{N}}$ telle que pour tous $\sigma, \tau \in \text{dom } T$, $\sigma \preceq \tau$ si, et seulement si, $T(\sigma) \preceq T(\tau)$. Un sous-f-arbre d'un f-arbre $T$ est un f-arbre $S$ tel que $\text{Im } S \subseteq \text{Im } T$. Un f-arbre $T : 2^{<\mathbb{N}} \to 2^{<\mathbb{N}}$ s'étend en une fonction $\hat{T} : 2^{\mathbb{N}} \to 2^{\mathbb{N}}$ définie par $\{\hat{T}(X)\} = \bigcap_n [T(X]_n)]$. Un chemin de $T$ est un élément de $\text{Im } \hat{T}$. On note $[T]$ l'ensemble des chemins de $T$.

On appelle *forcing de Sacks calculable* l'ensemble des f-arbres calculables partiellement ordonnés par la relation de sous f-arbre. Comme il n'y aura pas d'ambiguïté possible dans ce livre, on dira parfois plus simplement *forcing de Sacks*. On peut associer à tout filtre maximal $F$ sur cet ordre un ensemble d'entiers $\dot{F} \in 2^\mathbb{N}$ qui est l'élément du singleton $\bigcap_{T \in F}[T]$. Muni de cette interprétation des filtres, le forcing de Sacks est un forcing de Cantor (voir la définition 2.1).
**Remarque**

Rappelons qu'une classe $\mathcal{P} \subseteq 2^\mathbb{N}$ est parfaite si $\mathcal{P} = [T]$ pour un f-arbre $T$. Le forcing de Sacks n'est cependant pas la restriction du forcing de Jockusch-Soare aux classes $\Pi_1^0$ parfaites : certaines classes $\Pi_1^0$ parfaites ne peuvent pas nécessairement être représentées par un f-arbre calculable.

En effet, pour tout f-arbre calculable $T$, $[T]$ contient une infinité d'éléments calculables, à savoir $T(X)$ pour tout ensemble calculable $X$, ce qui n'est par exemple pas le cas de la classe $\Pi_1^0$ des fonctions $\text{DNC}_2$, qui est pourtant bien une classe parfaite.

Comme expliqué dans la remarque précédente, tout f-arbre calculable possède une infinité de chemins calculables. En revanche, tout ensemble suffisamment générique pour le forcing de Sacks sera non calculable.

**Exercice 3.3.** ($\star$) Soit $(A_n)_{n \in \mathbb{N}}$ une suite quelconque d'ensembles. Montrer que tout $G$ suffisamment générique pour le forcing de Sacks est différent de chaque $A_n$. $\diamond$

Un examen attentif de la première preuve que nous avons donnée de l'existence d'un degré calculatoirement dominé différent de 0, à l'aide de f-arbre, montre en fait que l'on a le résultat suivant.

**Théorème (reformulation du théorème 7-5.6)**

Soit $G$ un ensemble suffisamment générique pour le forcing de Sacks. Alors, $G$ est non calculable et calculatoirement dominé.

**PREUVE.** Soit $(\mathbb{P}, \leqslant)$ le forcing de Sacks. La preuve du théorème 7-5.6 montre la chose suivante : pour toute fonctionnelle $\Phi_e$ et tout $c \in \mathbb{P}$, il existe $d \leqslant c$ tel que $d \Vdash^* \exists n \Phi_e(G, n) \uparrow$ ou il existe $d \leqslant c$ et une fonction calculable $f : \mathbb{N} \to \mathbb{N}$ telle que $d \Vdash^* \Phi_e(G, n) \downarrow< f(n)$ pour tout $n$. Donc, l'ensemble $C_e$ des conditions qui forcent $\Phi_e$ à être partielle ou bien bornée par une fonction calculable est dense. Tout filtre suffisamment générique contient une condition de chacun des $C_e$. Donc si $G \in 2^\mathbb{N}$ est suffisamment générique il est calculatoirement dominé.

Par ailleurs, l'exercice 3.3 montre que si $G$ est suffisamment générique, il est non calculable. $\blacksquare$

**Exercice 3.5.** ($\star$) Soit $A$ un ensemble non calculable. Montrer que si $G$ est suffisamment générique pour le forcing de Sacks, il ne calcule pas $A$. $\diamond$

**Exercice 3.6.** ($\star\star$) Un ensemble $X$ est calculatoirement traçable (Terwijn et Zambella [222]) s'il existe une borne calculable $h : \mathbb{N} \to \mathbb{N}$ telle
que pour toute fonction $X$-calculable $f : \mathbb{N} \to \mathbb{N}$, il existe une suite calculable $(T_n)_{n \in \mathbb{N}}$ d'ensembles finis tels que $|T_n| \le h(n)$ et tels que $f(n) \in T_n$ pour tout $n$.

1. Montrer que si $X$ est suffisamment générique pour le forcing de Sacks, il est calculatoirement traçable.

2. Montrer que si $X$ est calculatoirement traçable via une borne calculable $h$, alors il est calculatoirement traçable pour n'importe quelle borne calculable $h'$ telle que $h'(n) \le h'(n+1)$ et $\lim_n h(n) = +\infty$ (Terwijn et Zambella [222]).

3. Soit $(2^n)^N$ l'ensemble des fonctions $f : \mathbb{N} \to \mathbb{N}$ telles que $f(n) < 2^n$, et soit $(2^n)^{<N}$ l'ensemble des préfixes de fonctions de $(2^n)^N$. Soit $(\mathbb{P}, \leq)$ l'ensemble des conditions de forcing données par $T \in \mathbb{P}$ si $T \subseteq (2^n)^{<N}$ est un arbre calculable qui vérifie la propriété suivante : pour tout $\sigma \in T$, il existe $\tau \in T$ avec $\tau \supseteq \sigma$ telle que pour tout $i < 2^{|\tau|}$ la chaîne $\tau i$ est dans $T$; autrement dit, chaque nœud a une extension de branchement maximal.

Montrer que tout ensemble suffisamment générique pour ce forcing est calculatoirement dominé et non calculatoirement traçable. ◇

## 4. Complexité calculatoire et question de forcing

Le forcing de Cohen présente une particularité qui le distingue des autres forcings de la calculabilité : l'ordre partiel $(2^{<N}, \supseteq)$ est calculable : l'ensemble $2^{<N}$ est calculable et étant donné $\sigma \in 2^{<N}$, on peut calculer l'ensemble des chaînes $\tau \supseteq \sigma$. Une autre de ses particularités est que la relation de forcing des contrats $\Sigma_1^0$ et $\Pi_1^0$ est respectivement $\Sigma_1^0$ et $\Pi_1^0$. Ces deux propriétés permettent d'obtenir la proposition 10-5.2 : si $\mathcal{R}$ est un contrat $\Sigma_n^0$ (resp. $\Pi_n^0$), le prédicat $\sigma \Vdash^* \mathcal{R}$ est $\Sigma_n^0$ (resp. $\Pi_n^0$). Ce contrôle très fin de la complexité de la relation de forcing permet alors un contrôle fin des sauts itérés des ensembles génériques, afin d'obtenir par exemple les résultats suivants.

1. Le corollaire 10-5.8 : si $X$ est non $\emptyset^{(n)}$-calculable et si l'ensemble $G$ est suffisamment générique, alors $G^{(n)}$ ne calcule pas $X$.

2. Le théorème 10-5.9 : si l'ensemble $G$ est suffisamment générique, on a alors $G \oplus \emptyset^{(n)} \geq_T G^{(n)}$.

C'est en général le genre de propriété que l'on cherche à obtenir avec n'importe quelle notion de forcing : le contrôle de la valeur de vérité de contrats
arithmétiques, plus ce contrôle est fin, meilleurs sont les théorèmes que l'on
peut obtenir. Malheureusement, les choses seront rarement aussi simples
qu'avec le forcing de Cohen. Examinons la complexité calculatoire du for-
cing de Jockusch-Soare et celle du forcing de Sacks.

**4.1. Complexité des ordres partiels**

Pour parler de la calculabilité des ordres partiels d'objets abstraits, il est nécessaire de s'accorder d'abord sur leur représentation par des ensembles d'entiers. Pour le forcing de Cohen, l'ordre partiel des chaînes admet un codage bijectif naturel, alors que les notions de forcing de Jockusch-Soare et de Sacks font intervenir des objets plus complexes.

**Forcing de Jockusch-Soare.** Une idée naturelle est de confondre $\mathbb{P}$ avec l'ensemble des codes de classes $\Pi_1^0$ non vides. Notons que l'on a alors des répétitions, car plusieurs entiers codent pour la même classe, ce qui en pratique n'est pas un problème.

**Proposition 4.1.** *L'ordre partiel du forcing de Jockusch-Soare est $\Pi_2^0$. ★*

PREUVE. Notons déjà que l'ensemble des codes de classes $\Pi_1^0$ non vides est $\Pi_1^0$. En effet, si une classe $\Pi_1^0$ est vide, alors l'arbre calculable $T \subseteq 2^{<\mathbb{N}}$ qui le représente n'a aucun chemin infini, et d'après le lemme de König il existe un entier $n$ tel qu'aucune chaîne de taille $n$ n'appartient à $T$, ce qui est un événement $\Sigma_1^0$.

À présent, étant donné deux classes $\Pi_1^0$ non vides $\mathcal{P}, \mathcal{Q}$, on a $\mathcal{P} \subseteq \mathcal{Q}$
ssi $\forall t \exists s \mathcal{P}[s] \subseteq \mathcal{Q}[t]$, ce qui est un prédicat $\Pi_2^0$. ■

Notons qu'il est possible d'améliorer la complexité de l'ordre partiel du forcing de Jockusch-Soare, en ne travaillant que sur une partie bien choisie des codes de classes $\Pi_1^0$ non vides. Il existe en effet une fonction calculable $f: \mathbb{N} \to \mathbb{N}$ telle que $f(e)$ code toujours pour une classe $\Pi_1^0$ non vide et telle que si $e$ code pour une classe $\Pi_1^0$ non vide, alors $e$ et $f(e)$ codent pour la même classe : il suffit étant donné $e$ de stopper la co-énumération de la classe $\Pi_1^0$ correspondante si celle-ci s'apprête à rendre la classe vide.

On peut également dans la pratique améliorer la complexité de l'ordre partiel en restreignant là aussi l'ensemble des codes sur lesquels on travaille : étant donné le code $e$ d'une classe $\Pi_1^0$ non vide $\mathcal{P}$, on peut considérer l'ensemble $\mathcal{A}$ des codes de toutes les classes $\Pi_1^0 \in \mathcal{Q}$ telles que $\mathcal{P} \cap \mathcal{Q}$ est non vide. L'ensemble $\mathcal{A}$ est $\Pi_1^0$, et contient au moins un code correspondant à chaque classe $\Pi_1^0$ non vide incluse dans $\mathcal{P}$. Cela ne permet pas bien entendu de décider si deux codes représentent des conditions de forcing comparables, mais cela simplifie la complexité calculatoire de trouver la liste de toutes les conditions de $\mathbb{P}$ se trouvant sous une condition donnée.
**Forcing de Sacks calculable.** Ici, l'idée naturelle est de confondre dans ce cadre les conditions du forcing de Sacks calculable avec les codes de fonctions $T: 2^{<\mathbb{N}} \to 2^{<\mathbb{N}}$ correspondant à des f-arbres. Là encore, le codage n'est pas injectif, mais ce n'est en pratique pas un problème.

**Proposition 4.2.** *L'ordre partiel du forcing de Sacks calculable est $\Pi_2^0$.\*

**PREUVE.** L'ensemble des conditions est l'ensemble des codes $e$ de fonctions $T_e: 2^{<\mathbb{N}} \to 2^{<\mathbb{N}}$ telles que $\forall\sigma \in 2^{<\mathbb{N}} \exists t \in \mathbb{N} T_e(\sigma)[t] \downarrow$ et telles que $\forall\sigma_0, \sigma_1 \in 2^{<\mathbb{N}} \sigma_0 \prec \sigma_1 \leftrightarrow T_e(\sigma_0) \prec T_e(\sigma_1)$. Ce sont bien des conditions $\Pi_2^0$ à vérifier.

Étant donné un f-arbre calculable $T$, l'ensemble des codes $e$ de f-arbres calculables $S_e$ tels que $[S_e] \subseteq [T]$ est l'ensemble des codes $e$ de f-arbre (ce qui est une condition $\Pi_2^0$) qui vérifient que pour toute chaîne $\sigma$ et pour tout entier $n$ suffisamment grand tel que $|T(\tau)| \ge |S_e(\sigma)|$ pour toute chaîne $\tau$ de taille $n$, il existe une chaîne $\tau$ telle que $|\tau| \le n$ pour laquelle $S_e(\sigma) = T(\tau)$. Il s'agit d'une condition $\Pi_1^0$.

## 4.2. Forcer des contrats $\Sigma_1^0/\Pi_1^0$

La complexité de la relation de forcing pour les contrats $\Sigma_1^0$ et $\Pi_1^0$ n'est pas directement liée à la complexité de l'ordre partiel. Nous allons voir en particulier que la relation de forcing syntaxique du forcing de Jockusch-Soare, est plus complexe que celle du forcing de Sacks.

**Forcing de Jockusch-Soare.** La complexité de la relation de forcing ne suit pas celle de la complexité des contrats à forcer, y compris déjà pour les contrats $\Sigma_1^0/\Pi_1^0$.

**Proposition 4.3.** Soit $(\mathbb{P}, \leqslant)$ le forcing de Jockusch-Soare et soit $\mathcal{R}$ un contrat. Soit $\mathcal{P}_e$ la classe $\Pi_1^0$ de code $e$, que l'on suppose non vide.

(1) Si $\mathcal{R}$ est $\Sigma_1^0$, alors le prédicat $\mathcal{P}_e \Vdash^* \mathcal{R}$ est $\Sigma_1^0$

(2) Si $\mathcal{R}$ est $\Pi_1^0$, alors le prédicat $\mathcal{P}_e \Vdash^* \mathcal{R}$ est $\Pi_2^0$

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

**PREUVE.** Soit $T_e \subseteq 2^{<\mathbb{N}}$ un arbre calculable tel que $[T_e] = \mathcal{P}_e$.

(1) Soit $\mathcal{R}$ de la forme $\Phi(G, 0) \downarrow$ pour une fonctionnelle $\Phi$. Alors, $\mathcal{P}_e \Vdash^* \mathcal{R}$ ssi $\Phi(X, 0) \downarrow$ pour tout $X \in \mathcal{P}_e$ ssi (par la propriété de l'usage et le lemme de König) $\exists n \forall \sigma \in T_e \cap 2^n$ on a $\Phi(\sigma, 0) \downarrow$.

(2) Soit $\mathcal{R}$ de la forme $\Phi(G, 0) \uparrow$ pour une fonctionnelle $\Phi$. Alors, on peut obtenir $a \in \mathbb{N}$ le code de la classe $\Pi_1^0$ telle que $\mathcal{P}_a = \{X : \Phi(G, 0) \uparrow\}$. On a alors $\mathcal{P}_e \Vdash^* \mathcal{R}$ ssi $\mathcal{P}_e \subseteq \mathcal{P}_a$. Comme vue dans la preuve de la proposition 4.2, la relation d'inclusion sur les codes des classes $\Pi_1^0$ est $\Pi_2^0$.

<figure><img src="image_81.png" /></figure>
Nous verrons dans les deux sections à venir comment contourner le problème de complexité soulevé par la précédente proposition.

**Exercice 4.4. (*)** Soit $(\mathbb{P}, \leqslant)$ l'ordre partiel des arbres calculables $T \subseteq 2^{<\mathbb{N}}$ infinis.

Soit $\Vdash^\circ$ la relation définie par

(1) $T \Vdash^\circ \exists n \Phi(G, n) \downarrow$ s'il existe $n, t \in \mathbb{N}$ tel que pour tout $\sigma \in T$ de longueur $t$, $\Phi(\sigma, n) \downarrow$

(2) $T \Vdash^\circ \forall n \Phi(G, n) \uparrow$ si pour tout $\sigma \in T$ et tout $n < |\sigma|$, $\Phi(\sigma, n) \uparrow$

Montrer les faits suivants.

(a) $(\mathbb{P}, \leqslant)$ est un forcing de Cantor, où $[T]$ est la classe des chemins de $T$.

(b) Les ensembles suffisamment génériques pour le forcing de Jockusch-Soare et pour $(\mathbb{P}, \leqslant)$ coïncident.

(c) L'ensemble $\{T \in \mathbb{P} : T \Vdash^\circ \exists n \Phi(G, n) \downarrow \text{ ou } T \Vdash^\circ \forall n \Phi(G, n) \uparrow\}$ est dense dans $(\mathbb{P}, \leqslant)$.

(d) Les relations $T \Vdash^\circ \exists n \Phi(G, n) \downarrow$ et $T \Vdash^\circ \forall n \Phi(G, n) \uparrow$ sont respectivement $\Sigma_1^0$ et $\Pi_1^0$. ◇

**Forcing de Sacks calculable.** Le forcing de contrats $\Sigma_1^0$ et $\Pi_1^0$ est dans ce cas-ci de complexité minimale.

**Proposition 4.5.** Soit $(\mathbb{P}, \leqslant)$ le forcing de Sacks et soit $\mathcal{R}$ un contrat. Soit $T_e$ le f-arbre calculable de code $e$.

(1) Si $\mathcal{R}$ est $\Sigma_1^0$, alors le prédicat $T_e \Vdash^* \mathcal{R}$ est $\Sigma_1^0$.

(2) Si $\mathcal{R}$ est $\Pi_1^0$, alors le prédicat $T_e \Vdash^* \mathcal{R}$ est $\Pi_1^0$. ★

**PREUVE.** (1) Soit $\mathcal{R}$ un contrat de la forme $\Phi(G, 0) \downarrow$ pour une fonctionnelle $\Phi$. On a $T_e \Vdash^* \mathcal{R}$ ssi il existe $n, t$ tels que $\Phi(\sigma, 0)[t] \downarrow$ pour toute chaîne $\sigma \in \text{Im } T_e$ de taille $n$.

(2) Soit $\mathcal{R}$ de la forme $\Phi(G, 0) \uparrow$ pour une fonctionnelle $\Phi$. On a $T_e \Vdash^* \mathcal{R}$ ssi pour tout $\sigma \in \text{Im } T_2$ et pour tout $t$ on a $\Phi(\sigma, 0)[t] \uparrow$. ■

**Continuité du saut Turing.** Nous voyons à présent un théorème qui contraste avec le fait que tout suffisamment générique pour le forcing de Cohen est low généralisé. Ce n’est en général pas le cas pour les forcings à base d’arbres, et ce n’est en particulier pas le cas pour le forcing de Sacks calculable.

**Théorème 4.6**

Soit $X$ un ensemble quelconque et soit $G$ un ensemble suffisamment générique pour le forcing de Sacks calculable. Alors, $X \oplus G \not\supseteq_T G'$.
PREUVE. Soit $T : 2^{<N} \to 2^{<N}$ un f-arbre calculable et soit $\Phi_e$ une fonctionnelle Turing. On va construire un sous f-arbre $S$ de $T$ tel que pour chacun des chemins $G$ de $S$ on a $\Phi_e(X \oplus G, n) \neq G'(n)$ pour un certain $n$. On considère un sous f-arbre calculable $S$ de $T$ tel que pour tout $\sigma \in \text{Im } S$ il existe $\tau \supseteq \sigma$ avec $\tau \in \text{Im } T$ et $\tau \notin \text{Im } S$.

On considère à présent le code $a$ de la fonctionnelle partielle calculable telle que $\Phi_a(Y, a) \uparrow$ pour tout $Y \in [S]$ et telle que $\Phi_a(Y, a) \downarrow$ pour tout $Y \notin [S]$. Notons en particulier que $\Phi_a(Y, a) \downarrow$ pour tout $Y \in [T] \setminus [S]$. Supposons d'abord que $\Phi_e(X \oplus \sigma, a) \uparrow \notin \{0, 1\}$ pour tout $\sigma \in \text{Im } S$. Alors, on peut prendre $S$ comme extension de forcing de $T$ afin de forcer la partialité de $\Phi_e$ sur l'entrée $a$. Sinon, soit $\sigma \in \text{Im } S$ telle que $\Phi_e(X \oplus \sigma, a) \downarrow = i$ pour $i \in \{0, 1\}$. Si $i = 0$, alors on choisit une chaîne $\tau \supseteq \sigma$ telle que $\tau \in \text{Im } T$ et $\tau \notin \text{Im } S$, et l'on prend comme extension de forcing un sous f-arbre de $T$ dont l'image ne contient que des extensions de $\tau$. Notons que l'on a alors $\Phi_a(Y, a) \downarrow$ pour tout chemin $Y$ de notre extension de forcing. Si $i = 1$, alors on prend comme extension de forcing le sous f-arbre de $S$ dont l'image ne contient que des extensions de $\sigma$. Notons que l'on a alors $\Phi_a(Y, a) \uparrow$ pour tout chemin $Y$ de notre extension de forcing.

Dans les deux cas, on force $\Phi_e(X \oplus G, a)$ à être différent de $G'(a)$ pour tout ensemble $G$ de notre condition de forcing. ■

Un théorème analogue pour le forcing de Jockusch-Soare ne sera pas nécessairement vrai, par exemple à cause de l'existence de classes $\Pi_1^0$ contenant un unique élément calculable. Même en se restreignant aux classes $\Pi_1^0$ ne contenant pas de points calculables, les choses ne sont pas aussi simples et dépendront de la classe $\Pi_1^0$ avec laquelle on commence le forcing.

**Exercice 4.7. (★★)** Soit $\mathcal{P}$ une classe $\Pi_1^0$ non vide. Alors, $\mathcal{P}$ est *fine* (définition due à Downey [49]) si pour toute sous-classe $\Pi_1^0$ non vide $\mathcal{Q} \subseteq \mathcal{P}$, il existe une suite finie de cylindres $[\sigma_0], \dots, [\sigma_n]$ telle que

$$ \mathcal{Q} = \mathcal{P} \cap ([\sigma_0] \cup \dots \cup [\sigma_n]). $$

1. Montrer l'existence d'une classe $\Pi_1^0$ fine parfaite (il s'agit d'un algorithme du type méthode de priorité comme exposé dans le chapitre 13).

2. Montrer que si $\mathcal{P}$ est fine et si $X \in \mathcal{P}$, alors $X \oplus \emptyset'' \geq_T X'$. ◇

**Exercice 4.8. (★) Cet exercice anticipe sur la partie II au sein de laquelle le lemme 18-3.3 devrait être utile. On considère une variante du forcing de Jockusch-Soare avec des classes $\Pi_1^0$ ne contenant que des aléatoires au sens de Martin-Löf. Montrer que pour tout $X$ et tout ensemble $Z$ suffisamment générique pour ce forcing on a $Z \oplus X \not\supseteq_T Z'$. ◇**
### 4.2.1. Forcer des contrats $\Sigma_2^0/\Pi_2^0$

Les forcing à base d'arbres sont en général adaptés, non pour forcer les contrats $\Sigma_1^0$ ou $\Pi_1^0$ (comme le montre le théorème 4.6, ils ne permettent pas d'obtenir des ensembles low généralisés), mais pour forcer les contrats $\Sigma_2^0$ ou $\Pi_2^0$, sur lesquels ils fonctionnent particulièrement bien. Nous avons vu dans la section 10-4 que dans le cas du forcing de Cohen, si l'on définit la relation de forcing par << tout filtre maximal satisfait le contrat >>, alors l'ensemble des conditions forçant un contrat $\Pi_2^0$ ou sa négation n'est pas dense en général. Cela nous a conduit à définir la relation de forcing pour tout filtre maximal suffisamment générique.

Contrairement au forcing de Cohen, les forcings à base d'arbres, comme le forcing de Jockusch-Soare ou le forcing de Sacks permettent en général de trouver des conditions de forcing dont tous les membres satisfont des formules $\Sigma_2^0$ ou $\Pi_2^0$. Le lecteur pourra constater que c'est bien ce mécanisme qui est à l'œuvre pour forcer un ensemble générique à être calculatoirement dominé. Nous introduisons pour voir cela la notion de question de forcing, notée $?\vdash$, qui sera développée et étudiée dans les sections suivantes pour des contrats arithmétiques arbitraires.

**Définition 4.9.** Soit $\mathcal{R}$ un contrat $\Sigma_2^0$ correspondant à $\exists n \Phi(G, n)\uparrow$ pour une fonctionnelle $\Phi$.

(1) Soit $\mathcal{P}$ une condition du forcing de Jockusch-Soare. On définit

$$ \mathcal{P} ?\vdash \exists n \Phi(G, n) \uparrow $$

s'il existe $n$ tel que $\mathcal{P} \Vdash^* \Phi(G, n)\downarrow$.

(2) Soit $T$ une condition du forcing de Sacks calculable. On définit

$$ T ?\vdash \exists n \Phi(G, n) \uparrow $$

s'il existe $n$ et $\sigma$ tel que $T \Vdash_{\sigma} ?^* \Phi(G, n)\uparrow$, où $T \Vdash_{\sigma}$ est le f-arbre $S$ défini par $S(\tau) = T(\sigma\tau)$. $\diamond$

Le premier intérêt de la relation de question de forcing que nous avons définie, est sa complexité qui est la même que celle du contrat concerné.

**Proposition 4.10.** Soit $c$ une condition du forcing de Jockusch-Soare ou du forcing de Sacks. Soit $\mathcal{R}$ un contrat $\Sigma_2^0$ correspondant à $\exists n \Phi(G, n)\uparrow$ pour une fonctionnelle $\Phi$. Le prédicat $c?\vdash \exists n \Phi(G, n)\uparrow$ est $\Sigma_2^0$. $\star$

**Préuve.** Commençons par le forcing de Jockusch-Soare. D'après la pro-
position 4.3, étant donné $n$, le prédicat $\mathcal{P} \Vdash^* \Phi(G, n)\downarrow$ est $\Sigma_1^0$, et le
prédicat $\mathcal{P} \Vdash^* \Phi(G, n)\downarrow$ est donc $\Pi_1^0$. Ainsi, le prédicat $\exists n \mathcal{P} \Vdash^* \Phi(G, n)\downarrow$
est $\Sigma_2^0$, et le prédicat $\mathcal{P} ?\vdash \Phi(G, n)\uparrow$ est donc $\Sigma_2^0$.
Passons au forcing de Sacks calculable. D'après la proposition 4.5, étant donné $n$, et un f-arbre $S$, le prédicat $S \Vdash^* \Phi(G, n) \uparrow$ est $\Pi_1^0$. Ainsi, le prédicat $\exists n \exists \sigma T \upharpoonright_\sigma \Vdash^* \Phi(G, n) \uparrow$ est $\Sigma_2^0$, et le prédicat $T \Vdash \exists n \Phi(G, n) \uparrow$ est donc $\Sigma_2^0$. ■

Le second intérêt de la relation de question de forcing, est qu'elle permet de décider si une condition $c$ pourra être étendue en une condition $d$ pour forcer un contrat $\Sigma_2^0$, ou la négation de ce contrat. De plus, dans le cas de formules $\Sigma_2^0/\Pi_2^0$, on pourra trouver une extension $d \le c$ telle que le contrat sera satisfait pour tous les éléments de $[d]$ (comme pour les contrats $\Sigma_1^0/\Pi_1^0$).

**Proposition 4.11.** Soit $c$ une condition du forcing de Jockusch-Soare ou du forcing de Sacks et soit $\mathcal{R}$ un contrat $\Sigma_2^0$ correspondant à $\exists n \Phi(G, n) \uparrow$ pour une fonctionnelle $\Phi$.

1. Si $c \Vdash \exists n \Phi(G, n) \uparrow$, alors il existe $d \le c$ tel que $\exists n \Phi(X, n) \uparrow$ est vrai pour tout $X \in [d]$.

2. Si $c \Vdash \exists n \Phi(G, n) \uparrow$, alors il existe $d \le c$ tel que $\forall n \Phi(X, n) \downarrow$ est vrai pour tout $X \in [d]$.

Dans les deux cas, on peut trouver $d$ uniformément en $c$ et $\Phi$ à l'aide de $\emptyset''$.★

**PREUVE.** Commençons par le forcing de Jockusch-Soare. Soit $\mathcal{P} \subseteq 2^N$ une classe $\Pi_1^0$ non vide.

1. Si $\mathcal{P} \Vdash \exists n \Phi(G, n) \uparrow$, alors il existe $n$ tel que $\mathcal{P} \nVdash^* \Phi(G, n) \downarrow$. Cela signifie que la classe $\mathcal{Q} = \{X \in \mathcal{P} : \Phi(X, n) \uparrow\}$ est une classe $\Pi_1^0$ non vide. Il s'agit alors de notre extension de forcing.

2. Si $\mathcal{P} \Vdash \exists n \Phi(G, n) \uparrow$, alors $\mathcal{P} \Vdash^* \Phi(G, n) \downarrow$ pour tout $n$. Dans ce cas, pour tout $X \in \mathcal{P}$, on a déjà $\forall n \Phi(X, n) \downarrow$.

Notons que $\emptyset''$ peut décider entre les deux cas, et donc trouver l'extension de forcing appropriée. Passons au forcing de Sacks calculable. Soit à cet effet $T : 2^{<N} \to 2^{<N}$ un f-arbre calculable.

1. Si $T \Vdash \exists n \Phi(G, n) \uparrow$, alors $\exists \sigma \in 2^{<N}$ et $\exists n \in \mathbb{N}$ tels que $T \upharpoonright_\sigma \Vdash^* \Phi(G, n) \uparrow$. Dans ce cas, le f-arbre $T \upharpoonright_\sigma$ est notre extension de forcing.

2. Si $T \Vdash \exists n \Phi(G, n) \uparrow$, alors pour tout $\sigma \in 2^{<N}$ et pour tout $n \in \mathbb{N}$ on a $T \upharpoonright_\sigma \nVdash^* \Phi(G, n) \uparrow$. Cela implique que pour tout $\sigma \in 2^{<N}$ et pour tout $n \in \mathbb{N}$, il existe $\tau \succeq \sigma$ tel que $\Phi(T(\sigma\tau), n) \downarrow$. Alors, on procède comme dans la preuve du théorème 7-5.6 pour calculer un sous f-arbre $S$ de $T$ tel que $\forall n \Phi(X, n) \downarrow$ pour tout $X \in [S]$.

Notons que là encore $\emptyset''$ peut décider entre les deux cas, et donc trouver l'extension de forcing appropriée. ■
Avant de voir comment étendre la relation de question de forcing aux contrats de complexité arbitraires, voyons comment utiliser les développements obtenus jusqu'ici pour montrer que tout ensemble suffisamment généré pour le forcing de Sacks ou le forcing de Jockusch-Soare est low₂ généralisé.

**Théorème 4.12**

Si $G$ est suffisamment générique pour le forcing de Sacks ou le forcing de Jockusch-Soare, il est low₂ généralisé dans un sens fort : $\emptyset'' \oplus G' \geq_T G''$.

PREUVE. Pour tout $n$, d'après le lemme 10-5.6 le contrat $n \in G''$ est $\Sigma_2^0$. D'après la proposition 4.10 et la proposition 4.11, on peut énumérer à l'aide de $\emptyset''$ un ensemble $D_1$ de conditions $c$ telles que $n \in X''$ pour tout $X \in [c]$, et un ensemble $D_2$ de conditions $c$ telles que $n \notin X''$ pour tout $X \in [c]$, le tout tel que $D_1 \cup D_2$ soit un ensemble de conditions denses. Si $G$ est suffisamment générique, il existe une condition de $c \in D_1 \cup D_2$ telle que $G \in [c]$. La condition $c$ étant un arbre, on a besoin de $G'$ pour savoir si $G \in [c]$. Une fois la condition $c$ trouvée telle que $G \in [c]$, si $c \in D_1$ alors $n \in G''$, et si $c \in D_2$ alors $n \notin G''$. $\blacksquare$

### 4.2.2. Forcer des contrats $\Sigma_n^0/\Pi_n^0$

Pour les contrats plus complexes, il n'est pas possible de trouver des conditions dont tous les éléments satisfont le contrat, et il faut revenir à la définition inductive du forcing. Notre objectif est à présent de montrer un analogue du théorème 10-5.7 de préservation de la hiérarchie arithmétique. Comme la relation $\Vdash^*$ pour les forcings de Sacks et de Jockusch-Soare est trop complexe, nous allons étendre et utiliser à la place la relation de question de forcing définie précédemment pour les contrats $\Sigma_2^0$.

**Définition 4.13.** Soit $c$ une condition du forcing de Jockusch-Soare ou de Sacks et soit $\mathcal{R}$ un contrat arithmétique. On définit la relation $\Vdash$ entre $c$ et $\mathcal{R}$ comme suit :

(1) $c \Vdash \mathcal{R}$ pour $\mathcal{R}$ un contrat $\Sigma_1^0$ ssi $c \Vdash^* \mathcal{R}$.

(2) $c \Vdash \exists x \mathcal{R}(x)$ où $\mathcal{R}(x)$ est un contrat $\Pi_1^0$ ssi $c \Vdash \exists x \mathcal{R}(x)$ au sens de la définition 4.9.

(3) $c \Vdash \exists x \mathcal{R}(x)$ où $\mathcal{R}(x)$ est un contrat $\Pi_k^0$ pour $k \geq 2$ ssi il existe un $d \leq c$ et un $n \in \mathbb{N}$ tels que $d \Vdash \mathcal{R}(n)$.

(4) $c \Vdash \mathcal{R}$ où $\mathcal{R}(x)$ est un contrat $\Pi_k^0$ ssi $c \Vdash \neg \mathcal{R}$. $\diamond$

Nous étendons à présent la proposition 4.10 et la proposition 4.11, en commençant par montrer que la relation de question de forcing est $\Sigma_n^0$ pour les contrats $\Sigma_n^0$.
**Proposition 4.14.** Soit $c$ une condition du forcing de Jockusch-Soare ou du forcing de Sacks et soit $\mathcal{R}$ un contrat $\Sigma_n^0$ (resp. $\Pi_n^0$). La relation $c?\vdash \mathcal{R}$ est $\Sigma_n^0$ (resp. $\Pi_n^0$). ⋆

**PREUVE.** Le cas où $\mathcal{R}$ est un contrat $\Sigma_1^0$ a été traité dans la proposition 4.3 et la proposition 4.5. Le cas où $\mathcal{R}$ est un contrat $\Sigma_2^0$ a été traité dans la proposition 4.10.

Supposons que $\mathcal{R}$ soit un contrat $\Sigma_{n+1}^0$ égal à $\exists x Q(x)$, où $Q(x)$ est un contrat $\Pi_k^0$ pour $k \ge 2$. Alors, $c?\vdash \exists x Q(x)$ ssi il existe une condition de forcing $d$ et un entier $n$ tels que $d \le c$ et tels que $d?\vdash Q(n)$. Le prédicat $d \le c$ est $\Pi_2^0$ (dans le cas du forcing de Jockusch-Soare et du forcing de Sacks) et le prédicat $d?\vdash Q(n)$ est par induction $\Pi_k^0$ pour $k \ge 2$. Il s'ensuit que le prédicat $c?\vdash \exists x Q(x)$ est $\Sigma_{k+1}^0$.

Enfin, si $\mathcal{R}$ est un contrat $\Pi_n^0$, alors $P?\vdash \mathcal{R}$ ssi $P?\nvDash \neg \mathcal{R}$, ce qui est $\Pi_n^0$ par hypothèse d'induction. ■

On montre à présent l'extension de la proposition 4.11 : si $c?\vdash \mathcal{R}$, alors on va pouvoir trouver une extension $d \le c$ qui va forcer $\mathcal{R}$, mais attention, il s'agit ici du forcing sémantique et non du forcing syntaxique.

**Proposition 4.15.** Soit $c$ une condition du forcing de Jockusch-Soare ou de Sacks et soit $\mathcal{R}$ un contrat arithmétique. Si $c?\vdash \mathcal{R}$, alors il existe $d \le c$ tel que $d \Vdash \mathcal{R}$. ⋆

**PREUVE.** Si $\mathcal{R}$ est un contrat $\Sigma_1^0$ ou $\Pi_1^0$, alors le résultat est trivial par définition. Si $\mathcal{R}$ est un contrat $\Sigma_2^0$ ou $\Pi_2^0$, alors il s'agit de la proposition 4.11.

Supposons $\mathcal{R} = \exists x S(x)$ où $S(x)$ est un contrat $\Pi_k^0$ pour $k \ge 2$. Supposons que $c?\vdash \exists x S(x)$. Par définition, il existe une extension $d \le c$ et un entier $n \in \mathbb{N}$ tels que $d?\vdash S(n)$. Par hypothèse de récurrence, il existe un $e \le d$ tel que $e \Vdash S(n)$. En particulier, $e \Vdash \exists n S(n)$.

Supposons $\mathcal{R} = \forall x S(x)$, où $S(x)$ est un contrat $\Sigma_k^0$ pour $k \ge 2$. Supposons que $c?\vdash \forall x S(x)$. Alors, $c?\vdash \exists x \neg S(x)$. Par définition, pour toute extension $d \le c$ et tout $n \in \mathbb{N}$, $d?\nvDash \neg S(n)$. Montrons que pour tout $n$, l'ensemble $D_n = \{d : d \Vdash S(n)\}$ est dense sous $c$. Soient $n \in \mathbb{N}$ et $d \le c$. Par définition, comme $d?\nvDash S(n)$, alors $d?\vdash S(n)$. Par hypothèse d'induction, comme $d?\vdash S(n)$, alors il existe une extension $e \le d$ telle que $e \Vdash S(n)$. L'ensemble $D_n$ est donc dense sous $c$. Il s'ensuit par l'exercice 2.4 que l'on a $c \Vdash S(n)$ pour tout $n$, donc $c \Vdash \forall x S(x)$, autrement dit $c \Vdash \mathcal{R}$. ■

Cette fameuse question de forcing va nous permettre un contrôle fin de ce que calcule des itérations arbitraires du saut Turing. C'est l'objet de la section suivante.
## 4.3. Question de forcing

Essayons d'abstraire un peu ce qui a été fait jusqu'ici, afin d'étudier la notion de question de forcing, indépendamment du forcing sur lequel on travaille.

**Définition 4.16.** Soit $(\mathbb{P}, \leqslant)$ un forcing de Cantor. Une question de forcing est une relation $?\vdash$ entre les conditions et les contrats, telle que pour toute condition $c \in \mathbb{P}$ et tout contrat arithmétique $\mathcal{R}$

(1) Si $c?\vdash \mathcal{R}$, alors il existe une extension $d \leqslant c$ telle que $d$ force $\mathcal{R}$

(2) $c?\vdash \mathcal{R}$ ou $c?\vdash \neg \mathcal{R}$.

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

Il s'ensuit de (1) et (2) que si $c?\neg \mathcal{R}$, alors il existe une extension $d \leqslant c$ telle que $d$ force $\neg \mathcal{R}$. Toute relation de forcing $\models$ induit une question de forcing $?\vdash$ en définissant $c?\vdash \mathcal{R}$ pour un contrat $\Sigma_n^0 \mathcal{R}$ s'il existe une extension $d \leqslant c$ telle que $d \models \mathcal{R}$ et $c?\vdash \mathcal{R}$ pour un contrat $\Pi_n^0$ si $c?\neg \neg \mathcal{R}$. Si la notion de forcing est calculable, comme c'est le cas pour le forcing de Cohen, la complexité de la question de forcing pour les contrats $\Sigma_n^0$ hérite de la complexité de la relation de forcing pour les mêmes contrats.

**Exercice 4.17.** Soit $(\mathbb{P}, \leqslant)$ un forcing de Cantor, et $\models$ une relation de forcing. Montrer que la relation définie par $c?\vdash \mathcal{R}$ s'il existe une extension $d \leqslant c$ telle que $d \models \mathcal{R}$ est une question de forcing. ◇

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

### 4.3.1. Préservation de la hiérarchie arithmétique

Un certain nombre de propriétés de faiblesse des ensembles suffisamment génériques pour les forcings de Cantor dépendent de l'existence d'une question de forcing avec de bonnes propriétés définitionnelles. Dans ce qui suit, nous fixons un forcing de Cantor $(\mathbb{P}, \leqslant)$ ainsi qu'une question de forcing $?\vdash$. La proposition 4.19 suivante en est le premier exemple, et généralise le théorème 10-5.7.

**Définition 4.18.** Une question de forcing $?\vdash$ préserve la hiérarchie arithmétique si pour toute condition $c$ et tout contrat $\mathcal{R} \Sigma_n^0$, la relation $c?\vdash \mathcal{R}$ est $\Sigma_n^0$ uniformément en $c$ et $\mathcal{R}$.

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

**Proposition 4.19.** Soit $?\vdash$ une question de forcing qui préserve la hiérarchie arithmétique. Alors, pour tout $n \geqslant 1$, pour tout ensemble $A$ qui n'est pas $\Sigma_n^0$, et pour tout ensemble $G$ suffisamment générique, $A$ n'est pas $\Sigma_n^0(G)$. ⋆

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

**PREUVE.** Pour tout $e \in \mathbb{N}$, soit

$$D_e = \{c \in \mathbb{P} : (\exists m \notin A \ c \models m \in W_e^{G^{(n-1)}}) \text{ ou } (\exists m \in A \ c \models m \notin W_e^{G^{(n-1)}})\}$$
Montrons que $D_e$ est un ensemble dense dans $(\mathbb{P}, \leqslant)$. Soit $c \in \mathbb{P}$, et soit

$$U = \{m \in \mathbb{N} : c?\vdash m \in W_e^{G^{(n-1)}}\}$$

D'après le lemme 10-5.6, le contrat $m \in W^{G^{(n-1)}}$ est $\Sigma_n^0$ uniformément en $m$, donc comme la question de forcing préserve la hiérarchie arithmétique, l'ensemble $U$ est $\Sigma_n^0$. L'ensemble $A$ n'étant pas $\Sigma_n^0$, alors la différence symétrique $U\Delta A = (U \setminus A) \cup (A \setminus U)$ n'est pas vide.

Soit $m \in U\Delta A$.

Cas 1. On a $m \in U \setminus A$. Alors, par définition de la question de forcing, il existe une extension $d \leqslant c$ telle que $d \models m \in W_e^{G^{(n-1)}}$. En particulier, $d \in D_e$.

Cas 2. On a $m \in A \setminus U$. Alors, toujours par la définition de la question de forcing, il existe une extension $d \leqslant c$ telle que $d \models m \notin W_e^{G^{(n-1)}}$. Là encore, $d \in D_e$.

Dans tous les cas, il existe une extension de $d$ dans $D_e$, et l'ensemble $D_e$ est donc dense. Soit $F$ un filtre suffisamment générique pour $(\mathbb{P}, \leqslant)$. Par densité de $D_e$, on peut supposer que $F$ intersecte $D_e$ pour tout $e \in \mathbb{N}$. Soit $G = \dot{F}$. Par définition de la relation de forcing, pour tout $e \in \mathbb{N}$, soit $m \in W_e^{G^{(n-1)}}$ pour un $m \notin A$, soit $m \notin W_e^{G^{(n-1)}}$ pour un $m \in A$. On en déduit donc que $A$ n'est pas $\Sigma_n^0(G)$. ■

**Corollaire 4.20**

Soit $?\vdash$ une question de forcing qui préserve la hiérarchie arithmétique.

Alors, pour tout $n \geqslant 0$ et tout ensemble $A$ non $\emptyset^{(n)}$-calculable, pour tout ensemble $G$ suffisamment générique, $A$ n'est pas $G^{(n)}$-calculable.

PREUVE. Comme $A$ n'est pas $\emptyset^{(n)}$-calculable, il n'est pas $\Delta_{n+1}^0$. Soit $A$ n'est pas $\Sigma_{n+1}^0$, soit $\bar{A}$ n'est pas $\Sigma_{n+1}^0$. Par la proposition 4.19, pour tout ensemble $G$ suffisamment générique pour $(\mathbb{P}, \leqslant)$, $A$ n'est pas $\Sigma_{n+1}^0(G)$ dans le premier cas, et $\bar{A}$ n'est pas $\Sigma_{n+1}^0(G)$ dans le second cas. Dans tous les cas, $A$ n'est pas $\Delta_{n+1}^0(G)$, et donc pas $G^{(n)}$-calculable. ■

**Corollaire 4.21**

Soit $n \geqslant 0$, et soit $A \in 2^\mathbb{N}$ un ensemble non $\emptyset^{(n)}$-calculable. Si $G$ est suffisamment générique pour le forcing de Jockusch-Soare ou pour le forcing de Sacks, alors $A$ n'est pas $G^{(n)}$-calculable.

PREUVE. D'après la proposition 4.14, ces deux notions de forcing pré-servent la hiérarchie arithmétique. ■
### 4.3.2. Préservation d'hyperimmunité

Rappelons qu'une fonction $f: \mathbb{N} \to \mathbb{N}$ est hyperimmune relativement à $X$ si elle n'est dominée par aucune fonction $X$-calculable (voir la section 7-4). Aucune fonction n'est hyperimmune relativement à tous les degrés Turing, à commencer par le degré Turing de la fonction elle-même. Cependant, si une fonction est hyperimmune, elle est également hyperimmune relativement à tout degré calculatoirement dominé. On peut donc considérer que les degrés calculatoirement dominés ≪ préservent ≫ les hyperimmunités de toutes les fonctions simultanément. Nous allons maintenant étudier dans quelle mesure les ensembles suffisamment génériques pour des forcings de Cantor préservent des hyperimmunités.

Nous avons vu dans la section 10-3.1 que tout ensemble $X$ faiblement 1-générique était de degré hyperimmune. Plus précisément, la fonction principale $p_X$ de $X$ qui à $n$ associe le $n$-ième élément de $X$ est hyperimmune. Les ensembles suffisamment génériques pour le forcing de Cantor ne préservent donc pas toutes les hyperimmunités simultanément. Cependant, il est possible de s'assurer qu'ils préservent l'hyperimmunité de toute fonction hyperimmune fixée à l'avance.

**Définition 4.22.** Une question de forcing $?\vdash$ est *compacte* si pour tout $c \in \mathbb{P}$, tout contrat arithmétique $\mathcal{R}(x)$, si $c?\vdash \exists x \mathcal{R}(x)$, alors il existe un ensemble fini $U \subseteq \mathbb{N}$ tel que $c?\vdash \exists x \in U \mathcal{R}(x)$. ◇

La compacité d'une question de forcing est suffisante pour assurer la propriété de préservation d'une hyperimmunité.

**Proposition 4.23.** Soit $?\vdash$ une question de forcing compacte qui préserve la hiérarchie arithmétique. Alors, pour tout $n \ge 0$ et toute fonction hyperimmune $f: \mathbb{N} \to \mathbb{N}$ relativement à $\emptyset^{(n)}$, pour tout ensemble $G$ suffisamment générique pour $(\mathbb{P}, \leqslant)$, la fonction $f$ est hyperimmune relativement à $G^{(n)}$.★

**PREUVE.** Soit $f: \mathbb{N} \to \mathbb{N}$ une fonction hyperimmune relativement à $\emptyset^{(n)}$. Pour tout $e \in \mathbb{N}$, soit

$$D_e = \{c \in \mathbb{P} : (\exists m c \Vdash \Phi_e(G^{(n)}, m)\uparrow) \text{ ou } (\exists m c \Vdash \Phi_e(G^{(n)}, m)\downarrow< f(m))\}.$$

Montrons alors que $D_e$ est un ensemble dense dans $(\mathbb{P}, \leqslant)$. Soit $c \in \mathbb{P}$, et soit $g: \mathbb{N} \to \mathbb{N}$, la fonction partielle qui pour tout $m$, cherche un ensemble fini $U \subseteq \mathbb{N}$ tel que $c?\vdash \Phi_e(G^{(n)}, m)\downarrow \in U$. Si un tel ensemble $U$ est trouvé, $g(m) = 1 + \max U$, sinon $g(m)$ n'est pas défini. Sachant que la question de forcing préserve la hiérarchie arithmétique, $g$ est partielle $\emptyset^{(n)}$-calculable. Les deux cas suivants se présentent.
Cas 1. Il existe un $m$ tel que $g(m)$ n'est pas défini. Alors, par compacité de la question de forcing, $c \nleq \Phi_e(G^{(n)}, m) \downarrow$, donc il existe un $d \leq c$ tel que $d \Vdash \Phi_e(G^{(n)}, m) \uparrow$. En particulier, $d \in D_e$.

Cas 2. La fonction $g$ est totale $\emptyset^{(n)}$-calculable. Par hyperimmunité de $f$ relativement à $\emptyset^{(n)}$, il existe un $m \in \mathbb{N}$ tel que $g(m) \leq f(m)$. En particulier, $c \nleq \Phi_e(G^{(n)}, m) \downarrow \in U$ pour un ensemble fini $U$ tel que $\max U < f(m)$. Par définition d'une question de forcing, il existe une extension $d \leq c$ telle que $d \Vdash \Phi_e(G^{(n)}, m) \downarrow \in U$, donc $\Phi_e(G^{(n)}, m) \downarrow < f(m)$. Il s'ensuit que $d \in D_e$.

Dans tous les cas, il existe une extension de $d$ dans $D_e$, donc l'ensemble $D_e$ est dense. Soit $F$ un filtre suffisamment générique pour $(\mathbb{P}, \leq)$. Par densité de $D_e$, on peut supposer que $F$ intersecte $D_e$ pour tout $e \in \mathbb{N}$. Soit $G = \dot{F}$. Par définition de la relation de forcing, pour tout $e \in \mathbb{N}$, soit $\Phi_e(G^{(n)})$ est une fonction partielle, soit $\Phi_e(G^{(n)}, m) \downarrow < f(m)$ pour un $m \in \mathbb{N}$, donc $f$ est hyperimmune relativement à $G^{(n)}$. ■

La question de forcing canonique du forcing de Cohen est compacte et préserve la hiérarchie arithmétique, ce qui implique que tout ensemble suffisamment générique pour le forcing de Cohen préserve l'hyperimmunité de toute fonction préalablement fixée. On peut montrer qu'il en va de même pour les forcings de Jockusch-Soare et de Sacks.

### 4.3.3. Préservation des degrés non PA

Nous allons terminer l'étude des propriétés des questions de forcing avec un critère pour ne pas calculer de degré PA.

**Définition 4.24.** Une question de forcing $?\Vdash$ est $\Pi$-fusionnable si pour tout $c \in \mathbb{P}$, toute paire de contrats $\Pi_n^0 \mathcal{R}_0, \mathcal{R}_1$ telle que $c \nleq \mathcal{R}_0$ et $c \nleq \mathcal{R}_1$, il existe une extension $d \leq c$ qui force simultanément $\mathcal{R}_0$ et $\mathcal{R}_1$. ◇

**Proposition 4.25.** Soit $?\Vdash$ une question de forcing $\Pi$-fusionnable qui préserve la hiérarchie arithmétique. Alors, pour tout $n \geq 0$ pour tout ensemble $G$ suffisamment générique pour $(\mathbb{P}, \leq)$, $G^{(n)}$ n'est pas de degré PA relativement à $\emptyset^{(n)}$. ★

**PREUVE.** D'après le théorème 8-6.2, un degré Turing est PA ssi il calcule une fonction DNC à valeurs dans $\{0, 1\}$. Dans ce qui suit, nous supposerons que $\Phi_0, \Phi_1, \dots$ est l'énumération des fonctionnelles de Turing à valeurs dans $\{0, 1\}$. Pour tout $e \in \mathbb{N}$, soit

$$D_e = \left\{ c \in \mathbb{P} : \begin{array}{l} (\exists m \ c \Vdash \Phi_e(G^{(n)}, m) \uparrow) \\ \text{ou} \\ (\exists m \ c \Vdash \Phi_e(G^{(n)}, m) \downarrow = \Phi_e(\emptyset^{(n)}, m)) \end{array} \right\}.$$
Montrons que $D_e$ est un ensemble dense dans $(\mathbb{P}, \leqslant)$. Soit $c \in \mathbb{P}$, et soit la fonction partielle $g: \mathbb{N} \to \mathbb{N}$, qui pour tout $m$, cherche un entier $v \in \{0, 1\}$ tel que $c \not\vdash \Phi_e(G^{(n)}, m) \downarrow = v$. Si un tel $v$ est trouvé, $g(m) = v$, sinon $g(m)$ n'est pas défini. Sachant que la question de forcing préserve la hiérarchie arithmétique, $g$ est partielle $\emptyset^{(n)}$-calculable. Deux cas se présentent.

Cas 1. Il existe un $m$ tel que $g(m)$ n'est pas défini. Alors, pour tout $v < 2$, on a $c \nvdash \Phi_e(G^{(n)}, m) \downarrow = v$, autrement dit $c \not\vdash \neg(\Phi_e(G^{(n)}, m) \downarrow = v)$. Comme la relation est Π-fusionnable, il existe un $d \leqslant c$ tel que $d$ force à la fois $\neg(\Phi_e(G^{(n)}, m) \downarrow = 0)$ et $\neg(\Phi_e(G^{(n)}, m) \downarrow = 1)$; or, la fonctionnelle étant à valeurs dans $\{0, 1\}$, $d$ force donc $\Phi_e(G^{(n)}, m) \uparrow$. En particulier, $d \in D_e$.

Cas 2. La fonction $g$ est totale $\emptyset^{(n)}$-calculable. Sachant qu'un degré n'est pas PA relativement à lui-même, il existe $m \in \mathbb{N}$ tel que $g(m) = \Phi_m(\emptyset^{(n)}, m)$. En particulier, $c \not\vdash \Phi_e(G^{(n)}, m) \downarrow = g(m)$, donc par définition d'une question de forcing, il existe une extension $d \leqslant c$ telle que

$$d \vdash \Phi_e(G^{(n)}, m) \downarrow = g(m) = \Phi_m(\emptyset^{(n)}, m).$$

Il s'ensuit que $d \in D_e$.

Dans tous les cas, il existe une extension de $d$ dans $D_e$, et l'ensemble $D_e$ est donc dense. Soit $F$ un filtre suffisamment générique pour $(\mathbb{P}, \leqslant)$. Par densité de $D_e$, on peut supposer que $F$ intersecte $D_e$ pour tout $e \in \mathbb{N}$. Soit alors $G = \dot{F}$.

Par définition de la relation de forcing, pour tout entier $e \in \mathbb{N}$, soit la fonction $m \mapsto \Phi_e(G^{(n)}, m)$ est partielle, soit $\Phi_e(G^{(n)}, m) \downarrow = \Phi_m(\emptyset^{(n)}, m)$ pour un entier $m \in \mathbb{N}$, donc $G^{(n)}$ n'est pas de degré PA relativement à $\emptyset^{(n)}$.■

La question de forcing pour le forcing de Cohen est Π-fusionnable, tout comme la question de forcing pour le forcing de Sacks calculable. Il n'existe en revanche pas de question de forcing Π-fusionnable pour le forcing de Jockusch-Soare, car il existe des classes $\Pi_1^0$ non vides ne contenant que des ensembles de degré PA.

**Exercice 4.26. (⋆)** Une question de forcing ?$\vdash$ est Π-$\omega$-fusionnable si pour tout $c \in \mathbb{P}$, toute suite de contrats $\Pi_n^0 \mathcal{R}_0, \mathcal{R}_1, \dots$ telle que $c \not\vdash \mathcal{R}_i$ pour tout $i \in \mathbb{N}$, il existe une extension $d \leqslant c$ qui force simultanément $\mathcal{R}_i$ pour tout $i$. Montrer que si ?$\vdash$ est une question de forcing Π-$\omega$-fusionnable qui préserve la hiérarchie arithmétique, alors pour tout ensemble $G$ suffisamment générique et tout $n$, son saut itéré $G^{(n)}$ n'est pas de degré DNC relativement à $\emptyset^{(n)}$. ◇
Chapitre
12

La quête de degrés naturels

Les débuts de la calculabilité ont permis d'observer que tous les ensembles
calculatoirement énumérables provenant de problèmes naturels étaient soit
calculables, soit aussi puissants que le problème de l'arrêt, qui plus est via
une réduction many-one (voir la section 5-4). Cela a conduit Post à se poser
en 1944 la question suivante.

**Question (Problème de Post [181]).** Existe-t-il des degrés c. e. et non calculables qui soient strictement plus faibles que le problème de l'arrêt ?★

Le problème de Post est resté ouvert pendant près d'une décennie, avant
d'être résolue par l'affirmative par Muchnik [163] et Friedberg [63] via la
méthode des priorités, que nous verrons dans la section 13-3. Le problème
de Post a depuis connu bien d'autres résolutions différentes, ne faisant pas
nécessairement appel à la méthode de priorité. On peut citer par exemple
la construction d'un ensemble K-trivial c. e. et non calculable, que nous
verrons avec le théorème 16-4.5. Toutes ces constructions reposent toutefois
sur une argumentation complexe permettant de construire tout exprès un
ensemble « artificiel » ayant les propriétés voulues, et les seuls problèmes de
décision « naturels » indécidables connus à ce jour se réduisent au problème
de l'arrêt<fnref n="1" />. À l'inverse, le problème de l'arrêt semble survenir naturellement
un peu partout. La question s'est alors posée des propriétés qui lui conferent
cette naturalité.

<footnote n="1">1. Cette affirmation doit toutefois être reçue avec précaution, et sera atténuée dans
la dernière section de ce chapitre.</footnote>
# 1. Trois problèmes indécidables emblématiques

Avant d'aborder directement le problème de Post, voyons trois exemples emblématiques de problèmes de décision c. e. et indécidables, tous équivalents au problème de l'arrêt.

## Problème de correspondance de Post

Nous commençons par un problème défini par Post lui-même en 1946, que l'on appelle problème de correspondance de Post, et qui ne doit pas être confondu avec le « Problème de Post », qui fait référence à la question ci-dessus.

Étant donné deux listes finies de chaînes

$$ \sigma_0, \dots, \sigma_n \in 2^{<\mathbb{N}} \quad \text{et} \quad \tau_0, \dots, \tau_n \in 2^{<\mathbb{N}}, $$

existe-t-il une suite d'indices $(i_k)_{k \le K}$ — possiblement avec répétition — telle que les concatenénations $\sigma_{i_0}\sigma_{i_1}\dots\sigma_{i_K}$ et $\tau_{i_0}\tau_{i_1}\dots\tau_{i_K}$ forment la même chaîne ?

La question peut sembler simple en apparence, et l'on pourrait même penser au premier abord qu'il est facile de créer un algorithme permettant de la résoudre. Après tout, le nombre de chaînes en question est fini. En y réfléchissant plus longuement, le problème ne devrait pas s'avérer si évident, et pour cause, même si cela peut paraître surprenant, il s'agit d'une question indécidable, et aussi difficile que celle de savoir si un programme informatique s'arrête ou pas.

Pour le montrer, Post trouve une manière astucieuse d'encoder le calcul d'une machine de Turing via des instances du problème de correspondance. Ainsi, une instance pour laquelle une correspondance existe correspondra à un calcul qui s'arrête, et une instance pour laquelle aucune correspondance n'existe correspondra à un calcul qui se déroule à l'infini.

## Pavage du Plan

En 1961, Hao Wang imagine le problème suivant : étant donné un ensemble fini de tuiles, c'est-à-dire de carrés ayant une couleur sur chacun de leur côtés, l'objectif est de faire un pavage du plan en n'utilisant que des tuiles dont les couleurs correspondent à celles de l'une des tuiles de notre ensemble fini, en imposant que deux tuiles côte à côte partagent la même couleur sur leur côté en commun. Il y a bien entendu des ensembles de tuiles pour lesquels un tel pavage du plan est possible, et d'autres pour lesquels cela ne l'est pas.
<figure><img src="image_86.png" /><figcaption>FIGURE 1.1 – Début de pavage du plan à l'aide des quatre tuiles ci-dessus</figcaption></figure>

Un lemme découlant de celui de König s'applique aux pavages du plan utilisant un nombre fini de tuiles : si pour tout $n$ il existe un pavage de $n×n$ tuiles, alors il existe un pavage infini du plan. On en déduit alors que si un ensemble fini de tuiles ne permet pas de paver le plan, il existe $n$ tel qu'aucun pavage de taille $n×n$ n'est possible. Si un pavage est impossible il suffit alors de chercher le plus petit $n$ tel qu'aucune configuration de pavage de taille $n×n$ ne fonctionne. Autrement dit, les ensembles finis de tuiles ne permettant pas de paver le plan peuvent être énumérés par un algorithme.

Wang conjecture alors qu'il en va de même pour les ensembles finis de tuiles permettant de paver le plan, ce qui rendrait décidable le problème de pavage du plan : il existerait un algorithme permettant de décider, étant donné un ensemble fini de tuiles, si ce dernier peut ou non paver le plan.

Mais en 1966, Robert Berger (un élève de Wang) montre que le problème de pavage du plan n'est pas décidable, en lui réduisant là encore le problème de l'arrêt des machines de Turing, à la manière de Post : Berger crée un système de pavage permettant de « simuler » le calcul s'effectuant sur une machine de Turing, un pavage impossible signifiant que la machine s'arrête, et un pavage possible signifiant que le calcul se poursuit indéfiniment.
## Dixième problème de Hilbert

Une équation diophantienne est une équation polynomiale à une ou plusieurs inconnues dont les solutions sont à chercher parmi les nombres entiers — ou éventuellement rationnels —, les coefficients étant eux-mêmes également entiers. Par exemple, $a^2 + b^2 = c^2$ est une équation diophantienne ayant de nombreuses solutions comme $a = 3$, $b = 4$ et $c = 5$. Il y a en revanche des équations diophantiennes n'ayant aucune solution. Certaines d'entre elles ont demandé pour leur résolution — pour en trouver les solutions ou montrer qu'elles n'en ont pas — des efforts considérables de nombreux mathématiciens sur plusieurs siècles. L'exemple par excellence est certainement le fameux « dernier théorème de Fermat » qui stipule que pour tout entier $n > 2$, l'équation $a^n + b^n = c^n$ n'a pas de solutions entières (non triviales).

Fermat énonce son théorème en marge d'une traduction des « Arithmétiques de Diophante », dans laquelle il écrit : « Au contraire, il est impossible de partager soit un cube en deux cubes, soit un bicarré en deux bicarrés, soit en général une puissance quelconque supérieure au carré en deux puissances de même degré : j'en ai découvert une démonstration véritablement merveilleuse que cette marge est trop étroite pour contenir. »

De nombreux mathématiciens ont cherché cette démonstration merveilleuse des siècles durant et sans succès. C'est seulement après 357 ans d'efforts que le mathématicien Andrew Wiles, aidé de son ex-étudiant Richard Taylor apportera une preuve en utilisant des outils mathématiques évidemment bien plus complexes que ceux qui existaient à l'époque de Fermat.

En 1900, Hilbert place la question de la résolution des équations diophantiennes en dixième position dans sa fameuse liste de vingt-trois problèmes : « On donne une équation diophantienne à un nombre quelconque d'inconnues et à coefficients entiers : on demande de trouver une méthode par laquelle, au moyen d'un nombre fini d'opérations, on pourra distinguer si l'équation est résoluble en nombres entiers. »

Hilbert demande, avant que l'on en ait une définition formelle, l'existence d'un *algorithme* permettant de savoir si toute équation diophantienne admet ou non une solution.

Là encore, l'ensemble des équations diophantiennes ayant une solution est calculatoirement énumérable ; il suffit en effet de chercher parmi tous les candidats potentiels si l'un d'eux est une solution. Martin Davis, Hilary Putnam et Julia Robinson eurent l'idée de montrer que le dixième problème de Hilbert est indécidable en suivant une intuition audacieuse, et qui s'averrera juste : une équation diophantienne est la brique de base d'une formule de l'arithmétique, en l'occurrence l'égalité entre deux termes. Aussi
Gödel a-t-il montré que les ensembles c. e. sont exactement ceux qui peuvent
se définir par des formules $\Sigma_1^0$ de l'arithmétique.

Ne serait-il pas possible de transformer une telle formule en une formule $\Sigma_1^0$ équivalente $\exists x_1 \dots \exists x_n F(x_1, \dots, x_n)$, mais où F ne soit plus qu'une grosse équation diophantienne ? Considérons par exemple le cas de la formule

$$
t_1(a_1, \dots, a_i) = q_1(b_1, \dots, b_j) \lor t_2(x_1, \dots, x_k) = q_2(y_1, \dots, y_l),
$$

où $t_1, t_2$ et $q_1, q_2$ sont des termes. Alors, cette formule est vraie dans $\mathbb{N}$ si,
et seulement si, la formule

$$
t_1(a_1, \dots, a_i) - q_1(b_1, \dots, b_j) = 0 \lor t_2(x_1, \dots, x_k) - q_2(y_1, \dots, y_l) = 0
$$

est vraie dans $\mathbb{Z}$, ou ce qui revient au même si l'équation diophantienne

$$
(t_1(a_1, \dots, a_i) - q_1(b_1, \dots, b_j)) \times (t_2(x_1, \dots, x_k) - q_2(y_1, \dots, y_l)) = 0
$$

admet des solutions. On montre sans peine quelque chose de similaire pour
le connecteur ∧, la difficulté restante étant dans la suppression des quanti-
fications existentielles et universelles bornées. Davis, Putnam et Robinson
réussirent à supprimer les quantifications bornées au prix de l'utilisation de
la fonction exponentielle dans les équations résultantes. Le travail sera alors
achevé par Matiiassevitch, qui parvint à encoder la fonction exponentielle
en équations diophantiennes, conduisant au théorème suivant.

Théorème 1.2 (Théorème MRDP)

Soit $A \subseteq \mathbb{N}$ un ensemble calculatoirement énumérable. Alors, il existe
une formule $\Sigma_1^0$ de l'arithmétique $F(x) = \exists y_1, \dots, \exists y_n G(x, y_1, \dots, y_n)$,
où $G$ n'a pas de quantificateur tel que $x \in A$ si, et seulement si, $\mathbb{N} \models F(x)$.

Le théorème MRDP est remarquable en ce sens qu’il illustre le fait que
l’indécidabilité de l’arithmétique de Peano est dissimulée dans la structure
même de l’addition et de la multiplication des entiers, et ce sans aucun
besoin de recourir aux quantifications bornées. Il apporte bien sûr une
réponse au dixième problème de Hilbert : si un algorithme permet de savoir
si une équation diophantienne a des solutions entières, alors on peut créer
un algorithme calculant le problème de l’arrêt.

2. Approche pour la naturalité des degrés Turing

Revenons à notre question d'origine : qu'y a-t-il de spécial à propos du problème de l'arrêt pour que tous les problèmes de décision c. e. lui soient équivalents ? Qu'est-ce qui fait au fond la naturalité d'un degré Turing ?
Steel [217] suggère une réponse : un degré Turing naturel devrait être définissable, et sa définition devrait se relativiser à n'importe quel degré. Par exemple, le problème de l'arrêt $\emptyset'$, initialement défini comme un ensemble particulier, à savoir $\{e : \Phi_e(e)\downarrow\}$, se relativise à tout ensemble $X$, en considérant l'ensemble $X' = \{e : \Phi_e(X, e) \downarrow\}$. Comme déjà vu dans la section 4-6, il s'agit d'une notion sur les degrés Turing, dans le sens où si $X \equiv_T Y$, alors $X' \equiv_T Y'$.

## 2.1. Question de Sacks

L'idée de Steel fait écho à une vieille question de Sacks [188] : existe-t-il une solution au problème de Post qui soit invariante sur les degrés Turing ? On dira que $W$ est un opérateur c. e. si $W$ correspond à une fonctionnelle Turing qui uniformément en un ensemble $X$ énumère un ensemble, que l'on notera $W^X$.

Sacks demande s'il existe un opérateur c. e. $W$ tel que $X <_T W^X <_T X'$ pour tout $X$ et tel que $X_0 \equiv_T X_1$ implique $W^{X_0} \equiv_T W^{X_1}$ pour tout $X_0, X_1$.

En y travaillant un peu, le lecteur pourra constater que la méthode de priorité utilisée dans le théorème 13-3.1 pour construire un ensemble c. e. $Y$ tel que $0 <_T Y <_T \emptyset'$ peut se relativiser à n'importe quel oracle $X$ pour obtenir un ensemble $X$-c. e. $Y$ tel que $X <_T Y <_T X'$. En revanche, il est beaucoup plus incertain que cette relativisation soit invariante dans les degrés Turing, et de fait elle ne l'est pas. Le premier résultat dans cette direction fut obtenu par Lachlan, qui apporta une réponse négative à la question de Sacks, dans le cas particulier où l'on attend de l'invariance qu'elle soit uniforme, c'est-à-dire que l'on demande l'existence de fonctions $h_1, h_2$ telles que si $\Phi_{a_1}(X_1) = X_2$ et $\Phi_{a_2}(X_2) = X_1$, alors $\Phi_{h_1(a_1)}(W^{X_1}) = W^{X_2}$ et $\Phi_{h_2(a_2)}(W^{X_2}) = W^{X_1}$. Notons que Lachlan ne demande pas que les fonctions $h_1, h_2$ soient calculables, mais simplement qu'elles existent.

Dans le cas où l'opérateur est invariant dans les degrés Turing, la notation $W(a)$ pour un degré Turing $a$ admet un sens : il s'agit du degré Turing obtenu en appliquant à $W$ un ensemble quelconque dans le degré $a$. Lachlan montre en fait la chose suivante : pour tout opérateur c. e. $W$ uniformément invariant tel que $W(d) \ge d$ pour tout degré $d$, il existe un degré $a$ tel que pour tout degré $d \ge a$ on a $W(d) = d$, ou bien tel que pour tout degré $d \ge a$ on a $W(d) = d'$. Dans le premier cas, on dira que $W$ coïncide avec l'identité sur un cône, et dans le second que $W$ coïncide avec le saut Turing sur un cône. L'expression sur un cône signifiant alors sur un cône dans les degrés Turing, c'est-à-dire sur tous les degrés supérieurs à $a$ pour un certain $a$, le degré $a$ étant la base du cône. Lachlan obtient donc le résultat suivant.
**Théorème 2.1 (Lachlan [132])**

Soit W un opérateur c. e. uniformément invariant tel que $W(d) \geqslant d$ pour tout degré d. Alors, W est l'opérateur de saut sur un cône ou bien W est l'opérateur identité sur un cône.

**2.2. Question de Sacks pour des degrés quelconques**

Nous avons jusqu'à présent parlé des degrés c. e. naturels, en argumentant sur le fait que $\mathbf{0}$ et $\mathbf{0}'$ sont les seuls d'entre eux. Il existe toutefois beaucoup de problèmes de décision naturels strictement plus puissants que le problème de l'arrêt, et qui ne sont bien entendu pas c. e. On peut alors pousser la question de la naturalité pour des degrés quelconques. Voyons d'abord quelques exemples canoniques.

1. P : le problème de déterminer si un polynôme de $\mathbb{Z}[x, y_0, y_1, y_2, \dots]$ a des solutions pour tout élément $x$ suffisamment grand.

2. T : le problème de savoir si un énoncé de l'arithmétique est vrai dans $\mathbb{N}$.

3. WF : le problème de savoir si un arbre calculable de $\mathbb{N}^{<\mathbb{N}}$ a des chemins infinis.

Le problème P est $\Sigma_3^0$, et le triple arrêt s'y réduit de manière many-one. Le problème T permet de many-one calculer $\emptyset^{(n)}$ pour tout $n \in \mathbb{N}$ uniformément en l'entier $n$. Il est par ailleurs many-one calculable avec l'oracle $\emptyset^{(\omega)} = \bigoplus_n \emptyset^{(n)}$ et correspond donc au premier niveau transfini dans la hiérarchie des sauts Turing (nous verrons cela formellement dans la partie IV). Le problème WF est, quant à lui, plus complexe encore, et correspond à un saut Turing transfini plus élevé, que l'on peut noter $\emptyset^{(\omega_1^{\aleph_1})}$ et que l'on appelle communément *l'hypersaut* (nous verrons également cela formellement dans la partie IV).

Notons que les itérations du saut Turing, tout comme le saut Turing simple, se relativisent également à tout oracle de manière invariante sur les degrés Turing : par exemple, si $X \equiv_T Y$, alors $X^{(3)} \equiv_T Y^{(3)}$. Les opérateurs de saut itéré sont donc eux aussi naturels, et l'on peut trouver pour chacun d'entre eux des problèmes de décision qui leur correspondent. On peut parallèlement itérer la question de Sacks : les solutions du problème de Post ne sont pas les seules constructions de degrés exotiques en calculabilité, et cette question de l'invariance des opérateurs peut être étendue à toute construction. Considérons par exemple la construction d'un ensemble calculatoirement dominé du théorème 7-5.6 ou celle du théorème 8-4.5. Dans les deux cas, la construction nécessite $\emptyset''$. On vérifie sans peine avec l'une ou l'autre construction que l'on peut créer un opérateur $\emptyset''$-calculable W
tel que pour tout $X$ l'ensemble $W^X$ vérifie $X <_T W^X$ et est tel que $W^X$ est calculatoirement dominé relativement à $X$. Un tel opérateur peut-il être invariant dans les degrés Turing ? Si ce n'est pas le cas, peut-on en obtenir un calculable en $\emptyset''$ ou en un oracle plus puissant ?

## 2.3. Conjecture de Martin

Inspiré par ces questions, et peut-être par le résultat de Lachlan sur les opérateurs c. e., Martin propose alors une conjecture pour le moins hardie qui dit essentiellement : l'opérateur de saut et ses itérations, sont les seuls opérateurs définissables et invariants dans les degrés Turing. Plus formellement, la conjecture comporte deux parties distinctes.

**Conjecture 2.2 (Martin [1] p. 281).** Soit $f : 2^N \to 2^N$ une fonction borélienne et invariante dans les degrés Turing. Alors, en voyant $f$ comme une fonction sur les degrés Turing, on a ce qui suit :

I. soit $f$ est constante sur un cône, soit $f$ est croissante sur un cône;

II. si $f$ est croissante sur un cône, alors elle correspond à l'une des itérations (possiblement zéro ou transfinie) du saut Turing. ★

Que veut-on dire par $f$ borélienne ? Avant d'y répondre, notons que si l'on sort complètement du cadre de la calculabilité, on peut parfaitement définir des fonctions $f$ invariantes dans les degrés Turing telles que $\mathbf{a} < f(\mathbf{a}) < \mathbf{a}'$ pour tout $\mathbf{a}$, à l'aide simplement de l'axiome du choix de la théorie des ensembles. L'objectif de restreindre la conjecture aux fonctions $f$ boréliennes a essentiellement pour but d'interdire l'utilisation de cet axiome, et la conjecture est généralement présentée sans la restriction pour $f$ d'être borélienne, et avec des hypothèses supplémentaires sur les axiomes de la théorie des ensembles, signifiants essentiellement : « pour toute fonction $f$ que l'on peut définir sans utiliser l'axiome du choix ».

La conjecture de Martin nous dit en substance que les seuls opérateurs naturels et non constants dans les degrés Turing sont l'opérateur identité, l'opérateur de saut et ses itérations. Si cette conjecture est à ce jour encore ouverte, de nombreux progrès ont été faits, en y ajoutant comme le fit Lachlan la condition d'uniformité dans l'invariance des fonctions $f$ considérées. D'abord, Steel [217] a montré la partie II de la conjecture de Martin, pour les fonctions uniformément invariantes, généralisant donc considérablement le résultat de Lachlan. Ensuite, toujours pour les fonctions uniformément invariantes, Slaman et Steel [205] ont montré I, et ont aussi réussi à se passer, via une preuve très astucieuse, de l'uniformité pour le cas des fonctions $f$ telles que $f(\mathbf{a}) < \mathbf{a}$ pour tout degré $\mathbf{a}$ sur un cône : ces fonctions là sont nécessairement constantes sur un cône.
On ne sait à ce jour pas grand-chose sur la conjecture dans le cas général, et c'est par ailleurs également valable pour la question de Sacks potentiellement bien plus simple, qui elle aussi reste ouverte dans le cas de la non-uniformité. Cette histoire de non-uniformité a toutefois de quoi instiller le doute : si l'on cherche au fond à construire des fonctions invariantes dans les degrés Turing, on arrive toujours à une invariance uniforme. Cette constatation a conduit Steel à faire la conjecture suivante :

**Conjecture 2.3 (Steel [217])**. Si une fonction borélienne est invariante dans les degrés Turing, alors elle est uniformément invariante. ★

Si la conjecture de Steel est vraie, cela montrera alors la conjecture de Martin.

## 3. Problèmes de masse

Face au problème de Post, nous avons vu une première réponse négative, à savoir que sous des hypothèses de naturalité, il n'existe pas de degrés c. e. non calculables intermédiaires. Il existe une autre approche, complémentaire de la première, qui consiste à dire que si les itérations du saut Turing sont les seuls degrés naturels, c'est à cause de la nature trop restrictive d'un degré Turing : il existe des puissances calculatoires qui ne correspondent pas à des degrés Turing pris individuellement, mais à des classes de degrés.

Considérons par exemple les complétions de l'arithmétique de Peano. Nous avons vu avec le théorème 9-3.10 une preuve que toute théorie complète et cohérente qui étend l'arithmétique de Peano est incalculable, mais nous ne l'avons pas fait en montrant que le problème de l'arrêt pouvait se réduire à une telle théorie, et pour cause ce n'est pas toujours le cas : il existe des degrés PA $\Delta_2^0$ ne calculant pas le problème de l'arrêt. Ce n'est pas incompatible avec la conjecture de Martin, dans le sens où si l'on cherche à définir une extension naturelle bien spécifique de l'arithmétique de Peano qui soit complète et cohérente, on en trouvera une qui calcule le problème de l'arrêt ou plus. C'est le cas par exemple de l'ensemble des formules vraies dans $\mathbb{N}$.

Les degrés PA forment une puissance calculatoire *naturelle* en tant que classe : pour tout arbre binaire infini calculable, il existe une procédure qui prend une complétion de l'arithmétique de Peano en entrée, et calcule un chemin de l'arbre en retour. On sort ici de la naturalité des degrés, pour considérer à la place la naturalité des classes de degrés. Comme nous l'avons vu dans ce livre, il existe une grande variété de classes de degrés toutes définies de manière très naturelle, et qui ne correspondent pas à des itérations de l'arrêt : les degrés high, hyperimmunes, PA, ... La notion de
classe de degrés est en général abordée via le principe des *problèmes de masse*. Ces derniers remontent à Kolmogorov [119], qui en parle informellement comme d'une formalisation des principes de logique intuitionniste de Brouwer, avant d'être définis de manière rigoureuse par Medvedev [154] et Muchnik [165].

**Définition 3.1.** Un problème de masse $\mathcal{P} \subseteq 2^\mathbb{N}$ est vu comme l'ensemble de ses solutions possibles, identifiées, via un codage approprié, à des éléments de $2^\mathbb{N}$. $\diamond$

Un problème sera par exemple résoluble s'il contient un élément calculable. Les problèmes sont étudiés en particulier via les rapports de force qu'ils entretiennent les uns par rapport aux autres. Muchnik propose l'approche suivante.

**Définition 3.2 (Réduction de Muchnik).** Un problème de masse $\mathcal{P}$ se réduit au sens de Muchnik à un problème de masse $\mathcal{Q}$, auquel cas on note $\mathcal{P} \leq_w \mathcal{Q}$, si toute solution de $\mathcal{Q}$ permet de calculer une solution de $\mathcal{P}$. $\diamond$

Par exemple, n'importe quelle classe $\Pi_1^0$ non vide se réduit au sens de Muchnik au problème constitué des extensions complètes et cohérentes de PA. Medvedev propose lui une définition plus restrictive en demandant l'uniformité.

**Définition 3.3 (Réduction de Medvedev).** Un problème de masse $\mathcal{P}$ de réduit au sens de Medvedev à un problème de masse $\mathcal{Q}$, auquel cas on note $\mathcal{P} \leq_s \mathcal{Q}$, s'il existe une fonctionnelle $\Phi$ telle que $\Phi(X) \in \mathcal{P}$ pour tout $X \in \mathcal{Q}$. $\diamond$

Toute classe $\Pi_1^0$ non vide se réduit également au sens de Medvedev à la classe des ensembles PA. Les deux notions ne coïncident cependant pas dans le cas général. Jockusch [105] a par exemple montré que la classe des fonctions DNC$_2$ se réduisait au sens de Muchnik à celle des fonctions DNC$_3$, mais pas au sens de Medvedev.

Les classes d'équivalence des relations $\equiv_w$ et $\equiv_s$ (dont les définitions découlent de $\leq_w$ et $\leq_s$) sont respectivement les degrés Muchnik et degrés Medvedev, dont la structure a été très étudiée. Il existe un plongement naturel des degrés Turing vers les degrés Muchnik et Medvedev, en associant à un degré Turing $\deg_T(X)$ le degré Muchnik ou Medvedev du problème $\{X\}$. Ce plongement respecte la structure de demi-treillis. On peut donc considérer les degrés Muchnik et Medvedev comme une extension des degrés Turing. En particulier, on peut définir $\mathbf{0}_w$ et $\mathbf{0}'_w$, les degrés Muchnik respectifs de $\{\emptyset\}$ et $\{\emptyset'\}$. La proposition suivante est donc d'une certaine manière liée à la question originale de Post.
**Proposition 3.4.** Soit PA le degré Muchnik des degrés PA. Alors,

$$0_w <_w PA <_w 0'_w.$$

*

Cette généralisation des degrés Turing a un coût : les degrés Muchnik et Medvedev sont bien plus nombreux. Plus précisément, les degrés Turing ont la puissance du continu ($|2^N|$), tandis que les degrés Muchnik et Medvedev ont pour cardinalité $|2^{2^N}|$ et possèdent des anti-chaînes de cette taille.
<figure><img src="image_87.png" /></figure>
Chapitre 13

Méthode de priorité et
degrés c. e.

Parmi les ensembles non calculables, les ensembles calculatoirement énumérables jouent un rôle particulièrement important. Ces ensembles sont << presque calculables >> au sens où si un entier $n$ appartient à un ensemble c. e. A, alors cette information sera connue en un temps fini. La classe des ensembles calculatoirement énumérables est assez naturelle, pour plusieurs raisons.

Tout d'abord, les ensembles c. e. possèdent plusieurs caractérisations très différentes, ce qui en fait une classe relativement *robuste*. Par définition, un ensemble est c. e. s'il est le domaine d'une fonction partielle calculable. Les ensembles c. e. non vides sont également précisément ceux qui sont l'image d'une fonction totale calculable, la fonction pouvant être injective si l'ensemble est infini (voir la proposition 3-7.2). De manière équivalente, un ensemble est c. e. si, et seulement si, il est réductible au problème de l'arrêt par une réduction many-one, ou encore s'il est $\Sigma_1^0$.

Les ensembles calculatoirement énumérables forment une *classe syntaxique* contrairement aux ensembles calculables. En effet, les ensembles c. e. sont précisément les ensembles $\Sigma_1^0$, tandis que les ensembles calculables sont les ensembles définissables à la fois par un prédicat $\Sigma_1^0$ et $\Pi_1^0$. Cette nature syntaxique donne aux ensembles c. e. de meilleures propriétés d'uniformité. Ainsi, la classe des ensembles calculatoirement énumérables est uniformément c. e., car il suffit de lister toutes les fonctions partielles calculables, ou de manière équivalente toutes les formules $\Sigma_1^0$. Les ensembles calculables ne peuvent en revanche pas être listés de manière calculable (d'après le théorème 7-6.2, les degrés high sont exactement ceux permettant de lister les ensembles calculables).
Enfin, et c'est peut-être un des arguments les plus importants en faveur de la naturalité des ensembles c. e., un certain nombre de problèmes non décidables en mathématiques se trouvent être calculatoirement énumérables. Parmi eux, on citera bien sûr le problème de l'arrêt, mais également l'ensemble des théorèmes de l'arithmétique (voir le théorème 9-3.7), ou même l'ensemble des solutions d'équations diophantiennes (voir, à cet effet, le théorème 12-1.2).

# 1. Degrés c. e.

Être calculatoirement énumérable est une propriété d'ensemble et non de degré Turing. En effet, nous avons vu que les degrés Turing sont clos par complémentaire, or par la proposition 3-7.4, si un ensemble et son complémentaire sont c. e., alors ils sont calculables. En particulier, le problème de l'arrêt $\emptyset'$ est c. e., mais est Turing-équivalent à son complémentaire, qui lui ne l'est pas. Nous avons cependant défini une notion de degré c. e. au début de la section 7-3, définition que nous répétons ci-après.

**Définition 1.1.** Un degré Turing est c. e. s'il contient un ensemble calculatoirement énumérable. ◇

Nous avons vu que les degrés Turing n'étaient pas bornés, car pour tout degré $d$, son saut Turing $d'$ est strictement au-dessus. Les degrés c. e., en revanche, sont bornés par $0'$.

**Proposition 1.2.** Les degrés c. e. ont pour degré maximum $0'$. ★

PREUVE. Par le théorème de Post (voir la proposition 5-4.3), un ensemble est c. e. si, et seulement si, il est many-one réductible à $\emptyset'$. Les réductions many-one étant des cas particuliers de réductions Turing, tout degré c. e. est Turing-réductible à $\emptyset'$. ■

Les degrés c. e. formant un sous-ensemble des degrés Turing, aussi les questions concernant les degrés Turing se formulent-elles pour les degrés calculatoirement énumérables. Sont-ils linéairement ordonnés ? Forment-ils un ordre bien fondé ? Et, avant tout cela, existe-t-il des degrés c. e. autres que $0$, le degré Turing des ensembles calculables, et $0'$, le degré Turing du problème de l'arrêt ?

Les degrés c. e. sont notoirement difficiles à manipuler, en raison de la contrainte de calculabilité de leur énumération. La méthode des extensions finies n'est plus adaptée, et il faudra faire appel à des techniques très élaborées pour prouver des résultats similaires à ceux obtenus dans les degrés Turing.
## 2. Méthode de permission

La méthode de permission permet de calculer un ensemble c. e. $A$ à partir d'un autre ensemble c. e. $B$. Elle se base sur la notion de fonction de calcul vue à la section 4-7. Rappelons qu'étant donné une approximation c. e. $(A_s)_{s \in \mathbb{N}}$ d'un ensemble c. e. $A$ (ou plus généralement pour toute approximation $\Delta_2^0$), la fonction de calcul associée à cette approximation est la fonction $c_A : \mathbb{N} \to \mathbb{N}$ qui à $n$ associe le plus petit temps $s$ tel que $A_s \upharpoonright_n A \upharpoonright_n$. En particulier, cette fonction est calculable en $A$. De plus, par la proposition 4-7.9, toute fonction dominant $c_A$ recalcule $A$.

**Proposition 2.1 (Méthode de permission).** Soient $A$ et $B$ des ensembles c. e. d'approximations c. e. respectives $(A_s)_{s \in \mathbb{N}}$ et $(B_s)_{s \in \mathbb{N}}$. S'il existe une fonction $B$-calculable $f : \mathbb{N} \to \mathbb{N}$ telle que pour tout $n, s \in \mathbb{N}$

$$A_{s+1} \upharpoonright_n \mathcal{A}_s \upharpoonright_n \Rightarrow B_{s+1} \upharpoonright_{f(n)} \neq B_s \upharpoonright_{f(n)},$$

alors $A \leq_T B$.

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

**PREUVE.** Pour tout $n, c_A(n) \leq c_B(f(n))$, or $c_B \oplus f \leq_T B$, donc $B$ calcule une fonction dominant $c_A$. Par la proposition 4-7.9, $B$ calcule $A$. ■

La plupart du temps, la fonction $f$ sera calculable et croissante, voire la fonction identité. Informellement, l'approximation de $A$ n'est autorisée à ajouter un élément à $A$ que si au même moment, $B$ ajoute un élément plus petit que $f(x)$. Autrement dit, l'ensemble $A$ attend la permission de $B$ pour ajouter des éléments, ce qui donne son nom à cette méthode. La méthode de permission se combine souvent avec d'autres techniques comme la méthode de priorité que nous verrons dans la section suivante. La méthode de permission ne perd pas en généralité, au sens où l'on peut prouver la réciproque suivante dans le cas où l'ensemble $B$ est infini.

**Proposition 2.2.** Soient $A$ et $B$ des ensembles c. e. tels que $A \leq_T B$ et $B$ est infini. Alors, il existe des approximations c. e. $(A_s)_{s \in \mathbb{N}}$ et $(B_s)_{s \in \mathbb{N}}$ et une fonction $B$-calculable $f : \mathbb{N} \to \mathbb{N}$ telle que pour tout $n, s \in \mathbb{N}$

$$A_{s+1} \upharpoonright_n \mathcal{A}_s \upharpoonright_n \Rightarrow B_{s+1} \upharpoonright_{f(n)} \neq B_s \upharpoonright_{f(n)}.$$

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

**PREUVE.** Soient $(A_s)_{s \in \mathbb{N}}$ et $(B_s)_{s \in \mathbb{N}}$ des approximations c. e. de respectivement $A$ et $B$. Sachant que $B$ est infini, en accélérant son approximation c. e., on peut supposer sans perte de généralité que $B_{s+1} \neq B_s$ pour tout $s$. Soit $f : \mathbb{N} \to \mathbb{N}$ la fonction qui à $n$ associe le plus petit entier $m$ tel que $B_{s+1} \upharpoonright_m \neq B_s \upharpoonright_m$ pour tout $s \leq c_A(n)$. La fonction $f$ est $c_A \oplus B$-calculable, or $c_A \leq_T A \leq_T B$, donc $f \leq_T B$. Pour tout $n, s \in \mathbb{N}$, si $A_{s+1} \upharpoonright_n \mathcal{A}_s \upharpoonright_n$, alors $c_A(n) \geq s + 1$, donc $B_{s+1} \upharpoonright_{f(n)} \neq B_s \upharpoonright_{f(n)}$. ■
### 3. Méthode de priorité $\Sigma_1^0$ (à blessure finie)

Post posa la question en 1944 [181] de savoir s'il existait des ensembles calculatoirement énumérables qui sont à la fois non calculables et Turing incomplets, c'est-à-dire qui ne permettent pas en tant qu'oracle de calculer le problème de l'arrêt. La question est restée ouverte pendant plus d'une décennie, avant d'être résolue par l'affirmative indépendamment par Muchnik [163] et Friedberg [63], qui ont introduit la fameuse méthode de priorité. Cette technique trouvera par la suite de très nombreuses applications pour l'étude des ensembles c. e. et $\Delta_2^0$, qui s'avèrent avoir une structure très riche, comme en témoigne le théorème de densité de Sacks : soient $X, Y$ des ensembles c. e. tels que $X <_T Y$ ; il existe alors un ensemble c. e. $Z$ tel que $X <_T Z <_T Y$.

De manière générale, la méthode de priorité sert le même but que la méthode des extensions finies (voir la section 4-8), c'est-à-dire construire des ensembles satisfaisant des propriétés de force et de faiblesse, mais cette fois-ci en contrôlant la complexité de ces ensembles dans la hiérarchie arithmétique. Cette contrainte supplémentaire est à l'origine d'une explosion de la complexité des constructions. En effet, comme dans la méthode des extensions finies, il s'agit de satisfaire une infinité de contrats simultanément, mais tandis que pour la méthode des extensions finies, la construction est omnisciente, l'argument de méthode de priorité doit s'effectuer avec une puissance calculatoire limitée. Il est donc nécessaire de poursuivre la construction de l'ensemble sans avoir une pleine connaissance de la situation. La construction se fait donc par essais-erreurs, avec des rétropédalages lorsque l'on s'aperçoit d'une erreur. Les stratégies pour satisfaire les contrats entrent en conflit, et toute la difficulté de la construction consiste à s'assurer que ces conflits et rétropédalages n'empêchent pas l'objectif global : construire un ensemble satisfaisant tous les contrats.

Nous commençons ici simplement par la plus facile des utilisations de la méthode de priorité, qui fut la première à être introduite, permettant de résoudre le problème de Post. Il s'agit d'une méthode de priorité à blessure finie, c'est-à-dire que chaque stratégie pour satisfaire un contrat ne devra rétropédaler qu'un nombre fini de fois avant de pouvoir réaliser son objectif.

**Théorème 3.1 (Friedberg (1957), Muchnik (1956))**

*Il existe des ensembles c. e. incomparables pour la réduction Turing.*

L'énoncé du théorème de Friedberg et Muchnick est similaire au théorème de Kleene et Post (voir la proposition 4-8.1), mais impose la contrainte supplémentaire aux ensembles d'être calculatoirement énumérables.
PREUVE. Comme pour le théorème de Kleene et Post (voir la proposition 4-8.1), nous allons construire deux ensembles, A et B, satisfaisant chacun une propriété de force et une propriété de faiblesse. Ces propriétés se déclinent chacune sous la forme de deux suites de contrats : ($\mathcal{R}_e$)$_{e \in \mathbb{N}}$ et ($\mathcal{S}_e$)$_{e \in \mathbb{N}}$ :
$$ \mathcal{R}_e : W_e^A \neq B \qquad \mathcal{S}_e : W_e^B \neq A. $$

Rappelons le sens de la notation $W_e^A$, qui désigne l'ensemble c. e. relativement à A de code $e$ (c'est-à-dire l'ensemble $\{n \in \mathbb{N} : \Phi_e(A, n) \downarrow\}$). Les contrats ($\mathcal{R}_e$)$_{e \in \mathbb{N}}$ assurent que $A \not\supsetneq_T B$, car le complémentaire de B n'est pas c. e. en A. Symétriquement, si les contrats ($\mathcal{S}_e$)$_{e \in \mathbb{N}}$ sont simultanément satisfaits, alors $B \not\supsetneq_T A$.

**Remarque**

Les ensembles A et B étant c. e., il est équivalent de dire qu'ils ne sont pas calculables, ou que leur complémentaire n'est pas c. e. Ainsi, les contrats ($\mathcal{R}_e$)$_{e \in \mathbb{N}}$ et ($\mathcal{S}_e$)$_{e \in \mathbb{N}}$ sont sans perte de généralité. Cette formulation des contrats simplifie les notations.

Les ensembles A et B devant être c. e., nous allons énumérer des éléments dans A et dans B au cours d'un processus calculable. Plus formellement, nous allons définir deux suites uniformément calculables d'ensembles finis $A_0 \subseteq A_1 \subseteq \dots$ et $B_0 \subseteq B_1 \subseteq \dots$ en commençant par $A_0 = B_0 = \emptyset$. Pour des raisons de présentation, nous omettrons l'indice $s$ et parlerons de A et B comme des ensembles en cours de construction et évoluant au cours du temps. Nous utiliserons les indices lorsqu'il sera nécessaire de distinguer les ensembles à différentes étapes de temps. Pour chaque contrat $\mathcal{R}_e$ ou $\mathcal{S}_e$, nous allons décrire un processus responsable de sa satisfaction. Les différents processus s'exécuteront en parallèle. Un processus responsable de la satisfaction d'un contrat $\mathcal{R}_e$ (resp. $\mathcal{S}_e$) est appelé **stratégie pour $\mathcal{R}_e$** (resp. $\mathcal{S}_e$). Dans cette construction, une seule stratégie sera nécessaire par contrat. Nous verrons plus tard des arguments de priorité qui associeront plusieurs stratégies à chaque contrat.

**Satisfaction d'un contrat** $\mathcal{R}_e$. Voici une stratégie pour construire deux ensembles c. e. A et B satisfaisant un unique contrat $\mathcal{R}_e$. Pour gagner en généralité et préparer la satisfaction de plusieurs contrats, nous allons également supposer que d'autres processus ou stratégies tournent en parallèle, et ajoutent des éléments à A et B au cours du temps. À chaque instant $t$, la stratégie pour $\mathcal{R}_e$ se retrouve dans l'un des trois états suivants :

<figure><img src="image_90.png" /></figure>
État i. C'est l'état initial du processus. Pour sortir de cet état, le processus passe par une phase d'initialisation qui consiste à choisir un entier $x_{\mathcal{R}_e} \notin B$ unique. Ce nombre existe, car, à tout instant, les ensembles $A$ et $B$ ont un nombre fini d'éléments. Une fois $x_{\mathcal{R}_e}$ choisi, notre processus pose une restreinte sur $x_{\mathcal{R}_e}$, c'est-à-dire qu'il interdit aux autres processus tournant en parallèle d'ajouter $x_{\mathcal{R}_e}$ dans $B$. Seul notre processus est décisionnaire de l'ajout de $x_{\mathcal{R}_e}$. Notons qu'une fois que $x_{\mathcal{R}_e}$ est ajouté à $B$, il ne pourra plus en ressortir, car l'ensemble $B$ est c. e. Une fois la restreinte posée, le processus entre dans l'état **e**, dit d'exécution.

État **e**. Pendant cette phase, le processus exécute $\Phi_e^A(x_{\mathcal{R}_e})$ jusqu'à ce que l'exécution se termine. Si celle-ci ne se termine pas, le processus reste dans cet état. Notons qu'au cours de cette phase, l'ensemble $A$ peut évoluer, car d'autres processus peuvent ajouter des éléments à $A$ en parallèle. Le processus doit prendre en compte cette évolution, et calcule donc $\Phi_e^{A_t}(x_{\mathcal{R}_e})[t]$ à l'instant $t$. Si $\Phi_e^{A_t}(x_{\mathcal{R}_e}) \downarrow$ à un instant $t$, alors le processus pose une restreinte sur l'usage de ce calcul, c'est-à-dire sur les bits de l'oracle $A_t$ ayant servi à cette exécution, empêchant ainsi les autres processus d'y effectuer une modification. On s'assure donc que $\Phi_e^A(x_{\mathcal{R}_e}) \downarrow$, autrement dit que $x_{\mathcal{R}_e} \in W_e^A$. Le processus ajoute alors $x_{\mathcal{R}_e}$ à $B$, de telle sorte que $W_e^A \neq \bar{B}$, et se retrouve dans l'état **t**.

État **t**. Dans cet état, le processus a terminé son exécution. Il ne sort pas de cet état.

**Issues.** Étudions les différentes issues de la stratégie pour $\mathcal{R}_e$. Le processus passe toujours de l'état **i** à l'état **e**, mais peut ne jamais arriver dans l'état **t**. Nous avons donc deux issues possibles. Issue **p** : il reste bloqué dans l'état d'exécution (état **e**). Dans ce cas, $\Phi_e^A(x_{\mathcal{R}_e}) \uparrow$ et $x_{\mathcal{R}_e} \notin B$, donc $W_e^A \neq \bar{B}$. On dit que le contrat $\mathcal{R}_e$ est satisfait passivement. Issue **a** : il entre dans l'état **t** de terminaison. Alors, par ses actions de restreintes et l'ajout de $x_{\mathcal{R}_e}$ dans $B$, il s'assure que le contrat $\mathcal{R}_e$ est satisfait par la seconde clause de la disjonction. On dit alors que le contrat $\mathcal{R}_e$ est satisfait activement. Dans les deux cas, le contrat $\mathcal{R}_e$ est satisfait.

État versus issue d'une stratégie

Il convient de bien distinguer l'état d'une stratégie, et son issue. L'état d'une stratégie dépend de chaque étape, et est une information connue à cette étape. L'issue de la stratégie est un comportement limite qui n'est pas connu en temps fini. Nous n'avons vu que des issues de la forme « La stratégie restera dans tel état au bout d'un moment », mais nous verrons d'autres issues dans la méthode de priorité à blessure infinie, comme « La stratégie passera successivement par tous ses états. »
**Conflits.** Des complications se posent lorsque l'on veut satisfaire plusieurs contrats simultanément. En effet, la stratégie d'un contrat pose des restreintes sur des bouts finis de A et B au cours du temps, ce qui peut entrer en conflit avec les besoins des autres stratégies. Nous allons donc analyser dans quelle mesure les stratégies peuvent entrer en conflit, que cela soit entre stratégies pour contrats de même type (par exemple $R_a$ et $R_b$), ou entre stratégies pour contrats de type différent (par exemple $R_a$ et $S_b$).

**Satisfaction de tous les contrats** ($R_e)_{e \in \mathbb{N}$}. De manière générale, dans les arguments de priorité, les stratégies pour les contrats de même nature sont relativement faciles à satisfaire simultanément. Les seuls conflits possibles entre deux contrats $R_e$ et $R_d$ surviendraient si les deux stratégies avaient choisi le même entier $x$ (autrement dit, $x_{R_e} = x_{R_d}$) lors de leur passage de l'état **i** à l'état **e**, et l'un des deux, disons $R_e$, voit son calcul $\Phi_e^A(x)$ se terminer et cherche à ajouter $x$ dans B pour passer à l'état **t** de terminaison, tandis que $R_d$ est encore dans l'état **e** d'exécution. Pour éviter ces conflits, il suffit d'associer dans l'état **i** un entier $x$ différent pour chaque contrat $R_e$. Cela est possible, car, B étant fini au cours de la construction, il existe une infinité d'entiers hors de B.

**Satisfaction d'un contrat** $R_e$ et $S_d$. Supposons maintenant que l'on veuille satisfaire deux contrats de nature opposée. Par défaut, le contrat $S_d$ jouant un rôle symétrique, la stratégie pour le satisfaire s'obtient à partir de celle pour $R_e$ en substituant A à B et inversement.

▷ État **i**. Choisir un entier $x_{S_d} \notin A$, et poser une restreinte sur $x_{S_d}$.

▷ État **e**. Exécuter $\Phi_d^B(x_{S_d})$. Si l'exécution s'arrête à l'instant $t$, restreindre l'usage de $\Phi_d^{B_t}(x_{S_d})$ et ajouter $x_{S_d}$ à A, puis passer dans l'état $t$.

▷ État **t**. Le processus est terminé.

Un nouveau conflit peut se poser entre la stratégie pour $R_e$ et celle pour $S_d$. Dans l'état **e**, la stratégie pour $R_e$ peut voir l'exécution de $\Phi_e^A(x)$ s'arrêter avec un usage de $s$ bits d'oracle, pour $s > x_{S_d}$. Il impose alors une restreinte sur $A_t \upharpoonright_s$, interdisant aux autres processus de modifier ces valeurs. Si, plus tard, la stratégie pour $S_d$ voit son exécution de $\Phi_d^B(x_{S_d})$ se terminer, elle ne pourra pas ajouter $x_{S_d}$ à A à cause de la restreinte précédente. La stratégie pour $S_d$ est blessée et va devoir revenir dans son état **i**, choisir un nouvel entier $x_{S_d}$ suffisamment grand pour ne pas être restreint, et recommencer la procédure. La stratégie pour $R_e$ étant à l'état $t$ de terminaison, elle n'agira plus, et ne posera donc plus de nouvelle restreinte risquant de blesser la stratégie pour $S_d$.

De manière générale, on peut satisfaire un nombre fini de contrats $R_e$ et $S_d$ simultanément avec la même méthode. Dès lors qu'une stratégie pose