libre d'ensemble, et avec les même variables libres d'entiers que $F$ plus une variable libre d'entier $\sigma$, telle que pour tout ensemble $G \subseteq M$,

$$ M \cup \{G\} \models F(G) \iff \exists k H(G \upharpoonright_k). \quad \diamond $$

Venons-en à la preuve du théorème 6.15. Soit $M = (M, S^M)$ un modèle dénombrable de RCA$_0$, et soit $T \in S^M$ un arbre binaire $M$-infini (voir la section 5.2). Nous allons construire un chemin $M$-infini $G \in [T]$ par un forcing $\mathbb{P}$ sur les sous-arbres $M$-finis de $T$ dans $S^M$. Commençons par montrer que tout filtre $\mathcal{F}$ suffisamment générique pour $\mathbb{P}$ induit un unique chemin $G \in \bigcap_{T \in \mathcal{F}} [T]$.

**Lemme 6.17.** Pour tout entier $n \in M$, l'ensemble $D_n$ des arbres $S \in \mathbb{P}$ ne contenant qu'une chaîne de longueur $n$ est dense dans $\mathbb{P}$.

**PREUVE.** Soit $T \in \mathbb{P}$ un arbre binaire $M$-infini.

Pour tout $\sigma \in 2^n$, soit $S_\sigma = \{\tau \in T : \sigma \preceq \tau \vee \sigma \succ \tau\}$. Montrons qu'il existe $\sigma \in 2^n$ tel que $S_\sigma$ est $M$-infini.

En effet, si tous les ensembles $S_\sigma$ sont $M$-finis, on a :

$$ \forall \sigma \in 2^n \exists m \forall \tau \in 2^m (\sigma \prec \tau \rightarrow \tau \notin T). $$

On utilise $B\Sigma_1^0$ (qui est une conséquence de RCA$_0$) pour obtenir :

$$ \exists m \forall \sigma \in 2^n \exists m' < m \forall \tau \in 2^{m'} (\sigma \prec \tau \rightarrow \tau \notin T). $$

Et, par clôture de $T$ par le bas, on obtient $\exists m \forall \tau \in 2^m \tau \notin T$, donc $T$ est $M$-fini, ce qui contredit notre hypothèse sur $T \in \mathbb{P}$.

Rappelons qu'une condition $T$ force une formule $F(G)$, formule supposée $\Sigma_1^0$ ou $\Pi_1^0$, si $M \models F(P)$ pour tout $P \in [T]$. Notre but est de << réduire >> l'induction $\Sigma_1^0$ de $M \cup \{G\}$ à celle de $M$ à l'aide de la relation de forcing. En effet, la relation de forcing pour les propriétés $\Sigma_1^0$ est $\Sigma_1^0$ sur $M$. Plus précisément, nous allons utiliser le principe $L\Pi_1^0$, équivalent à $I\Sigma_1^0$, qui affirme que tout sous-ensemble $\Pi_1^0$ non vide de $\mathcal{N}$ admet un élément minimum. Pour ce faire, supposons que $F(x, G)$ soit une formule $\Sigma_1^0$ telle que $T \Vdash \neg F(b, G)$ pour une condition $T \in \mathbb{P}$ dans notre filtre et un $b \in M$. Il s'ensuit que l'ensemble $\{a \in M : \neg F(a, G)\}$ sera non vide, où $G$ est l'ensemble générique construit. Pour que $F$ satisfasse le principe $L\Pi_1^0$, il faudra s'assurer qu'il existe un élément $b_1$ minimum dans $M$ tel que $\neg F(b_1, G)$ soit vrai. Une manière de s'en assurer consiste à trouver une extension $S \in \mathbb{P}$ telle que pour tout $a <^M b$, $S \Vdash F(a, G)$ ou $S \Vdash \neg F(a, G)$. En effet, l'ensemble $E = \{a \leq^M b : S \Vdash \neg F(a, G)\}$ est $\Pi_1^0$ non vide dans $M$ et doit donc satisfaire le principe $L\Pi_1^0$ dans le modèle de départ $M$. On en déduit donc
qu'il existe un $b_1$ minimum dans $\mathcal{M}$ tel que $S \Vdash \neg F(b_1, G)$, donc que $\text{LP}_1^0$ est satisfait pour $F$.

Étant donné une condition $T \in \mathbb{P}$ et une formule $\Sigma_1^0 F(G)$, il est aisé de trouver une extension $S$ forçant soit $F(G)$, soit $\neg F(G)$. L'approche naturelle pour préserver $\text{LP}_1^0$ consisterait à essayer de créer une suite décroissante d'extensions $T \supseteq T_1 \supseteq T_2 \supseteq T_3 \supseteq \dots \supseteq T_b$ telle que $T_{a+1} \Vdash F(a, G)$ ou $T_{a+1} \Vdash \neg F(a, G)$ pour tout $a <^M b$. Nous travaillons cependant dans un modèle dénombrable arbitraire de RCA$_0$, qui peut contenir des entiers $b$ non standard, et notamment tels que l'ensemble $\{a \in \mathcal{M} : a <^M b\}$ est infini. Le but du lemme suivant est de montrer que l'on arrive à forcer simultanément $F(a, G)$ ou $\neg F(a, G)$ pour tout $a <^M b$ avec une même condition de forcing, quand bien même l'ensemble $\{a \in \mathcal{M} : a <^M b\}$ serait infini.

**Lemme 6.18.** Pour tout $b \in \mathcal{M}$ et toute formule $\Sigma_1^0 F(x, G)$, l'ensemble $D_{b,F}$ des arbres $S \in \mathbb{P}$ tels que pour tout $a <^M b$, $S \Vdash F(a, G)$ ou $S \Vdash \neg F(a, G)$ est dense dans $\mathbb{P}$.

⋆

### PREUVE

Par l'exercice 6.16, $F(x, G) \equiv \exists z H(x, z, G \upharpoonright z)$ pour une formule $\Delta_0^0 H$. Pour tout $\sigma \in 2^{\leq b}$, définissons $S_\sigma \subseteq T$ inductivement comme suit : $S_\epsilon = S$. Supposons que $S_\sigma$ est défini. Alors, $S_{\sigma 0} = \{\rho \in S_\sigma : \forall z < |\rho| \neg H(a, z, \rho \upharpoonright z)\}$ et $S_{\sigma 1} = S_\sigma$. Soit $U = \{\sigma \in 2^b : S_\sigma \text{ est } \mathcal{M}\text{-infini}\}$.

Notons que $U$ est non vide, car $S_{111...1} = S$ est $\mathcal{M}$-infini. De plus, $U$ est $\Pi_1^0$ dans $\mathcal{M}$, car $S_\sigma$ est clos par préfixe pour tout $\sigma$ :

$$U = \{\sigma \in 2^b : \forall n \in \mathcal{M} \exists \tau \in 2^n \tau \in S_\sigma\}.$$

Par $\text{LP}_1^0$, $U$ contient un élément minimum $\sigma$ pour l'ordre lexicographique.

Montrons que $S_\sigma \in D_{b,F}$. Soit $a <^M b$.

▷ Si $\sigma(a) = 0$, on a alors $\forall \rho \in S_\sigma \forall z < |\rho| \neg H(a, z, \rho \upharpoonright z)$. Ainsi, pour tout $G \in [S_\sigma]$, on a $\forall z \neg H(a, z, G \upharpoonright z)$, autrement dit $\neg F(a, G)$. Donc, $S_\sigma \Vdash \neg F(a, G)$.

▷ Si $\sigma(a) = 1$, alors par minimalité de $\sigma$ dans $U$, la chaîne $\sigma \upharpoonright a$ $0111...1$ de longueur $b$ n'est pas dans $U$, donc $S_{\sigma \upharpoonright a 0}$ est $\mathcal{M}$-fini. Il s'ensuit qu'il existe un $k \in \mathcal{M}$ tel que pour toute chaîne $\rho \in 2^k$, si $\rho \in S_{\sigma \upharpoonright a}$ alors $\exists z < k H(a, z, \rho \upharpoonright z)$. Ainsi, pour tout $G \in [S_{\sigma \upharpoonright a}]$, il existe $z < k$ tel que $H(a, z, G \upharpoonright z)$, donc $S_{\sigma \upharpoonright a} \Vdash F(a, G)$, or $S_\sigma \subseteq S_{\sigma \upharpoonright a}$, de sorte que $S_\sigma \Vdash F(a, G)$. ■

Nous sommes maintenant prêts à assembler les pièces du puzzle pour prouver le théorème 6.15.
PREUVE DU THÉORÈME 6.15. Par la proposition 6.14, il suffit de montrer que pour tout modèle dénombrable $\mathcal{M} = (M, S^\mathcal{M})$ de RCA₀ et tout arbre binaire $\mathcal{M}$-infini $T \in \mathcal{M}$, il existe un ensemble $G \subseteq M$ tel que $G \in [T]$ et $\mathcal{M} \cup \{G\} \models \text{L}\Pi_1^0$. Fixons $\mathcal{M}$, et $T \in \mathcal{M}$. Soit $\mathbb{P}$ la collection des sous-arbres $\mathcal{M}$-infinis de $T$ dans $S^\mathcal{M}$, ordonnés par l'inclusion, et soit $\mathcal{F}$ un filtre suffisamment générique pour $\mathbb{P}$. Par le lemme 6.17, il existe un unique ensemble $G \subseteq M$ tel que $G \in \bigcap_{S \in \mathcal{F}} [S]$. En particulier, $T \in \mathcal{F}$, donc $G \in [T]$.

Montrons que $\mathcal{M} \cup \{G\} \models \text{L}\Pi_1^0$. Soit donc $F(x, G)$ une formule $\Sigma_1^0$ telle que $\mathcal{M} \cup \{G\} \models \neg F(b, G)$ pour un élément $b \in M$. Par le lemme 6.18, il existe une condition $S \in \mathcal{F}$ telle que pour tout $a \leq^\mathcal{M} b$, $S \Vdash F(a, G)$ ou $S \Vdash \neg F(a, G)$. On a ainsi

$$ \{a \leq^\mathcal{M} b : \mathcal{M} \cup \{G\} \Vdash F(a, G)\} = \{a \leq^\mathcal{M} b : S \Vdash F(a, G)\}, $$

et le second prédicat est $\Sigma_1^0$ dans $\mathcal{M}$. Comme $\neg F(b, G)$, alors $S \Vdash \neg F(b, G)$, donc par $\text{L}\Pi_1^0$ appliqué au prédicat $\Sigma_1^0$ $S \Vdash F(x, G)$ avec pour variable libre $x$, il existe un plus petit $a \leq^\mathcal{M} b$ tel que $S \Vdash \neg F(a, G)$. En particulier, $a$ est le plus petit élément tel que $\neg F(a, G)$ est satisfait. Cela termine la preuve du théorème 6.15. $\blacksquare$

### Corollaire 6.19

Le système $\text{WKL}_0$ est une extension conservative de $\Sigma_1$-PA.

PREUVE. Soit $F$ une formule close de $\mathcal{L}_{\text{PA}}$ telle que $\Sigma_1$-PA $\nvDash$ $F$. Par le théorème 6.10, RCA₀ $\nvDash$ $F$, et par le théorème 6.15, $\text{WKL}_0$ $\nvDash$ $F$. $\blacksquare$

# 7. Programme de Hilbert

Revenons aux motivations originelles des mathématiques à rebours. Comme nous l'avons mentionné dans le chapitre 9, les mathématiques ont connu une grande crise des fondements au début du XXᵉ siècle, avec le développement d'une théorie de l'infini par Cantor marquant une étape supplémentaire dans l'abstraction mathématique et son éloignement d'avec le réel. La difficulté, voire l'impossibilité, de raccrocher l'infini à une réalité sensible, ainsi que les paradoxes sur lesquels ont trébuché les mathématiciens ont naturellement suscité la méfiance. Ainsi la crise des fondements a-t-elle favorisé le développement de pensées finitistes. À cette époque, les avancées scientifiques tendaient à montrer la finitude du monde réel, à travers la découverte de l'atome (l'infiniment petit n'existerait donc pas) ou de la finitude de l'univers (l'infiniment grand non plus). Des mathématiciens influents comme Poincaré, Brouwer ou Kronecker ont alors prôné la restriction aux mathématiques finitaires.
## 7.1. Interprétation formelle du programme de Hilbert

David Hilbert proposa en 1900 un programme destiné à rétablir la confiance dans les fondements des mathématiques, dont l'objectif était de fonder les mathématiques dans toute leur généralité, sur des bases purement finitaires. Ce programme peut se décomposer en trois étapes :

(1) formaliser les mathématiques infinitaires $T_∞$;

(2) identifier le fragment finitaire $T_{fin}$ des mathématiques;

(3) montrer que tout énoncé, ou tout du moins tout énoncé dans une certaine classe $C$, prouvable dans $T_∞$ est prouvable dans $T_{fin}$.

Hilbert ayant laissé des points d'incertitude quant à la teneur formelle de son programme, Steve Simpson [202] en a proposé l'interprétation suivante.

**La théorie $T_∞$.** Simpson propose le choix de $Z_2$ comme théorie de référence pour les mathématiques infinitaires. Ce choix est justifié par les travaux de Hilbert et Bernays, *Grundlagen der Mathematik* (1934-1936), qui montrent que la grande majorité des mathématiques usuelles peut être formalisée dans l'arithmétique du second ordre.

**La théorie $T_{fin}$.** Une première idée serait de choisir $RCA_0$ comme fragment finitaire de référence. Toutefois, le schéma d'axiomes d'induction, même restreint aux formules $\Sigma_1^0$, constitue une hypothèse infinitaire. Elle est malheureusement nécessaire pour formaliser la notion de fonction calculable au sein de l'arithmétique. Un système plus élémentaire est cependant possible : celui dit d'arithmétique primitive récursive (PRA), lequel fait généralement consensus (voir Tait [220]). L'idée est la suivante, on restreint l'induction à son strict minimum, c'est-à-dire aux formules sans quantificateurs (le $I_{ouvert}$ défini dans la section 2.2). Afin de garder malgré tout quelques outils de travail, on rajoute des symboles de fonctions dans notre langage permettant de manipuler directement d'autres fonctions usuelles que l'addition et la multiplication, et en premier lieu la fonction exponentielle. On s'auto-risera en fait toutes les fonctions primitives récursives, telles que définies dans la section 6-1.

## 7.2. Quelques intuitions sur le système PRA

Rappelons ici la définition de la classe des fonctions primitives récursives que l'on dénote par $\mathcal{PR}$. Il s'agit de la plus petite classe de fonctions de $\mathbb{N}^n$ vers $\mathbb{N}$ pour $n \in \mathbb{N}$ quelconque, contenant les fonctions de base suivantes.

(a) La fonction successeur : $succ(x) = x + 1$.

(b) Les fonctions constantes : $c_m^n(x_1, \dots, x_n) = m$ pour tous $n, m \ge 0$.

(c) Les projections : $p_i^n(x_1, \dots, x_n) = x_i$ pour tout $n$ et tout $i \in 1, \dots, n$ et qui est close par les opérations suivantes :
▷ **composition** : si $g_1, \dots, g_m \in \mathcal{PR}$ sont des fonctions de $n$ variables et
que $h \in \mathcal{PR}$ soit une fonction de $m$ variables, alors la fonction

est dans $\mathcal{PR}$;
$$f(\bar{x}) = h(g_1(\bar{x}), \dots, g_m(\bar{x}))$$

▷ **récursion primitive** : si $g, h \in \mathcal{PR}$ sont des fonctions de respective-
ment $n$ et $n + 2$ variables, la fonction $f$ définie par $f(\bar{x}, 0) = g(\bar{x})$
et $f(\bar{x}, m + 1) = h(\bar{x}, m, f(m, \bar{x}))$ est une fonction de $n + 1$ variables
dans $\mathcal{PR}$.

Le lecteur peut se reporter à la section 6-1 pour une argumentation du fait que les fonctions primitives récursives sont calculables (et par définition totales) et à la section 6-3 pour une étude formelle de ces fonctions et enfin au théorème 4.6 pour une preuve que ces fonctions sont toutes prouvablement totales dans RCA₀. Il ne s'agit toutefois que d'une sous-classe stricte de la classe de toutes les fonctions calculables totales, et il est nécessaire de rajouter la clôture par le schéma de minimisation afin de les obtenir toutes.

Si la classe $\mathcal{PR}$ ne contient pas toutes les fonctions calculables, elle contient cependant un grand nombre de fonctions usuelles, comme l'addition, la multiplication, la fonction exponentielle, mais également des fonctions de codage et décodage, comme celle des paires d'entiers de Cantor. Elle forme donc une classe robuste de fonctions calculables avec de bonnes propriétés de clôture.

Le système PRA se place donc dans un langage contenant un symbole pour chaque fonction primitive récursive. Ses axiomes comportent le schéma d'induction $l_{ouvert}$, et de la même manière que les axiomes de Q régulent le comportement de l'addition et de la multiplications, ceux de PRA vont réguler chacune des fonctions primitives récursives.

Ainsi, si $f, h, g_1, \dots, g_m$ sont, à titre d'exemple, des symboles de fonctions
tels que $f$ doit être interprété par $\bar{x} \mapsto h(g_1(\bar{x}), \dots, g_m(\bar{x}))$, alors

sera un axiome.
$$\forall \bar{x} \ f(\bar{x}) = h(g_1(\bar{x}), \dots, g_m(\bar{x}))$$

Les résultats suivants, dont les preuves dépassent le cadre de cet ouvrage, montrent que le système PRA est suffisant pour montrer tous les énoncés $\Pi_2$ prouvables dans $WKL_0$.

**Théorème 7.1 (Friedman (voir Simpson [203]))**

Le système RCA₀ est une extension conservative de PRA pour les énon-
cés $\Pi_2$ de PA.

Notons que si l'on est tout à fait formel, le théorème ci-dessus n'entre pas
dans le cadre des énoncés de conservation, pour les deux raisons suivantes.
Tout d'abord, le langage de l'arithmétique du second ordre n'est pas une extension de celui de l'arithmétique primitive récursive. En effet, PRA comporte des symboles de fonction pour chaque fonction primitive récursive. Cependant, comme nous l'avons vu avec le théorème 4.6, toute fonction primitive récursive est définissable par une formule de l'arithmétique du premier ordre. On peut donc traduire toute formule de PRA en une formule de PA, et *a fortiori* en une formule de l'arithmétique du second ordre.

Ensuite, les énoncés $Π_2$ de l'arithmétique du premier ordre ne sont pas des énoncés de l'arithmétique primitive récursive : en effet, PA possède un symbole de fonction pour l'addition, un pour la multiplication, et un symbole de relation pour l'ordre. Cependant, ces deux opérations et la relation d'ordre sont primitives récursives, et il existe donc une traduction naturelle des énoncés de l'arithmétique vers le langage de PRA.

Il existe donc une double traduction des énoncés de PA vers PRA et réciproquement, de telle sorte que les formules obtenues par va-et-vient sont prouvablement équivalentes à la formule de départ. Le théorème 7.1 nous donne le corollaire suivant.

**Corollaire 7.2 (Friedman)**

Le système $WKL_0$ est une extension conservative de PRA pour les énoncés $Π_2$.

**PREUVE.** Supposons que $WKL_0 \vdash F$ pour $F$ un énoncé $Π_2$. En particulier, $F$ est $Π_1$, donc $RCA_0 \vdash F$ par le théorème 6.15. Il vient alors, par le théorème 7.1, PRA $\vdash F$. ■

La connexion entre PRA et $RCA_0$ va plus loin : les fonctions primitives récursives sont exactement les fonctions totales qui sont prouvablement calculables dans $RCA_0$.

**Théorème (1.4 Parikh, voir Hajek et Pudlak [81])**

Les fonctions $RCA_0$-prouvablement calculables sont exactement les fonctions primitives récursives.

Ce dernier résultat est à mettre en perspective avec l'assertion selon laquelle $RCA_0$ capture les mathématiques calculables. Du point de vue de la calculabilité, qui se préoccupe des modèles standard, il existe un $ω$-modèle minimal (pour l'inclusion) de $RCA_0$ qui contient exactement les ensembles calculables au second ordre. Ainsi, du point de vue sémantique, $RCA_0$ capture les mathématiques calculables. En revanche, du point de vue de $RCA_0$, les seuls prédicats que la théorie peut prouver comme étant $\Delta_1^0$ sont les prédicats primitifs récursifs, et ainsi $RCA_0$ ne peut prouver que l'existence
des ensembles primitifs récursifs. Cette différence vient du fait que la notion de $\Delta_1^0$ est relative à une théorie ou à un modèle, contrairement à la notion de $\Sigma_1^0$ qui est syntaxique et donc absolue.
<figure><img src="image_145.png" /></figure>
Chapitre 24

Réductions calculatoires

Comme mentionné dans la section 22-8.1, la plupart des théorèmes que nous étudierons dans cette partie s’expriment sous la forme

$$
\forall X(F(X) \rightarrow \exists Y G(X, Y)),
$$

où F et G sont des formules arithmétiques. On peut alors voir le théorème comme un problème mathématique, formulé en termes d'instances et de solutions. On dira qu'un ensemble X est une instance du problème si F(X) est vrai, et que Y est une solution de l'instance X si G(X, Y) est vrai.

**Exemple 1.** Le lemme de König est le problème dont les instances sont les arbres infinis à branchement fini, et pour lequel les solutions d'un arbre sont ses chemins infinis.

Ce genre de théorème porte sur l'existence d'objets du second ordre, et
l'écrasante majorité des séparations de la forme RCA₀ + T₁ ∖ T₂, où T₁, T₂
sont deux théorèmes de ce type, se fait en construisant un ω-modèle du
système RCA₀ + T₁ qui n'est pas un modèle de T₂. C'est ce que nous allons
étudier dans ce chapitre. Nous nous recentrons donc sur les ω-modèles afin
de nous concentrer sur la puissance calculatoire des théorèmes. Définissons
ce que nous entendons par problème en toute généralité.

**Définition 2.** Un **problème** est une relation $\mathbf{P} \subseteq 2^\mathbb{N} \times 2^\mathbb{N}$. Une **instance** de $\mathbf{P}$ est un élément de dom $\mathbf{P} = \{X \in 2^\mathbb{N} : \exists Y (X, Y) \in \mathbf{P}\}$. Étant donné une instance $X$ de $\mathbf{P}$, on notera $\mathbf{P}(X) = \{Y : (X, Y) \in \mathbf{P}\}$ la classe des **solutions** de $X$. ◇
Pour toute formule $\forall X(F(X) \rightarrow \exists Y G(X, Y))$ vraie, où F et G sont des formules arithmétiques, on peut associer le problème

$$P_{F,G} = \{(X, Y) \in 2^N \times 2^N : F(X) \land G(X, Y)\}.$$

On a alors $dom(P_{F,G}) = \{X \in 2^N : F(X)\}$ et pour tout $X \in dom(P_{F,G})$, la classe $P_{F,G}(X) = \{Y \in 2^N : G(X, Y)\}$. On appelle problème $\Pi_2^1$ un problème de cette forme, et on l'identifiera à sa formule correspondante.

**Exemple 3.** Le lemme de König est un problème $\Pi_2^1$. Voyons un autre exemple. Le théorème ADS — acronyme de « Ascending-Descending Sequence » — affirme pour tout ordre linéaire infini $R \subseteq \mathbb{N} \times \mathbb{N}$, l'existence d'une suite infinie strictement croissante, ou celle d'une suite infinie strictement décroissante. Ce théorème est donc le problème $\Pi_2^1$ ADS $\subseteq 2^N \times 2^N$ dont les instances sont les ordres infinis linéaires sur $\mathbb{N}$ et, pour chaque instance $R \in dom(ADS)$, les solutions ADS($R$) sont les suites infinies strictement croissantes ou strictement décroissantes d'éléments.

Nous allons étudier différentes notions de réductions entre les problèmes. Informellement, une réduction $P \le Q$ entre deux problèmes P et Q signifie que le problème Q est au moins aussi difficile à résoudre que P, au sens où si l'on disposait d'une boîte noire permettant de calculer des solutions des instances de Q, il serait possible de calculer des solutions des instances de P. Voyons tout de suite notre première réduction, qui découle directement des techniques de séparations usuelles de théorèmes dans RCA₀.

# 1. ω-réduction

L'implication dans RCA₀ induit une réduction purement calculatoire en se restreignant aux ω-structures. Considérons un problème $\Pi_2^1$ P, et sa formule correspondante $\forall X(F(X) \rightarrow \exists Y G(X, Y))$. Soit $M = (M, S, +, \times, <)$ une $L_{Z_2}$-structure. Alors, $M \models P$ si, et seulement si, pour tout $X \in S$ tel que $M \models F(X)$, il existe $Y \in S$ tel que $M \models G(X, Y)$. Rappelons qu'une ω-structure $M = (\omega, \mathcal{I}, +, \times, <)$ est un modèle de RCA₀ si $\mathcal{I}$ est un idéal Turing. Cela nous conduit à la définition suivante.

**Définition 1.1.** Un idéal Turing $\mathcal{I}$ satisfait un problème P (noté $\mathcal{I} \models P$) si pour toute instance X de P dans $\mathcal{I}$, il existe une solution de X dans $\mathcal{I}$. ◇

Notons que pour un problème $\Pi_2^1$ P, un idéal Turing $\mathcal{I}$ satisfait P si, et seulement si, l'ω-structure $M = (\omega, \mathcal{I}, +, \times, <)$ satisfait sa formule correspondante. La restriction aux ω-structures permet de définir une notion de satisfiability sur des problèmes arbitraires, au-delà des problèmes $\Pi_2^1$.
**Définition 1.2.** Un problème P est $\omega$-réductible à Q (noté $P \leq_{\omega} Q$) si tout idéal Turing qui satisfait Q satisfait aussi P. ◇

En particulier, si P et Q sont des problèmes $\Pi_2^1$, alors $P \leq_{\omega} Q$ si, et seulement si, tout $\omega$-modèle de $\mathrm{RCA}_0 + \mathrm{Q}$ est un $\omega$-modèle de P.

**Exemple 1.3.** Considérons les problèmes KL et J, où KL est le problème associé au lemme de König (distinct de WKL, le lemme faible de König), et où J est le problème du saut Turing, dont les instances sont les éléments de $2^N$, et dont l'unique solution de l'instance X est $X'$. Les idéaux Turing satisfaisant J sont par définition les idéaux de saut (voir la section 22-6.1), et caractérisent les $\omega$-modèles de $\mathrm{ACA}_0$.

Montrons que KL $\leq_{\omega}$ J. Soit $\mathcal{I} \models J$, et soit $T \in \mathcal{I}$ une instance de KL. Alors, T est un arbre calculatoirement borné relativement à $T'$. Par le corollaire 8-7.9 relativisé à $T'$, tout degré PA relativement à $T'$ calcule un chemin de T. En particulier, le double saut Turing de T calcule un chemin de T. Comme $\mathcal{I} \models J$ et $T \in \mathcal{I}$, alors $T' \in \mathcal{I}$, et donc $T'' \in \mathcal{I}$. Par clôture de $\mathcal{I}$ par réduction Turing, $\mathcal{I}$ contient un chemin de T. Ainsi, $\mathcal{I} \models KL$.

Montrons que $J \leq_{\omega} KL$. Soit $\mathcal{I} \models KL$, et soit $X \in \mathcal{I}$ une instance de J. Par la proposition 8-7.4, il existe un arbre X-calculable $T$ à branchement fini dont l'unique chemin est Turing équivalent à $X'$. Comme $\mathcal{I}$ est un idéal Turing, $T \in \mathcal{I}$. Comme $\mathcal{I} \models KL$, l'unique chemin de T appartient à $\mathcal{I}$, et comme $\mathcal{I}$ est un idéal Turing, $X' \in \mathcal{I}$. Donc, $\mathcal{I} \models J$.

Notons que dans l'exemple précédent, nous avons utilisé deux instances de J pour « résoudre » une instance de KL, tandis que dans le sens contraire, une seule instance de KL a suffi. Nous reviendrons sur ce point dans la section suivante.

**Exercice 1.4.** Rappelons que WKL et KL dénotent respectivement le lemme de König pour les arbres binaires infinis et les arbres infinis à branchement fini. Montrer que WKL $\leq_{\omega}$ KL, mais $KL \not\leq_{\omega}$ WKL. ◇

**1.1. Preuves de séparation**

Soient P et Q des problèmes $\Pi_2^1$. Comme déjà expliqué, si $\mathrm{RCA}_0 + \mathrm{Q} \vdash \mathrm{P}$, alors en particulier $P \leq_{\omega} Q^1$. Par contraposée, la réduction $\leq_{\omega}$ permet de séparer des théorèmes : si l'on arrive à montrer $P \not\leq_{\omega} Q$, alors $\mathrm{RCA}_0 + \mathrm{Q} \not\vdash \mathrm{P}$. La grande majorité des preuves de séparation en mathématiques à rebours sont de fait des preuves de séparation pour l'-$\omega$-réduction.

<footnote n="1">1. Il est à noter que l’on n’a pas nécessairement $P \leq_{\omega} Q$ implique $\mathrm{RCA}_0 \vdash Q \to P$.</footnote>
**Exemple 1.5.** La séparation de WKL₀ et ACA₀ de la proposition 22-7.3 s'est faite en montrant $J \not\leq_{\omega} WKL$.

Afin de prouver une séparation $P \not\leq_{\omega} Q$, il est nécessaire de créer un idéal Turing $\mathcal{I}$ tel que $\mathcal{I} \models Q$ mais $\mathcal{I} \not\models P$. Pour cela, on fixe en général une instance $X_P$ de P dont les solutions sont « calculatoirement compliquées », et qui en particulier ne sont pas $X_P$-calculables. La classe

$$ \mathcal{I}_0 = \{ Z \in 2^{\mathbb{N}} : Z \leq_T X_P \} $$

est un idéal Turing contenant l'instance $X_P$, mais aucune de ses solutions. Ainsi, $\mathcal{I}_0 \not\models P$. Il s'agit ensuite d'étendre $\mathcal{I}_0$ en un idéal Turing $\mathcal{I} \models Q$, tout en s'assurant que $\mathcal{I}$ ne possède pas de solution pour $X_P$.

La démarche consiste à fixer une instance $X_0$ de Q dans $\mathcal{I}_0$, à choisir une solution $Y_0$ « calculatoirement faible » — suffisamment pour que $X_P \oplus Y_0$ ne calcule aucune solution de $X_P$ — et à définir

$$ \mathcal{I}_1 = \{ Z \in 2^{\mathbb{N}} : Z \leq_T X_P \oplus Y_0 \}. $$

L'idéal Turing $\mathcal{I}_1$ a fait une étape de progression pour satisfaire Q, en ajoutant une solution de $X_0$, sans pour autant en ajouter une de $X_P$. En revanche, cette solution a aussi ajouté de nouvelles instances de Q dans $\mathcal{I}_1$, qu'il faudra également satisfaire. Il s'agit alors d'itérer intelligemment la construction, pour définir une suite croissante d'idéaux Turing $\mathcal{I}_0 \subseteq \mathcal{I}_1 \subseteq \mathcal{I}_2 \subseteq \dots$ de manière à prendre en compte toutes les instances de Q qui apparaissent dans $\mathcal{I}_n$ pour un certain $n$, tout en s'assurant d'éviter de rajouter des solutions de $X_P$. On obtient un idéal Turing $\mathcal{I} = \bigcup_n \mathcal{I}_n$ satisfaisant Q, sans pour autant satisfaire P.

La notion de solution « calculatoirement faible » correspondra à une propriété de faiblesse, telle que définie dans la section 4-8 sur la méthode des extensions finies :

**Définition 1.6.** Une propriété de faiblesse est une classe $W \subseteq 2^{\mathbb{N}}$ close par le bas pour la réduction Turing : si $X \in W$ et $Y \leq_T X$, alors $Y \in W$. ♦

En particulier, tout idéal Turing est une propriété de faiblesse. De nombreuses notions de calculabilité sont des propriétés de faiblesse sans toute-fois forcément former des idéaux Turing.

**Exemple 1.7.** Les classes suivantes sont des propriétés de faiblesse :

1. les ensembles de degré low;

2. les ensembles calculatoirement dominés;

3. pour tout $A$ non calculable, la classe $W = \{ Z \in 2^{\mathbb{N}} : A \not\leq_T Z \}$;

4. les ensembles arithmétiques.
Soit $\mathcal{W}$ une propriété de faiblesse non vide. Supposons que P possède une instance $X_P \in \mathcal{W}$ telle que $\mathcal{W}$ ne contient aucune solution de $X_P$. On va alors chercher à construire notre idéal $\mathcal{I} \subseteq \mathcal{W}$ avec $X_P \in \mathcal{I}$ et tel que $\mathcal{I} \models Q$. Au cours de la construction de notre idéal, on se retrouvera avec des instances de Q calculables relativement à des solutions d'instances précédemment considérées. Cela nous conduit à la définition suivante.

**Définition 1.8.** Soit $\mathcal{W}$ une propriété de faiblesse. Un problème Q pré-serve $\mathcal{W}$ si pour tout $Z \in \mathcal{W}$, toute instance $X \leq_T Z$ de Q admet une solution $Y$ telle que $Z \oplus Y \in \mathcal{W}$. ◇

Nous avons déjà vu un certain nombre de preuves de préservation en calculabilité.

**Exemple 1.9.** Le système WKL préserve la classe des ensembles low. Pour tout $Z$ de degré low, pour tout arbre $T \subseteq 2^{<\mathbb{N}}$ infini $Z$-calculable, par le théorème 8-4.3 relativisé à $Z$, il existe $P \in [T]$ tel que $Z \oplus P$ est low relativement à $Z$. Or, si $A$ est low, et si $B$ est low relativement à $A$, alors $B$ est low. En effet, $B' \leq_T A' \leq_T \emptyset'$. Il s'ensuit que $Z \oplus P$ est low. De la même manière, par le théorème 8-4.5, WKL préserve la classe des ensembles calculatoirement dominés.

La notion de préservation d'une propriété de faiblesse est un outil très puissant pour prouver des séparations pour l'ω-réduction.

**Lemme 1.10.** Supposons que Q préserve une propriété de faiblesse $\mathcal{W}$. Alors, pour tout $X \in \mathcal{W}$, il existe un idéal Turing $\mathcal{I} \subseteq \mathcal{W}$ contenant $X$ tel que $\mathcal{I} \models Q$. ★

**PREUVE.** Définissons une suite croissante d'ensembles $Z_0 \leq_T Z_1 \leq_T \dots$ telle que $Z_0 = X$, telle que pour tout $n \in \mathbb{N}$ on a $Z_n \in \mathcal{W}$, et telle que pour tout $n, e \in \mathbb{N}$, si $\Phi_e^{Z_n}$ est une Q-instance, alors $Z_{\langle n, e \rangle}$ calcule une solution de $\Phi_e^{Z_n}$.

Supposons que $Z_0, \dots, Z_n$ est défini. Soit $n+1 = \langle p, e \rangle$, avec $p, e \leq n$. Si $\Phi_e^{Z_p}$ n'est pas une instance de Q, alors $Z_{n+1} = Z_n$. Sinon, comme Q préserve $\mathcal{W}$ et $Z_n \in \mathcal{W}$, il existe une solution $\tilde{Y}$ de $\Phi_e^{Z_p}$ — car, en particulier, $\tilde{Y}$ est aussi calculable en $Z_n$ — telle que $Z_n \oplus \tilde{Y} \in \mathcal{W}$. Soit $Z_{n+1} = Z_n \oplus \tilde{Y}$.

Par l'exercice 22-5.11, $\mathcal{I} = \{Y \in 2^{<\mathbb{N}} : \exists n \ Y \leq_T Z_n\}$ est un idéal Turing. Comme $Z_0 = X$, alors $X \in \mathcal{I}$. Enfin, montrons que $\mathcal{I} \models Q$. Soit $\tilde{X}$ une instance de Q dans $\mathcal{I}$. Soit $n \in \mathbb{N}$ tel que $\tilde{X} \leq_T Z_n$, et soit $e \in \mathbb{N}$ tel que $\Phi_e^{Z_n} = \tilde{X}$. Alors, $Z_{\langle n, e \rangle}$ calcule une solution de $\tilde{X}$, $Z_{\langle n, e \rangle} \in \mathcal{I}$, et $\mathcal{I}$ contient donc une solution de $\tilde{X}$. ■
Le théorème suivant généralise de nombreuses constructions des mathématiques à rebours.

**Théorème 1.11**

Soit $\mathcal{W}$ une propriété de faiblesse. Supposons que $\mathcal{Q}$ préserve $\mathcal{W}$, contrairement à $\mathcal{P}$. Alors, $\mathcal{P} \not\leq_{\omega} \mathcal{Q}$.

**PREUVE.** Comme $\mathcal{P}$ ne préserve pas $\mathcal{W}$, il existe un élément $Z \in \mathcal{W}$ et une P-instance $X \leq_T Z$ telle que pour toute P-solution $Y$, $Z \oplus Y \notin \mathcal{W}$. Comme $\mathcal{Q}$ préserve $\mathcal{W}$, par le lemme 1.10, il existe un idéal Turing $\mathcal{I} \subseteq \mathcal{W}$ tel que $Z \in \mathcal{I}$ et $\mathcal{I} \models \mathcal{Q}$. Montrons que $\mathcal{I} \not\models \mathcal{P}$. En effet, par clôture de $\mathcal{I}$ par la réduction Turing, $X \in \mathcal{I}$. Soit $Y$ une P-solution de $X$. Alors, $Z \oplus Y \notin \mathcal{W}$, donc $Z \oplus Y \notin \mathcal{I}$; or, $Z \in \mathcal{I}$, donc par clôture de $\mathcal{I}$ par jointure, $Y \notin \mathcal{I}$. Ainsi, $\mathcal{I}$ est un idéal Turing satisfaisant $\mathcal{Q}$ mais non $\mathcal{P}$, et donc $\mathcal{P} \not\leq_{\omega} \mathcal{Q}$. ■

**Corollaire 1.12**

Soit $\mathcal{W}$ une propriété de faiblesse, et soient $\mathcal{P}$, $\mathcal{Q}$ des problèmes $\Pi_2^1$. Supposons que $\mathcal{Q}$ préserve $\mathcal{W}$, contrairement à $\mathcal{P}$. Alors, $\mathcal{RCA}_0 + \mathcal{Q} \not\models \mathcal{P}$.

**PREUVE.** Par le théorème 1.11, $\mathcal{P} \not\leq_{\omega} \mathcal{Q}$, donc il existe un $\omega$-modèle $\mathcal{M}$ de $\mathcal{RCA}_0 + \mathcal{P}$ qui n'est pas un modèle de $\mathcal{P}$, et donc $\mathcal{RCA}_0 + \mathcal{Q} \not\models \mathcal{P}$. ■

Par exemple, WKL préserve la classe des ensembles low, tandis que KL ne la préserve pas, donc KL $\not\leq_{\omega}$ WKL, et $\mathcal{RCA}_0 + \mathcal{WKL} \not\models KL$.

## 1.2. Préservation de cônes

Parmi les propriétés de faiblesse, on comptera plusieurs grandes familles récurrentes en mathématiques à rebours. La plus emblématique est celle de *préservation de cône*, qui exprime l'incapacité d'un problème de « co-der » un ensemble non calculable dans chacune de ses solutions.

**Définition 1.13.** Soit $k \in \mathbb{N}$. Un problème P préserve $k$ cônes (resp. $\omega$ cônes) si pour tout $Z \in 2^{\mathbb{N}}$, toute suite $(C_j)_{j<k}$ (resp. $(C_j)_{j \in \mathbb{N}}$) d'ensembles non $Z$-calculables, et pour toute instance $X \leq_T Z$ de P, il existe une solution $Y$ de $X$ telle $C_j$ n'est $Z \oplus X$-calculable pour aucun $j < k$ (resp. aucun $j \in \mathbb{N}$). ◇

Formulé dans le langage des préservations, pour tout $k \in \mathbb{N}$ et toute suite d'ensembles $\overline{C} = (C_j)_{j<k}$, on associe la propriété de faiblesse

$$W_{\overline{C}} = \{Z : \forall j < k \ C_j \not\leq_T Z\}.$$

Notons que $W_{\overline{C}} = \emptyset$ si l'un des ensembles $C_j$ est calculable, auquel cas tout problème préserve $W_{\overline{C}}$. En déroulant les définitions, P préserve $k$ cônes ssi P
préserve $W_{\overline{C}}$ pour toute suite d'ensembles $\overline{C} = (C_j)_{j<k}$. En particulier, par le théorème 1.11, si $Q$ préserve $k$ cônes, contrairement à $P$, alors $P \not\le_{\omega} Q$.

**Exemple 1.14.** Le système WKL préserve $\omega$ cônes, au vu du théorème 8-4.7. En revanche, KL ne préserve pas de cône, car il existe un arbre calculable à branchement fini dont tous les chemins calculent le problème de l'arrêt. Il s'ensuit par le théorème 1.11 que KL $\not\le_c$ WKL.

La notion de préservation de cône est notamment utilisée pour séparer des théorèmes de ACA₀. Nous en verrons un exemple non trivial avec le théorème de Ramsey pour les paires. Outre son utilisation pour les théorèmes de séparation, la notion fut étudiée pour elle-même, notamment par Downey, Greenberg, Harrison-Trainor, Patey et Turetsky [46], qui en ont trouvé plusieurs caractérisations équivalentes. Mentionnons en particulier le joli résultat suivant.

**Théorème 1.15 ([46]**

Un problème P préserve un cône si, et seulement si, il préserve $\omega$ cônes.

## 2. Réduction calculatoire

L'implication dans RCA₀ et l'ω-réduction sont grossières d'un point de vue calculatoire, car elles ne prennent pas en compte le nombre d'applications de chaque problème. Pour prouver RCA₀ ⊢ Q → P, on peut utiliser la prémisse Q autant de fois que l'on veut dans notre démonstration. De la même manière, pour prouver P $\leq_{\omega}$ Q, on est autorisé à faire usage d'un nombre arbitraire d'instances de Q pour résoudre P.

Dès lors que l'on suppose l'existence du saut Turing dans RCA₀, le système obtenu implique ACA₀, et implique l'existence de toutes les itérations finies du saut Turing. Dzhafarov [52] a introduit une notion de réduction plus fine, sensible au nombre d'applications de chaque problème.

**Définition 2.1.** Un problème P est calculatoirement réductible à Q (ce que l'on note P $\leq_c$ Q) si pour toute instance X de P, il existe une instance $\tilde{X}$ de Q calculable en X, telle que pour toute Q-solution $\tilde{Y}$ de $\tilde{X}$, l'ensemble $X \oplus \tilde{Y}$ calcule une P-solution de X. ◇

La réduction calculatoire est plus proche des notions de réduction étudiées en théorie de la complexité. Notons que la Q-solution $\tilde{Y}$ de $\tilde{X}$ a le droit de faire appel à l'instance X de P pour calculer une P-solution de X. La réduction calculatoire est un raffinement de l'ω-réduction.
**Exercice 2.2.** Montrer que si $P \leq_c Q$, alors $P \leq_{\omega} Q$.

◇

L'implication inverse n'est pas vraie en général. Intuitivement, la réduction calculatoire est une $\omega$-réduction qui n'autorise qu'une seule application du problème de droite. Elle permet par exemple de donner un cadre formel pour signifier qu'une seule application du problème J ne suffit pas pour prouver la réduction $KL \leq_{\omega} J$ dans l'exemple 1.3.

**Exercice 2.3.** Avec toujours KL et J les problèmes définis dans l'exemple 1.3. Montrer que $KL \not\leq_c J$.

◇

La réduction calculatoire est donc strictement plus fine que l'ω-réduction.

**Remarque**

La réduction RCA₀ $\vdash$ Q $\rightarrow$ P n'implique pas $P \leq_c Q$, car plusieurs instances de Q sont peut-être nécessaires dans la preuve. Il est à noter aussi que la réduction $P \leq_c Q$ n'implique pas non plus RCA₀ $\vdash$ Q $\rightarrow$ P, car les réductions Turing utilisées dans $P \leq_c Q$ ne sont pas nécessairement prouvablement totales à l'aide seule de l'induction $\Sigma_1^0$.

Cependant, beaucoup de preuves de RCA₀ $\vdash$ Q $\rightarrow$ P sont en réalité des preuves de $P \leq_c Q$ qui se formalisent dans RCA₀.

Comme nous l'avons vu, $P \leq_{\omega} Q$ n'implique pas en général $P \leq_c Q$. C'est cependant le cas lorsque $Q = \text{WKL}$. Ici, WKL est le problème dont les instances sont les arbres binaires infinis, et les solutions sont les chemins de ces arbres. La raison de cette implication provient du résultat suivant, dû à Scott.

**Proposition 2.4 (Scott [194]).** Soit P un degré PA. Il existe un idéal de Scott dont tous les éléments sont P-calculables.

★

**PREUVE.** Soit $T$ une fonctionnelle d'arbre telle que pour tout $X \in 2^N$, $T^X$ est un arbre binaire dont tous les chemins sont de degré PA relativement à $X$. Par exemple, $T^X = \{\sigma \in 2^{<N} : \forall e < |\sigma| \Phi_e^X(e)][\sigma]| \neq \sigma(e)\}$. Soit alors $C = \{\bigoplus_i X_i \in 2^N : \forall i X_{i+1} \in [T^{X_i}]\}$. Notons que $C$ est une classe $\Pi_1^0$ non vide. En particulier, $P$ calcule un membre $\bigoplus_i X_i$ de $C$. Notons que $X_{i+1}$ est de degré PA relativement à $X_i$, et en particulier $X_{i+1} \geq_T X_i$ (voir l'exercice 8-7.6).

Soit $\mathcal{I} = \{Z \in 2^N : \exists i Z \leq_T X_i\}$. Par l'exercice 22-5.11, $\mathcal{I}$ est un idéal Turing. De plus, pour tout $Z \in \mathcal{I}$, il existe $i$ tel que $Z \leq_T X_i$ ; or, $X_{i+1} \in \mathcal{I}$ est de degré PA relativement à $X_i$, donc à $Z$. Ainsi, $\mathcal{I}$ est un idéal de Scott. Enfin, tous les éléments de $\mathcal{I}$ sont P-calculables.

■

La proposition suivante est une conséquence directe du résultat de Scott.
**Proposition 2.5 (Hirschfeldt et Jocksuch [88]).** Soit P un problème. Si $P \leq_{\omega} \mathrm{WKL}$, alors $P \leq_{c} \mathrm{WKL}$.

PREUVE. Soit $X$ une instance de P. Soit $T$ un arbre $X$-calculable dont tous les chemins sont de degré PA relativement à $X$. L'arbre $T$ est une instance $X$-calculable de WKL. Soit $\tilde{Y}$ une WKL-solution de $T$, autrement dit $\tilde{Y} \in [T]$. Montrons que $\tilde{Y}$ calcule une P-solution de $X$. Par la proposition 2.4 relativisée à $X$, il existe un idéal de Scott $\mathcal{I}$ contenant $X$ et dont tous les éléments sont $X \oplus \tilde{Y}$-calculables (donc $\tilde{Y}$-calculables, car $\tilde{Y} \geq_{T} X$). Comme $\mathcal{I}$ est un idéal de Scott, $\mathcal{I} \models \mathrm{WKL}$; or, $P \leq_{\omega} \mathrm{WKL}$, donc $\mathcal{I} \models \mathrm{P}$. Comme $X \in \mathcal{I}$, il existe une P-solution $Y$ de $X$ dans $\mathcal{I}$, et il existe donc une P-solution $\tilde{Y}$-calculable de $X$. ■

Notons que dans la preuve précédente, $\tilde{Y}$ n'a pas besoin de l'instance $X$ en oracle pour calculer une P-solution de $X$. Nous verrons dans la section 5 que cela correspond à une notion plus forte que la réduction calculatoire.

Terminons en introduisant une dernière notion qui formalise le fait que certains problèmes sont triviaux du point de vue de la réduction calculatoire.

**Définition 2.6.** Un problème P est calculatoirement vrai si toute instance $X$ de P calcule une P-solution de $X$. ◇

Nous verrons dans la proposition 25-2.4 que c'est par exemple le cas du principe des tiroirs.

**Exercice 2.7.** Montrer que P est calculatoirement vrai si, et seulement si, $P \leq_{c} \mathrm{Id}$, où $\mathrm{Id}$ est le problème identité dont les solutions sont égales aux instances. ◇

## 3. Réduction Weihrauch

Considérons la preuve dans $\mathrm{RCA}_0$ du théorème des valeurs intermédiaires (cf. la proposition 22-5.13). Étant donné une fonction continue $f : [0, 1] \to \mathbb{R}$ satisfaisant $f(0) < 0 < f(1)$, la preuve procède par analyse de cas : soit il existe un nombre rationnel $q \in ]0, 1[$ tel que $f(q) = 0$, auquel cas tout rationnel étant calculable, $f$ possède une solution calculable, soit l'on obtient un réel $r$ tel que $f(r) = 0$ par une recherche dichotomique calculable. Peut-on se passer de cette analyse de cas ? De même que la réduction calculatoire raffine l'ω-réduction en prenant en compte le nombre d'applications, la réduction de Weihrauch permet de donner un sens formel à la question précédente en prenant en compte l'uniformité des preuves.
**Définition 3.1**

Un problème $P$ est *Weihrauch réductible* à $Q$ (noté $P \leq_w Q$) s'il existe deux fonctionnelles Turing $\Phi$ et $\Psi$ telles que pour toute instance $X$ de $P$, l'ensemble $\Phi^X$ est une instance de $Q$, telle que pour toute $Q$-solution $\tilde{Y}$ de $\Phi^X$, l'ensemble $\Psi^{X \oplus \tilde{Y}}$ est une $P$-solution de $X$. On dit que les fonctionnelles $\Phi$ et $\Psi$ *témoignent* de $P \leq_w Q$. $\diamond$

Il résulte directement des définitions que si $P \leq_w Q$, alors $P \leq_c Q$. La réduction de Weihrauch a été introduite par Klaus Weihrauch dans les années 80 comme un outil de l'analyse calculable, avant de connaître un renouveau avec les travaux de Gherardi et Marcone [73], en 2009, montrant l'utilité de cette réduction pour analyser le contenu uniforme des preuves en mathématiques à rebours. Depuis, les degrés Weihrauch ont connu un essor et se présentent en formalisme concurrent de l'implication dans RCA₀ pour l'analyse des théorèmes.

**3.1. Théorème des valeurs intermédiaires**

Afin de formuler plus précisément notre question sur l'uniformité du théorème des valeurs intermédiaires, nous introduisons un analogue pour la réduction de Weihrauch de la notion de calculatoirement vrai.

**Définition 3.2.** Un problème $P$ est *uniformément vrai* s'il existe une fonctionnelle Turing $\Phi$ telle que pour toute instance $X$ de $P$, l'ensemble $\Phi^X$ est une $P$-solution de $X$. $\diamond$

**Exercice 3.3.** Montrer que $P$ est uniformément vrai si, et seulement si, la réduction $P \leq_w \emptyset$ est vraie — où $\emptyset$ désigne le problème identité dont les solutions sont égales aux instances. $\diamond$

Nous avons maintenant les outils nécessaires pour répondre à la question formulée en début de section, à savoir existe-t-il une preuve du théorème des valeurs intermédiaires sans analyse de cas ?

**Proposition 3.4 (Weihrauch [233]).** Le théorème des valeurs intermédiaires n'est pas uniformément vrai. ★

**PREUVE**

Soit $\Phi$ une fonctionnelle Turing telle que pour toute fonction $f : [0, 1] \to \mathbb{R}$ continue satisfaisant $f(0) < 0 < f(1)$, le réel $\Phi(f)$ est une racine de $f$. Le concept de fonctionnelle calculable $\Phi : C([0, 1], \mathbb{R}) \to \mathbb{R}$ se définit de la manière suivante. La fonctionnelle $\Phi$ lance son calcul sur un élément de $2^N$ qui représente une fonction continue comme expliqué dans la section 22-4, et renvoie un élément de $2^N$ qui représente — toujours comme expliqué dans la section 22-4 — un réel. On demande une seule chose, en l'occurrence que,
sur toute représentation de $f$, notre processus calcule une représentation de $\Phi(f)$.

Soit $f : [0, 1] \to \mathbb{R}$ une fonction continue strictement croissante sur l'intervalle $[0, 0.25]$, strictement décroissante sur l'intervalle $[0.25, 0.75]$, et strictement croissante sur $[0.75, 1]$, telle que

$$f(0) = -1, f(0.25) = 0.5, f(0.5) = 0, f(0.75) = -0.5 \text{ et } f(1) = 1$$

(voir la figure 3.5). Soit $g : [0, 1] \to \mathbb{R}$ définie par $g(a) = \Phi(x \mapsto f(x) + a)$. Le lecteur pourra vérifier que $g$ est une fonction continue, en particulier car $\Phi$ est calculable dans le sens donné ci-dessus. Aussi, pour $a \in ]0.5, 1[$, la fonction $x \mapsto f(x) + a$ n'a qu'une seule racine (celle de gauche). Par continuité, $g$ continuera de renvoyer la racine la plus à gauche sur $[0, 0.5]$. À l'inverse, pour $a \in ]-1, -0.5[$, la fonction $x \mapsto f(x) + a$ n'a que la racine de droite. Par continuité, $g$ renverra la racine la plus à droite sur $[-0.5, 0]$. On a donc deux valeurs différentes pour $g(0)$, d'où une contradiction. ■

<figure><img src="image_146.png" /><figcaption>FIGURE 3.5 – Graphe de la fonction $f$ de la proposition 3.4</figcaption></figure>

La structure des degrés induits par la réduction Weihrauch se révèle extrêmement riche. Le lecteur qui voudrait en savoir plus trouvera une introduction détaillée dans *Weihrauch Complexity in Computable Analysis* de Brattka, Gherardi et Pauly [24].

## 3.2. Problèmes de choix et parallélisation

La réduction Weihrauch fournit un panel de problèmes très faibles qui permettent de mesurer des puissances calculatoires qui ne sont pas analysables en termes de degrés Turing. Parmi ces problèmes, on compte les principes d'omniscience.

### Définition 3.6

(1) Le principe limité d'omniscience (LPO) est le problème dont les instances sont des suites $X \in 2^N$ et qui décide s'il existe $n \in \mathbb{N}$ tel que $X(n) = 0$.

(2) Le principe très limité d'omniscience (LLPO) est le problème dont les instances sont des suites $X \in 2^N$ telles que $X(n) = 1$ pour au plus un $n$, et dont les solutions sont les $i < 2$ tels que $\forall n X(2n + i) = 0$. ♦
Notons que le co-domaine de ces problèmes n’est pas dans $2^N$ mais dans $\mathbb{N}$.
Il est cependant possible de représenter tout entier $n$ comme la suite $1^n 0^\infty$.
Les acronymes viennent de l’anglais *Limited Principle of Omniscience* et *Lesser Limited Principle of Omniscience*. Chaque instance du principe LPO possède une solution unique, tandis que certaines instances de LLPO pos-sèdent deux solutions.

**Exercice 3.7.** (⋆) Montrer que la réduction LLPO $\leq_{\leq W}$ LPO est vraie, mais que LPO $\leq_{\leq W}$ LLPO ne l’est pas. ◇

**Exercice 3.8.** (⋆) Montrer que le principe très limité d'omniscience LLPO n'est pas uniformément vrai. ◇

Les problèmes LPO et LLPO peuvent être vus comme des versions ato-miques de phénomènes calculatoires bien connus à travers l'opération de parallélisation.

**Définition 3.9.** La *parallélisation* d'un problème P est le problème $\hat{P}$ dont les instances sont de la forme $\bigoplus_n X_n$, où $X_n \in \text{dom } P$ pour tout $n$. Une $\hat{P}$-solution de $\bigoplus_n X_n$ est un ensemble de la forme $\bigoplus_n Y_n$, où $Y_n$ est une P-solution de $X_n$ pour tout $n$. ◇

Il est aisé de montrer que l'opération de parallélisation est stable par réduction Weihrauch, et correspond donc à une opération sur les degrés Weihrauch.

**Exercice 3.10.** Montrer que si P $\leq_{\leq W}$ Q, alors P $\leq_{\leq W}$ Q. ◇

Rappelons que le problème du saut Turing est le problème J, dont les instances sont les ensembles $X \in 2^N$, chacune ayant pour unique solution son saut Turing $X'$. La proposition suivante montre que le problème LPO peut être vu comme un bit d'information du saut Turing.

**Proposition 3.11.** On a $J \equiv_W \widehat{\text{LPO}}$.

⋆

**PRÉUVE.** Montrons que $J \leq_W \widehat{\text{LPO}}$. Pour tout $e$, soit $\Gamma_e$ la fonctionnelle Turing définie par $\Gamma_e^X(s) = 0 \text{ ssi } \Phi_e^X(e)[s] \downarrow$. Notons que pour tout $X$, $\Gamma_e^X$ vu comme une instance de LPO a pour solution 1 ssi $\Phi_e^X(e) \downarrow$, autrement dit ssi $e \in X'$. Soit $\Phi$ la fonctionnelle Turing définie par $\Phi^X = \bigoplus_e \Gamma_e^X$. Soit $\Psi$ la fonctionnelle définie par $\Psi(X \oplus Y) = Y$. Les fonctionnelles $\Phi$ et $\Psi$ témoignent de $J \leq_W \widehat{\text{LPO}}$.

Montrons que $\widehat{\text{LPO}} \leq_W J$. Soit $\Psi$ définie comme suit : $\Psi^{X \oplus Y}(n) = Y(e_n)$, où $e_n$ est l'indice Turing de la machine telle que $\Phi_{e_n}^X(e_n) \downarrow$ ssi il existe $s \in \mathbb{N}$ tel que $\langle n, s \rangle \notin X$. Montrons que si $\bigoplus_r X_r$ est une instance de $\widehat{\text{LPO}}$, alors $\Psi((\bigoplus_r X_r) \oplus (\bigoplus_r X_r)')$ est une $\widehat{\text{LPO}}$-solution de $\bigoplus_r X_r$.
Soit $n \in \mathbb{N}$; on a $\Psi((\bigoplus_r X_r) \oplus (\bigoplus_r X_r)', n) = (\bigoplus_r X_r)'(e_n)$, où $\Phi_{e_n}^{\bigoplus_r X_r}(e_n) \downarrow$, ssi il existe $s \in \mathbb{N}$ tel que $s \notin X_n$. Ainsi, $(\bigoplus_r X_r)'(e_n) = 1$ ssi il existe un $s \in \mathbb{N}$ tel que $s \notin X_n$, donc pour tout $n$, $\Psi((\bigoplus_r X_r) \oplus (\bigoplus_r X_r)', n)$ est une LPO-solution de $X_n$. Ainsi, $\Psi((\bigoplus_r X_r) \oplus (\bigoplus_r X_r)')$ est une $\widehat{\text{LPO}}$-solution de $\bigoplus_r X_r$. La fonctionnelle identité ainsi que $\Psi$ témoignent donc de $\widehat{\text{LPO}} \leq_w J$. ■

De la même manière, le problème LLPO peut être vu comme une étape du
lemme faible de König.

**Exercice 3.12.** (⋆) Montrer que $\mathrm{WKL} \equiv_W \widehat{\mathrm{LPO}}$.

◇

Remarque

L'opérateur de parallélisation permet d'établir des ponts entre la
réduction Weihrauch et la réduction calculatoire. Par l'exercice 3.10,
si P ≲<sub>W</sub> Q, alors P̂ ≲<sub>W</sub> Q̂, donc en particulier P̂ ≲<sub>c</sub> Q̂. La contraposée
nous permet de prouver un certain nombre de résultats de séparation
dans les degrés Weihrauch à l'aide de la calculabilité. Par exemple, par
le théorème de base low pour les classe Π<sub>1</sub><sup>0</sup>, J ≲<sub>c</sub> WKL. Il s'ensuit, par
la proposition 3.11 et l'exercice 3.12, que LPO ≲<sub>W</sub> LLPO. De la même
manière, si P est uniformément vrai, alors P̂ est calculatoirement vrai.
On en déduit donc que, WKL n'étant pas calculatoirement vrai, LLPO
n'est pas uniformément vrai.

4. Jeux de réduction

Il est souvent plus intuitif de penser aux réductions calculatoires comme à
des jeux à deux : le premier joueur tente de convaincre que la réduction est
vraie, tandis que le second joueur met la réduction à l'épreuve en tentant
de faire les pires choix de solutions. Hirschfeldt et Jockusch [88] ont donné
une caractérisation de l'ω-réduction en termes de jeux.

**Définition 4.1.** Soient P et Q des problèmes. Le *jeu de réduction*

$$
G(Q \to P)
$$

est un jeu à deux joueurs qui procède comme suit.

(1) Si au cours du jeu, un joueur se retrouve bloqué, l'autre joueur gagne.

(2) Si un joueur gagne, le jeu se termine.

(3) Au premier tour, le joueur 1 joue une instance $X_0$ de P. Ensuite, le joueur 2 joue soit une solution $X_0$-calculable de $X_0$ et gagne, ou joue une instance $X_0$-calculable $Y_1$ de Q.
(4) Au tour $n>2$, le joueur 1 joue une solution $X_{n-1}$ de la Q-instance $Y_{n-1}$. Ensuite, le joueur 2 joue soit une P-solution $(X_0 \oplus \cdots \oplus X_{n-1})$-calculable de $X_0$ et gagne, ou joue une instance $(X_0 \oplus \cdots \oplus X_{n-1})$-calculable $Y_n$ de Q.

(5) Si le jeu ne se termine pas, le joueur 1 gagne.

◇

Notons que le joueur 1 ne peut jamais se retrouver bloqué, car par définition, toute instance admet une solution. En revanche, le joueur 2 peut se retrouver bloqué car Q peut n'avoir aucune instance $(X_0 \oplus \cdots \oplus X_{n-1})$-calculable. La plupart des problèmes considérés en mathématiques à rebours ont des instances calculables, et le jeu ne se retrouve jamais bloqué.

**Proposition 4.2 (Hirschfeldt et Jockusch [88]).** On a $P \leq_{\omega} Q$ si, et seulement si, le joueur 2 a une stratégie gagnante pour $G(Q \to P)$. ★

**PREUVE.** Supposons $P \leq_{\omega} Q$. Définissons une stratégie gagnante pour le joueur 2. Au tour $n$, quand le joueur 2 peut jouer, $X_0, \dots, X_{n-1}$ et $Y_1, \dots, Y_{n-1}$ ont déjà été définis. Si notre joueur 2 peut gagner en jouant une P-solution $(X_0 \oplus \cdots \oplus X_{n-1})$-calculable de $X_0$, alors il la joue et gagne. Sinon, soit $n = \langle m, e \rangle$. Si $\Phi_e(X_0 \oplus \cdots \oplus X_{n-1})$ est une instance de Q, alors le joueur 2 la joue. Sinon, le joueur 2 joue une instance $X_0$-calculable de Q. Notons que Q admet nécessairement une telle instance, car dans le cas contraire $\mathcal{I} = \{Z \in 2^N : Z \leq_T X_0\}$ serait un idéal Turing satisfaisant Q, donc satisfaisant P, donc $X_0$ aurait une solution $X_0$-calculable, et le joueur 2 aurait gagné au tour 1.

Supposons que le joueur 2 ne se retrouve jamais dans le cas où il trouve une solution de $X_0$. Le jeu ne se termine pas, donc le joueur 1 gagne. Soit $\mathcal{I} = \{Z : \exists n \ Z \leq_T X_0 \oplus \cdots \oplus X_n\}$. Par l'exercice 22-5.11, $\mathcal{I}$ est un idéal Turing. De plus, $X_0 \in \mathcal{I}$, mais comme le joueur 2 n'a à aucun moment réussi à calculer une solution de $X_0$, l'idéal $\mathcal{I}$ ne contient pas de solution de $X_0$, donc $\mathcal{I} \not\models P$. Enfin, pour toute Q-instance $Z \in \mathcal{I}$, soit $n$ tel que $Z \leq_T X_0 \oplus \cdots \oplus X_n$, et soit alors $e$ tel que $\Phi_e(X_0 \oplus \cdots \oplus X_n) = Z$. Par suite, $Y_{\langle n,e \rangle} = Z$, et $X_{\langle n,e \rangle}$ est une Q-solution de Z dans $\mathcal{I}$, donc $\mathcal{I} \models Q$. Il s'ensuit que $P \not\leq_{\omega} Q$. Contradiction! Le joueur 2 a donc une stratégie gagnante.

Supposons maintenant que $P \not\leq_{\omega} Q$. Définissons une stratégie gagnante pour le joueur 1. Soit $\mathcal{I}$ un idéal Turing tel que $\mathcal{I} \models Q$, mais $\mathcal{I} \not\models P$. Soit alors $X_0 \in \mathcal{I}$ une instance de P sans solution dans $\mathcal{I}$. La stratégie du joueur 1 consiste à maintenir le jeu dans $\mathcal{I}$ pour empêcher le joueur 2 de calculer une P-solution de $X_0$. Au tour 1, le joueur 1 joue $X_0$. Au tour $n > 1$, $X_0, \dots, X_{n-2}$ et $Y_0, \dots, Y_{n-1}$ ont déjà été joués, tous dans $\mathcal{I}$.
Comme $\mathcal{I} \models Q$, c'est que $Y_{n-1}$ possède une solution $X_{n-1}$ dans $\mathcal{I}$. Cette solution est jouée par le joueur 1. À tout instant de la construction, le joueur 2 ne possède que des oracles dans $\mathcal{I}$, et ne peut donc que jouer des instances de $Q$ dans $\mathcal{I}$. Le jeu ne s'arrête jamais, sauf si le joueur 2 se retrouve bloqué sans instance $(X_0 \oplus \cdots \oplus X_{n-1})$-calculable de $Q$. Dans les deux cas, le joueur 1 gagne. ■

Le formalisme des jeux permet également de compter le nombre d'instances nécessaires pour une réduction.

**Définition 4.3 (Hirschfeldt et Jockusch [88]).** On note $P \leq_{\omega}^{n} Q$ si le joueur 2 possède une stratégie gagnante pour le jeu $G(Q \to P)$ qui lui garantit une victoire en au plus $n+1$ tours. ◇

En particulier, $P \leq_{\omega}^{0} Q$ si, et seulement si, P est calculatoirement vrai. Si $P \leq_{c} Q$, alors $P \leq_{\omega}^{1} Q$. De plus, si $Q$ admet des instances calculables, alors la réciproque est vraie.

**Exercice 4.4.** (*) Rappelons que KL est le problème du lemme de König pour les arbres à branchement fini, et que J est le problème du saut Turing. Montrer que KL $\leq_{\omega}^{2}$ J, mais qu'en revanche KL $\not\leq_{\omega}^{1}$ J. ◇

Il existe des variantes du jeu de réduction pour formaliser des généralisations de la réduction Weihrauch (voir Hirschfeldt et Jockusch [88]) ainsi que des variantes orientées théorie des modèles qui formalisent l'implication dans RCA₀. Le lecteur intéressé par cette approche trouvera une analyse approfondie dans les travaux de Dzhafarov, Hirschfeldt et Reitzes [53].

# 5. Réductions fortes

Nous avons vu jusqu'à présent trois grandes réductions qui coexistent en calculabilité. L'ω-réduction est le pendant calculatoire de l'implication dans le système RCA₀. La réduction calculatoire raffine cette réduction en n'autorisant qu'une application du problème, tandis que la réduction de Weihrauch étudie la dimension uniforme de la réduction. Pour chacune des réductions $P \leq Q$, la solution de l'instance $\tilde{X}$ de Q est autorisée à utiliser l'instance $X$ de P en oracle pour calculer une solution de $X$. Il arrive cependant fréquemment que $\tilde{X}$ calcule directement une solution de $X$.

**Définition 5.1.** Un problème P est *fortement calculatoirement réducible* à Q (noté $P \leq_{sc} Q$) si pour toute instance $X$ de P, il existe une instance $\tilde{X}$ de Q calculable en $X$, telle que toute Q-solution $\tilde{Y}$ de $\tilde{X}$ calcule une P-solution de $X$. ◇
De la même manière, on définit la *réduction forte de Weihrauch*, que l'on note $\leqslant_{sW}$. Les réductions fortes traduisent un lien plus étroit entre les solutions de P et de Q, dans le sens où l'on est capable de coder l'intégralité de l'information d'une P-solution dans une Q-solution.

**Exemple 5.2.** La plupart des preuves de réduction que nous avons vues sont fortes. Par exemple, $WKL \leqslant_{sW} J \leqslant_{sW} KL$. En revanche, la réduction $LLPO \leqslant_{W} LPO$, vue dans l'exercice 3.7, n'est pas forte.

Certains problèmes, comme le lemme faible de König, possèdent la capacité de coder des ensembles dans leurs solutions. On les appelle des cylindres.

**Définition 5.3**

Le produit de deux problèmes P et Q, est le problème $P \times Q$ dont le domaine est $\{X_0 \oplus X_1 : X_0 \in \text{dom } P \wedge X_1 \in \text{dom } Q\}$, et tel que pour toute instance $X_0 \oplus X_1$, les solutions sont de la forme $Y_0 \oplus Y_1$, où $Y_0$ est une P-solution de $X_0$ et $Y_1$ une Q-solution de $X_1$. Un problème P est un cylindre pour $\leqslant_{sc}$ (resp. $\leqslant_{sW}$) si $\text{Id} \times P \leqslant_{sc} P$ (resp. $\text{Id} \times P \leqslant_{sW} P$). ◇

Trivialement, si P est un cylindre pour $\leqslant_{sW}$, alors c'est un cylindre pour $\leqslant_{sc}$. La notion de cylindre capture exactement les problèmes qui sont insensibles à la réduction forte, au sens suivant.

**Proposition 5.4.** Un problème Q est un cylindre pour $\leqslant_{sc}$ si, et seulement si, pour tout problème P, on a l'équivalence $P \leqslant_{c} Q \leftrightarrow P \leqslant_{sc} Q$. ★

**PREUVE.** Notons que pour tout problème Q, si $P \leqslant_{sc} Q$, alors $P \leqslant_{c} Q$, car il suffit de ne pas tenir compte de l'instance X de P.

Supposons que Q est un cylindre pour $\leqslant_{sc}$ et que $P \leqslant_{c} Q$. Soit X une instance de P. Soit $\tilde{X}$ l'instance X-calculable de Q telle que pour toute Q-solution $\tilde{Y}$, l'ensemble $X \oplus \tilde{Y}$ calcule une P-solution de X. Comme Q est un cylindre, $\text{Id} \times Q \leqslant_{sc} Q$. Soit $X_1$ l'instance $(X \oplus \tilde{X})$-calculable de Q telle que pour toute Q-solution $Y_1$ de $X_1$, $Y_1$ calcule une $(\text{Id} \times Q)$-solution de $X \oplus \tilde{X}$, autrement dit $Y_1$ calcule $X \oplus \tilde{Y}$, où $\tilde{Y}$ est une Q-solution de $\tilde{X}$. Comme $X \geqslant_{T} \tilde{X}$, $X_1$ est X-calculable, et comme $X \oplus \tilde{Y}$ calcule une P-solution de X, alors $Y_1$ calcule une P-solution de X. Donc, $P \leqslant_{sc} Q$.

Supposons maintenant que pour tout problème P, si l'on a $P \leqslant_{c} Q$, on a aussi $P \leqslant_{sc} Q$. En particulier, si l'on prend pour P le problème $\text{Id} \times Q$, on a bien $\text{Id} \times Q \leqslant_{c} Q$, donc $\text{Id} \times Q \leqslant_{sc} Q$. Autrement dit, Q est un cylindre pour $\leqslant_{sc}$. ■

Parmi les cylindres, on comptera le lemme faible de König, mais également le problème du saut J.
**Proposition 5.5.** Le problème WKL est un cylindre pour $\leq_{sW}$.

*

PREUVE. Soit $\Phi$ la fonctionnelle telle que pour tout ensemble $X$ et tout arbre binaire $T$, $\Phi(X \oplus T)$ est un arbre binaire satisfaisant

$$[\Phi(X \oplus T)] = \{X \oplus P : P \in [T]\}.$$

Plus précisément, on peut définir

$$\Phi(X \oplus T) = \left\{ \sigma \in 2^{<\mathbb{N}} : \exists \tau \in T^{[|\sigma|]} \forall i < |\sigma| \begin{array}{l} i \text{ pair } \rightarrow \sigma(i) = \tau(i/2) \\ i \text{ impair } \rightarrow \sigma(i) = X((i-1)/2) \end{array} \right\},$$

où $T^{[n]}$ est l'ensemble des nœuds de $T$ de taille $n$. Alors, $\Phi$ et la fonctionnelle identité témoignent de la réduction $\mathrm{Id} \times \mathrm{WKL} \leq_{sW} \mathrm{WKL}$. $\blacksquare$

Rappelons que par la proposition 2.5, si $P \leq_{\omega} \mathrm{WKL}$, alors $P \leq_{c} \mathrm{WKL}$. Grâce à la proposition 5.5 et la proposition 5.4, nous pouvons en déduire que $P \leq_{sc} \mathrm{WKL}$.

**Exercice 5.6.** Montrer l'équivalent de la proposition 5.4 pour la réduction de Weihrauch. $\diamond$

<figure><img src="image_147.png" /><figcaption>FIGURE 5.7 – *Diagramme récapitulatif des réductions calculatoires. Chacune des implications est stricte.*</figcaption></figure>
<figure><img src="image_148.png" /></figure>
Chapitre 25

Théorème de Ramsey

De l'avis de ses professeurs et contem-
porains, Frank Ramsey était un esprit
extrêmement brillant. Il est malheureu-
sement mort trop jeune, à vingt-six
ans, des suites d'une maladie. Malgré
son jeune âge, il avait déjà beaucoup
accompli, et son nom passera à la
postérité notamment à travers deux tra-
vaux. Le premier en économie : il publie
en 1928 un article sur le taux d'épargne,
où il développe ce que l'on appel-
era le modèle de Ramsey. Un de ses
professeurs, l'économiste mondialement
célèbre John Maynard Keynes quali-
fiera ce travail « d'une des contributions
les plus remarquables jamais apportées
aux mathématiques économiques ». Le
deuxième est en logique mathématique.

Ramsey s'intéresse à la philosophie, à la logique, aux probabilités et aux fondements des mathématiques. Il publiera en 1930 un article sur ce thème, dans lequel il étudie la cohérence de certaines formules logiques. Ce n'est toutefois pas l'objet initial de l'article que l'on retiendra, mais un simple lemme prouvé au détour d'une page, dont Erdös et Szekeres devaient prendre cinq ans plus tard toute la mesure. Ce lemme sera le point de départ de ce que l'on appellera la théorie de Ramsey, un champ de recherche important en mathématique combinatoire.

<figure><img src="image_149.png" /><figcaption>Frank Ramsey, 1903-1930</figcaption></figure>
# 1. Aperçu général

La grande observation historique des mathématiques à rebours est son phénomène de structure : la plupart des théorèmes ordinaires sont soit prouvables dans $RCA_0$, soit équivalents modulo $RCA_0$ à l'un des quatre grands systèmes d'axiomes $WKL_0$, $ACA_0$, $ATR_0$, $Π_1^1-CA_0$, linéairement ordonnés par l'implication dans $RCA_0$. Il s'agit d'un phénomène avant tout empirique, et qui porte sur les théorèmes « naturels » ; mais il est facile de concevoir des énoncés artificiels qui échappent à cette structure. Cette dernière relève-t-elle alors simplement d'un biais humain dans la pratique des mathématiques, ou bien en traduit-elle malgré tout quelque chose de plus profond ? Ce chapitre aidera peut-être le lecteur à se faire une opinion sur la question.

Le théorème de Ramsey pour les paires d'entiers a reçu une attention particulière, car c'est historiquement l'un des premiers théorèmes naturels échappant à cette classification. La communauté s'est donc penchée dans les moindres détails sur ses aspects méta-mathématiques, apportant peut-être ainsi quelques éléments de réponses à la question posée dans le paragraphe ci-dessus. Il s'agit d'une aventure mathématique passionnante à l'origine de la découverte de nombreuses techniques en calculabilité et en théorie de la preuve.

Commençons par fixer quelques notations et autres conventions, après quoi nous donnerons l'énoncé du théorème de Ramsey dans le cas général.

## Notation

Soit $X \subseteq \mathbb{N}$. On écrit $[X]^n$ pour désigner l'ensemble des sous-ensembles de $X$ de taille $n$.

Les ensembles non ordonnés de taille $n$ sont en correspondance bijective avec les $n$-uplets $(a_1, \dots, a_n)$, où $a_i < a_{i+1}$. On identifiera donc parfois $[X]^n$ avec l'ensemble des $n$-uplets strictement croissants et l'on parlera par abus de langage de $n$-uplets pour désigner les éléments de $[X]^n$. Un *coloriage* est une fonction $f : [\mathbb{N}]^n \to \mathbb{N}$. Si l'image de $f$ est bornée, de cardinal au plus $k$, il s'agit d'un *k-coloriage* ou *coloriage fini*. Étant donné un coloriage $f$ sur $[\mathbb{N}]^n$, un ensemble $X \subseteq \mathbb{N}$ est *homogène* pour $f$ si la couleur $f(\{x_1, \dots, x_n\})$ est la même pour tout $\{x_1, \dots, x_n\} \in [X]^n$.
On abrêgera $f(\{x_1, \dots, x_n\})$ par $f(x_1, \dots, x_n)$ — où l'on supposera alors $x_1 < \dots < x_n$ — suivant notre identification de $[X]^n$ avec l'ensemble des $n$-uplets strictement croissants. Enfin, on identifiera l'entier $k$ avec l'ensemble $\{0, 1, \dots, k-1\}$.
**Théorème 1.1 (Théorème de Ramsey généralisé)**

Soient $n, k \in \mathbb{N}^*$. Tout coloriage $f : [\mathbb{N}]^n \to k$ admet un ensemble homogène infini.

Le théorème établi à l'origine par Ramsey est en fait la restriction du théorème précédent au cas $n = 2$, c'est-à-dire aux paires d'entiers. À partir de $n > 1$, la preuve est non triviale et sera étudiée dans la section 2.

**Notation**

On désignera le théorème de Ramsey pour les $n$-uplets d'entiers et $k$ couleurs par $RT_k^n$.

L'énoncé $RT_k^n$ peut être vu comme le problème dont les instances sont des coloriages $f : [\mathbb{N}]^n \to k$, et dont les solutions sont les ensembles infinis homogènes. L'énoncé du théorème de Ramsey généralisé peut paraître assez abstrait à première vue. Arrêtons-nous sur sa signification pour des petites valeurs de $n$.

Cas $n = 1$. Il s'agit tout simplement du principe infini des tiroirs, qui dit que si l'on colorie un ensemble infini à l'aide d'un nombre fini de couleurs, alors une infinité d'éléments se voit attribuer la même couleur. Plus formellement, $RT_k^1$ énonce, pour toute $k$-partition $A_0 \cup \cdots \cup A_{k-1} = \mathbb{N}$, l'existence d'un ensemble infini $H \subseteq A_i$ pour une couleur $i < k$.

<table><caption>FIGURE 1.2 – Instance de $RT_3^1$ où chaque ligne correspond à une couleur. Si la première ligne est infinie, $H = \{0, 1, 3, 8, \dots\}$ est une solution, mais également tout sous-ensemble infini de $H$ en est une.</caption><tr><td>0</td><td>1</td><td>3</td><td>8</td><td>...</td></tr><tr><td></td><td>2</td><td>5</td><td>6</td><td>...</td></tr><tr><td></td><td></td><td>4</td><td>7</td><td>...</td></tr></table>

Le principe infini des tiroirs est combinatoirement trivial. Du point de vue calculatoire et de la théorie de la preuve, la situation est plus délicate. De la même manière que combinatoirement, le principe des tiroirs est le principe le plus fondamental à l'origine de la théorie de Ramsey, nous verrons que la plus grande partie des phénomènes calculatoires du théorème de Ramsey se retrouvent dans le principe des tiroirs.

Cas $n = 2$. Le théorème de Ramsey pour les paires est le théorème historique prouvé par Frank Ramsey. Il peut se formuler en termes de cliques comme suit : une clique est un graphe dont les sommets sont reliés deux à deux. Le théorème de Ramsey pour les paires et $k$ couleurs ($RT_k^2$) énonce,
pour tout *k*-coloriage des arêtes d'une clique infinie, l'existence d'un sous-ensemble infini de sommets dont le sous-graphe induit est monochrome. Dans le cas où $k = 2$, on peut également considérer la présence et l'absence d'arête comme chacune des deux couleurs. $RT_2^2$ énonce donc, pour tout graphe infini, l'existence d'un sous-ensemble de sommets dont le sous-graphe induit est soit une clique, soit une anti-clique (sans aucune arête).

<figure><img src="image_150.png" /><figcaption>FIGURE 1.3 – *Instance de* $RT_3^2$. *Les motifs des arêtes correspondent aux couleurs. Une solution est un sous-ensemble infini de sommets dont les arêtes ont le même motif.*</figcaption></figure>

Le théorème de Ramsey pour les paires est combinatoirement beaucoup moins trivial que celui pour les singletons, et cette complexité se traduit du point de vue calculatoire. Nous verrons que $RT_k^2$ échappe au phénomène de structure calculatoire des mathématiques à rebours. La démonstration du théorème de Ramsey pour les paires est un exercice intéressant qui requiert une manipulation un peu poussée des ensembles infinis. Nous encourageons le lecteur à en chercher une preuve par lui-même.

**Exercice 1.4. (*)** Démontrer le théorème de Ramsey pour les paires. ◇

Le théorème de Ramsey possède une version finie, qui découle de sa version infinie par compacité :

**Théorème 1.5 (Théorème de Ramsey fini)**

Pour tous $n, k, p \in \mathbb{N}^*$ il existe $m$ suffisamment grand tel que tout $k$-coloriage de $\{[1, \dots, m]\}^n$ admet un ensemble homogène de taille $p$.

**PREUVE.** Supposons que le théorème de Ramsey fini soit faux. Alors, il existe $n, k, p$ tels que pour tout $m$ il existe un $k$-coloriage de $\{[1, \dots, m]\}^n$ sans ensemble homogène de taille $p$. On peut alors construire un arbre dont les nœuds de taille $m$ sont les $k$-coloriages de $\{[1, \dots, m]\}^n$ n'admettant aucun ensemble homogène de taille supérieure à $p$. Comme il n'y a qu'un nombre fini de $k$-coloriages possibles de $\{[1, \dots, m]\}^n$, notre arbre est à branchement fini.

Par le lemme de König, l'arbre contient donc un chemin infini, qui est un coloriage de $[N]^n$ sans aucun ensemble homogène de taille supérieure à $p$, ce qui contredit le théorème de Ramsey infini. ■
La borne optimale $m$ en fonction de $n, k$ et $p$ est appelée *nombre de Ramsey*. La détermination des nombres de Ramsey en fonction des paramètres est encore un sujet de recherche en combinatoire.

## Théorème de Ramsey et degrés Weihrauch

Il existe deux traductions possibles du théorème de Ramsey en problème mathématique.

Dans tous les cas, une instance est un coloriage $f : [N]^n \to k$. En revanche, dans le premier cas, une solution est un ensemble $H$ homogène pour l'instance $f$, tandis que dans le second cas, la solution est $i \frown H$, où $H$ est homogène de couleur $i$ pour l'instance $f$. On appellera ces problèmes respectivement $RT_k^n$ et $cRT_k^n$. Cette distinction n'a pas d'importance pour la réduction Weihrauch, car en ayant accès à l'instance et l'ensemble homogène, il est possible de retrouver la couleur d'homogénéité. Ainsi, $RT_k^n \equiv_W cRT_k^n$ pour tous $n, k \ge 1$. En revanche, si l'on considère la réduction forte de Weihrauch où l'on perd l'accès à l'instance, la couleur d'homogénéité ne peut pas être récupérée en général, et l'on peut prouver que $cRT_k^n \le s_W RT_k^n$ pour tous $n, k \ge 1$.

Le théorème de Ramsey du point de vue des degrés Weihrauch a été étudié de manière systématique par Brattka et Rakotoniaina [25].

## 2. Théorème de Ramsey dans la hiérarchie arithmétique

Notre aventure commence avec Specker [213], qui montre que $RCA_0$ ne suffit pas à démontrer le théorème de Ramsey pour les paires, en construisant un coloriage calculable qui n'admet pas d'ensemble homogène calculable infini. Un an plus tard, en 1972, Carl Jockusch [99] améliore ce résultat dans un article fondateur, qui marque le point de départ d'une étude approfondie du théorème de Ramsey, et c'est essentiellement ce premier travail de Jockusch que nous présentons dans cette section, résumée par la figure 2.1.

Comme illustré dans la figure, l'article de 1972 de Jockusch laissa ouvertes deux questions : la prouvabilité de $ACA_0$ ou celle de $WKL_0$ dans le système $RCA_0 + RT_2^2$. Il faudra attendre vingt-trois ans pour que David Seetapun ne résolve la première par la négative (voir le corollaire 4.15), et ce ne sera qu'en 2012 que la dernière sera résolue également par la négative, par Lu Liu (voir le corollaire 4.17), jeune étudiant alors encore en licence cette année-là.
<figure><img src="image_151.png" /><figcaption>FIGURE 2.1 – Le travail de Jockusch. Les implications non représentées et qui ne peuvent être déduites des autres ne tiennent pas.</figcaption></figure>

## 2.1. Étude préliminaire

Avant de nous lancer dans la preuve du théorème de Ramsey, nous allons établir deux propositions utiles pour le reste de notre analyse. La première proposition est un renforcement du théorème de Ramsey qui exprime d'une certaine manière que c'est un énoncé qui ne dépend pas de la nature de l'ensemble, mais uniquement de sa cardinalité.

**Proposition 2.2.** Le système $RCA_0 + \text{RT}_k^n$ prouve que pour tout ensemble infini $X \subseteq \mathbb{N}$ et tout $k$-coloriage $f$ de $[X]^n$, il existe un ensemble $H \subseteq X$ infini homogène pour $f$.

**PREUVE.** Soit $X$ un ensemble infini, et soit $f : [X]^n \to k$ fixés. Considérons alors $g : \mathbb{N} \to X$ la bijection canonique qui à $m$ associe le $(m+1)$-ième élément de $X$. On peut alors définir un coloriage $h : [\mathbb{N}]^n \to k$ par $h(\{x_1, \dots, x_n\}) = f(\{g(x_1), \dots, g(x_n)\})$. Soit $Y \subseteq \mathbb{N}$ un ensemble infini homogène pour $h$. Alors, l'ensemble $H = \{g(x) : x \in Y\} \subseteq X$ est un ensemble infini homogène pour $f$. On vérifiera bien que sous l'hypothèse que $X$ est infini, l'induction $\Sigma_1^0$ sur le paramètre $X$ est suffisante pour montrer que $g$ est totale, et donc que $H$ est $\Delta_1^0$ (voir la section 23-3).

La seconde proposition montre que le nombre de couleurs $k$ du coloriage a peu d'impact en mathématiques à rebours. En effet, $\text{RT}_{k+1}^n$ implique trivialement $\text{RT}_k^n$, car tout $k$-coloriage est un $(k+1)$-coloriage. Inversement, un argument de « daltonisme » permet de prouver $\text{RT}_{k+1}^n$ à partir de $\text{RT}_k^n$.
**Proposition 2.3.** On a RCA₀ ⊢ ∀n ∀k ≥ 2 (RTₖⁿ → RTₖ₊₁ⁿ). ★

PREUVE. Supposons RTₖⁿ vrai. Considérons un coloriage f : [N]ⁿ → k + 1. Définissons alors le k-coloriage g : [N]ⁿ → k qui à un n-uplet {x₁, ..., xₙ} associe la couleur f({x₁, ..., xₙ}) si f({x₁, ..., xₙ}) < k, et la couleur k - 1 si f({x₁, ..., xₙ}) = k. Par RTₖⁿ, il existe un ensemble X infini homogène pour g. Si la couleur de X est parmi {0, ..., k - 2}, alors X est également homogène pour f. Supposons que X est homogène de couleur k - 1 pour g. Alors, f restreint à [X]ⁿ est un 2-coloriage. Par la version locale de RTₖⁿ (voir la proposition 2.2) appliquée à f : [X]ⁿ → {k - 1, k}, il existe un ensemble infini H ⊆ X homogène pour f. ■

Notons que la preuve de la proposition 2.3 fait appel à deux instances
de $\mathbb{R}T_k^n$ pour prouver $\mathbb{R}T_{k+1}^n$. Il s'agit d'applications multiples nécessaires :
on peut montrer $\mathbb{R}T_{k+1}^n \not\leq_c \mathbb{R}T_k^n$ pour tout $n, k \geq 1$ (voir Patey [172]). Dans
la suite on s'autorisera à utiliser la version locale du théorème de Ramsey
par la proposition 2.2, et l'on considérera principalement le cas $k = 2$ en
vertu de la proposition 2.3.

Le théorème de Ramsey se prouve de manière inductive sur la taille des *n*-uplets coloriés. Le cas de base est le principe infini des tiroirs $\mathbb{R}T_2^1$.

**Proposition 2.4.** RCA₀ ⊢ RT₂¹. ★

PREUVE. Soit $f : N \to 2$ un coloriage, et soit $C_i = \{x \in N : f(x) = i\}$. Notons que $C_i$ existe pour tout $i < 2$ par $\Delta_0^0$-compréhension paramétrée par $f$. Si $C_i$ est infini pour un $i < 2$, alors $C_i$ est un ensemble infini homogène pour $f$. Sinon, soient $n_0$ et $n_1$ des bornes respectives de $C_0$ et $C_1$. Alors, $\max(n_0, n_1)$ est une borne de $C_0 \cup C_1 = N$, contradiction. ■

Il s'ensuit que $\mathbb{R}T_k^1$ est prouvable dans RCA₀ pour tout $k \in N$, et que $\mathbb{R}T_k^1$
est un énoncé calculatoirement vrai, au sens où il a toujours une solution
calculable en son instance. Nous étudierons plus en détail le principe infini
des tiroirs — et ses richesses insoupçonnées — dans la section 3.

**2.2. Théorème de Ramsey pour les paires**

Nous rentrons à présent dans le vif du sujet en commençant par le théorème de Ramsey pour les paires, et en établissant des bornes très précises sur la complexité des solutions du point de vue de la hiérarchie arithmétique.

**Théorème 2.5 (Jockusch [99])**

Pour tout $k \ge 1$, toute instance $f$ de $\mathbb{R}T_k^2$ possède une solution $\Pi_2^0(f)$.
PREUVE. *Explications préliminaires.* Pour simplifier les notations, nous al-
lons prouver le cas $k = 2$. Le cas général est une simple adaptation de
la construction. Soit $f : [\mathbb{N}]^2 \to 2$ un coloriage. Le but est de construire
une suite $\Pi_2^0(f)$ d'éléments $x_0 < x_1 < x_2 < \dots$ telle que pour tout $x_i$
la couleur $f(\{x_i, x_j\})$ soit la même pour tout $x_j > x_i$. L'ensemble que
l'on construit n'est donc pas directement un ensemble homogène. En re-
vanche, on voit aisément comment calculer à partir d'une telle suite un sous-
ensemble homogène : soit $g : \mathbb{N} \to 2$ la fonction qui à $i$ associe $f(\{x_i, x_{i+1}\})$.
Par le principe infini des tiroirs, il existe une couleur $c < 2$ qui apparaît infi-
niment souvent. Alors, l'ensemble $\{x_i : g(i) = c\}$ est un sous-ensemble $\Pi_2^0(f)$
homogène infini.

Chaque élément $x_i$ sera approximé par une suite $(x_i^s)_{s \in \mathbb{N}}$. Au départ, chaque $x_i^0$ est indéfini. On va également utiliser une approximation d'ensembles $(X_i^s)_{s \in \mathbb{N}}$ qui sont eux aussi au départ tous indéfinis. Chaque ensemble $X_i^s$ qui est défini sera au départ égal à $\{x \in X_{i-1}^s : f(x_i^s, x) = 0\}$ en supposant au début qu'il s'agit d'un ensemble infini. Puis, si ce n'est pas le cas, on le changera pour qu'il devienne égal à $\{x \in X_{i-1}^s : f(x_i^s, x) = 1\}$, et ainsi de suite. On utilisera également une borne inférieure $b_s$ sur les nouveaux $x_i^s$ que l'on souhaite définir. L'utilité de cette borne est essentiellement de pouvoir rendre notre construction $\Pi_2^0(f)$.

*Construction.* À l'étape 0, on définit $x_0^0 = 0$, $X_0^0 = \{x : f(x_0^0, x) = 0\}$ et $b_0 = 0$. Supposons qu'à une étape $s$, on ait défini $x_0^s < \dots < x_n^s$ pour un certain $n$ (les $x_{n+1}^s$ suivants étant indéfinis), avec des ensembles calculables $X_0^s \supseteq \dots \supseteq X_n^s$. À l'étape $s+1$, on cherche à l'aide de $\emptyset'$ le plus grand $i \le n$ tel que $X_i^s$ possède au moins un élément strictement supérieur à $b_s$. Si un tel $i \ge 0$ n'existe pas, on pose $i = -1$.

Cas 1. Si $i = n$, alors on pose $X_j^{s+1} = X_j^s$ et $x_j^{s+1} = x_j^s$ pour $j \le n$, et l'on définit $x_{n+1}^{s+1}$ comme étant le plus petit élément de $X_n^{s+1}$ strictement supérieur à $b_s$, et aussi $X_{n+1}^{s+1} = \{x \in X_n^{s+1} : f(x_{n+1}^{s+1}, x) = 0\}$. On définit enfin $b_{s+1} = x_{n+1}^{s+1}$.

Cas 2. Si $i < n$, alors pour tout $j \le i$ on définit $X_j^{s+1} = X_j^s$ et $x_j^{s+1} = x_j^s$.
Puis, on définit $x_{i+1}^{s+1} = x_{i+1}^s$ et $X_{i+1}^{s+1} = \{x \in X_i^{s+1} : f(x_{i+1}^{s+1}, x) = 1\}$. Pour
tout $j > i + 1$, les valeurs $x_j^{s+1}$ et $X_j^{s+1}$ redeviennent indéfinies si elles ne
l'étaient pas déjà. On définit enfin $b_{s+1} = b_s$. Cela conclut la construction.

*Vérification.* Montrons que chaque suite $(x_n^s)_{s \in \mathbb{N}}$ est finalement définie et converge vers une valeur $x_n$, ainsi que chaque suite $(X_n^s)_{s \in \mathbb{N}}$, qui converge vers un ensemble $X_n$ tel que $|X_n| = \infty$. Il est clair que $(x_0^s)_{s \in \mathbb{N}}$ est toujours égale à 0. Si l'ensemble $X_0^0$ est infini, alors il est clair aussi qu'il ne changera jamais. S'il est fini, alors par construction il changera une seule fois pour
devenir co-fini, et ne changera donc plus jamais à partir de ce moment. Sup-
posons à présent qu’à l’étape $s$ les variables $x_0^s, \dots, x_n^s$ et $X_0^s, \dots, X_n^s$ aient
atteint leurs valeurs de convergence $x_0, \dots, x_n$ et $X_0, \dots, X_n$ avec $X_n$ infini.
Là encore, par construction, la suite $(x_{n+1}^t)_{t>s}$ sera définie et constante à
chaque étape $t$. Il s’ensuit que si $X_{n+1}^t \subseteq X_n$ est infini pour $t > s$, il ne
changera jamais, sinon il changera une fois pour devenir co-fini.

Montrons enfin que la suite $x_0 < x_1 < \dots$ est $\Pi_2^0(f)$. On montre pour
cela qu'elle est co-énumérée à l'aide de $f'$. Il suffit pour cela d'utiliser le
marqueur $b_s$. En effet, à l'étape $s+1$, l'élément que l'on ajoute est forcément
supérieur à $b_s$. Les éléments qui passent de indéfini à défini à l'étape $s$ sont
forcément supérieurs à $b_s$. La co-énumération se fait donc à chaque étape $s$
en supprimant tous les éléments plus petits que $b_s$ et qui sont différents
d'un certain $x_n^s$ pour $x_n^s$ défini.

■

Notons que le théorème précédent constitue une preuve du théorème de Ramsey pour les paires. Le fait que la solution exhibée soit calculable à l'aide du double saut suggère que la preuve a été faite dans *ACA*₀. Pour s'en assurer, il faut vérifier que la démonstration du fait que l'ensemble $\Pi_2^0(f)$ qui est construit est bien infini et homogène pour $f$, n'utilise pas plus que l'induction arithmétique. Le lecteur pourra constater que c'est bien le cas, et nous verrons à défaut que c'est une conséquence du théorème 2.17.

La borne supérieure $\Pi_2^0(f)$ du théorème précédent est-elle optimale du point de vue de la hiérarchie arithmétique ? Jockusch a répondu positivement, via le résultat suivant.

**Théorème 2.6 (Jockusch [99])**

Il existe une instance calculable de $RT_2^2$ qui ne possède aucune solution $\Sigma_2^0$.

PREUVE. Montrons d'abord qu'il existe un coloriage calculable $f : [\mathbb{N}]^2 \to 2$ sans ensemble homogène infini $\Delta_2^0$.

Pour tous $e, s \in \mathbb{N}$, soit $A_{e,s} = \{x < s : \Phi_e(\emptyset', x)[s] \downarrow= 1\}$. Notons que $(A_{e,s})_{e,s \in \mathbb{N}}$ est uniformément calculable. De plus, si $x \mapsto \Phi_e(\emptyset', x)$ est une fonction totale, alors pour tout $x, \Phi_e(\emptyset', x) = 1 \text{ ssi } \forall^\infty s \ x \in A_{e,s}$. Notons que si $\Phi_e(\emptyset', x) \uparrow$ pour $x, e$, alors $x$ peut entrer et sortir de $A_{e,s}$ pour une infinité de $s$.

On définit $f : [\mathbb{N}]^2 \to 2$ de la manière suivante : à l'étape de calcul $s$, pour tout $e < s$, si jamais $|A_{e,s}| \ge 2(e+1)$, alors on choisit les deux plus petits éléments distincts $a, b \in A_{e,s}$ tels que $f(\{a, s\})$ et $f(\{b, s\})$ ne sont pas encore définis, et l'on définit $f(\{a, s\}) = 0$ et $f(\{b, s\}) = 1$.
Notons que si $|A_{e,s}| \ge 2(e+1)$, il y a forcément toujours deux éléments $a, b \in A_{e,s}$ sur lesquels $f(\{a, s\})$ et $f(\{b, s\})$ ne sont pas encore définis : par induction sur $e < s$, $f(\{x, s\})$ est défini pour au plus $2e$ valeurs de $x$ avant de choisir les éléments de $A_{e,s}$. Ainsi, si $|A_{e,s}| \ge 2(e+1)$, il y a toujours au moins deux valeurs disponibles.

Montrons que $f$ n'admet aucun ensemble homogène infini $\Delta_2^0$.

Soit $A$ un ensemble $\Delta_2^0$ infini. Alors, il existe un entier $e$ tel que pour tout $x, x \in A$ si, et seulement si, $\forall^\infty s \ x \in A_{e,s}$. Soit $n \in \mathbb{N}$ le plus petit entier tel que $A \upharpoonright_n$ possède $2(e+1)$ éléments, et soit $s \in A$ suffisamment grand tel que $A_{e,s} \upharpoonright_n = A \upharpoonright_n$. En particulier, $|A_{e,s}| \ge 2(e+1)$, et l'on choisira deux éléments $a, b \in A \upharpoonright_n$ tels que $f(\{a, s\}) \ne f(\{b, s\})$. Comme $a, b, s \in A$, l'ensemble $A$ n'est pas homogène pour $f$.

Pour finir, il suffit de montrer que tout ensemble $\Sigma_2^0$ infini contient un ensemble $\Delta_2^0$ infini.

Étant donné $A = \{n : \exists x \ \forall y \ R(x, y, n)\}$ pour un prédicat calculable $R$, à l'aide de $\emptyset'$ on cherche $n_0$ et $x$ tels que $\forall y \ R(x, y, n_0)$, puis on cherche $n_1 > n_0$ et $x$ tels que $\forall y \ R(x, y, n_1)$, etc. Comme tout sous-ensemble homogène d'un ensemble homogène est lui aussi homogène, un coloriage qui n'a aucun ensemble homogène $\emptyset'$-calculable n'a aussi aucun ensemble homogène $\Sigma_2^0$. ■

En particulier, le simple saut n'est pas suffisant pour calculer un ensemble homogène infini pour un coloriage calculable des paires. Cela implique notamment que $RT_2^2$ n'est pas prouvable à partir du lemme faible de König.

**Corollaire 2.7**

On a $RT_2^2 \not\leq_{\omega} WKL$. En particulier, $WKL_0 \not\models RT_2^2$.

PREUVE. Par l'exercice 22-7.5, il existe un idéal de Scott $\mathcal{I}$ ne contenant que des ensembles low, et donc $\Delta_2^0$. Par la proposition 22-7.2, $\mathcal{I} \models WKL$. En revanche, par le théorème 2.6, il existe une instance calculable $f : [\mathbb{N}]^2 \to 2$ de $RT_2^2$ n'admettant aucune solution $\Delta_2^0$. En particulier, $f \in \mathcal{I}$, mais $f$ n'admet pas de solution dans $\mathcal{I}$, donc $\mathcal{I} \not\models RT_2^2$. Il vient alors $RT_2^2 \not\leq_{\omega} WKL$, de sorte que $WKL_0 \not\models RT_2^2$. ■

## 2.3. Théorème de Ramsey généralisé

Nous allons maintenant étendre l'analyse précédente au théorème de Ramsey généralisé aux $n$-uplets. La preuve inductive du théorème de Ramsey se fait à l'aide de la notion d'ensemble pré-homogène, qui permet de réduire un coloriage des $(n+1)$-uplets en un coloriage des $n$-uplets.
**Définition 2.8.** Soient $n, k \ge 1$, et soit $f : [\mathbb{N}]^{n+1} \to k$ un coloriage. Un ensemble $X \subseteq \mathbb{N}$ est pré-homogène pour la fonction $f$ si la couleur d'un $(n+1)$-uplet de $X$ dépend uniquement des $n$ premiers éléments du $(n+1)$-uplet. Formellement, pour $x_1 < \dots < x_n \in X$ fixé, pour tout $y_1, y_2 \in X$ avec $y_1, y_2 > x_n$, on a

$$f(\{x_1, \dots, x_n, y_1\}) = f(\{x_1, \dots, x_n, y_2\}). \qquad \diamond$$

Les ensembles pré-homogènes forment une passerelle entre les instances de $RT_k^{n+1}$ et celles de $RT_k^n$ dans le sens suivant.

**Fait**

Fixons $n, k \ge 1$, puis un coloriage $f : [\mathbb{N}]^{n+1} \to k$ et enfin un ensemble infini $X$ pré-homogène pour $f$. Soit $g : [\mathbb{N}]^n \to k$ le coloriage qui à $\{x_1, \dots, x_n\} \in [X]^n$ associe $f(\{x_1, \dots, x_n, y\})$ pour n'importe quel $y \in X$ satisfaisant $y > x_n$. Alors, tout ensemble homogène $Y \subseteq X$ pour $g$ est un ensemble homogène pour $f$.

Il s'agit donc de prouver, pour tout coloriage $f : [\mathbb{N}]^{n+1} \to k$, l'existence d'un ensemble infini pré-homogène pour $f$.

**Proposition 2.9.** Étant donné un coloriage $f : [\mathbb{N}]^{n+1} \to k$, il existe un arbre $T \subseteq \mathbb{N}^< f$-calculable, infini à branchement fini, tel que tout chemin est un ensemble infini pré-homogène pour $f$. En particulier, tout degré PA relativement à $f'$ calcule un ensemble infini pré-homogène pour $f$. $\star$

**PREUVE.** L'arbre que nous allons construire est connu sous le nom d'arbre d'Erdős-Radó. Soit $T_0$ l'arbre ne contenant que le nœud 0. Nous allons définir inductivement à chaque étape $s+1$ un arbre $T_{s+1}$ qui contiendra les nœuds de $T_s$, auquel on rajoutera le nœud $\sigma \frown (s+1)$ pour un certain $\sigma \in T_s$.

Aux étapes $0 < s < n$, on met dans l'arbre $T_s$ l'entier $s$ comme fils du nœud $0 \frown 1 \frown 2 \frown \dots \frown s - 1 \in T_{s-1}$. Soit $T_s$ le résultat du calcul à une étape $s \ge n - 1$. À l'étape $s+1$, nous allons parcourir l'arbre $T_s$ depuis sa racine pour trouver le nœud $\sigma \in T_s$ auquel nous rajouterons $s+1$ comme fils de $\sigma$ dans $T_{s+1}$. On définit $\sigma_0 = 0 \frown 1 \frown 2 \frown \dots \frown n - 1 \in T_s$, puis à chaque étape $i$, en supposant $\sigma_i$ définie, on cherche $a$ tel que $\sigma_i a \in T_s$ et tel que $f(\sigma(m_1), \dots, \sigma(m_n), s+1) = f(\sigma(m_1), \dots, \sigma(m_n), a)$ pour tous entiers $m_1 < \dots < m_n < |\sigma_i|$. Si l'on trouve un tel entier $a$, on définit alors $\sigma_{i+1} = \sigma_i a$. Sinon, notre recherche s'arrête là, et l'on définit $T_{s+1}$ comme étant $T_s \cup \{\sigma_i \frown (s+1)\}$.

L'arbre $T = \bigcup_s T_s$ est calculable, et infini car $|T_{s+1}| = |T_s| + 1$ pour tout $s$. Il est aussi à branchement fini, car pour tout nœud $\sigma a \in T$, il n'y a qu'un nombre fini de possibilités pour les combinaisons $f(\sigma(m_1), \dots, \sigma(m_n), a)$ de valeurs, pour tous $m_1 < \dots < m_n < |\sigma|$. Enfin, par construction, il est clair que tout chemin constitue un ensemble infini pré-homogène. ■
La proposition 2.9 permet de transférer la borne supérieure de Jockusch du théorème de Ramsey pour les paires vers le théorème généralisé de Ramsey.

**Corollaire 2.10 (Jockusch [99])**

Soient $n, k \ge 1$. Toute instance $f$ de $RT_k^n$ possède une solution $\Pi_n^0(f)$.

**PREUVE.** On procède par induction sur $n$. Pour $n=1$, toute instance $f$-calculable de $RT_k^1$ admet une solution $f$-calculable, donc en particulier $\Pi_1^0(f)$. Pour $n=2$, il s'agit du théorème 2.5. Supposons le théorème vrai pour $n$ et montrons qu'il est vrai pour $n+1$. Soit $f : [\mathbb{N}]^{n+1} \to k$ un coloriage. Par le théorème 8-4.3, il existe un ensemble $P$ de degré PA relativement à $f'$ tel que $P' \le_T f''$. Par la proposition 2.9, $P$ calcule un ensemble infini $X$ pré-homogène pour $f$. Soit $g : [X]^n \to k$ le coloriage $P$-calculable qui à $\{x_1, \dots, x_n\}$ associe $f(\{x_1, \dots, x_n, y\})$ pour n'importe quel $y \in X$ tel que $y > x_n$. Par hypothèse d'induction relativisée à $P$, il existe un ensemble $\Pi_n^0(g)$ infini $Y \subseteq X$ homogène pour $g$, donc homogène pour $f$. En particulier, $Y$ est $\Pi_{n-1}^0(g')$, donc $\Pi_{n-1}^0(f'')$, et donc $\Pi_{n+1}^0(f)$. $\blacksquare$

La notion d'ensemble pré-homogène donne la possibilité, via la proposition 2.9, de transformer un coloriage sur les $(n+1)$-uplets en un coloriage sur les $n$-uplets calculables en un degré PA relativement à $\emptyset'$. La proposition suivante est une sorte de réciproque partielle.

**Proposition 2.11.** Pour tout coloriage $\emptyset'\text{-calculable } f : [\mathbb{N}]^n \to k$, il existe un coloriage calculable $g : [\mathbb{N}]^{n+1} \to k$ tel que tout ensemble infini homogène pour $g$ est homogène pour $f$. $\star$

**PREUVE.** Soit $f : [\mathbb{N}]^n \to k$ un coloriage $\emptyset'\text{-calculable}$. Par le lemme de limite de Shoenfield (voir le lemme 4-7.2), il existe une approximation $\Delta_2^0$ de la fonction $f$. On peut voir cette approximation $\Delta_2^0$ comme une fonction calculable $g : [\mathbb{N}]^{n+1} \to k$ dont le dernier paramètre correspond au temps d'approximation. Ainsi, pour $\{x_1, \dots, x_n\} \in [\mathbb{N}]^n$,

$$ \lim_z g(\{x_1, \dots, x_n, z\}) = f(\{x_1, \dots, x_n\}). $$

Soit $H$ un ensemble infini homogène pour $g$, de couleur $i < k$. Montrons que $H$ est homogène pour $f$ de couleur $i$. Soit $\{x_1, \dots, x_n\} \in [H]^n$. Soit $y \in H$ suffisamment grand pour que l'on ait

$$ g(\{x_1, \dots, x_n, y\}) = \lim_z g(\{x_1, \dots, x_n, z\}). $$

En particulier, $\lim_z g(\{x_1, \dots, x_n, z\}) = i$, et ainsi $f(\{x_1, \dots, x_n\}) = i$. $\blacksquare$

Notons que la fonction $g$ construite dans la proposition précédente peut posséder des ensembles homogènes finis qui ne sont pas homogènes pour $f$.
De même que la notion d'ensemble pré-homogène a permis d'obtenir une borne supérieure de la complexité du théorème de Ramsey généralisé, la proposition 2.11 permet de transférer la borne inférieure de Jockusch aux coloriages sur les *n*-uplets.

**Corollaire 2.12 (Jockusch [99])**

Pour tout $n \ge 2$, il existe une instance calculable de $RT_2^n$ sans solution $\Sigma_n^0$.

**PREUVE.** Montrons par induction sur $n \ge 2$ que pour tout $Z$, il existe une instance $Z$-calculable de $RT_2^n$ qui ne possède aucune solution $\Sigma_n^0(Z)$. Le cas $n=2$ est une relativisation du théorème 2.6. Supposons vrai le cas $n$ et montrons le cas $n+1$. Soit $Z$ fixé. Par hypothèse d'induction appliquée à $Z'$, il existe une instance $Z'$-calculable $f$ de $RT_2^n$ qui ne possède aucune solution $\Sigma_n^0(Z')$, donc $\Sigma_{n+1}^0(Z)$. Par la proposition 2.11 relativisée, il existe une instance $Z$-calculable $g$ de $RT_2^{n+1}$ telle que tout ensemble infini homogène pour $g$ est homogène pour $f$. En particulier, $g$ ne possède pas de solution $\Sigma_{n+1}^0(Z)$. ■

La situation du théorème de Ramsey vis-à-vis de la hiérarchie arithmétique est donc la suivante.

<figure><img src="image_152.png" /><figcaption>**FIGURE 2.13 –** Théorème de Ramsey dans la hiérarchie arithmétique</figcaption></figure>

Les théorèmes de Jockusch cisèlent avec une précision d'horloger les contours de la complexité arithmétique des solutions possibles pour le théorème de Ramsey généralisé : pour tout $n$, toute instance calculable de $RT_2^n$ a une solution $\Pi_n^0$, et l'une de ces instances n'a pas de solution $\Sigma_n^0$. Pourtant, ces théorèmes ne nous renseignent pas sur la « force calculatoire » du théorème de Ramsey : nous savons créer des instances calculables qui demandent beaucoup de puissance de calcul pour en trouver des solutions,
mais nous ne savons pas créer d'instances calculables dont toutes les solutions possibles ont beaucoup de puissance de calcul. C'est typiquement le genre de chose que nous devons faire pour montrer par exemple l'implication $RCA_0 \vdash \text{RT}_k^n \to ACA_0$.

Prenons l'exemple de $\text{RT}_2^2$, dont les instances calculables admettent toujours des solutions $\Pi_2^0$. Le double saut peut donc toujours calculer des solutions de $\text{RT}_2^2$. Serait-il possible de construire une instance dont toutes les solutions calculent le double saut ? Jockusch a répondu à cette première question par la négative, en montrant qu'un degré $\text{PA}(\emptyset')$ était en fait suffisant.

**Théorème 2.14 (Jockusch [99])**

Pour tout $n, k \ge 1$ et tout coloriage $f : [\mathbb{N}]^n \to k$, tout degré $\text{PA}$ relativement à $f^{(n-1)}$ calcule un ensemble infini homogène pour $f$.

**PREUVE.** Par induction sur $n \ge 1$. Pour $n=1$, $f$ calcule un ensemble infini homogène pour $f$. Tout degré $\text{PA}$ relativement à $f$ calcule $f$, donc calcule un ensemble infini homogène pour $f$.

Supposons que cela soit le cas pour $n \ge 1$. Soit $f : [\mathbb{N}]^{n+1} \to k$ un coloriage, et soit $P_0$ un ensemble $\text{PA}(f')$ tel que $P_0' \le_T f''$ et soit aussi $P_1$ un ensemble $\text{PA}(f^{(n)})$. Par la proposition 2.9, $P_0$ calcule un ensemble infini $X$ pré-homogène pour $f$. Soit $g : [X]^n \to k$ le coloriage $P_0$-calculable qui à $\{x_1, \dots, x_n\}$ associe $f(\{x_1, \dots, x_n, y\})$ pour n'importe quel $y \in X$ tel que $y > x_n$. En particulier, $P_0^{(n-1)} \le_T f^{(n)}$, donc $P_1$ est $\text{PA}(P_0^{(n-1)})$ et donc $\text{PA}(g^{(n-1)})$. Par hypothèse d'induction, $P_1$ calcule un ensemble infini $H \subseteq X$ homogène pour $g$, donc homogène pour $f$. $\blacksquare$

En particulier, un degré $\text{PA}(\emptyset')$ permet de calculer une solution de toute instance calculable de $\text{RT}_2^2$. À l'inverse, est-il possible de trouver une instance de $\text{RT}_2^2$ dont toutes les solutions sont de degré $\text{PA}(\emptyset')$ ? Jockusch n'a pu le montrer que pour les instances de $\text{RT}_2^3$ et non $\text{RT}_2^2$. Nous verrons de fait dans la section 4 qu'il est impossible « d'encoder » de la puissance de calcul dans les solutions possibles d'une instance calculable de $\text{RT}_2^2$. C'est en revanche le cas pour celles de $\text{RT}_2^3$ :

**Exercice 2.15.** $(\star)$ Construire une instance $\emptyset'$-calculable de $\text{RT}_2^2$ dont toutes les solutions calculent $\emptyset'$. En déduire qu'il existe des instances calculables de $\text{RT}_2^3$ dont toutes les solutions calculent $\emptyset'$.

Indication.– Utiliser la notion de modulus (voir la définition 4-7.7). ◇

Il est possible de renforcer l'exercice précédent, et d'encoder dans les instances calculables de $\text{RT}_2^3$, la puissance nécessaire au calcul d'ensembles pré-homogènes.
**Théorème 2.16 (Hirschfeldt et Jockusch [88])**

Il existe un coloriage calculable $f : [\mathbb{N}]^3 \to 2$ tel que tout ensemble infini pré-homogène pour $f$ est de degré PA relativement à $\emptyset'$.

**PREUVE**

Soit $\Phi_0, \Phi_1, \dots$ une énumération de toutes les fonctionnelles Turing à valeurs dans $\{0, 1\}$. On peut supposer sans perte de généralité que $\Phi_e(\emptyset'_s, e)[s]$ renvoie une valeur pour n'importe quel temps de calcul $s$ (en assignant par exemple 0 si $\Phi_e(\emptyset'_s, e)[s] \uparrow$). Soit $f : [\mathbb{N}]^3 \to 2$ défini pour tous $m < s < t$ par $f(\{m, s, t\}) = 1$ si pour tout $e < m$, $\Phi_e(\emptyset'_s, e)[s] = \Phi_e(\emptyset'_t, e)[t]$. Si-non, $f(\{m, s, t\}) = 0$. Soit $X$ un ensemble infini pré-homogène pour $f$. Soit $g : \mathbb{N} \to 2$ la fonction qui, sur $e$, cherche un entier $m \in X$ tel que $e < m$, et des entiers $s, t \in X$ tels que $m < s < t$ et $\Phi_e(\emptyset'_s, e)[s] = \Phi_e(\emptyset'_t, e)[t]$, et renvoie $1 - \Phi_e(\emptyset'_s, e)[s]$. Notons qu'une telle recherche aboutit forcément, car il n'y a que deux valeurs possibles pour chaque $\Phi_e$.

Par pré-homogénéité de $X$, $g(e) = 1 - \Phi_e(\emptyset'_t, e)[t]$ pour une infinité de $t \in X$. La fonction $g$ est totale $X$-calculable. Montrons que $g$ est une fonction DNC relativement à $\emptyset'$. Soit $e$ tel que $\Phi_e(\emptyset', e) \downarrow$. Alors, $\lim_{t \in X} \Phi_e(\emptyset'_t, e)[t]$ existe, donc $g(e) = 1 - \Phi_e(\emptyset', e)$. Toute fonction DNC relativement à $\emptyset'$ à valeurs dans $\{0, 1\}$ est de degré PA relativement à $\emptyset'$.

Le théorème précédent se reformule par $KL \leq_c RT_2^3$ dans le langage des réductions calculatoires.

## 2.4. Mathématiques à rebours

L'analyse purement calculatoire effectuée par Jockusch [99] a été formalisée par Simpson [203] dans l'arithmétique du second ordre pour en déduire la puissance logique du théorème de Ramsey en mathématiques à rebours. Les preuves du théorème 2.17 sont essentiellement les constructions vues précédemment, mais analysées avec soin pour s'assurer que l'on n'utilise que les axiomes disponibles dans RCA₀.

**Théorème 2.17 (Jockusch [99] et Simpson [203])**

Pour tout $n \geq 3$, on a l'équivalence $RCA_0 \vdash \forall k RT_k^n \leftrightarrow ACA_0$.

**PREUVE.** Montrons par induction sur $n \in \mathbb{N}$ que $ACA_0 \vdash \forall k RT_k^n$.

On a $ACA_0 \vdash \forall k RT_k^1$, comme nous le verrons dans la proposition 3.1. Supposons que $ACA_0 \vdash RT_k^n$. Soit $f : [\mathbb{N}]^{n+1} \to k$ une instance de $RT_k^{n+1}$. Soit $T \subseteq \mathbb{N}^< \text{ l'arbre d'Erdős-Radó de la proposition 2.9. Il est clair que la définition de } T \text{ peut être faite de manière primitive récursive relativement à } f. \text{ D'après le théorème 23-4.6, l'induction } \Sigma_1^0 \text{ suffit pour montrer que la fonction qui sur } n \text{ renvoie le nœud } \sigma \frown n \in T \text{ est totale, et}$
donc que l'arbre admet une définition $\Delta_1^0$: il existe donc par le schéma de compréhension $\Delta_1^0$. Par définition, il est infini, et $\text{RCA}_0$ suffit à prouver qu'il est infini à branchement fini. Par le lemme de König, prouvable dans $\text{ACA}_0$, il existe un chemin $P \in [T]$, donc un ensemble infini pré-homogène pour $f$. Soit $g: [P]^n \to k$ le coloriage qui à $\{x_1, \dots, x_n\}$ associe $f(\{x_1, \dots, x_n, y\})$ pour n'importe quel $y \in X$ tel que $y > x_n$. Le coloriage $g$ existe par le schéma de compréhension $\Delta_1^0$. Par hypothèse d'induction, et par la proposition 2.2, $\text{ACA}_0$ montre l'existence d'un ensemble infini $H \subseteq P$ homogène pour $g$. En particulier, $H$ est homogène pour $f$.

Montrons que $\text{RCA}_0 + \text{RT}_2^3 \vdash \forall X \exists Y Y = X'$.

Soit $X$ un ensemble, et soit $f: [N]^3 \to 2$ la fonction définie pour $x < s < t$ par $f(\{x, s, t\}) = 1$ si, et seulement si,

$$ \forall e < x ((\Phi_e(X, e)[s] \downarrow \wedge \Phi_e(X, e)[t] \downarrow) \lor (\Phi_e(X, e)[s] \uparrow \wedge \Phi_e(X, e)[t] \uparrow)). $$

Soit $H$ un ensemble infini homogène pour $f$. Montrons que $H$ est homogène de couleur 1. Soit $x \in H$, et soit $g: H \to 2^x$ définie par $g(s) = \langle a_e : e < x \rangle$ où $a_e = 1$ si $\Phi_e(X, e)[s] \downarrow$, et $a_e = 0$ sinon. $\text{RCA}_0$ prouve que $g$ n'est pas injective, donc il existe $s < t \in H$ tels que $g(s) = g(t)$. En particulier, $f(\{x, s, t\}) = 1$. Soit $p_H: N \to N$ la fonction principale de $H$. Alors, l'ensemble $Y = \{e \in N : \Phi_e(X, e)[p_H(e)] \downarrow\}$ existe par le schéma de compréhension $\Delta_1^0$, et $Y = X'$. ■

Notons que l'induction sur $n$ dans la preuve du théorème 2.14 se fait à l'extérieur de $\text{ACA}_0$. Il s'agit en effet d'une induction sur une formule du second ordre. Le corollaire 2.12, combiné au théorème de Jockusch et Solovay (voir le théorème 22-8.1), nous permet de montrer que l'énoncé $\forall n \text{RT}_2^n$ n'est pas prouvable dans $\text{ACA}_0$.

**Proposition 2.18.** On a $\text{ACA}_0 \not\leq \forall n \text{RT}_2^n$.

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

**PREUVE.** Supposons que $\text{ACA}_0 \vdash \forall n \text{RT}_2^n$. Par le théorème de Jockusch et Solovay (voir le théorème 22-8.1), il existe une borne $k \in N$ telle que $\text{ACA}_0$ prouve que pour tout $n \in N$, toute instance $f: [N]^n \to 2$ admet une solution $\Sigma_k^0(f)$. En particulier, pour $n = k$, par le corollaire 2.12, il existe une instance calculable $f: [N]^k \to 2$ sans solution $\Sigma_k^0$. Contradiction! ■

Comme expliqué dans la section 22-8.1, une telle séparation se fait nécessairement dans les modèles non standard puisque $\text{ACA}'_0$ et $\text{ACA}_0$ partagent les mêmes $\omega$-modèles. En adaptant la preuve du théorème 2.14, McAloon [153] a prouvé que l'énoncé $\forall n \text{RT}_2^n$ était équivalent à $\text{ACA}'_0$.

L'équivalence du théorème 2.17 n'est pas satisfaisante du point de vue de la calculabilité, dans la mesure où elle n'est pas sensible aux niveaux de la
hiérarchie arithmétique. Le corollaire 2.12 montre que plus la taille des $n$-uplets coloriés est grande, plus il faut de la puissance calculatoire pour trouver des solutions. La preuve dans $\text{RCA}_0$ de $\text{RT}_2^n \to \text{RT}_2^{n+1}$ lorsque $n \ge 3$ s'effectue en plusieurs étapes : une première instance de $\text{RT}_2^n$ permet de calculer un ensemble infini pré-homogène pour l'instance de $\text{RT}_2^{n+1}$, ce qui la réduit en une seconde instance de $\text{RT}_2^n$. La réduction calculatoire, sensible au nombre d'applications, permet de rendre compte de cette différence.

**Proposition 2.19.** Pour tout $n \ge 1$, on a $\text{RT}_2^{n+1} \not\le_c \text{RT}_2^n$.

★

**PREUVE.** Par le corollaire 2.12, il existe une instance $f$ calculable de $\text{RT}_2^{n+1}$ sans solution $\Sigma_{n+1}^0$. Pour toute instance $g$ de $\text{RT}_2^n$ calculable en $f$, par le corollaire 2.10, $g$ admet une solution $H \Pi_n^0(f)$, donc $\Pi_n^0$. Tout ce que calcule $H$ est $\Delta_{n+1}^0$, et donc aussi $\Sigma_{n+1}^0$. Donc cette solution, $H$ de $g$ ne calcule (et donc ne $f$-calcule) pas de solution de $f$. ■

Du point de vue des mathématiques à rebours, le théorème de Ramsey pour les singletons est prouvable dans $\text{RCA}_0$, et le théorème de Ramsey pour les $n$-uplets est équivalent à $\text{ACA}_0$ lorsque $n \ge 3$. Le cas du théorème de Ramsey pour les paires est plus intriguant. Par le théorème 2.17, $\text{RT}_2^2$ est prouvable dans $\text{ACA}_0$, et par le corollaire 2.7 il n'est pas prouvable dans $\text{WKL}_0$. Qu'en est-il des réciproques ? Une manière de prouver que le théorème de Ramsey pour les paires implique $\text{ACA}_0$ serait d'adapter la preuve du théorème 2.16 pour construire un coloriage calculable $f : [N]^2 \to 2$ dont tous les ensembles homogènes calculent le problème de l'arrêt, et de vérifier que l'argument se formalise dans $\text{RCA}_0$. David Seetapun [195] réussit à montrer en 1995 qu'une telle chose est impossible. En 2012, Lu Liu [146] montrera qu'il est également impossible de construire une instance calculable de $\text{RT}_2^2$ dont toutes les solutions sont de degré PA. Ces deux résultats majeurs passent par une bonne compréhension du principe infini des tiroirs.

## 3. Principe infini des tiroirs

La notion d'ensemble pré-homogène $P$ permet de réduire une instance calculable de $\text{RT}_k^{n+1}$ en une instance $P$-calculable de $\text{RT}_k^n$. En particulier, le théorème de Ramsey pour les paires est réduit à une instance non calculable du principe infini des tiroirs. Il est donc naturel d'étudier les instances non calculables de $\text{RT}_k^1$.

Nous marquons donc une pause dans l'analyse calculatoire du théorème de Ramsey pour nous pencher sur son cas de base : le principe infini des tiroirs. Nous allons voir que ce principe, si élémentaire soit-il, présente tout de même quelques subtilités, et que l'analyse d'instances arbitraires de $\text{RT}_k^1$ est loin d'être triviale.
**3.1. Nombre de couleurs et uniformité**

Nous avons vu avec la proposition 2.3 et la proposition 2.4 que $\text{RCA}_0 \vdash \text{RT}_k^1$ pour tout entier standard $k$. En particulier, $\text{RT}_k^1$ est calculatoirement vrai, au sens où toute instance calcule sa propre solution.

En revanche, l'induction restreinte de RCA₀ n'est pas suffisante pour en déduire RCA₀ $\vdash \forall k \text{RT}_k^1$. Nous le montrons formellement avec la proposition suivante, via l'équivalence dans RCA₀ de $\forall k \text{RT}_k^1$ et du principe de collection pour les formules $\Pi_1^0$, qui comme nous l'avons vu n'est pas prouvable dans RCA₀.

**Proposition 3.1 (Hirst [91]).** On a l'équivalence

$$ \text{RCA}_0 \vdash \forall k \text{RT}_k^1 \leftrightarrow \text{B}\Pi_1^0. \quad \star $$

**PREUVE**

$\text{B}\Pi_1^0 \rightarrow \forall k \text{RT}_k^1$. Soit $f: \mathbb{N} \rightarrow k$ une instance de $\forall k \text{RT}_k^1$. Soit $F(x, y)$ la formule $\Pi_1^0 \forall z > y f(z) \neq x$. S'il existe $x < k$ tel que pour tout $y, F(x, y)$ est faux, alors l'ensemble $\{z \in \mathbb{N} : f(z) = x\}$ est infini, et existe par le schéma de compréhension $\Delta_0^0$. Sinon, pour tout $x < k$, il existe $y$ tel que $F(x, y)$ est vrai. Par $\text{B}\Pi_1^0$, il existe $p \in \mathbb{N}$ tel que pour tout $x < k$, il existe $y < p$ tel que $F(x, y)$ est vrai. Soit $x$ la couleur de $f(p+1)$. Alors, $p+1$ contredit $F(x, p)$.

$\forall k \text{RT}_k^1 \rightarrow \text{B}\Pi_1^0$. Soit $F(x, y) = \forall z G(x, y, z)$ une formule $\Pi_1^0$, et soit $k \in \mathbb{N}$ tels que $\forall x < k \exists y F(x, y)$. Soit $f: \mathbb{N} \rightarrow k$ définie par $f(t) = n$ pour le plus petit entier $n$ tel que $\forall x < k \exists y < n \forall z < t G(x, y, z)$, si un tel $n$ existe; sinon, $f(t) = t$. S'il existe un ensemble infini $H$ homogène pour $f$ de couleur $\ell$ pour un entier $\ell \in \mathbb{N}$, alors $\forall x < k \exists y < \ell \forall z G(x, y, z)$.

S'il n'existe pas d'ensemble infini $H$ homogène pour $f$, alors par $\forall k \text{RT}_k^1$, l'image de $f$ est non bornée. Par compréhension $\Delta_0^0$, il est possible de construire une suite $(t_i)_{i \in \mathbb{N}}$ strictement croissante telle que $f(t_i) < f(t_{i+1})$ pour tout $i \in \mathbb{N}$. Soit $g: \mathbb{N} \rightarrow \mathbb{N}$ défini comme suit : $g(i)$ est le plus petit $x < k$ tel que $\forall y < f(t_i) - 1 \exists z < t_i \neg G(x, y, z)$. Soit $S$ un ensemble infini homogène pour $g$, de couleur $x_0$. Soit $y \in \mathbb{N}$. Comme $S$ est infini, il existe $i \in S$ tel que $f(t_i) - 1 > y$, donc $\exists z < t_i \neg G(x_0, y, z)$. Ainsi, $\forall y \exists z \neg G(x_0, y, z)$, d'où contradiction.

■

Notons que la preuve de $\text{RCA}_0 \vdash \forall k \text{RT}_k^1 \rightarrow \text{B}\Pi_1^0$ fait intervenir deux instances de $\forall k \text{RT}_k^1$.

Nous voyons à présent que le théorème de Ramsey pour les paires est suffisant pour montrer $\forall k \text{RT}_k^1$ dans RCA₀. Nous sommes ici dans un cas typique où un énoncé qui porte sur le second ordre a des conséquences sur le premier ordre. Cela vient du fait que les solutions d'une instance de $\text{RT}_2^2$ peuvent être utilisées comme paramètres dans le schéma d'induction $\Sigma_1^0$.
**Proposition 3.2.** Pour tout $n \ge 1$, $\text{RCA}_0 \vdash \text{RT}_2^{n+1} \rightarrow \forall k \text{RT}_k^n$. En particulier, $\text{RCA}_0 \vdash \text{RT}_2^2 \rightarrow \text{B}\Pi_1^0$.

★

**PREUVE.** Soit $f : [\mathbb{N}]^n \rightarrow k$ une instance de $\text{RT}_k^n$ pour un $k \in \mathbb{N}$, et soit $g : [\mathbb{N}]^{n+1} \rightarrow 2$ définie pour tout $F \in [\mathbb{N}]^{n+1}$ par $g(F) = 1$ ssi $F$ est homogène pour $f$. Soit $H$ un ensemble infini homogène pour $g$.

Montrons que $G$ est homogène pour $g$ de couleur 1. Par le théorème fini de Ramsey (prouvable dans $\text{RCA}_0$, voir le théorème 1.10 dans Hájek et Pudlák [81]), il existe un sous-ensemble $A \in [H]^{n+1}$ homogène pour $f$. Donc, $g(A) = 1$.

Montrons que $H$ est homogène pour $f$. Soient $A, B \in [H]^n$. Alors, il existe une suite finie d'ensembles $A_0, \dots, A_\ell \in [H]^{n+1}$ telle que $A \subseteq A_0, B \subseteq A_\ell$ et pour tout $i < \ell - 1$, $|A_i \cap A_{i+1}| \ge n$. Comme $A_0, \dots, A_\ell \in [H]^{n+1}$, alors ils sont tous $f$-homogènes, et comme $|A_i \cap A_{i+1}| \ge n$, alors $A_i$ et $A_{i+1}$ sont $f$-homogènes pour la même couleur. Il s'ensuit que $f(A) = f(B)$. Pour $n = 1$, $\text{RCA}_0 \vdash \text{RT}_2^2 \rightarrow \forall k \text{RT}_k^1$, donc $\text{RCA}_0 \vdash \text{RT}_2^2 \rightarrow \text{B}\Pi_1^0$ par 3.1. ■

La question de savoir si $\text{RCA}_0 + \text{RT}_2^2$ permet de montrer d'autres énoncés du premier ordre que $\text{B}\Pi_1^0$ est toujours ouverte.

**Question 3.3.** $\text{RT}_2^2$ est-il une extension conservative de $\text{RCA}_0 + \text{B}\Pi_1^0$ pour les formules arithmétiques ?

★

Un progrès a été fait dans cette direction par Patey et Yokoyama, qui ont montré que $\text{RCA}_0 + \text{RT}_2^2$ ne pouvait montrer aucun énoncé $\Pi_3^0$ qui n'était pas déjà démontrable dans $\text{RCA}_0$.

**Théorème 3.4 (Patey, Yokoyama [173])**

Le système $\text{RT}_2^2$ est une extension conservative de $\text{RCA}_0$ pour les formules $\Pi_3^0$.

Le lecteur pourra vérifier qu'il n'y a pas de contradiction avec le fait que $\text{RCA}_0 + \text{RT}_2^2$ implique $\text{B}\Pi_1^0$.

**Exercice 3.5.** (★) Montrer qu'une instance de $\text{B}\Pi_1^0$ est un énoncé $\Sigma_4^0$, et prouvablement équivalent à un énoncé $\Sigma_3^0$ dans $\text{RCA}_0$. ◇

Recentrons-nous à présent sur les $\omega$-modèles. La preuve de $\text{RCA}_0 \vdash \text{RT}_2^1$ procède par analyse de cas sur les couleurs : soit la couleur 0 apparaît infini-ment souvent, soit non auquel cas la couleur 1 apparaît infiniment souvent. En particulier, le choix de la couleur n'est pas uniforme de manière calculable, car il résulte de la réponse à une question $\Pi_2^0$. La réduction Weihrauch permet de traduire cette non-uniformité. Brattka et Rakotoniaina [25] et Hirschfeldt et Jockusch [88] ont prouvé de manière indépendante la proposition suivante.
**Proposition 3.6 ([25],[88]).** Pour tout $k \ge 1$, $\mathrm{RT}_{k+1}^1 \ll_W \mathrm{RT}_k^1$.

⋆

**Préuve.** Supposons que $\mathrm{RT}_{k+1}^1 \le_W \mathrm{RT}_k^1$ via des fonctionnelles $\Phi$ et $\Psi$. Soit $P(n)$ le prédicat $\ll$ il existe une suite $\sigma_0 < \dots < \sigma_n \in (k+1)^{<\mathbb{N}}$ de segments initiaux de l'instance de $\mathrm{RT}_{k+1}^1$, une suite d'ensembles finis non vides $F_0, \dots, F_{n-1}$ de solutions partielles pour les instances partielles $\Phi(\sigma_0), \dots, \Phi(\sigma_{n-1})$ de $\mathrm{RT}_k^1$, de couleurs respectives et deux à deux distinctes $i_0, \dots, i_{n-1} \in \{0, \dots, k-1\}$, telles que pour tout $s < n$, il existe $x$ pour lequel $\sigma_{s+1}(x) = s$ et $\Psi(\sigma_{s+1} \oplus F_s, x) \downarrow= 1$. On a $P(0)$ avec la chaîne $\sigma_0 = \epsilon$. Montrons que l'on a $P(n) \to P(n+1)$ pour tout $n \le k$, ce qui implique une contradiction pour $P(k+1)$, car on a alors une suite de couleurs deux à deux différentes $i_0, \dots, i_k \in \{0, \dots, k-1\}$.

Supposons que $P(n)$ est vérifié avec $\sigma_0, \dots, \sigma_n, F_0, \dots, F_{n-1}$ et $i_0, \dots, i_{n-1}$. Soit $H$ une solution pour l'instance $\Phi(\sigma_n \frown n^\infty)$ de $\mathrm{RT}_k^1$, et soit $i$ sa couleur. On peut supposer que $\min H > |\sigma_n|$.

Si $i = i_s$ pour un $s < n$, alors $F_s \cup H$ est toujours homogène. En particulier, $\Psi((\sigma_n \frown n^\infty) \oplus (F_s \cup H))$ est infini, si bien qu'il doit être homogène pour l'ensemble $\sigma_n \frown n^\infty$ de couleur $n$. Cependant, par hypothèse d'induction, il existe $x$ tel que $\sigma_{s+1}(x) = s$ et $\Psi(\sigma_{s+1} \oplus F_s, x) \downarrow= 1$, donc $\Psi((\sigma_n \frown n^\infty) \oplus (F_s \cup H))$ contient à la fois des éléments de couleur $n$ et $s$, contradiction. Donc, $i$ est différent de $i_s$ pour tout $s < n$.

Soit $i_n = i$. Soit $F_n$ un ensemble fini non vide homogène pour $\Phi(\sigma_n \frown n^\infty)$ de couleur $i$, et soit $x \ge |\sigma_n|$ tel que $\Psi((\sigma_n \frown n^\infty) \oplus F_n, x) \downarrow= 1$. Soit enfin $\sigma_{n+1}$ un segment initial de $\sigma_n \frown n^\infty$ suffisamment long pour que $F_n$ soit solution partielle de $\Phi(\sigma_{n+1})$ et pour que $\Psi(\sigma_{n+1} \oplus F_n, x) \downarrow= 1$. On a bien $P(n+1)$. ■

**Exercice 3.7.** Vérifier que la preuve de la proposition 3.2 est aussi une preuve de $\mathrm{RT}_k^n \le_W \mathrm{RT}_2^{n+1}$ pour tous $n, k \ge 1$. ◇

## 3.2. Principe infini des tiroirs et évitement de cônes

Nous nous attaquons à présent aux instances non calculables de $\mathrm{RT}_2^1$. Le but de cette section est de démontrer le théorème suivant.

**Théorème 3.8 (Dzhafarov et Jockusch [54])**

Pour tout ensemble $A$ et tout ensemble $C$ non calculable, il existe un ensemble infini $H \subseteq A$ ou $H \subseteq \mathbb{N} \setminus A$ tel que $C \ll_T H$.
Nous verrons que ce théorème constitue une étape clef pour montrer que $RT_2^2$ préserve la propriété de faiblesse donnée par $\{X : X \not\supseteq_T C\}$ pour tout $C$ non calculable (voir la définition 24-1.6). Via les développements de la section 24-1.1, cela nous permettra en particulier de construire un $\omega$-modèle de $\mathrm{RCA}_0 + RT_2^2$ ne contenant pas $\emptyset'$, et donc d'établir le théorème 4.14 de Seetapun à venir, qui sépare $RT_2^2$ de $\mathrm{ACA}_0$. Notons que nous ne suivons pas la preuve originale de Seetapun, qui est plus directe, mais aussi moins informative, notamment sur la faiblesse combinatoire des instances arbitraires du problème $RT_2^1$.

Nous invitons le lecteur à réfléchir à la signification du théorème ci-dessus, en commençant peut-être par le mettre en parallèle avec quelque chose que nous avons déjà utilisé dans la preuve du lemme 14-4.6, et que nous donnons ci-après en exercice.

**Exercice 3.9.** (⋆) Soit $C$ un ensemble quelconque. Montrer qu'il existe un ensemble infini $A$ dont tous les sous-ensembles infinis permettent de calculer $C$. ◇

La preuve du théorème 3.8 se fait via une notion de forcing définie par Dzhafarov et Jockusch, qui consiste en une variante effective du *forcing de Mathias*, utilisé au départ en théorie des ensembles pour construire des modèles de ZFC dans lesquels pour n'importe quelle classe $C \subseteq 2^N$, il existe un ensemble infini dont tous les sous-ensembles infinis sont dans $C$ ou dans $2^N \setminus C$ ([151] et [152], voir [106]). Commençons par définir quelques notations qui en simplifieront la présentation.

**Notation**

On considérera les chaînes $\sigma \in 2^{<N}$ comme des ensemble finis d'entiers via les notations suivantes.

1. La chaîne $\sigma \cup \tau$ est la chaîne de taille $\max(|\sigma|, |\tau|)$ vérifiant que $\sigma \cup \tau(n) = 1$ ssi $\sigma(n) = 1$ ou $\tau(n) = 1$.

2. La chaîne $\tau - \sigma$ est la chaîne de taille $|\tau|$ à laquelle on enlève les 1 de $\sigma$. On a donc :

$$ (\tau - \sigma)(n) = 1 \text{ ssi } \tau(n) = 1 \text{ et } \sigma(n) = 0, \text{ pour } n < \min(|\sigma|, |\tau|), $$

et $(\tau - \sigma)(n) = 1 \text{ ssi } \tau(n) = 1$, pour $n$ tel que $|\tau| > n \ge \min(|\sigma|, |\tau|)$.

3. L'ensemble $X - \sigma$ est l'ensemble $X$ auquel on enlève les $n < |\sigma|$ tels que $\sigma(n) = 1$.

4. Le prédicat $\sigma \subseteq X$ signifie $\sigma(n) = 1$ implique $X(n) = 1$.

Le forcing de Mathias, tel qu'utilisé en combinatoire, est défini comme suit.
**Définition 3.10.** Une condition de Mathias est un couple $(\sigma, X)$ tel que

1. $\sigma \in 2^{<\mathbb{N}}$;

2. $X$ est un sous-ensemble infini de $\mathbb{N}$;

3. $X \cap \{0, \dots, |\sigma|\} = \emptyset$.

On dira pour deux conditions de Mathias $(\tau, Y)$ et $(\sigma, X)$ que $(\tau, Y)$ étend $(\sigma, X)$, et l'on écrira $(\tau, Y) \le (\sigma, X)$ si $\tau \supseteq \sigma$, $Y \subseteq X$ et $\tau - \sigma \subseteq X$. L'ordre partiel des conditions de Mathias peut être enrichi en un forcing de Cantor en interprétant tout filtre maximal $F$ par $\dot{F}$ comme étant l'unique élément de $\bigcap_{(\sigma,X) \in F}[\sigma]$. $\diamond$

Étant donné une condition de Mathias $(\sigma, X)$, on note $[\sigma, X] \in$ l'ensemble des filtres maximaux contenant $(\sigma, X)$, et $[\sigma, X] = \{\dot{F} : F \in [\sigma, X] \epsilon \}$. On a alors

$$[\sigma, X] = \{G \in \mathcal{P}(\mathbb{N}) : \sigma \prec G \text{ et } G - \sigma \subseteq X\}.$$

Ainsi, une condition de Mathias $(\sigma, X)$ peut être considérée comme un raffinement du forcing de Cohen. En effet, la partie finie $\sigma$ est un segment initial de l'élément construit, ce qui permet de fixer des propriétés $\Sigma_1^0$. On y ajoute un réservoir infini $X$ des valeurs que l'on autorise à ajouter au segment initial. Le réservoir ne contient que de l'information négative, au sens où si $G \in [\sigma, X]$ et $n \in X$, alors il n'est pas garanti que $n \in G$. En revanche, si $n \notin X$, alors $n \notin G$.

**Définition 3.11.** Soit $(\sigma, X)$ une condition de Mathias et soit $\Phi_e$ une fonctionnelle Turing.

1. $(\sigma, X) \Vdash \Phi_e(G, n) \downarrow = m$ si $\Phi_e(\sigma, n) \downarrow = m$.

2. $(\sigma, X) \Vdash \Phi_e(G, n) \uparrow$ si $\forall \tau \subseteq X \Phi_e(\sigma \cup \tau, n) \uparrow$.

$\diamond$

Nous sommes maintenant prêts à définir la notion de forcing de Dzhafarov-Jockusch, qui présente une certaine difficulté conceptuelle supplémentaire par rapport à un forcing classique : étant donné $A$ quelconque et $C$ non calculable, on ne saura pas à l'avance si l'ensemble générique $G \not\supseteq_T C$ que l'on cherche à construire sera un sous-ensemble infini de $A$ ou de $\mathbb{N} \setminus A$. On va donc construire en parallèle deux génériques $G^0, G^1$, l'un d'eux étant inclus dans $A$ et l'autre dans $\mathbb{N} \setminus A$.

**Définition 3.12.** Soit $A^0 \sqcup A^1$ une 2-partition de $\mathbb{N}$ et soit $\mathcal{I}$ un idéal de Scott. Une condition de Dzhafarov-Jockusch pour $A^0 \sqcup A^1$ et $\mathcal{I}$ est un triplet $(\sigma_0, \sigma_1, X)$ tel que

(1) $(\sigma_i, X)$ est une condition de Mathias pour tout $i < 2$;

(2) $\sigma_i \subseteq A^i$ pour tout $i < 2$;
(3) $X \in \mathcal{I}$.

Une condition $(\tau_0, \tau_1, Y)$ étend $(\sigma_0, \sigma_1, X)$ si $(\tau_i, Y)$ étend $(\sigma_i, X)$ au sens de Mathias pour chaque $i < 2$. ◇

Une condition de Dzhafarov-Jockusch dépendra par conséquent d'une partition $A^0 \sqcup A^1$ et d'un idéal de Scott $\mathcal{I}$.

**Notation**

Dans la suite de la preuve, on représentera les 2-partitions selon le contexte par $A, \mathbb{N} \setminus A$ pour un ensemble $A$, ou bien sous la forme de deux ensembles $A^0, A^1$, où $A^0$ est une notation pour $A$ et $A^1$ une notation pour $\mathbb{N} \setminus A$.

Pour construire un générique $G \not\cong_T C$ pour un certain ensemble $C$ non calculable fixé, on utilisera un idéal de Scott ne contenant pas $C$.

Un filtre maximal $F$ s'interprète en deux ensembles $\dot{F} = (G^0, G^1)$ définis pour tout $i < 2$ par $\{G^i\} = \bigcap_{(\sigma_0, \sigma_1, X) \in F} [\sigma_i]$. Pour une condition $(\sigma_0, \sigma_1, X)$, on définit

$$[\sigma_0, \sigma_1, X] = \{ (G^0, G^1) : \forall i < 2 \ \sigma_i \preceq G^i \wedge G^i - \sigma_i \subseteq X \}.$$

Ainsi, pour tout filtre maximal $F$, on a

$$\{\dot{F}\} = \bigcap_{(\sigma_0, \sigma_1, X) \in F} [\sigma_0, \sigma_1, X].$$

**Relation de forcing**

Notons ici une subtilité : pour une notion de forcing de Cantor $(\mathbb{P}, \leqslant)$ et pour $c \in \mathbb{P}$, nous avions défini $[c]_c$ comme la classe des filtres maximaux contenant $c$, et $[c] = \{\dot{F} : F \in [c]\}$. La définition de $[c]$ pour le forcing de Dzhafarov-Jockusch est différente. En effet, pour tout filtre maximal $F$, on a $\dot{F} \in [\sigma_0, \sigma_1, X]$ mais l'inverse n'est pas vrai, et il existe des paires $(G^0, G^1) \in [\sigma_0, \sigma_1, X]$ telles que $G^i \not\subseteq A^i$, tandis que c'est nécessairement le cas pour $\dot{F}$, par (2) de la définition d'une condition.

Nous imposerons également l'hypothèse suivante qu'il faudra justifier pour toute application du forcing de Dzhafarov-Jockusch.

Pour tout $i < 2$, il n'existe pas d'ensemble infini $H \subseteq A^i$ dans $\mathcal{I}$. (H1)

L'idée est que les éléments de $\mathcal{I}$ vont satisfaire la propriété que l'on veut montrer, typiquement ne pas calculer un ensemble $C$ fixé. Il s'ensuit que si un ensemble infini $H \subseteq A^i$ est dans $\mathcal{I}$, alors $H$ est la solution désirée, et il n'y a plus besoin de faire de construction. La supposition (H1) permet de prouver que les deux ensembles produits par un filtre suffisamment
générique pour le forcing de Dzhafarov-Jockusch sont infinis, comme le montre le lemme suivant.

**Lemme 3.13.** Supposons (H1). Soit $c = (\sigma_0, \sigma_1, X)$ une condition et soit $i < 2$. Il existe une extension $(\tau_0, \tau_1, Y)$ de $c$ et un entier $n > |\sigma_i|$ tels que $n \in \tau_i$. $\star$

PREUVE. Si $X \cap A^i$ est vide, alors $X \subseteq A^{1-i}$; or, $X \in \mathcal{I}$, ce qui contre-dit (H1). Ainsi, il existe $n \in X \cap A^i$. Soient $\tau_i = \sigma_i \cup \{n\}$ et $\tau_{1-i} = \sigma_{1-i}$. Alors, $(\tau_0, \tau_1, X \setminus \{0, \dots, n-1\})$ est une extension de $(\sigma_0, \sigma_1, X)$ telle que $n \in \tau_i$. ■

Nous avons vu dans la section 11-4 que les propriétés calculatoires d'un ensemble produit par un filtre suffisamment générique étaient très liées à l'existence d'une question de forcing avec de bonnes propriétés définitionnelles. Rappelons qu'une question de forcing pour un forcing de Cantor $\mathbb{P}$ est une relation $c?\vdash \mathcal{R}$, où $c \in \mathbb{P}$ et $\mathcal{R}$ est un contrat, telle que si $c?\vdash \mathcal{R}$ est vraie, alors il existe une extension $d \le c$ pour laquelle $d \vdash \mathcal{R}$, et sinon, il existe une extension $d \le c$ pour laquelle $d \vdash \neg \mathcal{R}$. La situation du forcing de Dzhafarov-Jockusch est un peu plus complexe, car deux ensembles distincts sont créés parallèlement. Il serait naturel de définir une question de forcing pour chaque ensemble construit :

$$ (\sigma_0, \sigma_1, X) ?\vdash^i \exists n \Phi_e(G, n) \downarrow $$

s'il existe une chaîne $\rho \subseteq X \cap A^i$ et un entier $n \in \mathbb{N}$ tels que $\Phi_e(\sigma_i \cup \rho, n) \downarrow$. Ainsi, si $(\sigma_0, \sigma_1, X) ?\vdash^i \exists n \Phi_e(G, n) \downarrow$, il existe une extension $(\tau_0, \tau_1, Y)$ telle que $(\tau_i, Y \cap A^i) \vdash \exists n \Phi_e(G, n) \downarrow$, et il existe sinon une extension $(\tau_0, \tau_1, Y)$ telle que $(\tau_i, Y \cap A^i) \vdash \forall n \Phi_e(G, n) \uparrow$. Cependant, cette définition de question de forcing ne satisfait pas les bonnes propriétés définitionnelles, car elle est $\Sigma_1^0(X \oplus A)$, or A peut être arbitrairement complexe.

Nous allons donc définir une variante de la question de forcing pour les contrats $\Sigma_1^0$ et $\Pi_1^0$ qui s'émancipe de A, au prix d'une disjonction.

**Définition 3.14.** Soit $c = (\sigma_0, \sigma_1, X)$ une condition et soient $e_0, e_1 \in \mathbb{N}$.

$$ c ?\vdash \exists n \Phi_{e_0}(G^0, n) \downarrow \lor \exists n \Phi_{e_1}(G^1, n) \downarrow $$

si pour toute 2-partition $Z^0 \sqcup Z^1 = \mathbb{N}$, il existe un entier $n \in \mathbb{N}$, un $i < 2$ et enfin une chaîne $\rho \subseteq Z^i \cap X$ tels que $\Phi_{e_i}(\sigma_i \cup \rho, n) \downarrow$. $\diamond$

À première vue, nous nous sommes abstraits de l'ensemble A en le remplaçant par une formule autrement plus compliquée qui quantifie universellement sur les 2-partitions. Cependant, par un argument de compacité,
la relation de la définition 3.14 se simplifie comme par magie en une formule $\Sigma_1^0(X)$.

**Lemme 3.15.** Soit $(\sigma_0, \sigma_1, X)$ une condition et soient $e_0, e_1 \in \mathbb{N}$. Alors, la relation

$$ (\sigma_0, \sigma_1, X) ?\vdash \exists n \Phi_{e_0}(G^0, n) \downarrow \lor \exists n \Phi_{e_1}(G^1, n) \downarrow $$

est $\Sigma_1^0(X)$ uniformément en $e_0$ et $e_1$.

*

**PREUVE.** Soit $\mathcal{C}$ la classe des ensembles $Z^0 \oplus Z^1$ tels que $Z^0 \sqcup Z^1 = \mathbb{N}$ et tels que pour tout $i < 2$, tout $\rho \subseteq Z^i \cap X$ et tout $n \in \mathbb{N}$, $\Phi_{e_i}(\sigma_i \cup \rho, n) \uparrow$. Alors, $(\sigma_0, \sigma_1, X) ?\vdash \exists n \Phi_{e_0}(G, n) \downarrow \lor \exists n \Phi_{e_1}(G, n) \downarrow \text{ssi } \mathcal{C} = \emptyset$. Comme $\mathcal{C}$ est une classe $\Pi_1^0(X)$, la relation $\mathcal{C} = \emptyset$ est $\Sigma_1^0(X)$. ■

La définition 3.14 peut être faite de manière explicitement $\Sigma_1^0(X)$ comme suit.

**Définition 3.16 (Définition alternative)**

Soit $c = (\sigma_0, \sigma_1, X)$ une condition et soient $e_0, e_1 \in \mathbb{N}$.

$$ c ?\vdash \exists n \Phi_{e_0}(G^0, n) \downarrow \lor \exists n \Phi_{e_1}(G^1, n) \downarrow $$

s'il existe $r \in \mathbb{N}$ tel que pour toute 2-partition $Z^0 \sqcup Z^1 = \{0, \dots, r-1\}$, il existe $i < 2$, une chaîne $\rho \subseteq Z^i \cap X$ et un entier $n \in \mathbb{N}$ tels que $\Phi_{e_i}(\sigma_i \cup \rho, n) \downarrow$. ◇

Arrêtons-nous sur la signification de la définition 3.14. Cette définition-là évite de mentionner l'ensemble $A$ en faisant une « sur-approximation ». La question de forcing demande si pour toutes les instances de $\text{RT}_2^1$, il est possible de trouver une extension finie qui force d'un côté le contrat $\Sigma_1^0$. Il est donc clair que si la réponse est oui, alors en particulier pour $Z^i = A^i$, il existe une extension $(\tau_0, \tau_1, Y)$ telle que $(\tau_i, Y) \vdash \exists n \Phi_{e_i}(G, n)$ pour un certain $i < 2$. En revanche, si la réponse à la question de forcing est non, alors cet échec peut être dû à une instance $Z^0 \sqcup Z^1 = \mathbb{N}$ de $\text{RT}_2^1$ qui n'a rien à voir avec l'instance originelle $A^0 \sqcup A^1 = \mathbb{N}$. C'est là que la nature combinatoire de la théorie de Ramsey entre en jeu : il suffit de construire un ensemble qui est à la fois solution de l'instance $Z^0 \sqcup Z^1 = \mathbb{N}$ et de l'instance $A^0 \sqcup A^1 = \mathbb{N}$ pour forcer la propriété.

**Proposition 3.17.** Soit $c = (\sigma_0, \sigma_1, X)$ une condition et soient $e_0, e_1 \in \mathbb{N}$.

(1) Si $c ?\vdash \exists n \Phi_{e_0}(G^0, n) \downarrow \lor \exists n \Phi_{e_1}(G^1, n) \downarrow$, alors il existe un entier $i < 2$ et une extension $(\tau_0, \tau_1, Y)$ tels que $(\tau_i, Y) \Vdash \exists n \Phi_{e_i}(G, n) \downarrow$.

(2) Si $c ?\Vdash \exists n \Phi_{e_0}(G^0, n) \downarrow \lor \exists n \Phi_{e_1}(G^1, n) \downarrow$, alors il existe un entier $i < 2$ et une extension $(\tau_0, \tau_1, Y)$ tels que $(\tau_i, Y) \Vdash \forall n \Phi_{e_i}(G, n) \uparrow$. ★

**PREUVE.** (1) Si $c ?\vdash \exists n \Phi_{e_0}(G^0, n) \downarrow \lor \exists n \Phi_{e_1}(G^1, n) \downarrow$, alors en particulier, pour $Z^i = A^i$, il existe $i < 2$, une chaîne $\rho \subseteq A^i \cap X$ et un entier $n \in \mathbb{N}$
tels que $\Phi_{e_i}(\sigma_i \cup \rho, n) \downarrow$. Supposons $i = 0$, l'autre cas étant symétrique. La condition $(\sigma_0 \cup \rho, \sigma_1, X \setminus \{0, \dots, |\rho|\})$ est une extension de $c$ telle que $(\sigma_0 \cup \rho, X \setminus \{0, \dots, |\rho|\}) \Vdash \Phi_{e_0}(G, n) \downarrow$.

(2) Cas où $c \not\Vdash \exists n \Phi_{e_0}(G^0, n) \downarrow \lor \exists n \Phi_{e_1}(G^1, n) \downarrow$. Soit alors $\mathcal{C}$ la classe des ensembles $Z^0 \oplus Z^1$ tels que $Z^0 \sqcup Z^1 = \mathbb{N}$ et tels que pour tout $i < 2$, tout $\rho \subseteq Z^i \cap X$ et tout $n \in \mathbb{N}$, on ait $\Phi_{e_i}(\sigma_i \cup \rho, n) \uparrow$. Par hypothèse, $\mathcal{C} \neq \emptyset$. De plus, $\mathcal{C}$ est une classe $\Pi_1^0(X)$ avec $X \in \mathcal{I}$; donc, comme $\mathcal{I}$ est un idéal de Scott, il existe $Z^0 \oplus Z^1 \in \mathcal{I} \cap \mathcal{C}$. Soit $i < 2$ tel que $X \cap Z^i$ est infini. Alors, la condition $(\sigma_0, \sigma_1, X \cap Z^i)$ est une extension de la condition $c$ telle que $(\sigma_i, X \cap Z^i) \Vdash \forall n \Phi_{e_i}(G, n) \uparrow$. Notons que $X \in \mathcal{I}$ et $Z^i \in \mathcal{I}$, donc $X \cap Z^i \in \mathcal{I}$. ■

Notons que dans chacun des deux cas précédents, il aurait été suffisant de s'assurer que $(\tau_i, Y \cap A^i)$ force la propriété, mais c'est également le cas pour $(\tau_i, Y)$, ce qui est un résultat plus fort.

Nous avons à présent tous les éléments nécessaires pour montrer le théorème de Dzhafarov et Jockusch, que nous rappelons ci-après.

**Théorème (3.8)**

*Pour tout ensemble $A$ et tout ensemble $C$ non calculable, il existe un ensemble infini $H \subseteq A$ ou $H \subseteq \mathbb{N} \setminus A$ tel que $C \not\subseteq_T H$.*

**PREUVE.** Soient $A$ et $C$ fixés. Par la proposition 22-7.3, il existe un idéal de Scott $\mathcal{I}$ tel que $C \notin \mathcal{I}$. Supposons (H1), sinon nous avons déjà la solution désirée. Nous allons construire deux ensembles infinis $G^0 \subseteq A^0$, $G^1 \subseteq A^1$ satisfaisant pour tous $e_0, e_1 \in \mathbb{N}$ le contrat

$$ \mathcal{R}_{e_0, e_1} : \Phi_{e_0}^{G^0} \neq C \lor \Phi_{e_1}^{G^1} \neq C. $$

Les ensembles $G^0$ et $G^1$ vont être construits par le forcing de Dzhafarov-Jockusch avec l'idéal $\mathcal{I}$.

**Lemme 3.19.** Soit $c = (\sigma_0, \sigma_1, X)$ une condition et soient $e_0, e_1 \in \mathbb{N}$. Il existe une extension $(\tau_0, \tau_1, Y)$ de $c$ forçant $\mathcal{R}_{e_0, e_1}$. ★

**PREUVE.** Soit $W = \{(x, v) \in \mathbb{N} \times \{0, 1\} : c \Vdash \Phi_{e_0}^{G^0}(x) \downarrow = v \lor \Phi_{e_1}^{G^1}(x) \downarrow = v\}$. Par le lemme 3.15, $W$ est $\Sigma_1^0(X)$, avec $X \in \mathcal{I}$. Trois cas se présentent.

▷ Cas 1. On suppose $(x, 1 - C(x)) \in W$ pour un certain $x \in \mathbb{N}$. Par la proposition 3.17, il existe une extension $(\tau_0, \tau_1, Y)$ de $c$ et un entier $i < 2$ tels que $(\tau_i, Y) \Vdash \Phi_{e_i}^G(x) \downarrow = 1 - C(x)$, donc $(\tau_i, Y) \Vdash \Phi_{e_i}^G \neq C$.

▷ Cas 2. On suppose $(x, C(x)) \notin W$ pour un certain $x \in \mathbb{N}$. Par la proposition 3.17, il existe une extension $(\tau_0, \tau_1, Y)$ de $c$ et un entier $i < 2$ tels que $(\tau_i, Y) \Vdash \Phi_{e_i}^G(x) \uparrow \lor \Phi_{e_i}^G(x) \downarrow \neq C(x)$, donc $(\tau_i, Y) \Vdash \Phi_{e_i}^G \neq C$.
▷ Cas 3. Pour tout $(x, v) \in W$, $C(x) = v$, et pour tout $x \in \mathbb{N}$, il existe un $v < 2$ tel que $(x, v) \in W$. Alors, $C \leq_T X$, car pour $x \in \mathbb{N}$, il suffit d'attendre qu'un couple $(x, v)$ soit $X$-énuméré dans $W$, et renvoyer $v$. Par hypothèse sur $X$, ce cas ne peut arriver. ■

Soit $F$ un filtre suffisamment générique pour le forcing de Dzhafarov-Jockusch, et soit $(G^0, G^1) = \dot{F}$. Par le lemme 3.13, $G^0$ et $G^1$ sont tous les deux infinis. Par définition d'une condition de forcing, $G^0 \subseteq A^0$ et $G^1 \subseteq A^1$. Par le lemme 3.19, $(G^0, G^1)$ satisfait $\mathcal{R}_{e_0, e_1}$ pour tous $e_0, e_1 \in \mathbb{N}$. Il y a alors deux possibilités : soit $C \not\leq_T G^0$, soit il existe $e_0$ tel que $\Phi_{e_0}^{G^0} = C$. Dans ce cas-ci, pour tout $e_1$ on a $\Phi_{e_1}^{G^1} \neq C$, car $\mathcal{R}_{e_0, e_1}$ est satisfait, et $C \not\leq_T G^1$. ■

**Exercice 3.20. (★★)** Montrer que pour tout ensemble $A$ et tout $C$ non $\Sigma_1^0$, il existe un ensemble infini $H \subseteq A$ ou $H \subseteq \bar{A}$ tel que $C$ n'est pas $\Sigma_1^0(H)$. ◇

**Exercice 3.21. (★★★)** Montrer que pour tout ensemble $A$ et toute fonction hyperimmune $f$, il existe un ensemble infini $H \subseteq A$ ou $H \subseteq \bar{A}$ tel que $f$ est $H$-hyperimmune. ◇

**Exercice 3.22. (★★)** Adapter l'exercice précédent pour montrer que pour tout ensemble $A$ et tout triplet de fonctions hyperimmunes $f_0, f_1, f_2$, il existe un ensemble infini $H \subseteq A$ ou $H \subseteq \bar{A}$ tel que au moins deux parmi les trois fonctions sont $H$-hyperimmunes. ◇

Le théorème 3.8 a été généralisé par Monin et Patey [161] à toute la hiérarchie arithmétique.

**Théorème 3.23 (Monin et Patey [161])**

Soit $n \geq 1$. Pour tout ensemble $A$ et tout $C$ non $\Delta_n^0$, il existe un ensemble infini $H \subseteq A$ ou $H \subseteq \mathbb{N} \setminus A$ tel que $C$ n'est pas $\Delta_n^0(H)$.

Une conséquence du théorème précédent est que pour tout ensemble $A$, il existe un ensemble infini $H \subseteq A$ ou $H \subseteq \mathbb{N} \setminus A$ qui n'est pas de degré high. La preuve se fait à l'aide d'une notion de forcing plus complexe qui sort du cadre introductif de ce livre.

## 3.3. Principe infini des tiroirs et degrés PA

Le théorème de Dzhafarov et Jockusch sera utilisé pour montrer le théorème de Seetapun : $RT_2^2$ n'implique pas $ACA_0$. Nous nous attaquons à présent au théorème de Liu, qui renforce celui de Seetapun en montrant que $RT_2^2$ n'implique pas $WKL_0$. Là encore, le cœur de la preuve se situe dans les instances arbitraires de $RT_2^1$.
**Théorème 3.24 (Liu [146])**

Pour tout ensemble $A$, il existe un ensemble infini $H \subseteq A$ ou $H \subseteq \mathbb{N} \setminus A$ qui n'est pas de degré $PA$.

La preuve que nous présentons ici de ce résultat est celle de Monin et Patey [159], plus courte que la preuve originale de Liu, grâce notamment à l'utilisation du concept de *classe large*.

**Définition 3.25**

Une classe $\mathcal{A} \subseteq 2^{\mathbb{N}}$ non vide est large si :

1. elle est close par le haut : $\forall X \in \mathcal{A} \ \forall Y \supseteq X \ Y \in \mathcal{A}$;

2. pour tout $k \in \mathbb{N}^*$, et pour tout $X_0 \sqcup \cdots \sqcup X_{k-1} = \mathbb{N}$, il existe $i < k$ tel que $X_i \in \mathcal{A}$. $\diamond$

Pour le reste de cette section on fixe un ensemble $\mathcal{A}$, et l'on pose $\mathcal{A}^0 = \mathcal{A}$ et $\mathcal{A}^1 = \mathbb{N} \setminus \mathcal{A}$. On fixe également une énumération $(\mathcal{U}_e)_{e \in \mathbb{N}}$ de toutes les classes $\Sigma_1^0$ closes par le haut.

**Définition 3.26**

Soit $\mathbb{P}$ l'ensemble des conditions de forcing de la forme $\langle (\sigma_s, X_s)_{s<k}, C \rangle$ pour $k \in \mathbb{N}^*$ telles que :

(a) pour tout $s < k$, il existe $i < 2$ tel que $\sigma_s \cup X_s \subseteq \mathcal{A}^i$;

(b) $X_0 \sqcup \cdots \sqcup X_{k-1} = \mathbb{N} - \{0, \dots, \max_s |\sigma_s|\}$;

(c) $\bigcap_{e \in C} \mathcal{U}_e$ est une classe large ne contenant que des ensembles infinis;

(d) $C$ est calculable. $\diamond$

Notons de suite que nous n'avons aucune restriction d'effectivité sur les réservoirs $X_0 \sqcup \cdots \sqcup X_{k-1}$.

**Définition 3.27**

L'ordre partiel sur $\mathbb{P}$ est défini par $\langle (\tau_s, Y_s)_{s<\ell}, D \rangle \le \langle (\sigma_s, X_s)_{s<k}, C \rangle$ si $C \subseteq D$, si $\ell \ge k$, et s'il existe une surjection $f : \ell \to k$ telle que pour tout $s < \ell$ on a $\sigma_{f(s)} \preceq \tau_s$, $Y_s \subseteq X_{f(s)}$, et $\tau_s - \sigma_{f(s)} \subseteq X_{f(s)}$. $\diamond$

Une condition $c = \langle (\sigma_s, X_s)_{s<k}, C \rangle$ doit être vue comme un ensemble de branches $(\sigma_s, X_s)$ chacune étant une condition de Mathias, à ceci près que l'on n'exige pas que $X_s$ soit infini. Une extension $d \le c$ est une condition dont chaque branche sera une extension d'une des branches de $c$.

**Définition 3.28**

Soit $\langle (\sigma_s, X_s)_{s<k}, C \rangle \in \mathbb{P}$. On appelle *branche* $c^{[s]}$ de $c$ la condition de
Mathias $(\sigma_s, X_s)$. Une telle branche est valide si $X_s \in \bigcap_{e \in C} \mathcal{U}_e$.

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

Notons que la notion de validité est cruciale : les branches de nos conditions $c_0 \ge c_1 \ge \dots$ vont former un arbre, et le générique final que nous utiliserons y proviendra d'un chemin infini de branches valides.

**Notation**

Pour deux conditions $c = \langle\langle(\tau_s, Y_s)_{s<\ell}, D\rangle\rangle$ et $d = \langle\langle(\sigma_s, X_s)_{s<k}, C\rangle\rangle$, on écrira $d \leq_f c$ si $d \leq c$ via la fonction $f : \ell \to k$. Si $f$ est la fonction identité, alors $d$ est une extension simple. Étant donné $s < k$, si $f^{-1}(t)$ est un singleton pour tout $t \neq s$, alors $d$ est une s-extension de $d$.

Le lemme suivant sera utilisé pour montrer que le générique que nous construisons est infini.

**Lemme 3.29.** Soit $c \in \mathbb{P}$ une condition de branche valide $c^{[s]} = (\sigma, X)$. Alors, il y a une extension simple $d \le c$ de branche $d^{[s]} = (\tau, Y)$ et un entier $n > |\sigma|$ tels que $n \in \tau$. $\star$

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

**PREUVE**

Soit $c = \langle\langle(\sigma_s, X_s)_{s<k}, C\rangle\rangle$. Comme $c^{[s]}$ est valide on a $X_s \in \bigcap_{e \in C} \mathcal{U}_e$. Comme $\bigcap_{e \in C} \mathcal{U}_e$ ne contient que des ensembles infinis, alors $X_s$ est infini. Soit $n \in X_s$ tel que $n > |\sigma_s|$. Alors, la condition

$$d = \langle\langle(\tau_s, X_s \cap ]n, \infty[)_{s<k}, C\rangle\rangle$$

définie par $\tau_s = \sigma_s \cup \{n\}$ et $\tau_t = \sigma_t$ pour $t \neq s$ est une extension simple de $c$ qui satisfait le lemme. $\blacksquare$

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

La définition suivante sera nécessaire pour développer le cœur de l'argument.

**Définition 3.30.** Soit $\xi : \mathbb{N} \times 2^{<\mathbb{N}} \to \mathbb{N}$ une fonction calculable qui prend le code $e$ d'une fonctionnelle Turing $\Phi_e(G, n)$, une chaîne $\sigma$, et qui renvoie le code de l'ouvert :

$$\{X : \exists \rho \subseteq X - \{0, \dots, |\sigma|\} \exists n \Phi_e(\sigma \cup \rho, n) \downarrow = \Phi_n(n)\}.$$

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

Nous arrivons finalement au lemme clef de la preuve.

**Lemme 3.31.** Soit $c^{[s]}$ la branche d'une condition $c \in \mathbb{P}$. Soit $\Phi_e(G, n)$ une fonctionnelle Turing à valeurs dans $\{0, 1\}$ pour tous ses oracles. Il y a une s-extension $d \leq_f c$ telle que pour toute branche valide $d^{[t]}$ de $d$ pour
laquelle $f(t) = s$, il existe $n$ pour lequel :

$$d^{[t]} \Vdash \Phi_e(G, n) \models = \Phi_n(n) \text{ ou } d^{[t]} \Vdash \Phi_e(G, n) \uparrow . \quad \star$$

PREUVE. Soit $c = \langle (\sigma_s, X_s)_{s<k}, C \rangle$, et soit $P(n, k, v)$ le prédicat :

$$\begin{gather*} \forall Z_0 \sqcup \cdots \sqcup Z_{k-1} = \mathbb{N} \exists j < k \\ Z_j \in \bigcap_{e \in C, e < k} \mathcal{U}_e \text{ et } \exists \rho \subseteq Z_j - \{0, \dots, |\sigma_s|\} \Phi_e(\sigma_s \cup \rho, n) \downarrow = v. \end{gather*}$$

Le prédicat $P(n, k, v)$ est vrai si, et seulement si, la classe $\Pi_1^0$ des éléments

$$\left\{ Z_0 \sqcup \cdots \sqcup Z_{k-1} = \mathbb{N} : \forall j < k \begin{array}{l} Z_j \notin \bigcap_{e \in C, e < k} \mathcal{U}_e \\ \text{ou } \forall \rho \subseteq Z_j - \{0, \dots, |\sigma_s|\} \Phi_e(\sigma_s \cup \rho, n) \uparrow \neq v \end{array} \right\}$$

est vide. La notation $\Phi_e(\sigma_s \cup \rho, n) \uparrow \neq v$ ci-dessus signifie

$$\Phi_e(\sigma_s \cup \rho, n) \uparrow \lor \Phi_e(\sigma_s \cup \rho, n) \downarrow \neq v.$$

Par le lemme faible de König, le prédicat $P(n, k, v)$ est donc $\Sigma_1^0$.

Supposons d'abord que, pour tout $k \in \mathbb{N}$, on ait $\forall n \exists v < 2 P(n, k, v)$. Notons que pour tout $k \in \mathbb{N}$ l'ensemble $W_k = \{(n, v) : P(n, k, v)\}$ est c. e. On doit donc avoir un entier $n \in \mathbb{N}$ tel que $(n, \Phi_n(n)) \in W_k$, sinon on calculerait une fonction DNC$_2$. Ainsi, en particulier :

$$\forall Z_0 \sqcup \cdots \sqcup Z_{k-1} = \mathbb{N} \exists j < k Z_j \in \bigcap_{e \in C} \mathcal{U}_e \cap \mathcal{U}_{\xi(e, \sigma_s)}.$$

D'où, $\bigcap_{e \in C} \mathcal{U}_e \cap \mathcal{U}_{\xi(e, \sigma_s)}$ est une classe large. Si $X_s \notin \bigcap_{e \in C} \mathcal{U}_e \cap \mathcal{U}_{\xi(e, \sigma_s)}$, alors $d = \langle (\sigma_s, X_s)_{s<k}, C \cup \{\xi(e, \sigma_s)\} \rangle$ est une s-extension de $c$ sur laquelle la branche $d^{[s]}$ n'est pas valide, et il n'y a rien de plus à vérifier.

Si $X_s \in \bigcap_{e \in C} \mathcal{U}_e \cap \mathcal{U}_{\xi(e, \sigma_s)}$, alors il existe $n$ et il existe $\rho \subseteq X_s - \{0, \dots, |\sigma_s|\}$ tels que $\Phi_e(\sigma_s \cup \rho, n) \downarrow = \Phi_n(n)$. La condition $d = \langle (\tau_s, X_s \setminus \{0, \dots, |\rho|\})_{s<k}, C \rangle$ définie par $\tau_s = \sigma_s \cup \rho$ et $\tau_t = \sigma_t$ pour $t \neq s$ est une s-extension de $c$ telle que $d^{[s]} \Vdash \Phi_e(G, n) \models = \Phi_n(n)$.

Supposons à présent qu'il existe $k \in \mathbb{N}$ tel que

$$\exists n \forall v < 2 \neg P(n, k, v).$$

En particulier, pour $k, n \in \mathbb{N}$, on a des partitions $Z_0^0 \sqcup \cdots \sqcup Z_{k-1}^0 = \mathbb{N}$ et $Z_0^1 \sqcup \cdots \sqcup Z_{k-1}^1 = \mathbb{N}$ telles que pour $v < 2$ on a :

$$\forall j < k \left( Z_j^v \notin \bigcap_{e \in C, e < k} \mathcal{U}_e \text{ ou } \forall \rho \subseteq Z_j^v - \{0, \dots, |\sigma_s|\} \Phi_e(\sigma_s \cup \rho, n) \uparrow \neq v \right).$$

Soit $d = \langle (\tau_s, Y_s)_{s<\ell}, C \rangle$ la s-extension de $c$ obtenue en dupliquant les branches $c^{[s_0, \ell]}$ en $k^2$ branches $c^{[s_{k-1}, k-1]}$, telles que $\tau_{s_{i,j}} = \sigma_s$ et $Y_{s_{i,j}} = X_s \cap Z_i^0 \cap Z_j^1$.
Chaque autre branche $c^{[t]}$ pour $t \neq s$ est identique dans $d$. Notons que si la branche $d^{[s_i,j]}$ est valide alors $X_s \cap Z_i^0 \cap Z_j^1 \in \bigcap_{e \in C} \mathcal{U}_e$ et donc

$$ \forall \rho \subseteq X_s \cap Z_i^0 \cap Z_j^1 - \{0, \dots, |\sigma_s|\} \Phi_e(\sigma_s \cup \rho, n) \uparrow \notin \{0, 1\}. $$

Comme $\Phi_e$ est à valeurs dans $\{0,1\}$, on a donc $d^{[s_i,j]} \models \Phi_e(G,n) \uparrow$ pour tous $i,j < k$ tels que $d^{[s_i,j]}$ est valide. Cela complète la preuve du lemme.

**Lemme 3.32.** Soit $c_0 \geqslant c_1 \geqslant \dots$ une suite décroissante de conditions. Alors, il existe une fonction $g: \mathbb{N} \to \mathbb{N}$ telle que $c_0^{[g(0)]} \geqslant c_1^{[g(1)]} \geqslant \dots$ et telle que pour tout $n$, $c_n^{[g(n)]}$ est une branche valide de $c_n$. $\star$

**PREUVE.** Montrons d'abord la chose suivante. Soit $c = \langle (\sigma_s, X_s)_{s<k}, C \rangle$, et soit $d = \langle (\tau_s, Y_s)_{s<\ell}, D \rangle$ avec $d \leqslant_f c$; si $d^{[s]}$ est valide, alors $c^{[f(s)]}$ est valide.

Supposons $d^{[s]}$ valide. Alors, $Y_s \in \bigcap_{e \in D} \mathcal{U}_e \subseteq \bigcap_{e \in C} \mathcal{U}_e$. Comme $Y_s \subseteq X_{f(s)}$ et comme chaque $\mathcal{U}_e$ est clos par le haut, alors $X_{f(s)} \in \bigcap_{e \in C} \mathcal{U}_e$, si bien que $c^{[f(s)]}$ est valide.

Les branches valides de chaque condition de la suite $(c_i)_{i \in \mathbb{N}}$ forment donc un arbre pour l'ordre $\leqslant$ entre les conditions de Mathias. L'arbre étant à branchement fini, il a un chemin infini si, seulement si, il est infini. Il est donc suffisant de montrer que chaque $c_i$ possède une branche valide. Soit $c_i = \langle (\sigma_s, X_s)_{s<k}, C \rangle$, et soit $m = \sup_{s<k} |\sigma_s|$. Alors,

$$ [0, m] \sqcup X_0 \sqcup \dots \sqcup X_{s-1} = \mathbb{N}. $$

Comme $\bigcap_{e \in C} \mathcal{U}_e$ est large et ne contient que des ensembles infinis, il existe nécessairement $s < k$ tel que $X_s \in \bigcap_{e \in C} \mathcal{U}_e$. La branche $c_i^{[s]}$ est donc valide.

La fonction $g$ du lemme est donnée par le chemin infini de notre arbre de branches valides. $\blacksquare$

**PREUVE DU THÉORÈME 3.24.** Soit $c_0 \geqslant c_1 \geqslant \dots$ un filtre de conditions suffisamment générique. Notons que l'on peut démarrer avec la condition $\langle (\epsilon, A^0), (\epsilon, A^1), C \rangle$, où $C$ est un ensemble calculable de codes tels que $\bigcap_{e \in C} \mathcal{U}_e$ est la classe des ensembles infinis.

D'après le lemme 3.32, soit $g: \mathbb{N} \to \mathbb{N}$ telle que $c_0^{[g(0)]} \geqslant c_1^{[g(1)]} \geqslant \dots$ et telle que pour tout $i$, $c_i^{[g(i)]}$ est une branche valide de $c_i$. D'après le lemme 3.29, l'ensemble générique $G$ résultant est infini. D'après le lemme 3.31, pour toute fonctionnelle $\Phi_e(G, n)$, il existe $n$ tel que $c_i^{[g(i)]} \models \Phi_e(G, n) \downarrow = \Phi_n(n)$ ou tel que $c_i^{[g(i)]} \models \Phi_e(G, n) \uparrow$. Il s'ensuit que notre générique n'est pas de degré PA. Enfin, par nature des conditions de forcing, on a $G \subseteq A^i$ pour $i=0$ ou $i=1$. $\blacksquare$
Le résultat de Liu est loin d’être évident, et la question de sa version itérée est encore ouverte à ce jour.

**Question 3.33.** Soit $n \ge 1$. Pour tout ensemble $A$, existe-t-il un ensemble infini $H \subseteq A$ ou $H \subseteq \mathbb{N} \setminus A$ tel que $H^{(n)}$ n’est pas de degré PA relativement à $\emptyset^{(n)}$ ?

Monin et Patey [160] ont donné une réponse positive partielle en montrant que c’était le cas pour les instances $\Delta_2^0$ de $\mathrm{RT}_2^1$.

**3.4. Instances $\Delta_2^0$ de $\mathrm{RT}_2^1$**

Les instances $\Delta_2^0$ sont particulièrement importantes pour l'étude du théorème de Ramsey pour les paires, car elles jouent un rôle clef dans la connexion entre $\mathrm{RT}_2^1$ et $\mathrm{RT}_2^2$, comme nous le verrons dans la section 4. Le principe infini des tiroirs étant calculatoirement vrai, toute instance $\Delta_2^0$ de $\mathrm{RT}_2^1$ admet une solution $\Delta_2^0$. Existe-t-il une instance $\Delta_2^0$ de $\mathrm{RT}_2^1$ sans solution calculable ? La question peut se reformuler comme suit : existe-t-il un ensemble $\Delta_2^0$ $A$ à la fois immune, et de complémentaire immune (voir la définition 7-1.1) ? La proposition 3.34 donne un résultat plus fort, en montrant l'existence d'une instance $\Delta_2^0$ de $\mathrm{RT}_k^1$ dont les solutions ne peuvent même pas être approximées par blocs.

**Proposition 3.34.** Il existe un ensemble $A$ $\Delta_2^0$ tel que $A$ et $\mathbb{N} \setminus A$ sont tous les deux hyperimmunes.

**PREUVE.** Rappelons que la fonction principale d'un ensemble infini $H$ est la fonction $p_H : \mathbb{N} \to \mathbb{N}$ qui à $n$ associe le $(n+1)$-ième élément de $H$. Rappelons également que $H$ est hyperimmune si, et seulement si, $p_H$ n'est bornée par aucune fonction calculable.

Nous définissons une suite $\emptyset'\text{-calculable } \sigma_0 \prec \sigma_1 \prec \dots A$ en alternant la concaténation de longues suites de 1 avec celle de longues suites de 0, afin de diagonaliser contre toutes les fonctions calculables.

Supposons $\sigma_{2e}$ définie, alors $\sigma_{2e+1} = \sigma_{2e} 0^{k+1} 1$ si $\Phi_e(|\sigma_{2e}| + 1) \downarrow = k$, et $\sigma_{2e+1} = \sigma_{2e} 1$ sinon. Supposons $\sigma_{2e+1}$ définie, alors $\sigma_{2e+2} = \sigma_{2e+1} 1^{k+1} 0$ si $\Phi_e(|\sigma_{2e+1}| + 1) \downarrow = k$, et $\sigma_{2e+2} = \sigma_{2e+1} 0$ sinon.

On vérifie sans peine que si $\Phi_e$ est totale, alors

pour $m = |\sigma_{2e}| + 1$, on a $p_A(m) \ge |\sigma_{2e+1}| - 1 > \Phi_e(m)$,
et pour $m = |\sigma_{2e+1}| + 1$, on a $p_{\mathbb{N}\setminus A}(m) \ge |\sigma_{2e+2}| - 1 > \Phi_e(m)$.

Notons qu’un sous-ensemble infini d’un ensemble hyperimmune est hyperimmune. La proposition 3.34 nous donne donc une instance $\Delta_2^0 B_0 \sqcup B_1 = \mathbb{N}$
de $RT_2^1$ telle que toute solution est de degré hyperimmune. En particulier, il existe une instance $\Delta_2^0$ de $RT_2^1$ sans solution calculable.

**Exercice 3.35.** (⋆) Montrer qu'il existe un ensemble $\Delta_2^0$ tel que $A$ et $N \setminus A$ sont effectivement immunes. En déduire que tout ensemble infini $H \subseteq A$ ou $H \subseteq N \setminus A$ est de degré DNC. ◇

**Exercice 3.36.** (⋆) Montrer que pour tout $k \ge 2$, il existe une $k$-partition $\Delta_2^0$, soit $A_0 \sqcup A_1 \sqcup \dots \sqcup A_{k-1} = N$, telle que pour tout $i < k$, $N \setminus A_i$ est hyperimmune. ◇

**Exercice 3.37.** (⋆⋆) Montrer qu'il existe une instance $g$ de $RT_3^1$ telle que pour toute instance $h$ de $RT_2^1$, il existe un ensemble $h$-homogène qui ne calcule pas d'ensemble $g$-homogène.

Indication.– Utiliser les exercices 3.36 et 3.22.

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

L'instance $\Delta_2^0$ de $RT_k^1$ créée par la proposition 3.34 n'est cependant pas trop complexe, et possède en particulier une solution low, comme l'ont prouvé Hirschfeldt, Jockusch, Kjos-Hanssen et Lempp [89].

**Proposition 3.38 ([89]).** Soit $A$ un ensemble $\Delta_2^0$ tel que $N \setminus A$ est hyperimmune. Alors, il existe un sous-ensemble infini $H \subseteq A$ de degré low. ★

**PREUVE.** Nous allons construire une suite $\Delta_2^0, \sigma_0, \sigma_1, \dots \in 2^{<N}$ de chaînes telles que pour tout $n$, $\sigma_n \subseteq A$, et telles que pour tout $e$,

$$ \Phi_e^{\sigma_{e+1}}(e) \downarrow \text{ ou } \forall \tau \succeq \sigma_{e+1} \quad \Phi_e^{\tau}(e) \uparrow. \quad (1) $$

Notons que dans la seconde clause de (1), $\tau$ n'est pas nécessairement inclus dans $A$. Ainsi, $\emptyset'$ arrive à décider si $\Phi_e^H(e) \downarrow$ pour $\{H\} = \bigcap_n[\sigma_n]$ en effectuant la construction jusqu'à $\sigma_{e+1}$, et en décidant à l'aide de $\emptyset'$ si l'on est dans le premier cas ou le second cas.

*Construction.* Supposons que l'on a construit $\sigma_e \in 2^{<N}$. Chercher $\emptyset'$-calculatoirement une extension $\sigma_{e+1} \succeq \sigma_e$ telle que $\sigma_{e+1} \subseteq A$ et telle que (1) est satisfait. Montrons qu'il existe toujours une telle extension. Pour tout entier $n > |\sigma_e|$, on cherche $\tau_n$, une extension de $0^n$, telle que $\Phi_e^{\sigma_e \cup \tau_n}(e) \downarrow$. S'il existe un $n$ tel que l'on ne trouve pas $\tau_n$, alors $\sigma_{e+1} = \sigma_e \cup 0^n$ est une extension de $\sigma_e$ satisfaisant la seconde clause de (1). Si $\tau_n$ est toujours défini, alors par hyperimmunité de $N \setminus A$, il existe $n > |\sigma_e|$ tel que $\tau_n \subseteq A$. Alors, $\sigma_{e+1} = \sigma_e \cup \tau_n$ est une extension de $\sigma_e$ satisfaisant la première clause de (1). Dans tous les cas, une telle extension existe. Cela conclut la construction et la preuve de la proposition 3.38. ■

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

Peut-on obtenir une solution low pour toute instance $\Delta_2^0$ du principe infini des tiroirs ? La réponse est non, et se prouve à l'aide d'un argument de
priorité à blessure infinie. Nous omettrons ici la preuve qui est longue et d'une grande complexité.

**Théorème 3.39 (Downey, Hirschfeldt, Lempp et Solomon [47])**

Il existe $A$ un ensemble $\Delta_2^0$ tel que ni lui ni son complémentaire ne contient de sous-ensemble infini low.

L'instance de $\text{RT}_2^1$ créée par le théorème 3.39 est très différente de celle créée par la proposition 3.34, puisque tout ensemble $\Delta_2^0$ dont le complémentaire est hyperimmune admet un sous-ensemble infini de degré low.

Cholak, Jockusch et Slaman [33] ont cependant prouvé que toute instance $\Delta_2^0$ de $\text{RT}_2^1$ admet une solution « presque low », dans le sens où tout degré PA relativement à $\emptyset'$ calcule son saut Turing.

**Théorème 3.40 (Cholak, Jockusch et Slaman [33])**

Soit $A$ un ensemble $\Delta_2^0$ et $P$ un degré PA relativement à $\emptyset'$. Il existe un ensemble infini $H \subseteq A$ ou $H \subseteq \mathbb{N} \setminus A$ tel que $H' \leq_{T} P$.

**PREUVE.** La preuve du théorème 3.40 se fait à l'aide d'une construction effective d'un filtre générique pour le forcing de Dzhafarov-Jockusch. Rapelons qu'un code de lowness d'un ensemble low $X$ est un entier $e$ tel que $\{n : \Phi_e(\emptyset', n)\downarrow\} = X'$ (voir la section 5-7). Le théorème de base $\Pi_1^0$ low est uniforme, au sens où il existe une fonction calculable $g : \mathbb{N} \to \mathbb{N}$ telle que si $\Phi_e$ est un arbre binaire infini, alors $g(e)$ est le code de lowness d'un chemin de $\Phi_e$. Par l'exercice 22-7.5, il existe un idéal de Scott $\mathcal{I}$ dont tous les éléments sont low. La construction est uniforme, et il existe une fonction calculable $h_{\text{WKL}} : \mathbb{N} \to \mathbb{N}$ telle que si $e$ est le code de lowness d'un arbre binaire infini dans $\mathcal{I}$, alors $h_{\text{WKL}}(e)$ est le code de lowness d'un chemin infini de cet arbre dans $\mathcal{I}$. De plus, il existe fonction calculable $h_{\oplus} : \mathbb{N} \times \mathbb{N} \to \mathbb{N}$ qui, étant donné deux indices de lowness $e_0, e_1$ d'ensembles $X$ et $Y$, renvoie un code de lowness de l'ensemble $X \oplus Y$ dans $\mathcal{I}$. Un code de condition $(\sigma_0, \sigma_1, X)$ est un triplet $(\sigma_0, \sigma_1, e)$ tel que $e$ est un code de lowness de $X$. Ainsi, toute condition de Dzhafarov-Jockusch dans l'idéal $\mathcal{I}$ peut être codée de manière finie.

Supposons (H1) (définie dans la section 3.2). En effet, il existe sinon un ensemble infini $H \subseteq A^0$ ou $H \subseteq A^1$ de degré low, et l'on a en particulier, $H' \leq_T \emptyset' \leq_T P$. Sachant que $A$ est fixé et $\Delta_2^0$, le lemme 3.13 est uniforme en $\emptyset'$, au sens où il existe une procédure $\emptyset'$-calculable qui prend en entrée un code $(\sigma_0, \sigma_1, a)$ de condition $(\sigma_0, \sigma_1, X)$ et un entier $i < 2$, et renvoie un code $(\tau_0, \tau_1, b)$ de condition $(\tau_0, \tau_1, Y)$ étendant $(\sigma_0, \sigma_1, X)$ tel qu'il existe un entier $n \geq |\sigma_i|$ pour lequel $\tau_i(n) = 1$. Sachant que $\emptyset' \leq_T P$, alors $P$ calcule deux ensembles infinis $G^0 \subseteq A^0$ et $G^1 \subseteq A^1$. Nous voulons
cependant décider le saut Turing de $G^0$ et $G^1$, à l'aide de la question de forcing.

Considérons une condition $c = (\sigma_0, \sigma_1, X)$ et deux entiers $e_0, e_1 \in \mathbb{N}$. Par le lemme 3.15, le prédicat $c?\vdash \Phi_{e_0}^{G^0}(e_0) \downarrow \lor \Phi_{e_1}^{G^1}(e_1) \downarrow$ est $\Sigma_1^0(X)$. Ainsi, $\emptyset'$ peut décider, étant donné un code de la condition $c$, si le prédicat est vrai ou non. Si le prédicat est vrai, alors $\emptyset'$ peut chercher un entier $i < 2$, et une chaîne finie $\rho \subseteq X \cap A^i$ telle que $\Phi_{e_i}^{\sigma_i \cup \rho}(e_i) \downarrow$, et calculer un code de lowness de l'ensemble $X \setminus \{0, \dots, |\rho|\}$. Ainsi, si le prédicat est vrai, $\emptyset'$ peut calculer un code d'une extension $d$ de $c$ et trouver un $i < 2$ forçant $\Phi_{e_i}^{G^i}(e_i) \downarrow$. Si le prédicat est faux, alors $\emptyset'$ peut calculer un code de lowness d'un ensemble $Z^0 \oplus Z^1$ tel que $Z^0 \sqcup Z^1 = X$, et pour tout $i < 2$ et tout $\rho \subseteq Z^i \cup X$, on a $\Phi_{e_i}^{\sigma_i \cup \rho}(e_i) \uparrow$. Jusqu'ici, toutes les opérations pouvaient être effectuées à l'aide de $\emptyset'$. En revanche, il est nécessaire d'avoir recours à $P$ pour trouver un entier $i < 2$ tel que $Z^i \cap X$ est infini, et donc pour calculer un code de l'extension $(\sigma_0, \sigma_1, Z^i \cap X)$. Un degré PA relativement à $\emptyset'$ est capable de trouver, parmi deux formules $\Pi_2^0, F_0$ et $F_1$ sachant que l'une des deux au moins est vraie, un entier $i < 2$ tel que $F_i$ est vraie. Ainsi, si le prédicat est faux, $P$ peut calculer un code d'une extension $d$ de $c$ et $i < 2$ tels que $d$ force $\Phi_{e_i}^{G^i}(e_i) \uparrow$.

*Construction.* Construire une suite $P$-calculable de codes de conditions

$$c_0 \ge c_1 \ge \dots, \text{ avec } c_s = (\sigma_0^s, \sigma_1^s, X^s)$$

telle que, pour tout $s \in \mathbb{N}$,

(1) il existe $n_0, n_1 > s$ tels que $\sigma_0^s(n_0) = 1$ et $\sigma_1^s(n_1) = 1$;

(2) si $s = \langle e_0, e_1 \rangle$, alors il existe $i < 2$ tel que $(\sigma_i^{s+1}, X^{s+1}) \Vdash \Phi_{e_i}^G(e_i) \downarrow$ ou $(\sigma_i^{s+1}, X^{s+1}) \Vdash \Phi_{e_i}^G(e_i) \uparrow$.

Soient $\{G^0\} = \bigcap_s[\sigma_0^s]$ et $\{G^1\} = \bigcap_s[\sigma_1^s]$. Par (1), $G^0$ et $G^1$ sont tous les deux infinis. Par construction, $G^0 \subseteq A^0$ et $G^1 \subseteq A^1$. Par (2), il existe $i < 2$ tel que pour tout $e \in \mathbb{N}$, il existe $s$ tel que $(\sigma_i^{s+1}, X^{s+1}) \Vdash \Phi_e^G(e) \downarrow$ ou $(\sigma_i^{s+1}, X^{s+1}) \Vdash \Phi_e^G(e) \uparrow$.

Montrons que le saut Turing de $G^i$ est $P$-calculable. En effet, pour décider si $\Phi_e^G(e) \downarrow$, il suffit d'exécuter à l'aide de $P$ la construction jusqu'à trouver un entier $s$ tel que $(\sigma_i^{s+1}, X^{s+1}) \Vdash \Phi_e^G(e) \downarrow$ ou $(\sigma_i^{s+1}, X^{s+1}) \Vdash \Phi_e^G(e) \uparrow$. Cela termine la preuve du théorème 3.40. ■

Rappelons qu'un ensemble $H$ est low$_2$ si $H'' \le_T \emptyset''$. Le théorème de base low $\Pi_1^0$ (voir le théorème 8-4.3) nous permet de déduire le corollaire suivant.
**Corollaire 3.41**

Soit $A$ un ensemble $\Delta_2^0$. Il existe un ensemble infini $H \subseteq A$ ou $H \subseteq N \setminus A$ de degré $low_2$.

PREUVE. Par le théorème 8-4.3 relativisé à $\emptyset'$, il existe un ensemble $P$ de degré PA relativement à $\emptyset'$ tel que $P' \leq_T \emptyset''$. Par le théorème 3.40, il existe un ensemble infini $H \subseteq A$ ou $H \subseteq N \setminus A$ tel que $H' \leq_T P$. En particulier, $H'' \leq_T P' \leq_T \emptyset''$, et $H$ est donc de degré $low_2$. ■

# 4. Théorème de Ramsey pour les paires

Le théorème 2.17 affirme que pour tout $n \geq 3$, $\forall k \text{RT}_k^n$ est équivalent à $\text{ACA}_0$. Ce théorème se prouve en montrant que toute instance calculable de $\text{RT}_k^n$ admet une solution arithmétique, tandis qu'il existe un coloriage calculable $f : [N]^3 \to 2$ dont tout ensemble infini homogène calcule $\emptyset'$. Le principe des tiroirs $\text{RT}_k^1$, quant à lui, est calculatoirement vrai, et prouvable dans $\text{RCA}_0$ pour tout entier $k$, tandis que l'énoncé $\forall k \text{RT}_k^1$ est équivalent au principe $\text{BII}_1^0$ dans $\text{RCA}_0$. Dans cette section, nous allons voir comme annoncé que les choses sont bien différentes pour le théorème de Ramsey pour les paires. En particulier, il existe une instance calculable de $\text{RT}_2^2$ dont aucune solution ne calcule $\emptyset'$, ce qui nous permettra de déduire le théorème de Seetapun. Nous verrons également qu'il existe une instance calculable de $\text{RT}_2^2$ dont aucune solution n'est de degré PA, ce qui nous amènera au théorème de Liu.

## 4.1. Principe de cohésion

La preuve du théorème de Ramsey se fait de manière inductive à l'aide de la notion d'ensemble pré-homogène. Dans le cas du théorème de Ramsey pour les paires, la bonne notion à considérer est celle d'ensemble cohésif, qui est une forme d'inversion de saut de la notion d'ensemble pré-homogène.

**Définition 4.1.** Étant donné deux ensembles $X$ et $Y$, on note $X \subseteq^* Y$ si $X \setminus Y$ est un ensemble fini. Soit $(R_n)_{n \in N}$ une suite d'ensembles. Un ensemble $C$ est dit *cohésif* pour $(R_n)_{n \in N}$ s'il est infini et si $C \subseteq^* R_n$ ou $C \subseteq^* N \setminus R_n$ pour tout $n$. ♦

**Notation**

On dénote par COH le principe suivant : pour toute suite $(R_n)_{n \in N}$, il existe un ensemble cohésif.
L'existence d'un ensemble cohésif pour tous les ensembles calculables se prouve aisément à l'aide de la restriction du forcing de Mathias aux conditions dont les réservoirs sont calculables.

**Exercice 4.2.** (⋆) Soit $\mathbb{P}$ l'ensemble des conditions de Mathias $(\sigma, X)$ telles que $X$ est calculable. Montrer que tout ensemble suffisamment générique pour $\mathbb{P}$ est cohésif pour tous les ensembles calculables. ◇

Soit $f : [\mathbb{N}]^2 \to 2$ une instance calculable de $\text{RT}_2^2$. Tandis qu'un ensemble pré-homogène $P$ transforme $f$ en une instance $P$-calculable de $\text{RT}_2^1$, un ensemble cohésif $C$ transforme $f$ en une instance $\Delta_2^0(P)$ de $\text{RT}_2^1$.

**Fait**

Avec $k \ge 1$, fixons un coloriage $f : [\mathbb{N}]^2 \to k$. Soit $(R_{n,i})_{n\in\mathbb{N},i<k}$ la suite d'ensembles définie par $R_{n,i} = \{y \in \mathbb{N} : f(\{n, y\}) = i\}$. Soit $C$ un ensemble infini cohésif pour $(R_{n,i})_{n\in\mathbb{N},i<k}$. Alors, pour tout $x \in C$, $\lim_{y \in C} f(\{x, y\})$ existe. De plus, soit $g : C \to k$ le coloriage $\Delta_2^0(C \oplus f)$ défini par $g(x) = \lim_{y \in C} f(\{x, y\})$. Pour tout ensemble infini $Y \subseteq C$ homogène pour $g$, $Y \oplus f$ calcule un ensemble infini homogène pour $f$.

**PREUVE.** Soit $i < k$ la couleur d'homogénéité de $Y$ pour $g$. Alors, pour tout $x \in Y$, $\lim_{y \in C} f(\{x, y\}) = i$. Ainsi, soit $(x_n)_{n \in \mathbb{N}}$ la suite d'éléments de $Y$ définie comme suit : si $x_s$ est défini pour tout $s < n$, alors $x_n$ est le plus petit élément de $Y$ tel que pour tout $s < n$, $f(\{x_s, x_n\}) = i$. Un tel $x_n$ existe par l'hypothèse de limite. L'ensemble $\{x_n : n \in \mathbb{N}\}$ est homogène pour $f$. ■

Le fait 4.1 ramène donc l'étude des instances calculables de $\text{RT}_2^2$ à celle des instances $\Delta_2^0$ de $\text{RT}_2^1$ et des instances calculables de COH. Nous avons déjà étudié de manière extensive le principe infini des tiroirs dans la section 3, ce qui nous ramène à l'étude de COH.

La proposition suivante nous indique que COH n'est pas calculatoirement plus compliqué que $\text{RT}_2^2$. La réduction de COH à $\text{RT}_2^2$ est un peu subtile, et demande quelques précautions pour être formalisée dans RCA$_0$.

**Proposition 4.3 (Mileti [156]).** On a :

$$ \mathrm{RCA}_0 \vdash \mathrm{RT}_2^2 \to \mathrm{COH} \quad \text{et} \quad \mathrm{COH} \leq_W \mathrm{RT}_2^2. $$

⋆

**PREUVE.** Supposons $\text{RT}_2^2$. Soit $(R_n)_{n \in \mathbb{N}}$ une suite d'ensembles. En rajoutant de manière calculable des ensembles à $(R_n)_{n \in \mathbb{N}}$, on peut supposer que pour tout $x < y$, il existe un plus petit $i \in \mathbb{N}$ tel que $R_i(x) \neq R_i(y)$;
soit $i_{x,y}$ cet entier. On définit alors le coloriage $f : [\mathbb{N}]^2 \to 2$ pour tout $x < y$ par $f(\{x, y\}) = 1$ si $x \in X_{i_{x,y}}$, et $f(\{x, y\}) = 0$ sinon.

Soit $C = \{a_0 < a_1 < a_2 < \dots \}$ un ensemble homogène pour $f$ de couleur 0 (le cas 1 est symétrique). Soit $(H_{n,b}^i)$ la propriété « Pour tout ensemble fini $F$, si $R_n(a_s) = i$ et $R_n(a_{s+1}) = 1 - i$ pour tout $s \in F$, alors $|F| < b$. » Montrons que $(H_{n,b}^1)$ implique $(H_{n,b+1}^0)$. Soit $F = \{s_0 < s_1 < \dots < s_{l-1}\}$ un ensemble fini tel que $R_n(a_s) = 0$ et $R_n(a_{s+1}) = 1$ pour tout $s \in F$. Alors, pour tout $t < l-1$, il existe $s \in ]s_t, s_{t+1}]$ tel que $R_n(a_s) = 1$ et $R_n(a_{s+1}) = 0$, donc par $(H_{n,b}^1)$, $l-1 < b$, et donc $|F| < b+1$. Ainsi, $(H_{n,b+1}^0)$ est vrai.

Montrons par induction sur $n$ que $(H_{n,2^n}^1)$ est vrai. La formule $(H_{n,2^n}^1)$ étant $\Pi_1^0$, cette induction est valide car $\text{RCA}_0 \vdash \Pi_1^0$. Supposons que $(H_{m,2^m}^1)$ soit vrai pour tout $m < n$. Soit $F$ un ensemble tel que $R_n(a_s) = 1$ et $R_n(a_{s+1}) = 0$ pour tout $s \in F$. Comme $C$ est homogène pour $f$ de couleur 0, pour tout $s \in F$, on a $i_{a_s,a_{s+1}} < n$, car sinon on aurait $i_{a_s,a_{s+1}} = n$, et donc $f(\{a_s, a_{s+1}\}) = 1$.

Pour tout $m < n$, soit $F_m = \{s \in F : i_{a_s,a_{s+1}} = m\}$. Notons que pour tout $s \in F_m$, $R_m(a_s) = 0$ et $R_m(a_{s+1}) = 1$, car $C$ est homogène pour $f$ de couleur 0. Donc, par $(H_{m,2^m+1}^0)$, $|F_m| \le 2^m$. Comme $\bigcup_{m<n} F_m = F$, il vient $|F| \le \sum_{m<n} 2^m < 2^n$. Ainsi, $(H_{n,2^n}^1)$ est vrai.

Il est clair que si $(H_{n,2^n}^1)$ est vrai pour tout entier $n$, alors $C$ est cohésif pour $(R_n)_{n \in \mathbb{N}}$. $\blacksquare$

Jockusch et Stephan, [103] ont étudié la puissance calculatoire des ensembles cohésifs pour certaines suites d'ensembles particulières. La puissance calculatoire de COH est mise en lumière par la notion d'arbre de décision.

## Notation

Étant donné une suite $(R_n)_{n \in \mathbb{N}}$ et $\sigma \in 2^{<\mathbb{N}}$, on note $R^\sigma$ l'intersection

$$ \bigcap_{\sigma(n)=0} \mathbb{N} \setminus R_n \bigcap_{\sigma(n)=1} R_n $$

On note $C((R_n)_{n \in \mathbb{N}}) = \{P \in 2^{\mathbb{N}} : \forall \sigma < P |R^\sigma| = \infty\}$.

Intuitivement, lors de la construction d'un ensemble infini $C$ cohésif pour la suite $(R_n)_{n \in \mathbb{N}}$, on est confronté pour chaque $n$ à la décision de s'assurer que $C \subseteq^* R_n$ ou $C \subseteq^* \mathbb{N} \setminus R_n$. Si l'on note $R_n^0 = \mathbb{N} \setminus R_n$ et $R_n^1 = R_n$, alors $R^\sigma$ représente les décisions prises pour chaque $n < |\sigma|$. Une décision est mauvaise si $R^\sigma$ est un ensemble fini. Notons que si la suite $(R_n)_{n \in \mathbb{N}}$ est calculable, alors la classe $C((R_n)_{n \in \mathbb{N}})$ est $\Pi_1^0(\emptyset')$.
Les deux propositions suivantes clarifient les liens entre la puissance re-
quise pour calculer un chemin dans un arbre $\Delta_2^0$ et celle permettant de
calculer un ensemble cohésif pour une suite calculable d'ensembles. Elles
ont été prouvées de manière indépendante par Brattka et Rakotoniaina [25]
et Patey [172].

**Proposition 4.4.** Soit $(R_n)_{n \in \mathbb{N}}$ une suite calculable d'ensembles. Un ensemble calcule un ensemble cohésif pour $(R_n)_{n \in \mathbb{N}}$ si, et seulement si, son saut Turing calcule un membre de $C((R_n)_{n \in \mathbb{N}})$. $\star$

PREUVE. Soit $C$ un ensemble cohésif pour $(R_n)_{n \in \mathbb{N}}$. Soit $P \in 2^N$ l'unique suite telle que pour tout $\sigma < P$, $C \subseteq^* R^\sigma$. L'ensemble $P$ est $\Delta_2^0(C)$, et pour tout $\sigma < P$, $R^\sigma$ est infini, donc $P \in C((R_n)_{n \in \mathbb{N}})$.

Réciproquement, soit $X$ un ensemble dont le saut Turing calcule un mem-
bre $P$ de $C((R_n)_{n \in \mathbb{N}})$. Par le lemme de limite de Shoenfield, il existe une
fonction $X$-calculable $f : \mathbb{N}^2 \to 2$ telle que $\forall x \lim_y f(x, y) = P(x)$. Soit
alors $(x_n)_{n \in \mathbb{N}}$ la suite strictement croissante d'entiers définie $X$-calculatoi-
rement comme suit. Initialement, $x_0 = 0$; à chaque étape $s > 0$, cher-
cher une chaîne $\sigma \in 2^{<\mathbb{N}}$ de longueur $s$ et un entier $x_s \in R^\sigma$ plus grand
que $x_{s-1}$ tel que $f(x, x_s) = \sigma(x)$ pour tout $x < s$. Montrons que de
tels $\sigma$ et $x_s$ existent toujours. En effet, il existe un seuil $N_0 \in \mathbb{N}$ tel
que pour tout $x_s > N_0$ et tout $x < s$, $f(x, x_s) = P(x)$. En particulier,
pour $\sigma = P|_s$, $R^\sigma$ est infini, donc tout $x_s \in R^\sigma$ tel que $x_s > N_0$, satisfait
la propriété désirée.

Soit $C = \{x_n : n \in \mathbb{N}\}$. Montrons que $C$ est cohésif pour $(R_n)_{n \in \mathbb{N}}$. Pour tout $x \in \mathbb{N}$, il existe un seuil $N_1 \in \mathbb{N}$ tel que pour tout $s > N_1$, $f(x,x_s)=P(x)$. En particulier, $x_s \in R_x^{P(x)}$ pour tout $s > N_1$, donc $C \subseteq^* R_x^{P(x)}$. $\quad \blacksquare$

**Corollaire 4.5**

Soit $(R_n)_{n \in \mathbb{N}}$ une suite calculable d'ensembles. Tout degré high calcule un ensemble cohésif pour $(R_n)_{n \in \mathbb{N}}$.

PREUVE. À l'aide de $\emptyset''$, on peut calculer inductivement $\sigma_0 < \sigma_1 < \dots$, en cherchant à partir de $\sigma_n$ une valeur $i \in \{0,1\}$ telle que $|R^{\sigma_n i}| = \infty$. En particulier, si $X' \ge_T \emptyset''$, alors $X'$ calcule un membre de $C((R_n)_{n \in \mathbb{N}})$, et donc $X$ calcule un ensemble cohésif pour $(R_n)_{n \in \mathbb{N}}$. $\blacksquare$

Il est possible d'améliorer le corollaire précédent pour obtenir une ca-
ractérisation de la capacité à calculer un ensemble $(R_n)_{n \in \mathbb{N}}$-cohésif pour
toute suite calculable $(R_n)_{n \in \mathbb{N}}$.

**Proposition 4.6.** Une classe non vide $\mathcal{D} \subseteq 2^\mathbb{N}$ est $\Pi_1^0(\emptyset')$ si, et seulement si, il existe une suite calculable d'ensembles $(R_n)_{n \in \mathbb{N}}$ telle
que $\mathcal{C}((R_n)_{n \in \mathbb{N}}) = \mathcal{D}$. $^*$

PREUVE. Soit $(R_n)_{n \in \mathbb{N}}$ une suite calculable d'ensembles. Alors, $\mathcal{C}((R_n)_{n \in \mathbb{N}})$ est la classe $\Pi_1^0(\emptyset')$ donnée par $\{P \in 2^\mathbb{N} : \forall \sigma < P \ \forall x \ |R^\sigma| > x\}$. Notons que l'on peut obtenir un code de l'ensemble calculable $R^\sigma$ uniformément en $\sigma$, et donc que $\emptyset'$ peut répondre uniformément à la question de savoir si $|R^\sigma| > x$. Cela rend bien $\Pi_1^0(\emptyset')$ la classe $\mathcal{C}((R_n)_{n \in \mathbb{N}})$.

Pour la direction inverse, soit $T \subseteq 2^{<\mathbb{N}}$ un arbre $\Delta_2^0$ tel que $[T] = \mathcal{D}$. Par le lemme de limite de Shoenfield, il existe une fonction $f: 2^{<\mathbb{N}} \times \mathbb{N} \to 2$ calculable et telle que pour tout $\sigma \in 2^{<\mathbb{N}}$, $\lim_s f(\sigma, s) = T(\sigma)$. $\mathcal{D}$ étant non vide, $T$ est un arbre infini, et l'on peut donc supposer que

(1) pour tout $s \in \mathbb{N}$, l'ensemble $U_s = \{\sigma \in 2^s : f(\sigma, s) = 1\}$ est non vide.

(2) pour tout $\sigma < \tau$ et $s$, si $g(\tau, s) = 1$, alors $g(\sigma, s) = 1$.

Nous allons construire une suite calculable d'ensembles $(R_n)_{n \in \mathbb{N}}$ telle que $\mathcal{C}((R_n)_{n \in \mathbb{N}}) = \mathcal{D}$ comme suit. À l'étape 0, $R_n = \emptyset$ pour tout $n \in \mathbb{N}$, et supposons que l'on ait déjà décidé $R_n \upharpoonright_{k_s}$ pour tout $n \in \mathbb{N}$. À l'étape $s+1$, soit $p = |U_{s+1}|$. Nous allons ajouter des éléments $[n_s, k_s+p]$ à $R_0, \dots, R_s$ de telle sorte que pour toute chaîne $\sigma \in 2^{<\mathbb{N}}$ de longueur $s+1$, $R^\sigma \cap [k_s, k_s+p] \neq \emptyset$ ssi $\sigma \in U_{s+1}$. Pour cela, soit $\{\sigma_0, \dots, \sigma_{p-1}\} = U_{s+1}$. Pour tout $j \leqslant s$, ajouter à $R_j$ l'ensemble $\{k_s + i : \sigma_i(j) = 1, i < p\}$. Soit $k_{s+1} = k_s + p$. Cela termine la construction. Notons que par (1), la suite $(k_s)_{s \in \mathbb{N}}$ est strictement croissante, et les ensembles $(R_n)_{n \in \mathbb{N}}$ sont donc définis pour des segments initiaux arbitrairement grands.

Montrons que $R^\sigma$ est infini ssi $\sigma < P$ pour un $P \in \mathcal{D}$. Si $\sigma$ n'est préfixe d'aucun membre de la classe $\mathcal{D}$, alors par compacité, il existe un $t$ tel qu'aucun $\tau \supseteq \sigma$ de longueur $t$ n'est dans $T$. Soit $N_0 \in \mathbb{N}$ un seuil tel que pour tout $s > N_0$, $\sigma$ ne possède aucune extension dans $U_{s+1}$. Alors, par construction, pour tout $s > N_0$, $R^\sigma \cap [k_s, k_{s+1}] = \emptyset$, et $R^\sigma$ est donc fini.

Inversement, si $\sigma < P$ pour un $P \in \mathcal{D}$, alors par (2), il existe un seuil $N_1$ tel que pour tout $s > N_0$, $\sigma$ possède une extension dans $U_{s+1}$. Alors, par construction, pour tout $s > N_0$, $R^\sigma \cap [k_s, k_{s+1}] \neq \emptyset$, et $R^\sigma$ est donc infini. $\blacksquare$

**Corollaire 4.7 (Jockusch et Stephan [103])**

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

(1) Pour toute suite calculable d'ensembles $(R_n)_{n \in \mathbb{N}}$, $X$ calcule un ensemble cohésif pour $(R_n)_{n \in \mathbb{N}}$.

(2) Le saut $X'$ est $PA(\emptyset')$.

PREUVE. Immédiat, par la proposition 4.4 et la proposition 4.6. $\blacksquare$
Instance universelle pour COH

Nous avons vu dans le chapitre 8 que la classe $Π_1^0$ des complétions de l'arithmétique de Peano est *universelle*, au sens où tout degré PA calcule un membre de toute classe $Π_1^0$ non vide (voir la remarque 8-6). De la même manière, COH possède une instance $(R_n)_{n \in N}$ universelle, dans le sens où tout ensemble cohésif pour $(R_n)_{n \in N}$ calcule un ensemble cohésif pour toute suite calculable. En effet, par la proposition 4.4 et la proposition 4.6, il existe une suite calculable d'ensembles telle que tout ensemble cohésif a un saut Turing de degré PA relativement à $\emptyset'$. Par le corollaire 4.7, tout ensemble dont le saut Turing est PA relativement à $\emptyset'$ calcule un ensemble cohésif pour toute suite calculable d'ensembles.

Terminons l'étude calculatoire du principe de cohésion par la proposition suivante qui sera très utile dans la section 4.2.

**Proposition 4.8.** Soit $A$ un ensemble et soit $B \subseteq N^N$ un fermé non vide dans l'espace de Baire n'ayant pas de membre calculable. Il existe un ensemble $X$ tel que $X' \geq_T A$ et $X$ ne calcule pas de membre de $B$. ★

**PREUVE.** La preuve est similaire à celle de la proposition 4-10.2. Considérons la notion de forcing suivante : une condition est un couple $(g, n)$ pour $n \in N$, où $g$ est une fonction de type $\{0, \dots, p\}^2 \to 2$ pour $p \in N$. Une condition $(h, m)$ étend $(g, n)$ si $g \subseteq h, m \ge n$, et pour tout $(x, y)$ dans $dom h \setminus dom g$, si $x < n$, alors $y = A(x)$. Ainsi, pour toute condition $(g, n)$, les $n$ premières colonnes de $g$ sont stabilisées sur la valeur de $A$. Tout filtre maximal $F$ peut être interprété en une fonction $G = \bigcup_{(g,n) \in F} g$. Il est aisé de vérifier que $dom G = N \times N$, et que si $F$ est suffisamment générique, alors pour tout $x \in N$, $\lim_y G(x, y) = A(x)$. Ainsi, $A$ est $\Delta_2^0(G)$.

**Lemme 4.9.** Pour toute condition $c = (g, n)$ et tout $e \in N$, il existe une extension $d$ de $c$ forçant $\Phi_e^G \notin B$. ★

**PREUVE.** Trois cas se présentent.

Cas 1. Il existe $(h, n) \le (g, n)$ et $\sigma \in N^{<N}$ tel que $\Phi_e^h|_{\sigma|} = \sigma$ avec $[\sigma] \cap B = \emptyset$. Dans ce cas, $(h, n)$ force $\Phi_e^G \notin B$.

Cas 2. Il existe $(h, n) \le (g, n)$ et un entier $x$ tels que $\Phi_e^f(x) \uparrow$ pour tout $(f, m) \le (h, n)$. Alors, $(h, n)$ force $\Phi_e^G(x) \uparrow$, donc $\Phi_e^G \notin B$.

Cas 3. Les cas 1 et 2 sont faux. On obtient alors une contradiction en calculant une suite $(h, n) \ge (h_0, n) \ge (h_1, n) \ge \dots$ de conditions telle que $\Phi_e^{h_{x+1}} \supseteq \sigma_x$ avec $|\sigma_x| \ge x$. D'après la négation du cas 2, on peut toujours continuer une telle suite (notons à ce propos que la recherche d'extensions de conditions $(h_x, n)$ est calculable, car il n'y a besoin de connaître que les $n$ premiers bits de $A$, et que si $(h_x, m)$ est une extension de $(h_{x-1}, n)$, alors $(h_x, n)$ est aussi une extension valide de $(h_{x-1}, n)$). D'après la négation
du cas 1, on a $[\sigma_x] \cap \mathcal{B} \neq \emptyset$ pour tout $x$. Soit $P \in \bigcap_x [\sigma_x]$. Comme $\mathcal{B}$ est clos, $P \in \mathcal{B}$, ce qui contredit le fait que $\mathcal{B}$ n'ait pas de membre calculable. ■

Soit $F$ un filtre suffisamment générique pour cette notion de forcing, et soit $G = \bigcup_{(g,n) \in F} g$. Par le lemme 4.9, $G$ ne calcule pas de membre de $\mathcal{B}$, et par définition du forcing, $A$ est $\Delta_2^0(G)$. ■

**Corollaire 4.10**

Soit $(R_n)_{n \in \mathbb{N}}$ une suite calculable et $\mathcal{B} \subseteq \mathbb{N}^\mathbb{N}$ un fermé non vide dans l'espace de Baire n'ayant pas de membre calculable. Il existe un ensemble $C$ cohésif pour $(R_n)_{n \in \mathbb{N}}$ ne calculant pas de membre de $\mathcal{B}$.

PRÉUVE. Soit $A = \emptyset''$. Par la proposition 4.8, il existe un ensemble $X$ tel que $X' \geq_T \emptyset''$ et $X$ ne calcule pas de membre de $\mathcal{B}$. Par le corollaire 4.7, $X$ calcule un ensemble cohésif pour $(R_n)_{n \in \mathbb{N}}$. ■

**Exercice 4.11.** (⋆) (Wang [232]). Montrer à l'aide du forcing de Mathias calculable que si $C$ n'est pas $\Sigma_1^0$, pour toute suite calculable $(R_n)_{n \in \mathbb{N}}$, il existe un ensemble cohésif $D$ tel que $C$ n'est pas $\Sigma_1^0(D)$. ◇

## 4.2. Faiblesse calculatoire de $RT_2^2$

Le principe de cohésion étant calculatoirement très faible, une grande partie des propriétés calculatoires des instances non calculables du principe infini des tiroirs se retrouve dans les instances calculables du théorème de Ramsey pour les paires.

Rappelons qu'un problème $P$ préserve une propriété de faiblesse $\mathcal{W}$ si pour tout $Z \in \mathcal{W}$ et toute instance $X \leq_T Z$ de $P$, il existe une solution $Y$ telle que $Z \oplus Y \in \mathcal{W}$ (voir la section 24-1.1). Nous pouvons définir une notion forte de préservation en retirant la contrainte d'effectivité sur $X$.

**Définition 4.12.** Soit $\mathcal{W}$ une propriété de faiblesse. Un problème $Q$ préserve fortement $\mathcal{W}$ si pour tout $Z \in \mathcal{W}$, toute instance (arbitraire) $X$ de $Q$ admet une solution $Y$ telle que $Z \oplus Y \in \mathcal{W}$. ◇

Nous avons la correspondance formelle suivante entre les instances calculables de $RT_2^2$ et les instances arbitraires de $RT_2^1$.

**Proposition 4.13.** Soit $\mathcal{B} \subseteq \mathbb{N}^\mathbb{N}$ un fermé non vide dans l'espace de Baire, et soit $\mathcal{W} = \{Z : Z \text{ ne calcule pas de membre de } \mathcal{B}\}$. Alors, $RT_2^2$ préserve $\mathcal{W}$ si, et seulement si, $RT_2^1$ préserve fortement $\mathcal{W}$. ★
PREUVE. Supposons que $RT_2^2$ préserve $\mathcal{W}$. Soit $Z$ un ensemble ne calculant pas de membre de $\mathcal{B}$ et soit $g : \mathbb{N} \to 2$ une instance de $RT_2^1$. Par la proposition 4.8, il existe un ensemble $X$ tel que $g$ est $\Delta_2^0(X)$ et $X \oplus Z$ ne calcule pas de membre de $\mathcal{B}$. Par le lemme de limite de Shoenfield, il existe une fonction $X$-calculable $f : [\mathbb{N}]^2 \to 2$ telle que pour tout $x \in \mathbb{N}$, on a $\lim_y f(\{x, y\}) = g(x)$. Comme $RT_2^2$ préserve $\mathcal{W}$, il existe un ensemble infini $H$ homogène pour $f$ tel que $H \oplus X \oplus Z$ ne calcule pas de membre de $\mathcal{B}$. En particulier, $H$ est homogène pour $g$ et $H \oplus Z$ ne calcule pas de membre de $\mathcal{B}$, donc $RT_2^1$ préserve fortement $\mathcal{W}$.

Supposons que $RT_2^1$ préserve fortement $\mathcal{W}$. Soit $Z$ un ensemble ne calculant pas de membre de $\mathcal{B}$, et soit $f \leq_T Z$ une instance de $RT_2^2$. Soit $(R_n)_{n \in \mathbb{N}}$ la suite calculable définie par $R_x = \{y : f(\{x, y\}) = 1\}$. Par le corol- laire 4.10, il existe un ensemble $C$ cohésif pour $(R_n)_{n \in \mathbb{N}}$ tel que $C \oplus Z$ ne calcule pas de membre de $\mathcal{B}$. Comme $C$ est cohésif pour $(R_n)_{n \in \mathbb{N}}$, pour tout $x \in C$, $\lim_{y \in C} f(\{x, y\})$ existe. Soit $g : C \to 2$ le coloriage défini par $g(x) = \lim_{y \in C} f(\{x, y\})$. Par la proposition 2.2 et sachant que $RT_2^1$ préserve fortement $\mathcal{W}$, il existe un ensemble infini $H \subseteq C$ homogène pour $g$ tel que $H \oplus C \oplus Z$ ne calcule pas de membre de $\mathcal{B}$. Par le fait 4.1, $H \oplus C \oplus Z$ calcule un ensemble infini $Y$ homogène pour $f$. En particulier, $Y \oplus Z$ ne calcule pas de membre de $\mathcal{B}$, donc $RT_2^2$ préserve $\mathcal{W}$. $\blacksquare$

Nous avons à présent les éléments nécessaires pour montrer le théorème de Seetapun, qui stipule que $RT_2^2$, contrairement à $RT_2^3$, n'implique pas $ACA_0$ dans $RCA_0$.

**Théorème 4.14 (Seetapun [195])**

Pour tout ensemble $C$ non calculable et pour tout coloriage $f : [\mathbb{N}]^2 \to 2$ calculable, il existe un ensemble infini $H$ homogène pour $f$ tel que $C \not\leq_T H$.

PREUVE. Soit $C$ un ensemble non calculable, et soit $W=\{Z:C \not\leq_T Z\}$. Par le théorème 3.8 relativisé, $RT_2^1$ préserve fortement $\mathcal{W}$, donc par la proposi- tion 4.13, $RT_2^2$ préserve $\mathcal{W}$. Comme $C$ n'est pas calculable, $\emptyset \in \mathcal{W}$, de sorte que par la définition de la préservation pour $Z = \emptyset$, nous obtenons l'énoncé du théorème 4.14. $\blacksquare$

La preuve du théorème de Seetapun se relativise bien, et permet donc de créer, pour tout ensemble non calculable $C$, un idéal Turing satisfaisant $RT_2^2$ mais ne contenant pas $C$.
**Corollaire 4.15 (Seetapun [195])**

On a : RCA₀ + RT²₂ ⊊ ACA₀.

PREUVE. Soit $\mathcal{W} = \{X : \emptyset' \not\leq_T X\}$. Par le théorème 4.14, $RT_2^2$ préserve $\mathcal{W}$;
Comme ACA₀ ne préserve pas $\mathcal{W}$, le résultat escompté découle alors du
corollaire 24-1.12.
■

Jockusch [99] a prouvé l'existence d'une instance calculable de $RT_2^2$ sans
solution $\Delta_2^0$, montrant ainsi que $WKL_0$ n'implique pas $RT_2^2$ dans RCA₀.
Sachant que $RT_2^2$ est strictement plus faible que ACA₀, la dernière question
ouverte en lien avec les cinq grands systèmes des mathématiques à rebours
consiste à savoir si $RT_2^2$ implique $WKL_0$ dans RCA₀. Cette question, connue
sous le nom d'énigme de Seetapun, est également restée ouverte plusieurs
décennies avant que Liu [146] n'y réponde négativement, montrant ainsi
l'existence d'un théorème naturel qui n'est pas linéairement ordonné avec
le Club des cinq.

**Théorème 4.16 (Liu [146])**

Pour toute fonction calculable $f : [N]^2 \to 2$, il existe un ensemble infini $H$
homogène pour $f$ qui n'est pas de degré PA.

PREUVE. Soit $\mathcal{W} = \{X : X \text{ n'est pas de degré PA}\}$. Par le théorème 3.24 relativisé, $RT_2^1$ préserve fortement $\mathcal{W}$, donc par la proposition 4.13, $RT_2^2$ préserve $\mathcal{W}$. Comme $\emptyset \in \mathcal{W}$, par la définition de la préservation pour $Z = \emptyset$, nous obtenons l'énoncé du théorème 4.16.

■

**Corollaire 4.17**

On a : RCA₀ + RT²₂ ⊊ WKL₀.

PREUVE. Soit $\mathcal{W} = \{X : X \text{ n'est pas de degré PA}\}$.

Par le théorème 4.16, $RT_2^2$ préserve $\mathcal{W}$; or; $WKL_0$ ne préserve pas $\mathcal{W}$, donc
par le corollaire 24-1.12, $RCA_0 + RT_2^2 \not\subseteq WKL_0$.

■

**Exercice 4.18.** Montrer que pour tout ensemble *C* non $\Sigma_1^0$ et tout coloriage calculable $f : [N]^2 \to 2$, il existe un ensemble infini *H* homogène pour *f* tel que *C* n'est pas $\Sigma_1^0(H)$. ◇

Nous avons vu avec la proposition 4.4 et la proposition 4.4 l'existence d'une
instance calculable de COH dont toutes les solutions ont un saut Turing de
degré PA relativement à $\emptyset'$. Par la proposition 4.3, COH $\leq_W$ $RT_2^2$, donc il
existe une instance calculable de $RT_2^2$ dont toutes les solutions ont un saut
Turing de degré PA relativement à $\emptyset'$. Peut-on faire mieux ? Le théorème
suivant de Cholak, Jockusch et Slaman [33] affirme d'une certaine manière l'optimalité de cette borne en montrant qu'il est toujours possible d'obtenir une solution dont le saut Turing est borné par un degré PA relativement à $\emptyset'$.

**Théorème 4.19 (Cholak, Jockusch et Slaman [33])**

Pour tout coloriage calculable $f : [\mathbb{N}]^2 \to 2$ et pour tout ensemble $P$ de degré PA relativement à $\emptyset'$, il existe un ensemble infini $H$ homogène pour $f$ tel que $H' \leq_T P$.

**PREUVE.** Par l'exercice 14-1.12 relativisé à $\emptyset'$, il existe un ensemble $P_1$ de degré PA relativement à $\emptyset'$, tel que $P$ est de degré PA relativement à $P_1$. Par le théorème d'inversion de saut de Friedberg (voir le corollaire 10-3.33), il existe un ensemble $X$ tel que $X' \equiv_T P_1$. En particulier, $P$ est de degré PA relativement à $X'$.

Soit $(R_n)_{n \in \mathbb{N}}$ la suite calculable définie par $R_x = \{y : f(\{x, y\}) = 1\}$. Par le corollaire 4.7, $X$ calcule un ensemble $C$ cohésif pour $(R_n)_{n \in \mathbb{N}}$. En particulier, pour tout $x \in C$, $\lim_{y \in C} f(\{x, y\})$ existe.

Soit $g : C \to 2$ le coloriage $\Delta_2^0(C)$ défini par $g(x) = \lim_{y \in C} f(\{x, y\})$. Par la proposition 2.2 et le théorème 3.40 relativisé à $C$, il existe un ensemble infini $H \subseteq C$ homogène pour $g$ tel que $(H \oplus C)' \leq_T P \oplus C \leq_T P$. Par le fait 4.1, $H \oplus C$ calcule un ensemble infini $Y$ homogène pour $f$. En particulier, $Y' \leq_T (H \oplus C)' \leq_T P$. ■

**Corollaire 4.20 (Cholak, Jockusch et Slaman [33])**

Pour tout coloriage calculable $f : [\mathbb{N}]^2 \to 2$, il existe un ensemble infini $H$ homogène pour $f$ de degré $\text{low}_2$.

**PREUVE.** Par le théorème 8-4.3 relativisé à $\emptyset'$, il existe un ensemble $P$ de degré PA relativement à $\emptyset'$ tel que $P' \leq_T \emptyset''$. Par le théorème 4.19, il existe un ensemble infini $H$ homogène pour $f$ tel que $H' \leq_T P$. En particulier, $H'' \leq_T P' \leq_T \emptyset''$, donc $H$ est de degré $\text{low}_2$. ■

Le théorème de Seetapun se généralise à toute la hiérarchie arithmétique.

**Proposition 4.21 (Wang [232]).** Pour tout $n \geq 1$, tout ensemble $C$ non $\Delta_n^0$ et tout coloriage calculable $f : [\mathbb{N}]^2 \to 2$, il existe un ensemble infini $H$ homogène pour $f$ tel que $C$ n'est pas $\Delta_n^0(H)$. ★

**PREUVE.** Pour $n = 1$, il s'agit du théorème 4.14. Soit $n \geq 2$. Si $C$ n'est pas $\Delta_n^0$, alors il n'est pas $\Delta_{n-1}^0(\emptyset')$. Par le théorème de base d'évitement de cône relativisé à $\emptyset'$ (voir le théorème 8-4.7), il existe un ensemble $P$
de degré PA relativement à $\emptyset'$ tel que $C$ n'est pas $\Delta_{n-1}^0(P)$. Par le théorème 4.19, il existe un ensemble infini $H$ homogène pour $f$ tel que $H' \leq_T P$. En particulier, $C$ n'est pas $\Delta_{n-1}^0(H')$, et donc pas non plus $\Delta_n^0(H)$. ■

### 4.3. Invariants combinatoires du théorème de Ramsey

Rappelons ici la notion de préservation forte de la définition 4.12. On dira qu'un problème $P$ préserve fortement un cône si pour tout $C$ non calculable, tout ensemble $Z$ ne calculant pas $C$, toute instance arbitraire de $P$ admet une solution $X$ telle que $Z \oplus X \not\leq_T C$. La notion de préservation (non forte) de cône de la définition 24-1.13 est identique, mais pour des instances $Z$-calculables de $P$.

Nous avons une grande différence combinatoire du point de vue de la calculabilité entre $RT_k^1$ et $RT_k^2$. Le premier préserve fortement un cône, mais pas le deuxième : nous avons vu en effet que l'on pouvait construire une instance $\Delta_2^0$ de $RT_2^2$ dont toutes les solutions calculent $\emptyset'$. Wang a découvert qu'un léger affaiblissement du théorème de Ramsey pour les paires permettait de rétablir la préservation forte de cône.

**Notation**

On dénote par $RT_{k,\ell}^n$ l'énoncé $\ll$ Pour tout coloriage $f : [\mathbb{N}]^n \to k$, il existe un ensemble infini $H \subseteq \mathbb{N}$ tel que $|f([H]^n)| \leq \ell$. $\gg$

En particulier, $RT_{k,1}^n$ est l'énoncé $RT_k^n$. Une grande partie de l'analyse combinatoire du théorème de Ramsey se généralise à $RT_{k,\ell}^n$. En particulier, pour tout $k \geq \ell+1$, $RT_{k,\ell}^n$ implique $RT_{k+1,\ell}^n$ dans $\text{RCA}_0$ par un argument de d'altonisme (voir la proposition 2.3). Lorsque $k \leq \ell$, $RT_{k,\ell}^n$ est trivial, et donc calculatoirement vrai. Ainsi, seul le cas $RT_{\ell+1,\ell}^n$ est vraiment intéressant du point de vue des mathématiques à rebours.

Wang [231] a prouvé que pour tout $n$, lorsque $\ell$ est suffisamment grand par rapport à $n$, l'énoncé $\forall kRT_{k,\ell}^n$ évite fortement un cône. Cholak et Patey [34] ont étudié la borne exacte $\ell$ en fonction de $n$ pour laquelle $\forall kRT_{k,\ell}^n$ évite fortement un cône, et celle-ci coïncide de manière surprenante avec les nombres de Catalan, très connus en combinatoire.

**Définition 4.22.** La suite de Catalan est définie de manière inductive comme suit :

$$C_0 = 1 \quad \text{et} \quad C_{n+1} = \sum_{i=0}^{n} C_i C_{n-i}.$$

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

Les premières valeurs de la suite de Catalan sont 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, ... La suite de Catalan admet de nombreuses caractérisations combinatoires.
**Exemple 4.23.** Un parenthésage est une chaîne à valeurs dans {(), }}. Il est dit valide si le nombre de parenthèses ouvrantes est égal au nombre de parenthèses fermantes, et si pour tout préfixe, le nombre de parenthèses fermantes n’est jamais plus grand que celui de parenthèses ouvrantes. Ainsi, ((()())() est un parenthésage valide, tandis que )( et ((()() ne le sont pas. Notons qu’un parenthésage valide est forcément de longueur paire. Soit $C_n$ le nombre de parenthésages valides de longueur $2n$. Par exemple, il n’existe qu’un parenthésage valide de longueur 0, à savoir la chaîne vide, donc $C_0 = 1$. Il existe également un unique parenthésage valide de longueur 2, qui est (), donc $C_1 = 1$. En revanche, il existe deux parenthésages valides de longueur 4, qui sont ()() et ((()).

C'est avec l'élégante caractérisation suivante que nous concluons notre analyse du théorème de Ramsey du point de vue de la calculabilité.

**Théorème 4.24 (Wang [231], Cholak et Patey [34])**

Pour tout $n \ge 1$, $\forall kRT_{k,l}^n$ préserve fortement 1 cône si, et seulement si, $\ell \ge C_n$. Ainsi, $\forall kRT_{k,\ell}^{n+1}$ préserve un cône si, et seulement si, $\ell \ge C_n$.
<figure><img src="image_161.png" /></figure>
Quatrième partie

Hypercalculabilité
<figure><img src="image_162.png" /></figure>
Chapitre 26

Introduction

Il n’est pas aussi aisé de définir l’hypercalculabilité *per se* que nous ne l’avons fait pour les trois premières parties de cet ouvrage, à savoir la calculabilité classique, l’aléatoire algorithmique ou les mathématiques à rebours. En effet, l’hypercalculabilité ne manipule pas des objets mathématiques à correspondance épistémologique immédiate, comme c’est le cas pour les fonctions calculables ou les suites aléatoires. Ce domaine de recherche est avant tout un pont, entre la calculabilité classique d’une part, et la théorie des ensembles et la théorie descriptive des ensembles d’autre part. Pour ces raisons, l’hypercalculabilité se définit plus facilement en référence à ces théories, en adoptant soit une approche *descendante*, partant du point de vue de la théorie descriptive des ensembles et en considérant l’hypercalculabilité comme une effectivisation de ses concepts, soit une approche *ascendante*, en considérant l’hypercalculabilité comme une généralisation de la calculabilité classique pour laquelle on s’autorise *une infinité* d’étapes de calcul, via la notion *d’ordinaux*.

Pour le théoricien des ensembles, l'hypercalculabilité peut d'abord être vue comme l'étude des premiers niveaux de la hiérarchie de l'univers des constructibles. La constructibilité est un champ d'étude initié par Gödel, qui à partir d'un modèle de ZF, a montré comment construire un sous-modèle de ZF satisfaisant à la fois l'axiome du choix et l'hypothèse du continu. Le modèle de Gödel est l'univers des constructibles : les ensembles que l'on peut construire récursivement le long des ordinaux (que nous définirons formellement bientôt). Il s'agit toutefois d'un point de vue que nous ne développerons pas davantage dans cet ouvrage, et le lecteur curieux d'en apprendre plus à leur sujet pourra se reporter à [35] ou encore [192].
L'hypercalculabilité peut également être vue comme une version effective de la théorie descriptive des ensembles. Cette branche des mathématiques classifie les ensembles en fonction de leur complexité définitionnelle. Elle est née de la continuation des travaux de Borel, Baire et Lebesgue, par Nikolaï Luzin et Mikhail Souslin [219] au début du XXᵉ siècle. Nous parlerons des aspects historiques de manière détaillée dans la section 29-1. La théorie descriptive des ensembles n'est au départ pas liée à la calculabilité, et ce sera essentiellement Stephen Cole Kleene qui en développera les aspects effectifs [114] [115] [117] [116] entre les années 1938 et 1955. Ce sont surtout les travaux de Kleene et de ses collègues que nous présenterons dans cette partie.

**Pour le théoricien de la calculabilité,** l'hypercalculabilité est une généralisation des concepts de la calculabilité classique à des calculs et des constructions en temps infini, via le concept d'ordinal. Cela permet d'étendre la notion de calcul et de ses intuitions à d'autres notions de définissabilité. Cet ouvrage traitant de calculabilité, il est naturel d'aborder l'hypercalculabilité principalement sous ce prisme.

Plus concrètement, de nombreuses définitions de calculabilité le long des entiers peuvent être généralisées à des définitions le long des ordinaux. Par exemple, la hiérarchie arithmétique peut être étendue à des niveaux ordinaux, pour former la hiérarchie hyperarithmétique. Nous verrons toute une correspondance entre la calculabilité classique et l'hypercalculabilité, où les ensembles hyperarithmétiques correspondront aux ensembles calculables, les ensembles $Π_1^0$ aux ensembles calculatoirement énumérables, et le $O$ de Kleene au saut Turing. Ces notions seront toutes définies dans cette partie.

# 1. Motivations

Nous commençons par présenter un exemple, qui part de notions de calculabilité classique vues jusqu'ici, afin d'en montrer les limites ainsi que la nécessité de l'hypercalculabilité pour traiter certaines questions.

Souvenons-nous de la proposition 8-3.6, qui stipule que si une classe $Π_1^0$ contient exactement un élément $X$, alors $X$ est calculable. Nous appellerons de tels éléments des *singletons* $Π_1^0$. Qu'en est-il des singletons $Π_2^0$ ? La preuve de la proposition 19-1.2 montre que tout ensemble $\emptyset'$-calculable est un singleton $Π_2^0$. Il serait tentant de vouloir généraliser la situation des singletons $Π_1^0$ en conjecturant que les singletons $Π_2^0$ sont exactement les ensembles $\emptyset'$-calculables, mais la situation est dans ce cas bien plus complexe.

Afin de voir cela, nous commençons par présenter une construction alternative pour montrer que $\emptyset'$ est un singleton $Π_2^0$. Nous utilisons pour cela (2)
de l'exemple 17-3.7 : la classe $\mathcal{S}$ des ensembles qui sont des sauts Turing d'autres ensembles est $\Pi_2^0$. L'exemple utilisait l'existence d'une fonctionnelle $\Phi_e$ telle que $\Phi_e(X)$ est totale pour tout $X$ et telle que $\Phi_e(X') = X$ pour tout $X$. En utilisant $\Phi_e$, nous avions défini $\mathcal{S}$ comme suit :

$$ \bigcap_n \left\{ \begin{array}{l} X : X(n) = 1 \land \Phi_n(\Phi_e(X), n) \downarrow \\ \phantom{X : {}} \cup \{X : X(n) = 0 \land \Phi_n(\Phi_e(X), n) \uparrow \end{array} \right\}. $$

La classe $\mathcal{S}$ est bien une classe $\Pi_2^0$, qui peut être utilisée pour montrer sans peine que l'arrêt $\emptyset'$ est un singleton $\Pi_2^0$: c'est l'unique élément de la classe $\mathcal{S} \cap \{X : \Phi_e(X) = \emptyset\}$. On vérifie aisément que $\{X : \Phi_e(X) = \emptyset\}$ est une classe $\Pi_1^0$, qui est donc d'après le lemme 17-3.12 également $\Pi_2^0$. L'intersection des deux classes est dès lors tout aussi bien une classe $\Pi_2^0$. Par ailleurs, il est clair d'après les définitions respectives de ces classes que l'intersection contient uniquement l'élément $\emptyset'$.

On peut à présent continuer pour montrer que $\emptyset''$ est lui aussi un singleton $\Pi_2^0$. Soit $S_1$ la classe $\Pi_2^0$ contenant exactement $\emptyset'$. Alors, on peut définir $S_2$ la classe $\Pi_2^0$ contenant exactement $\emptyset''$ par

$$ S_2 = \mathcal{S} \cap \{X : \Phi_e(X) \in S_1\}. $$

On voit aisément comment continuer avec $S_{n+1} = \mathcal{S} \cap \{X : \Phi_e(X) \in S_n\}$, faisant de chaque ensemble $\emptyset^{(n)}$ un singleton $\Pi_2^0$.

Les singletons $\Pi_2^0$ peuvent donc être de complexité arithmétique arbitraire. Remarquons avant de continuer que l'inverse n'est déjà plus vrai : il existe des ensembles $\emptyset''$-calculables qui ne sont pas des singletons $\Pi_2^0$. Il suffit par exemple de remarquer que tout singleton $\Pi_2^0$ est un $\emptyset'$-test de Martin-Löf, et de considérer un ensemble 2-aléatoire $\emptyset''$-calculable. Les ensembles arithmétiques ne sont donc pas tous des singletons $\Pi_2^0$. De leur côté, les singletons $\Pi_2^0$ sont-ils au moins tous arithmétiques ? Là encore, la situation n'est pas si simple...

Considérons l'ensemble $\emptyset^{(\omega)} = \bigoplus_n \emptyset^{(n)} : \langle n, m \rangle \in \emptyset^{(\omega)} \text{ ssi } n \in \emptyset^{(m)}$. L'ensemble $\emptyset^{(\omega)}$ ne peut pas être arithmétique, c'est-à-dire $\Sigma_n^0$ pour un certain $n$. En effet, si $\emptyset^{(\omega)}$ est $\Sigma_n^0$, alors $\emptyset^{(n)} \ge_T \emptyset^{(\omega)}$. Par ailleurs, $\emptyset^{(\omega)} \ge_T \emptyset^{(n+1)}$, et donc $\emptyset^{(n)} \ge_T \emptyset^{(n+1)}$, ce qui est une contradiction. Si $\emptyset^{(\omega)}$ n'est pas arithmétique, il n'en est pas moins singleton $\Pi_2^0$ via la classe suivante :

$$ S_{\omega} = \left\{ \bigoplus_n X_n : \forall n X_n \in S_n \right\}. $$

On peut bien sûr continuer avec les ensembles

$$ S_{\omega+n+1} = \mathcal{S} \cap \{X : \Phi_e(X) \in S_{\omega+n}\}. $$

Jusqu'où cela va-t-il ? Cette question nous amène à l'étude et à la définition des ensembles dit hyperarithmétiques, qui comme nous le verrons sont exactement les ensembles Turing calculables par un singleton $\Pi_2^0$.