# Chapitre 20

**Solution 1.2.** Il s'agit de la même preuve, sauf que l'on crée un ensemble borné de requêtes pour ≪ copier ≫ la machine $U^A$ par une machine sans oracle. Ainsi, à la place de chercher $n > 2e$ tel que $n \in W_e[t+1]$ et tel que

$$ \sum_{\substack{U(\tau)[t+1]\downarrow=m, \\ \text{avec } m \ge n}} 2^{-|\tau|} < 2^{-e-1}, $$

on cherche $n > 2e$ tel que $n \in W_e[t+1]$ et tel que

$$ \sum_{\substack{U^{A_{t+1|m}}(\tau)[t+1]\downarrow, \\ \text{avec } m \ge n}} 2^{-|\tau|} < 2^{-e-1}. $$

Si l'on trouve un tel $n$, on l'énumère dans $A$ à l'étape $t+1$, puis pour tout $\tau$ tel que $U^{A_{t+1|m}}(\tau)[t+1] \downarrow = x$ pour $m \ge n$, on énumère $(x, |\tau|)$ dans $L$ à l'étape $t+1$.

**Solution 1.5.** Soit $A$ un ensemble, et soit $g: \mathbb{N} \to 2^{<\mathbb{N}}$ une fonction partielle $A$-calculable telle que si $\Phi_e^A(e) \downarrow$, alors $g(e) \prec A$ et $\Phi_e^{g(e)}(e) \downarrow$. En particulier,

$$ K^A(g(e)) \le K(e) \le 2^{\log_2(e)}. $$

Si de plus $A$ est low-pour-K, alors $K(g(e)) \le K^A(g(e))$. Soit $c \in \mathbb{N}$ tel que pour tout $e$, $K(g(e)) \le 2 \log_2(e) + c$. Soit $U$ une machine universelle telle que $K_U = K$. Pour décider si $\Phi_e^A(e) \downarrow$, il suffit de considérer chaque chaîne $\sigma$ de longueur au plus $2 \log_2(e)+c$, de tester à l'aide de $\emptyset'$ si $U(\sigma) \downarrow$ et $U(\sigma) \prec A$ (ce qui est possible, car $A$ est $\Delta_2^0$) et si $\Phi_e^{U(\sigma)}(e) \downarrow$. Si c'est le cas pour une chaîne $\sigma$, alors $\Phi_e^A(e) \downarrow$. Réciproquement, si $\Phi_e^A(e) \downarrow$, alors $g(e) \downarrow$; or, $K(g(e)) \le 2 \log_2(e) + c$, si bien qu'il existe une chaîne $\sigma$ de longueur au plus $2 \log_2(e) + c$ telle que $U(\sigma) = g(e)$. Cette chaîne $\sigma$ satisfait la propriété désirée.

**Solution 3.3.** D'après le théorème de la base low, il existe un ensemble MLR low, et donc en particulier incomplet et $\Delta_2^0$. Cet élément étant MLR, il n'est évidemment pas K-trivial.

# Chapitre 22

**Solution 2.2.** Soit $F(x)$ une formule de l'arithmétique du second ordre telle que $F(0)$ est vrai et telle que pour tout $x$, $F(x) \to F(x+1)$. Par le schéma de compréhension (9), l'ensemble $X = \{n \in \mathbb{N} : F(x)\}$ existe. On a notamment $0 \in X$, et pour tout $x$, si $x \in X$ alors $x+1 \in X$. Par le schéma d'induction (10), pour tout $x$, on a $x \in X$, donc pour tout $x$, $F(x)$ est vrai.

**Solution 5.3.** Il suffit de voir que la formule $n \in X$ pour une variable d'ensemble $X$ est $\Delta_0^0$.
**Solution 5.7.** Soit $X$ un ensemble low non calculable. On construit à l'aide du théorème 10-3.31 un ensemble 1-générique $G \leq_T \emptyset'$ tel que $X \oplus G$ calcule $\emptyset'$. Notons que $G' \leq_T G \oplus \emptyset'$, donc $G$ est low.

**Solution 5.8.** On lance en parallèle la construction avec des arbres calculables de deux ensembles $X_0, X_1$ calculatoirement dominés. On encode dans $X_0$ l'information nécessaire pour passer de l'étape $n$ à $n+1$ dans la construction de $X_1$, puis alternativement dans $X_1$ l'information nécessaire pour passer de l'étape $n$ à $n+1$ dans la construction de $X_0$. L'encodage est fait par rapport au choix du chemin (aller à gauche ou aller à droite) de $X_0$ ou $X_1$ dans leurs arbres calculables respectifs. L'ensemble $X_0 \oplus X_1$ peut alors décodeur la construction : il suffira d'y inclure un encodage d'un ensemble arbitraire $Z$.

**Solution 5.10.** Soit $X \in \mathcal{I}$, et soit $Y \leq_T X$. Il existe en particulier $n$ tel que $X \in \mathcal{I}_n$. Par clôture de $\mathcal{I}_n$ par réduction Turing, $Y \in \mathcal{I}_n$, donc $Y \in \mathcal{I}$. Soient $X, Y \in \mathcal{I}$. En particulier, il existe $n_0, n_1$ tels que $X \in \mathcal{I}_{n_0}$ et $Y \in \mathcal{I}_{n_1}$. Soit $n = \max(n_0, n_1)$. On a $X, Y \in \mathcal{I}_n$, donc par clôture de $\mathcal{I}_n$ par jointure, $X \oplus Y \in \mathcal{I}_n$, donc $X \oplus Y \in \mathcal{I}$.

**Solution 5.11.** Soit $\mathcal{I}_0 \subseteq \mathcal{I}_1 \subseteq \dots$ la suite définie par $\mathcal{I}_n = \{X \in 2^\mathbb{N} : X \leq_T Z_n\}$. En particulier, $\mathcal{I}_n$ est un idéal Turing, donc par l'exercice 5.10, $\mathcal{I} = \bigcup_n \mathcal{I}_n$ est un idéal Turing.

**Solution 6.2.** La formule $F(e) \equiv \Phi_e^X(e) \downarrow$ étant $\Sigma_1^0$ avec paramètre $X$, $\text{ACA}_0$ prouve l'existence de l'ensemble $Y = \{e : \Phi_e^X(e) \downarrow\}$ à l'aide du schéma de compréhension arithmétique.

Réciproquement, par la proposition 6.1, il suffit de montrer que $\text{RCA}_0 + \forall X \exists Y Y = X'$ prouve le schéma de compréhension $\Sigma_1^0$. Soit $F(x)$ une formule $\Sigma_1^0$ avec paramètres $X_0, \dots, X_{k-1}$. En particulier, avec le schéma de compréhension $\Delta_1^0$, l'ensemble $X_0 \oplus \dots \oplus X_{k-1}$ existe, et l'ensemble $Y = (X_0 \oplus \dots \oplus X_{k-1})'$ existe donc également. Soit $Z = \{x : F(x)\}$. L'ensemble $Z$ est $X_0 \oplus \dots \oplus X_{k-1}$-c.e., donc $Y$-calculable. Par le schéma de compréhension $\Delta_1^0$ avec paramètre $Y$, l'ensemble $Z$ existe.

**Solution 6.6.** Pour tout $\sigma \in 2^\mathbb{N}$, soit $I_\sigma \subseteq [0, 1]$ l'intervalle des réels dont l'expansion binaire commence par $0.\sigma$. Soit

$$C = \{X \in 2^\mathbb{N} : \forall n \exists m > n \ x_m \in I_{X|_n}\}.$$

La classe $C$ est $\Pi_1^0(\emptyset')$, non vide et contient exactement les $X \in 2^\mathbb{N}$ tels que $0.X$ est un point de convergence d'une sous-suite de $(x_n)_{n \in \mathbb{N}}$. Par la proposition 8-3.3 relativisée à $\emptyset'$, il existe un arbre $\emptyset'$-calculable $T \subseteq 2^{<\mathbb{N}}$ tel que $[T] = C$.

Soit $T \subseteq 2^{<\mathbb{N}}$ un arbre $\emptyset'$-calculable infini. Par l'exercice 8-7.13, il existe un ensemble calculable $S = \{\sigma_0, \sigma_1, \dots\} \subseteq 2^{<\mathbb{N}}$ contenant exactement une chaîne de chaque longueur, et telle que $[T] = [\hat{S}]$, où $\hat{S}$ est la clôture par préfixe de $S$. La suite $(x_n)_{n \in \mathbb{N}}$ définie par $x_n = 0.\sigma_n$ est telle que les points de convergence de ses sous-suites sont exactement de la forme $0.X$, où $X \in [T]$.
**Solution 7.4.** La construction est exactement celle de la proposition 7.3, mais en appliquant le théorème de base $\Pi_1^0$ calculatoirement dominée à la place du théorème d'évitement de cône.

**Solution 7.5.** La construction est exactement celle de la proposition 7.3, mais en appliquant le théorème de base $\Pi_1^0$ low à la place du théorème d'évitement de cône.

**Solution 7.7.** Pour tout $n$, soit $T_n = \{\sigma \in T : |\sigma| = n\}$, et soit $U_n = \bigcup_{\sigma \in T_n} [\sigma]$. Notons que $[T] = \bigcap_n U_n$. Comme pour tout entier $n$, on a $U_{n+1} \subseteq U_n$, alors $\lambda([T]) = \lim \inf_n \lambda(U_n)$. Comme $T_n$ est sans préfixe, on a

$$ \lambda(U_n) = \sum_{\sigma \in T_n} \lambda([\sigma]) = \sum_{\sigma \in T_n} \frac{1}{2^n} = \frac{|\{\sigma \in T : |\sigma| = n\}|}{2^n}. $$

# Chapitre 23

**Solution 2.2.** Il suffit de reprendre l'exemple 2.1 en ayant cette fois deux éléments $\infty_1$ et $\infty_2$ tels que

$$ \begin{aligned} \infty_1 + \infty_2 &= \infty_2, \quad \infty_2 + \infty_1 &= \infty_1, \\ \infty_1 \times \infty_2 &= \infty_1, \quad \infty_2 \times \infty_1 &= \infty_2, \quad \infty_1 + \infty_1 &= \infty_1, \quad \infty_2 + \infty_2 &= \infty_2, \end{aligned} $$

ainsi que $i+n=n+i=i$ pour $i \in \{\infty_1, \infty_2\}$ et $n \in \omega$, de même que $i \times n = n \times i = i$ pour $i \in \{\infty_1, \infty_2\}$ et $n \in \omega$ avec $n \neq 0$, et finalement $i \times 0 = 0 \times i = 0$ pour $i \in \{\infty_1, \infty_2\}$.

**Solution 2.4.**

(1) La stratégie est la même que pour montrer $x + y = y + x$. On montre d'abord $0 \times x = 0$, puis $(x+1) \times y = x \times y + y$. Cette étape utilise l'associativité et la commutativité de l'addition. On utilise ces deux résultats pour montrer $x \times y = y \times x$. Les détails sont laissés aux lecteurs.

(2) On a $x \times (y+0) = x \times y = x \times y + x \times 0$ par (4) et (6) de Q. Supposons $x \times (y+z) = (x \times y) + (x \times z)$. Alors, $x \times (y+(z+1)) = x \times ((y+z)+1) = (x \times (y+z)) + x = (x \times y)+(x \times z)+x = x \times y+x \times (z+1)$ par (7) de Q, par l'hypothèse d'induction, et par l'associativité et la commutativité de l'addition.

(3) On a $(x \times y) \times 0 = 0 = x \times (y \times 0)$ par (6) de Q. Supposons $(x \times y) vz = x \times (y \times z)$. Alors, $(x \times y) \times (z+1) = ((x \times y) \times z) + (x \times y) = x \times (y \times z) + (x \times y) = x \times (y \times z + y) = x \times (y \times (z+1))$ par (7) de Q, par l'hypothèse d'induction et la distributivité.

**Solution 2.6.** Supposons $x < y$ et soit $z \neq 0$. On a $x + a = y$ pour $a \neq 0$. Donc, $(x+a) \times z = y \times z$. Par distributivité de la multiplication, on a

$$ x \times z + a \times z = y \times z. $$

Comme $a \neq 0$ et $z \neq 0$, on a $a \times z \neq 0$ par injectivité de la multiplication. Donc, $x \times z < y \times z$.
**Solution 2.7.** Montrons l'existence par induction sur $a$. Soit $b \neq 0$.

On a $0 = 0 \times b + 0$. Supposons $\exists q, r \leq a$ ($0 \leq r < b \land a = qb + r$). Si $r < b - 1$, alors $a + 1 = qb + (r + 1)$. Si $r = b - 1$, alors $a + 1 = (q + 1)b$. Dans tous les cas, $\exists q, r \leq a + 1$ ($0 \leq r < b \land a + 1 = qb + r$). Par $\mathrm{I}\Delta_n^0$, l'existence est assurée pour tout $a$.

Montrons l'unicité. Supposons $a = qb + r = q'b + r'$ avec $0 \leq r, r' < b$. Supposons par l'absurde $q \neq q'$. On peut supposer sans perte de généralité $q + 1 \leq q'$. Par l'exercice 2.6, on a $qb + b \leq q'b$. Comme $r < b$, on a $qb + r < qb + b \leq q'b \leq q'b + r'$. Donc, $qb + r < q'b + r'$, ce qui contredit $qb + r = q'b + r'$. Ainsi, $q = q'$, ce qui implique $r = r'$.

**Solution 3.6.** Nous allons le montrer dans le cas $\Sigma_n^0$. Le cas $\Pi_n^0$ est similaire. Soit $\mathbb{P}_n$ le schéma d'induction ordonné pour les formules $\Sigma_n^0$.

Montrons $\mathbb{Q} \vdash \mathrm{I}\Sigma_n^0 \to \mathbb{P}_n$. Soit $F(x)$ une formule $\Sigma_n^0$ telle que

$$ \forall x[(\forall y < x F(y)) \to F(x)], $$

et soit $z$ fixé. Montrons que $F(z)$ est vrai. Soit $G(x) \equiv (x \leq z \to \forall y < x F(y))$. Clairement, $G(0)$ est vrai, car $\forall y < 0 F(y)$ est vrai. De plus, si $G(x)$ est vrai, alors $G(x + 1)$ est vrai. En effet, si $x \leq z$, alors $\forall y < x F(y)$ est vrai, donc $F(x)$ est vrai, donc $\forall y < x + 1 F(y)$ est vrai, donc $G(x + 1)$ est vrai. Si $x > z$, alors trivalement $G(x + 1)$ est vrai. Il s'ensuit que $G$ satisfait les prémisses de $\mathrm{I}\Sigma_n^0$, donc $\forall x G(x)$ est vrai. En particulier, $G(z)$ est vrai, donc $\forall y < z F(y)$ est vrai, donc $F(z)$ est vrai.

Montrons $\mathbb{Q} \vdash \mathbb{P}_n \to \mathrm{I}\Sigma_n^0$. Soit $F(x)$ une formule $\Sigma_n^0$ telle que $F(0)$ et $\forall x(F(x) \to F(x + 1))$. En particulier, $\forall x[(\forall y < x F(y)) \to F(x)]$, donc par $\mathbb{P}_n$, $\forall x F(x)$ est vrai.

**Solution 5.4.** (i) La relation $x \in y$ est $\Delta_0^0$ pour tout $y$; l'ensemble $\{x \in \mathbb{N} : x \in y\}$ existe donc par le schéma de compréhension $\Delta_1^0$.

(ii) Soit $X$ un ensemble et soit $b \in \mathbb{N}$. La fonction $f : \mathbb{N} \to \mathbb{N}$ définie par $f(0) = 0$ et $f(n + 1) = f(n) + 2^n$ si $n \in X$, et $f(n + 1) = f(n)$ si $n \notin X$ est primitive récursive en $X$, donc prouvable dans $\mathrm{RCA}_0$. Par construction, $f(b)$ est le code canonique de l'ensemble $X$.

**Solution 5.7.** Le cas $n = 0$ est trivial, car $\mathrm{RCA}_0$ prouve les deux énoncés.

Supposons $\mathrm{I}\Delta_n^0$. Soient $F(x, y)$, $G(x, y)$ des formules respectivement $\Pi_{n-1}^0$, $\Sigma_{n-1}^0$ telles que $\forall x(\exists y F(x, y) \leftrightarrow \forall y G(x, y))$ et soit $a \in \mathbb{N}$. Montrons qu'avec ces hypothèses-là l'ensemble $A = \{x \in \mathbb{N} : x < a \land \exists y F(x, y)\}$ existe. On a

$$ \forall x \exists y (F(x, y) \lor \neg G(x, y)). $$

Par le théorème 3.9, $\mathrm{I}\Delta_n^0 \to \mathbb{B}\Sigma_n^0$, et par $\mathbb{B}\Sigma_n^0$, il existe un $b \in \mathbb{N}$ tel que

$$ \forall x \leq a \exists y \leq b (F(x, y) \lor \neg G(x, y)). $$

Ainsi, $A = \{x \in \mathbb{N} : x < a \land \exists y \leq b F(x, y)\}$, donc est $\Pi_{n-1}^0$. Par le théorème 3.7,
on a $B\Sigma_n^0 \to I\Sigma_{n-1}^0$, et par la proposition 5.6, $I\Sigma_{n-1}^0 \to BC\Sigma_{n-1}^0$, or $BC\Sigma_{n-1}^0 \leftrightarrow BC\Pi_{n-1}^0$, donc l'ensemble A existe.

Supposons $BC\Delta_n^0$. Soit $F(x)$ un prédicat $\Delta_n^0$ tel que $F(0)$ est vrai et pour tout entier $n$, on a $F(n) \to F(n+1)$. Soit $a \in \mathbb{N}$. Montrons que $F(a)$ est vrai. Par $BC\Delta_n^0$, l'ensemble $X = \{x \le a : F(x)\}$ existe. Par le schéma de compréhension $\Delta_1^0$, l'ensemble $Y = X \cup \{y \in \mathbb{N} : y > x\}$ existe. On a $0 \in Y$ et $\forall x (x \in Y \to x+1 \in Y)$. Par l'axiome d'induction (10), qui prouvable dans $RCA_0$, $\forall x, x \in Y$. En particulier, $a \in Y$, donc $F(a)$ est vrai.

**Solution 6.9.** Cette transformation purement syntaxique se fait par induction sur la structure des formules, en replaçant les formules basiques $x \in X$ par la formule $\Sigma_1 F_\exists(x)$, et $x \notin X$ par la formule $\Sigma_1 \neg F_\forall(x)$, où $F_\exists$ et $F_\forall$ définissent l'ensemble $X \in S^N$ à l'aide de paramètres dans $\mathcal{M}$. Les quantificateurs existentiels sortent de la formule à l'aide de $B\Sigma_1^0$, qui est satisfait par $\mathcal{M}$.

**Solution 6.16.** Il suffit de montrer l'exercice dans le cas où $F$ est $\Delta_0^0$. On imposera de plus que $H(\sigma)$ soit monotone sur $\sigma$, c'est-à-dire que si $H(\sigma)$ est vrai, $H(\tau)$ est vrai pour tout $\tau \ge \sigma$. On procède par induction sur $F$.

Les cas suivants sont immédiats.

Si $F(X) \equiv x \in X$, alors $H(\sigma) \equiv x < |\sigma| \wedge \sigma(x) = 1$.

Si $F(X) \equiv x \notin X$, alors $H(\sigma) \equiv x < |\sigma| \wedge \sigma(x) = 0$.

Si $F(X)$ est parmi $t_1 = t_2$, $t_1 \ne t_2$, ou $t_1 < t_2$, alors la variable $X$ n'apparaît pas dans $F$, et $H$ est donc identique à $F$.

Si $F(X)$ est parmi $F_1(X) \wedge F_2(X)$ ou $F_1(X) \equiv F_2(X)$, alors par hypothèse d'induction, il existe des formules $\Delta_0^0$ monotones $H_1(\sigma)$ et $H_2(\sigma)$ telles que pour tout ensemble $G \subseteq M$, $M \cup \{G\} \models F_i(G) \leftrightarrow \exists k H(G \upharpoonright_k)$. Alors, si $H(\sigma)$ est défini par $H_1(\sigma) \wedge H_2(\sigma)$ ou $H_1(\sigma) \vee H_2(\sigma)$ en fonction du cas.

Si $F(X) \equiv \exists x < t F_1(x, X)$, alors soit $H_1(x, \sigma)$ la formule $\Delta_0^0$ correspondant à $F_1$ par hypothèse d'induction. La formule $H(\sigma) \equiv \exists x < t H_1(x, \sigma)$ satisfait l'induction.

Le cas non trivial est la quantification universelle bornée : si

$$F(X) \equiv \forall x < t F_1(x, X),$$

alors soit $H_1(x, \sigma)$ la formule $\Delta_0^0$ correspondant à $F_1$ par hypothèse d'induction. Soit $H(\sigma) \equiv \forall x < t H_1(x, \sigma)$. Montrons que $H(\sigma)$ satisfait l'induction.

Soit $G \subseteq M$. Si $M \cup \{G\} \models \exists k H(G \upharpoonright_k)$, alors par définition, il existe $k \in M$ tel que $M \cup \{G\} \models \forall x < t H_1(x, G \upharpoonright_k)$, donc $M \cup \{G\} \models \forall x < t \exists k H_1(x, G \upharpoonright_k)$.

Par hypothèse d'induction, $M \cup \{G\} \models \forall x < t F_1(x, G)$ et $M \cup \{G\} \models F(G)$.

Réciproquement, supposons que $M \cup \{G\} \models F(G)$.

Alors, par définition, $M \cup \{G\} \models \forall x < t F_1(x, G)$, donc par hypothèse d'induction, $M \cup \{G\} \models \forall x < t \exists k F_1(x, G \upharpoonright_k)$. Par $B\Sigma_1^0$ et monotonicité de $F_1$, $M \cup \{G\} \models \exists k \forall x < t F_1(x, G \upharpoonright_k)$.
# Chapitre 24

**Solution 1.4.** Montrons $\mathbf{WKL} \leq_{\omega} \mathbf{KL}$. Les idéaux Turing satisfaisant $\mathbf{WKL}$ sont les idéaux de Scott, tandis que ceux satisfaisant $\mathbf{KL}$ sont les idéaux de saut. Sachant que pour tout $X, X'$ est de degré PA relativement à $X$, tout idéal de saut est un idéal de Scott.

Montrons $\mathbf{KL} \not\leq_{\omega} \mathbf{WKL}$. Soit $\mathcal{I}$ un idéal de Scott ne contenant que des ensembles low (voir l'exercice 22-7.5). Alors, $\mathcal{I}$ n'est pas un idéal de saut, puisque $\emptyset \in \mathcal{I}$ mais $\emptyset' \notin \mathcal{I}$. Ainsi, $\mathcal{I} \models \mathbf{WKL}$, mais $\mathcal{I} \not\models \mathbf{KL}$.

**Solution 2.2.** Soit $\mathcal{I}$ un idéal Turing satisfaisant $\mathcal{Q}$. Montrons que $\mathcal{I} \models \mathbf{P}$. Soit $X$ une instance de $\mathbf{P}$ dans $\mathcal{I}$. Comme $\mathbf{P} \leq_c \mathcal{Q}$, il existe une instance $\tilde{X}$ de $\mathcal{Q}$ telle que pour toute $\mathcal{Q}$-solution $\tilde{Y}$ de $\tilde{X}$, $X \oplus \tilde{Y}$ calcule une $\mathbf{P}$-solution de $X$. Comme $\mathcal{I}$ est clos par réduction Turing, $\tilde{X} \in \mathcal{I}$. Comme $\mathcal{I} \models \mathcal{Q}$, il existe une $\mathcal{Q}$-solution $\tilde{Y}$ de $\tilde{X}$ dans $\mathcal{I}$. Par clôture de $\mathcal{I}$ par jointure effective, $X \oplus \tilde{Y} \in \mathcal{I}$, et enfin par clôture de $\mathcal{I}$ par réduction Turing, $\mathcal{I}$ contient une $\mathbf{P}$-solution de $X$. Donc, $\mathcal{I} \models \mathbf{P}$.

**Solution 2.3.** Soit $T$, un arbre infini calculable à branchement fini, dont tous les chemins sont de degré PA relativement à $\emptyset'$ (voir la proposition 8-7.4). Soit $\tilde{X} \leq_T T$ une instance de $J$. En particulier, $\tilde{X}$ est calculable, donc $\tilde{X}' \equiv_T \emptyset'$, et $\tilde{X}'$ n'est donc pas de degré PA relativement à $\emptyset'$. Comme $\tilde{X}'$ est l'unique solution de $\tilde{X}$ et ne $T$-calcule pas de chemin infini de $T$, $\mathbf{KL} \not\leq_c \mathbf{J}$.

**Solution 2.7.** Supposons que $\mathbf{P}$ est calculatoirement vrai. Soit $X$ une instance de $\mathbf{P}$. En particulier, $X$ est une instance de $\mathbf{Id}$, donc l'unique solution est $X$; or, $X \oplus X \geq X$ et $X$ calcule une $\mathbf{P}$-solution de $X$, donc $X \oplus X$ calcule une solution de $X$.

Supposons que $\mathbf{P} \leq_c \mathbf{Id}$. Soit $X$ une instance de $\mathbf{P}$. Soit $\tilde{X}$ une instance $X$-calculable de $\mathbf{Id}$ telle que pour toute $\mathbf{Id}$-solution $\tilde{Y}$ de $\tilde{X}$, $X \oplus \tilde{Y}$ calcule une solution de $\mathbf{P}$. Comme $\tilde{X}$ est l'unique $\mathbf{Id}$-solution $\tilde{Y}$ et $X \geq_T X \oplus \tilde{X}$, alors $X$ calcule une $\mathbf{P}$-solution de $X$, donc $\mathbf{P}$ est calculatoirement vrai.

**Solution 3.3.** Supposons que $\mathbf{P}$ est uniformément vrai à l'aide de la fonctionnelle $\Phi$. Soit $\Psi$ la fonctionnelle définie par $\Psi(A \oplus B) = \Psi(B)$. Alors, $\mathbf{P} \leq_w \mathbf{Id}$ comme en témoignent les fonctionnelles $\Phi$ et $\Psi$.

Réciproquement, supposons que $\mathbf{P} \leq_w \mathbf{Id}$ à l'aide des fonctionnelles $\Phi$ et $\Psi$. Soit $\Gamma$ la fonctionnelle définie par $\Gamma(X) = \Psi(X \oplus \Phi(X))$. Pour toute instance $X$ de $\mathbf{P}$, $\Gamma(X)$ est une solution de $X$.

**Solution 3.7.** Montrons que $\mathbf{LLPO} \leq_w \mathbf{LPO}$. Soit $\Phi$ la fonctionnelle définie par $\Phi^X(n) = 1-X(n)$. Soit $\Psi$ la fonctionnelle telle $\Psi^{X \oplus i}(0)$ cherche un entier $n$ tel que $X(n) = 1$ si $i = 1$, et renvoie $(n+1)$ mod 2. Si $i = 0$, la fonctionnelle renvoie 0 (par convention, on aurait pu choisir 1). Si $X$ est une instance de $\mathbf{LLPO}$, alors $\Phi^X$ est une instance de $\mathbf{LPO}$ dont la solution est 1 ssi il existe $n$ tel que $X(n) = 1$.
Ainsi, si $i = 1$, l'instance $X$ de LLPO n'aura qu'une seule solution, et la recherche de $\Psi^{X \oplus i}(0)$ s'arrête et renvoie la bonne solution. Si $i = 0$, les deux valeurs sont des solutions de $X$, $\Psi^{X \oplus i}(0) = 0$ est donc une solution valide. Ainsi, $\Phi$ et $\Psi$ témoignent de LLPO $\leq_W$ LPO.

Montrons que LPO $\leq_W$ LLPO. Raisonnons par l'absurde. Supposons que LPO $\leq_W$ LLPO est témoigné par des fonctionnelles $\Phi$ et $\Psi$. La suite $1^\infty$ est une instance de LPO dont la solution est $0$. Ainsi, $\Phi(1^\infty)$ est une instance de LLPO.

Cas 1. $\Phi(1^\infty) = 0^\infty$, autrement dit, les valeurs $0$ et $1$ sont toutes deux LLPO-solutions de $\Phi(1^\infty)$. Alors, $\Psi^{1^\infty \oplus 0}(0) \downarrow = \Psi^{1^\infty \oplus 1}(0) \downarrow = 0$. Soit $n$ la taille maximum de l'usage de ces deux calculs. Alors, $\Psi^{0^n 1^\infty \oplus 0}(0) \downarrow = \Psi^{0^n 1^\infty \oplus 1}(0) \downarrow = 0$, ce qui n'est pas la LPO-solution de $0^n 1^\infty$.

Cas 2. $\Phi(1^\infty)(s) = 1$ pour un $s \in \omega$. Alors, $i = (s+1)$ mod $2$ est l'unique solution de la LLPO-instance $\Phi(1^\infty)$ et $\Psi^{1^\infty \oplus i}(0) \downarrow = 0$. Soit $n$ plus grand que l'usage de $\Phi(1^\infty)(s)$ et de $\Psi^{1^\infty \oplus i}(0)$. En particulier, $\Phi(1^n 0^\infty)(s) = 1$ et $\Psi^{1^n 0^\infty \oplus i}(0) \downarrow = 0$; or, $i$ est la LLPO-solution de $\Phi(1^n 0^\infty)$, mais $0$ n'est pas la LPO-solution de $1^n 0^\infty$. Contradiction !

**Solution 3.8.** Supposons que LLPO est uniformément vrai, avec $\Phi$ comme fonctionnelle Turing. En particulier, $0^\infty$ est une instance de LLPO, donc $\Phi(0^\infty)(0) \downarrow = i$ pour un $i < 2$. Soit $n$ la longueur de l'usage de ce calcul.

En particulier, $X_0 = 0^n 10^\infty$ et $X_1 = 0^n 010^\infty$ sont deux instances de LLPO telles que $\Phi(X_0) = \Phi(X_1) = i$ par la propriété de l'usage, mais $X_0$ et $X_1$ ont des solutions opposées. Contradiction !

**Solution 3.10.** Soient $\Phi$, $\Psi$ des fonctionnelles Turing qui témoignent de P$\leq_W$ Q. Soit $\Phi_1$ la fonctionnelle définie par $\Phi_1(\bigoplus_n X_n) = \bigoplus_n \Phi(X_n)$ et soit $\Psi_1$ la fonctionnelle définie par $\Psi_1(\bigoplus_n X_n, \bigoplus_n Y_n) = \bigoplus_n \Psi(X_n, Y_n)$. Les fonctionnelles $\Phi_1$ et $\Psi_1$ témoignent de $\hat{P} \leq_W \hat{Q}$.

**Solution 3.12.** Montrons que WKL $\leq_W$ $\overline{LLPO}$. Pour tout $\sigma \in 2^{<N}$, soit $\Gamma_\sigma$ la fonctionnelle Turing définie par $\Gamma_\sigma^T(2s + i) = 1$ ssi $s$ est le plus petit entier tel que $\forall \tau \in 2^{\sigma|s+1}$ ($\sigma i \le \tau \to \tau \notin T$). Autrement dit, soit $T \subseteq 2^{<N}$ un arbre binaire, et $\sigma \in T$ un nœud dont la sous-branche dans $T$ est infinie. Si $i < 2$ est une solution de $\Gamma_\sigma^T$ vue comme une instance de LLPO, $\sigma i$ est un nœud dont la sous-branche dans $T$ est encore infinie. Soit $\Phi$ la fonctionnelle Turing définie par $\Phi^X = \bigcup_{\sigma \in 2^{<N}} \Gamma_\sigma^X$. Soit $\Psi$ la fonctionnelle Turing définie pour tout $n$ par

$$ \Psi(T \oplus (\bigoplus_{\sigma} i_{\sigma})) (n) = i_{\Psi(T \oplus (\bigoplus_{\sigma} i_{\sigma}))} |_n. $$

Les fonctionnelles $\Phi$ et $\Psi$ témoignent de WKL $\leq_W$ $\overline{LLPO}$.

Montrons que $\overline{LLPO} \leq_W$ WKL. Soit $\Phi$ la fonctionnelle Turing définie par

$$ \Phi^{\oplus_n X_n} = \{ \sigma \in 2^{<N} : \forall n, s < |\sigma| X_n (2s + \sigma(n)) = 0 \}. $$

Notons que $\Phi^{\oplus_n X_n}$ est un arbre binaire infini dont tous les chemins sont des $\overline{LLPO}$-solutions de $\bigoplus_n X_n$. Soit $\Psi$ la fonctionnelle définie par $\Psi(X \oplus Y) = Y$. Les fonctionnelles $\Phi$ et $\Psi$ témoignent de $\overline{LLPO} \leq_W$ WKL.
**Solution 4.4.** Montrons que $KL \leq_{\omega}^2 J$. Soit $T$ une instance de KL jouée par le joueur 1. Autrement dit, $T$ est un arbre infini à branchement fini. Le joueur 2 joue $T$ comme une instance de $J$. Le joueur 1 n'a pas d'autre choix que de jouer l'unique J-solution de $T$, à savoir $T'$. Le joueur 2 joue $T'$ comme une instance $J$. Le joueur 1 joue alors $T''$, et le joueur 2 $T''$-calcule une solution de $T$, car tout arbre infini à branchement fini admet une solution calculable en son double saut. Le joueur 2 a donc une stratégie qui le fait gagner en au plus trois tours.

Montrons que $J \not\leq_{\omega}^1 KL$. Le joueur 1 joue un arbre $T$ infini à branchement fini calculable n'ayant pas de chemin $\emptyset'$-calculable. Le joueur 2 doit alors jouer une $J$-instance $X \leq T$, et le joueur 1 joue alors la J-solution $X'$. Comme $X' \leq_T T'$ et $T$ n'admet pas de solution $T'$-calculable, le joueur 2 ne gagne pas non plus au second tour.

**Solution 5.6.** Notons que pour tout problème $Q$, si $P \leq_{sW} Q$, alors $P \leq_W Q$, car il suffit de ne pas tenir compte de l'instance $X$ de $P$.

Supposons que $Q$ est un cylindre pour $\leq_{sW}$ et que $P \leq_W Q$, comme en témoignent des fonctionnelles $\Phi_0, \Psi_0$. Soient alors $\Phi_1, \Psi_1$ les fonctionnelles témoignant de $\mathrm{Id} \times Q \leq_{sW} Q$. Soit $\Phi_2$ la fonctionnelle définie par $\Phi_2(X) = \Phi_1(X \oplus \Phi_0(X))$ et $\Psi_2$ la fonctionnelle définie par $\Psi_2(Y) = \Psi_0(\Psi_1(Y))$. Les fonctionnelles $\Phi_2$ et $\Psi_2$ témoignent de $P \leq_{sW} Q$.

Supposons maintenant que pour tout problème $P$, si $P \leq_W Q$ alors $P \leq_{sW} Q$. En particulier, pour $P$ le problème $\mathrm{Id} \times Q$, on a bien $\mathrm{Id} \times Q \leq_W Q$, donc $\mathrm{Id} \times Q \leq_{sW} Q$. Autrement dit, $Q$ est un cylindre pour $\leq_{sW}$.

# Chapitre 25

**Solution 1.4.** Voir le théorème 2.5.

**Solution 2.15.** Soit $h : \mathbb{N} \to \mathbb{N}$ un modulus de $\emptyset'$. On définit la fonction $h$-calculable $f : [\mathbb{N}]^2 \to 2$ en associant à $x < y$ la couleur 1 ssi $h(x) < y$. Tout ensemble infini $H$ homogène pour $f$ est homogène de couleur 1, et la fonction qui à $n$ associe le $n$-ième élément de $H$ domine $h$. La proposition 2.11 permet de conclure.

**Solution 3.5.** Pour une formule $\Delta_0^0 \Phi(x, y, n)$ et un paramètre du premier ordre $k$ l'énoncé est

$$ \exists x < k \forall y \exists n \Phi(x, y, n) \lor \exists z \forall x < k \exists y < z \forall n \Phi(x, y, n). $$

Il est clair que si $\exists y < z \forall n \Phi(x, y, n)$, alors $\forall a \exists y < z \forall n < a \Phi(x, y, n)$. Inversement, si $\forall y < z \exists n \neg \Phi(x, y, n)$, alors par $B\Sigma_1^0$ (prouvable dans $\mathrm{RCA}_0$)

$$ \exists a \forall y < z \exists n < a \neg \Phi(x, y, n). $$

Ainsi, on a

$$ \exists y < z \forall n \Phi(x, y, n) \iff \forall a \exists y < z \forall n < a \Phi(x, y, n). $$
**Solution 3.7.** Trivial.

**Solution 3.9.** Voir la preuve du lemme 14-4.6.

**Solution 3.20.** Soient $A$ et $C$ fixés. Par le corollaire 11-4.21, il existe un idéal de Scott $\mathcal{I}$ tel que pour tout $X \in \mathcal{I}$, $C$ n'est pas $\Sigma_1^0(X)$. Supposons (H1), car sinon nous avons déjà la solution désirée. Nous allons construire deux ensembles infinis $G^0 \subseteq A^0$, et $G^1 \subseteq A^1$ satisfaisant pour tout $e_0, e_1 \in \mathbb{N}$ le contrat

$$ \mathcal{R}_{e_0, e_1} : W_{e_0}^{G^0} \neq C \lor W_{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}$. Montrons le lemme suivant.

« 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 DU LEMME. Soit $W = \{x \in \mathbb{N} : c?\vdash x \in W_{e_0}^{G^0} \lor x \in W_{e_1}^{G^1}\}$. Par le lemme 3.15, $W$ est $\Sigma_1^0(X)$ avec $X \in \mathcal{I}$, et $C$ n'est pas $\Sigma_1^0(X)$, donc $W \neq C$. Deux cas se présentent.

▷ Cas 1. Il existe $x \in W \setminus C$. Par la proposition 3.17, il existe une extension $(\tau_0, \tau_1, Y)$ de $c$ et $i < 2$ tel que $(\tau_i, Y) \Vdash x \in W_{e_i}^G$.

▷ Cas 2. Il existe $x \in C \setminus W$. Par la proposition 3.17, il existe une extension $(\tau_0, \tau_1, Y)$ de $c$ et $i < 2$ tel que $(\tau_i, Y) \Vdash x \notin W_{e_i}^G$.

Soit $F$ un filtre suffisamment générique pour le forcing de Dzhafarov-Jockusch, et soit $(G^0, G^1) = \hat{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 ci-dessus, $(G^0, G^1)$ satisfont $\mathcal{R}_{e_0, e_1}$ pour tout $e_0, e_1 \in \mathbb{N}$. Donc, soit $C$ n'est pas $\Sigma_1^0(G^0)$, soit $C$ n'est pas $\Sigma_1^0(G^1)$. Ainsi, soit $G^0$, soit $G^1$ satisfait le théorème, ce qui conclut la preuve.

**Solution 3.21.** Soient $A$ et $f$ fixés. Par l'exercice 22-7.4, il existe un idéal de Scott $\mathcal{I}$ qui ne contient que des ensembles calculatoirement dominés. En particulier, pour tout $X \in \mathcal{I}$, la fonction $f$ est $X$-hyperimmune. Supposons (H1), car 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} \not\supsetneq f \lor \Phi_{e_1}^{G^1} \not\supsetneq f. $$

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

« 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 DU LEMME. Soit $g : \mathbb{N} \to \mathbb{N}$ la fonction qui sur tout $n$ cherche un ensemble fini $F \subseteq \mathbb{N}$ tel que $c?\vdash \Phi_{e_0}^{G^0}(n) \downarrow \in F \lor \Phi_{e_1}^{G^1}(n) \downarrow \in F$. Si un tel ensemble est trouvé, $g(n) = \max F$, sinon $g(n)$ n'est pas définie. Par le lemme 3.15, la fonction $g$ est partielle $X$-calculable avec $X \in \mathcal{I}$. Deux cas se présentent.
▷ Cas 1. $g$ est totale. Alors, comme $f$ est $X$-hyperimmune, il existe $n \in \mathbb{N}$ tel que $g(n) < f(n)$. Par définition de $g$, il existe un ensemble $F$ satisfaisant $\max F < f(n)$ et tel que $c?\vdash \Phi_{e_0}^{G_0}(n) \downarrow \in F \lor \Phi_{e_1}^{G_1}(n) \downarrow \in F$. Par la proposition 3.17, il existe une extension $(\tau_0, \tau_1, Y)$ de $c$ et $i < 2$ tel que $(\tau_i, Y) \models \Phi_{e_i}^{G_i}(n) \downarrow \in F$.

▷ Cas 2. Il existe $n \in \mathbb{N}$ tel que $g(n)$ n'est pas définie. Par définition de $g$, pour tout ensemble fini $F$, $c?\nvDash \Phi_{e_0}^{G_0}(n) \downarrow \in F \lor \Phi_{e_1}^{G_1}(n) \downarrow \in F$. Par comparité, $c?\nvDash \Phi_{e_0}^{G_0}(n) \downarrow \lor \Phi_{e_1}^{G_1}(n) \downarrow$. Par la proposition 3.17, il existe une extension $(\tau_0, \tau_1, Y)$ de $c$ et $i < 2$ tel que $(\tau_i, Y) \models \Phi_{e_i}^{G_i}(n) \uparrow$.

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 ci-dessus, $(G^0, G^1)$ satisfont $R_{e_0,e_1}$ pour tous $e_0, e_1 \in \mathbb{N}$. Donc, soit $f$ est $G^0$-hyperimmune, soit $f$ est $G^1$-hyperimmune. Ainsi, soit $G^0$, soit $G^1$ satisfait le théorème, ce qui conclut la preuve.

**Solution 3.22.** Il s'agit exactement de la construction de l'exercice 3.21, en forçant les contrats suivants pour tous $e_0, e_1 \in \mathbb{N}$ :

$$ \mathcal{R}_{e_0, e_1} : \Phi_{e_0}^{G_0} \not\geq f_0 \lor \Phi_{e_1}^{G_1} \not\geq f_0; $$

$$ \mathcal{S}_{e_0, e_1} : \Phi_{e_0}^{G_0} \not\geq f_1 \lor \Phi_{e_1}^{G_1} \not\geq f_1; $$

$$ \mathcal{T}_{e_0, e_1} : \Phi_{e_0}^{G_0} \not\geq f_2 \lor \Phi_{e_1}^{G_1} \not\geq f_2. $$

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 de l'exercice 3.21, $(G^0, G^1)$ satisfont $R_{e_0,e_1}$, $S_{e_0,e_1}$ et $T_{e_0,e_1}$ pour tous $e_0, e_1 \in \mathbb{N}$. Donc, pour tout $i < 3$, soit $f_i$ est $G^0$-hyperimmune, soit $f_i$ est $G^1$-hyperimmune. Par le principe des tiroirs, au moins deux fonctions $f_0, f_1$ et $f_2$ sont simultanément $G^0$-hyperimmunes ou $G^1$-hyperimmunes. Ainsi, soit $G^0$, soit $G^1$ satisfait le théorème, ce qui conclut la preuve.

**Solution 3.35.** La classe

$$ C = \{ X : \forall e \forall s (W_{e,s} \subseteq X \lor W_{e,s} \subseteq \bar{X}) \rightarrow |W_{e,s}| \leq 2e + 2 \} $$

est une classe $\Pi_1^0$ non vide, qui ne contient que des ensembles effectivement bi-immunes. En particulier, $C$ contient un membre low, donc $\Delta_2^0$.

**Solution 3.36.** Il s'agit d'une généralisation immédiate de la proposition 3.34. Nous définissons une suite $\emptyset'\text{-calculable } \sigma_0 < \sigma_1 < \dots$ de chaînes dans $k^{<\mathbb{N}}$ en alternant la concaténation de longues suites de $i$ pour chaque $i < k$ de telle sorte que la fonction principale de $\mathbb{N} \setminus A_i$ diagonalise contre toutes les fonctions calculables.
Supposons $\sigma_{ke+j}$ définie pour $j < k$, $\sigma_{ke+j+1} = \sigma_{ke+j}j^{\ell+1}0$ si $\Phi_e(|\sigma_{ke+j}|+1) \downarrow = \ell$, et $\sigma_{ke+k} = \sigma_{2e}0$ sinon. Aussi vérifie-t-on sans peine que si $\Phi_e$ est totale, alors pour $m = |\sigma_{ke+j}| + 1$ on a $p_A(m) \ge |\sigma_{ke+k+1}| - 1 > \Phi_e(m)$.

**Solution 3.37.** Soit $A_0 \sqcup A_1 \sqcup A_2 = \mathbb{N}$ une 3-partition $\Delta_2^0$ telle que pour tout $i < 3$, $\mathbb{N} \setminus A_i$ est hyperimmune. Son existence est assurée par l'exercice 3.36. On peut voir cette 3-partition comme une instance $g$ de $\text{RT}_3^1$ définie par $g(x) = i$ tel que $x \in A_i$.

Rappelons que la fonction principale d'un ensemble infini $H \subseteq \mathbb{N}$ 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 ssi $p_H$ n'est bornée par aucune fonction calculable. Pour tout $i < 3$, soit $f_i$ la fonction principale de $\mathbb{N} \setminus A_i$. Notons que $f_i$ est hyperimmune pour tout $i < 3$, et que pour tout ensemble $G$ infini $g$-homogène de couleur $i$, $G$ est un sous-ensemble de $A_i$, donc $G$ est un sous-ensemble de $\mathbb{N} \setminus A_j$ pour tout $j \neq i$. Il s'ensuit que sa fonction principale $p_G$ domine $f_j$ pour tout $j \neq i$, donc que aucun des $f_j$ n'est $G$-hyperimmune pour $j \neq i$.

Soit $h: \mathbb{N} \to 2$ une instance de $\text{RT}_2^1$. Par l'exercice 3.22, il existe un ensemble infini $h$-homogène $H$ tel que au moins deux parmi les trois fonctions $f_0, f_1$ et $f_2$ sont $H$-hyperimmunes. Il s'ensuit par l'observation précédente que $H$ ne calcule pas d'ensemble infini $g$-homogène.

**Solution 4.2.** Montrons tout d'abord que tout ensemble suffisamment générique pour $\mathbb{P}$ est infini. Soit $W_x \subseteq \mathbb{P}$ l'ensemble des conditions de Mathias $(\sigma, X)$ telles que $\sigma(y) = 1$ pour un $y > x$. Montrons que $W_x$ est dense dans $\mathbb{P}$. Soit $(\sigma, X) \in \mathbb{P}$. En particulier, $X$ est infini, donc il existe $y > x$ tel que $y \in X$. La condition $(\sigma \cup \{y\}, X \setminus \{0, \dots, y\})$ est une extension de $(\sigma, X)$ dans $W_x$. Ainsi, pour tout filtre $F$ suffisamment générique, $F \cap W_x \neq \emptyset$, et donc $\dot{F}$ sera infini.

Soit $Z$ un ensemble calculable, et soit $W_Z \subseteq \mathbb{P}$ l'ensemble des conditions de Mathias $(\sigma, X)$ telles que $X \subseteq Z$ ou $X \subseteq \bar{Z}$. Montrons que $W_Z$ est dense dans $\mathbb{P}$. Soit $(\sigma, X) \in \mathbb{P}$. Alors, $X \cap Z$ et $X \cap \bar{Z}$ sont tous les deux calculables, et au moins l'un des deux est infini. Alors, soit $(\sigma, X \cap Z)$, soit $(\sigma, X \cap \bar{Z})$ est une condition de Mathias valide étendant $(\sigma, X)$, et dans tous les cas, cette extension sera dans $W_Z$. Pour tout filtre $F$ suffisamment générique, $F \cap W_Z \neq \emptyset$, et donc $\dot{F} \subseteq^* Z$ ou $\dot{F} \subseteq^* \bar{Z}$. Ainsi, $\dot{F}$ est un ensemble cohésif pour tous les ensembles calculables.

**Solution 4.11.** Soit $C$ un ensemble non $\Sigma_1^0$. Soit $\mathbb{P}$ l'ensemble des conditions de Mathias $(\sigma, X)$ telles que $X$ est un ensemble calculable. Montrons que pour toute condition $(\sigma, X)$ et tout $e \in \mathbb{N}$, il existe une extension $(\tau, Y)$ forçant $W_e^G \neq C$. Soit $(\sigma, X)$ une condition, et soit $U = \{x \in \mathbb{N} : (\exists \rho \subseteq X)x \in W_e^{\sigma \cup \rho}\}$. L'ensemble $U$ est $\Sigma_1^0$ contrairement à $C$. S'il existe $x \in C \setminus U$, alors par définition de $U$, $(\sigma, X)$ force déjà $x \notin W_e^G$, donc force $W_e^G \neq C$. Sinon, il existe $x \in U \setminus C$. Soit $\rho \subseteq X$ tel que $x \in W_e^{\sigma \cup \rho}$. Alors, la condition $(\sigma \cup \rho, X \setminus \{0, \dots, |\rho|\})$ est
une extension de $(\sigma, X)$ forçant $x \in W_e^G$, donc forçant $W_e^G \neq C$. Ainsi, pour tout ensemble $G$ suffisamment générique pour $\mathbb{P}$, $C$ ne sera pas $\Sigma_1^0(G)$. De plus, pour toute condition $(\sigma, X)$ et tout $n$, soit $(\sigma, X \cap R_n)$, soit $(\sigma, X \cap \bar{R}_n)$ est une extension valide, donc si $G$ est un ensemble suffisamment générique pour $\mathbb{P}$, alors $G$ sera cohésif pour $(R_n)_{n \in \mathbb{N}}$.

**Solution 4.18.** Soit $(R_n)_{n \in \mathbb{N}}$ la suite calculable donnée par $R_x=\{y:f(\{x,y\})=1\}$. Par l'exercice 4.11, il existe un ensemble $D$ cohésif pour la suite $(R_n)_{n \in \mathbb{N}}$ tel que $C$ n'est pas $\Sigma_1^0(D)$. En particulier, pour tout $x \in D$, $\lim_{y \in D} f(\{x,y\})$ existe. Soit $g: D \to 2$ le coloriage défini par $g(x) = \lim_{y \in D} f(\{x,y\})$. Par la proposition 2.2 et l'exercice 3.20, il existe un ensemble infini $H \subseteq D$ homogène pour $g$ tel que $C$ n'est pas $\Sigma_1^0(H \oplus D)$. Par le fait 4.1, $H \oplus D$ calcule un ensemble infini $Y$ homogène pour $f$. En particulier, $C$ n'est pas $\Sigma_1^0(Y)$.

# Chapitre 27

## Solution 3.7.

(1) Après avoir écrasé $\omega$ Blarks, il reste $\omega$ Blarks. À l'étape $\omega \times \omega = \omega+\omega+\omega+...$, tous les Blarks apparus durant l'écrasement du n-ième bloc de $\omega$ Blarks seront anéantis durant l'écrasement du $(n+1)$-ième bloc de $\omega$ Blarks. Il n'y a donc plus de Blarks à l'étape $\omega \times \omega$.

(2) Soit $f(\alpha)$ le nombre de Blarks restant après avoir écrasé $\alpha$ Blarks. On a clairement $f(\omega) = \omega^2$, et de manière générale $f(\omega^n) = \omega^{(n+1)}$. En particulier,
$$f(\omega^\omega) = f(\sup_n \omega^n) = \sup_n f(\omega^n) = \sup_n \omega^{(n+1)} = \omega^\omega.$$

Il y a donc $\omega^\omega$ Blarks après les $\omega^\omega$ premières étapes. On répète alors l'argument de (1) pour voir qu'il n'y a plus de Blarks à l'étape $\omega^\omega \times \omega$.

(3) Étant donné les Blarks présents à l'étape $\alpha$, soit $A_\alpha$ le sous-ensemble de Blarks qui finiront par être foudroyés à une certaine étape $(A_\alpha)$ est défini via l'axiome de compréhension). Soit à présent $f(\alpha)$ la plus petite étape à laquelle tous les Blarks de $A_\alpha$ sont foudroyés (l'axiome de remplacement implique que le supremum des étapes auxquels les Blarks de $A_\alpha$ sont foudroyés est bien un ordinal). On définit $\alpha_0 = \omega$ puis, pour tout $n$, on définit $\alpha_{n+1} = f(\alpha_n)$. Si $\alpha_n = \alpha_{n+1}$ pour un certain $n$, cela signifie que plus aucun Blork ne sera foudroyé à partir de l'étape $\alpha_n$ et donc forcément qu'il n'y a plus de Blork à cette étape. Dans ce cas, tous les Blarks seront anéantis.

Sinon, $\alpha_n < \alpha_{n+1}$ pour tout $n$. Soit $\beta = \sup_n \alpha_n$. On a alors

$$f(\beta) = f(\sup_n \alpha_n) = \sup_n f(\alpha_n) = \sup_n \alpha_{n+1} = \beta.$$

Comme $f(\beta) = \beta$ cela signifie que plus aucun Blork ne sera foudroyé à partir de l'étape $\beta$ et donc forcément qu'il n'y a plus de Blork à cette étape. Dans tous les cas, tous les Blarks finiront par disparaître.
**Solution 5.3.** Il s'agit de montrer par induction que si $|a| = \alpha$ pour $a \in O$, alors
$$ \{|b| : b <_o a\} = \{\beta : \beta < \alpha\}. $$

**Solution 5.5.** La preuve se fait par induction sur $b$ via l'ordre bien fondé $<_o$. Si $b=1$, alors par définition $|a+_o b| = |a| = |a| + |b|$. Si $b=2^e$, alors $|a+_o b| = |2^{a+_o c}| = \text{succ}(|a+_o c|) = \text{succ}(|a| + |c|) = |a| + |b|$. Si $b=3 \times 5^e$, alors $|a+_o b| = \text{sup}_n |a+_o \Phi_e(n)| = \text{sup}_n (|a| + |\Phi_e(n)|) = |a| + |b|$.

**Solution 5.12.** La fonction $f$ sur l'entrée $n$ renvoie le code d'une énumération
$$ 0 < 1 < 2 < \dots $$

Si à un moment on s'aperçoit que $n \in \emptyset'$, la fonction choisi un nombre $k$ pour le-
quel rien n'a encore été décidé et énumère dorénavant des axiomes tels que $m < k$
pour tout autre entier $m$, tout en gardant l'ordre usuel sur les entiers différents
de $k$.

**Solution 5.17.** On a $\emptyset = |T| = |T|_{KB}$ pour l'arbre vide $T$. Soit $\alpha$ un ordinal et supposons $|T| \le |T|_{KB}$ pour tout arbre $T$ tel que $|T| < \alpha$. Soit $T$ un arbre tel que $|T| = \alpha$. Alors, pour chaque nœud $\sigma$ de $T$ de taille 1, on a $|T|_{\sigma} < \alpha$. Par hypothèse d'induction, on a donc $|T|_{\sigma} \le |T|_{KB}$ pour chaque $\sigma \in T$ de taille 1. Dans le contexte de $T$, on a $|T|_{\sigma} = |\sigma|$ et $|T|_{\sigma}|_{KB} \le |\sigma|_{KB}$ (car l'ordre $<_{KB}$ sur $T|_{\sigma}$ se plonge dans l'ordre $<_{KB}$ sur $T$). Par définition, on a donc

$$ |T| = \sup\{|\sigma|+1 : \sigma \in T \text{ de taille } 1\} \le \sup\{|\sigma|_{KB}+1 : \sigma \in T \text{ de taille } 1\} = |T|_{KB}. $$

# Chapitre 28

**Solution 1.11.** Montrons que chaque ensemble $T_{<\omega(\alpha+k)}$ est $\Sigma_{\alpha+2k}^0$ et chaque ensemble $T_{\le \omega(\alpha+k)+p}$ est $\Pi_{\alpha+2k+1}^0$. Pour tout $p \in \mathbb{N}$, l'ensemble $T_{\le p}$ est $\Pi_1^0$ uniformément en $p$: c'est l'ensemble des codes qui énumèrent des arbres de hauteurs inférieures ou égales à $p$.

Supposons que pour $\alpha = 0$ ou limite, pour $k \in \mathbb{N}$ et pour tout $p \in \mathbb{N}$ l'ensemble $T_{\le \omega(\alpha+k)+p}$ soit $\Pi_{\alpha+2k+1}^0$ uniformément en $p, k$ et un code de $\alpha$. Alors,

$$ T_{<\omega(\alpha+k+1)} = \bigcup_p T_{\le \omega(\alpha+k)+p} $$

est $\Sigma_{\alpha+2(k+1)}^0$ uniformément en $k+1$ et en un code de $\alpha$. De même, si $T_{\le \omega(\alpha+k)}$ est $\Pi_{\alpha+2k+1}^0$ uniformément en $k$ et un code de $\alpha$, pour $\alpha = 0$ ou limite et pour tout $k \in \mathbb{N}$, alors $T_{<\omega(\alpha+\omega)} = \bigcup_k T_{\le \omega(\alpha+k)}$ est $\Sigma_{\alpha+\omega}^0$.

Supposons à présent que pour $\alpha = 0$ ou limite, pour $k \in \mathbb{N}$ l'ensemble $T_{<\omega(\alpha+k)}$ est $\Sigma_{\alpha+2k}^0$ uniformément en $k$ et en un code de $\alpha$. Alors, pour $p \in \mathbb{N}$, l'ensemble $T_{\le \omega(\alpha+k)+p}$ est $\Pi_{\alpha+2k+1}^0$, car il s'agit de l'ensemble des codes d'arbres c. e. tels que pour tout nœud $\sigma$ de taille $p+1$ énuméré, le code de l'arbre $T|_{\sigma}$ appartient à $T_{<\omega(\alpha+k)}$, ce qui par hypothèse d'induction est une condition $\Pi_{\alpha+2k+1}^0$ uniformément en $p, k$ et en un code de $\alpha$.
On montre finalement l'existence d'une fonction $f : \mathbb{N}^2 \to \mathbb{N}$ telle que :

▷ pour tout $\Sigma_{\alpha+2k}^0$-code $e$ d'un ensemble $S_e$, la fonction $n \mapsto f(e, n)$ est totale et vérifie $n \in S_e$ implique $f(e, n) \in \mathcal{T}_{<\omega(\alpha+k)}$, et $n \notin S_e$ implique $f(e, n)$ mal fondé;

▷ pour tout $\Pi_{\alpha+2k+1}^0$-code $e$ d'un ensemble $S_e$, la fonction $n \mapsto f(e, n)$ est totale et vérifie $n \in S_e$ implique $f(e, n) \in \mathcal{T}_{\le \omega(\alpha+k)}$ et $n \notin S_e$ implique $f(e, n)$ mal fondé.

Si $e$ est le $\Pi_1^0$-code d'un ensemble $S_e$, alors $f(e, n)$ renvoie le code d'un arbre c. e. vide tant que $n \in S_e$, et mal fondé sinon ($n \notin S_e$ est un événement $\Sigma_1^0$). Si $e$ est le $\Sigma_\alpha^0$-code d'un ensemble $\bigcup_m F_{a_m}$, où chaque $F_{a_m}$ est de code $a_n$, alors $f(e, n)$ renvoie le résultat de la fonction OR de l'exercice 29-5.11 sur $\{f(a_m, n) : m \in \mathbb{N}\}$.

Si $e$ est le $\Pi_\alpha^0$-code d'un ensemble $\bigcap_m F_{a_m}$, où chaque $F_{a_m}$ est de code $a_n$, alors $f(e, n)$ renvoie le résultat de la fonction AND du lemme 29-5.10 sur l'ensemble

$$ \{f(a_m, n) : m \in \mathbb{N}\}. $$

On laisse au lecteur le soin de vérifier que $f$ a bien la propriété demandée.

**Solution 4.6.** Il faut reprendre les relations du lemme 1.3 pour montrer que les réunions et intersections finies de classes $\Sigma_\alpha^0$ sont uniformément $\Sigma_\alpha^0$. On peut ensuite utiliser cela pour obtenir à partir d'un $\Sigma_\alpha^0$-code de la classe $\bigcup_n \mathcal{B}_n$, un $\Sigma_\alpha^0$-code de la classe $\bigcup_n (\bigcup_{m \le n} \mathcal{B}_m)$.

**Solution 4.7.** D'après l'exercice précédent, on peut supposer sans perte de généralité que nos classes sont croissantes. Il faut montrer par induction que l'on a une fonction calculable $f$ telle que pour tout $\Sigma_\alpha^0$-code $e$ d'une classe $\mathcal{A}$, alors $f(e)$ est le $\Sigma_\alpha^0$-code de l'ensemble $\{q \in \mathbb{Q} : \lambda(\mathcal{A}) > q\}$. Pour le montrer, nous aurons en fait besoin de créer des codes de fonctions $f_{i,\varepsilon}$ pour $i \in \{-1, 1\}$ et $\varepsilon \in \mathbb{Q}$ tels que pour tout $\Sigma_\alpha^0$-code $e$ d'une classe $\mathcal{A}$, alors $f_{i,\varepsilon}(e)$ est le $\Sigma_\alpha^0$-code de l'ensemble

$$ \{q \in \mathbb{Q} : \lambda(\mathcal{A}) > i \times q + \varepsilon\}. $$

L'idée est la suivante. Si $\mathcal{A} = \bigcup_m \mathcal{B}_m$, où chaque $\mathcal{B}_m$ est $\Pi_\beta^0$ pour $\beta < \alpha$, alors

$$ \begin{aligned} \{q \in \mathbb{Q} : \lambda(\mathcal{A}) > q\} &= \bigcup_m \{q \in \mathbb{Q} : \lambda(\mathcal{B}_m) > q\} = \bigcup_{m,n} \{q \in \mathbb{Q} : \lambda(\mathcal{B}_m) > q + 2^{-n}\} \\ &= \bigcup_{m,n} \{q \in \mathbb{Q} : \lambda(2^{\mathbb{N}} \setminus \mathcal{B}_m) \le 1 - (q + 2^{-n})\}. \end{aligned} $$

Notons que chaque ensemble $\{q \in \mathbb{Q} : \lambda(2^{\mathbb{N}} \setminus \mathcal{B}_m) \le 1 - (q + 2^{-n})\}$ est le complémentaire de l'ensemble

$$ \{q \in \mathbb{Q} : \lambda(2^{\mathbb{N}} \setminus \mathcal{B}_m) > 1 - (q + 2^{-n})\} = \{q \in \mathbb{Q} : \lambda(2^{\mathbb{N}} \setminus \mathcal{B}_m) > -q + (1 - 2^{-n})\}, $$

qui a par induction un $\Sigma_\beta^0$-code via $f_{-1,1-2-\beta}$.

Les détails sont laissés au lecteur.
# Chapitre 29

**Solution 2.9.** Comme $X$ est $\Sigma_1^1(Y)$ et $Y$ est $\Delta_1^1(Z)$, on a

$$ 
\begin{align*}
X &= \{n \in \mathbb{N} : \exists f \mathcal{A}(Y, f, n)\} \\
Y &= \{n \in \mathbb{N} : \exists f_1 \mathcal{A}_1(Z, f_1, n)\} \\
\mathbb{N} \setminus Y &= \{n \in \mathbb{N} : \exists f_2 \mathcal{A}_2(Z, f_2, n)\},
\end{align*}
$$

où $\mathcal{A}_1$ et $\mathcal{A}_2$ sont arithmétiques. Alors,

$$ X = \{ n \in \mathbb{N} : \exists Y \ \forall m \left[ \begin{array}{l} (m \in Y \land \exists f_1 \mathcal{A}_1(Z, f_1, m)) \lor \\ (m \notin Y \land \exists f_2 \mathcal{A}_2(Z, f_2, m)) \end{array} \right] \land \exists f \mathcal{A}(Y, f, n) \}. $$

**Solution 3.9.** Pour chaque $e$, d'après le théorème 28-4.5, la classe

$$ \mathcal{B}_{e,\alpha} = \{X : e \in \mathcal{O}_{=\alpha}^X\} $$

est borélienne. Pour $e$ fixé, si $\alpha_1 \neq \alpha_2$ alors les classes $\mathcal{B}_{e,\alpha_1}$ et $\mathcal{B}_{e,\alpha_2}$ sont disjointes. Donc, par additivité dénombrable de la mesure, pour chaque rationnel $q > 0$ et chaque $e$ il n'y a qu'un nombre fini d'ordinaux $\alpha$ tels que $\lambda(\mathcal{B}_{e,\alpha}) > q$. Soit $\alpha_{e,q}$ le supremum de ces ordinaux. Soit $\beta = \sup_{e,q} \alpha_{e,q}$ et $\mathcal{B} = \bigcup_e \mathcal{B}_{e,\beta}$. On a nécessairement $\beta < \omega_1$ et $\lambda(\mathcal{B}) = 0$. Notons que $\mathcal{B}$ est une classe borélienne.

Soit $\mathcal{A}$ une classe $\Pi_1^1$. Alors, $\mathcal{A} = \mathcal{A} = \mathcal{A} = \bigcup_{\alpha<\omega_1} \{Y : e \in \mathcal{O}_{<\alpha}^Y\}$ pour un certain $e$. La classe $\bigcup_{\alpha \le \beta} \{Y : e \in \mathcal{O}_{<\alpha}^Y\}$ est borélienne, et la classe $\bigcup_{\beta < \alpha < \omega_1} \{Y : e \in \mathcal{O}_{<\alpha}^Y\}$ est incluse dans $\mathcal{B}$ puisque si $e \in \mathcal{O}_{<\alpha}^Y$ pour $\alpha > \beta$, alors il existe $e' \tel$ tel que $e' \in \mathcal{O}_{=\beta}^Y$.

**Solution 5.11.** On définit une suite d'arbres $(U_i)_{i \in \mathbb{N}}$. $U_0 = T_0$. Si $U_i$ est défini, alors $U_{i+1}$ est obtenu en y mettant tous les nœuds de $U_i$ taille inférieure ou égale à $i+1$, et pour chacun de ces nœuds $\sigma$, on y ajoute les nœuds $\sigma\tau$ pour tout $\tau \in T_{i+1} \lor U_i|_{\sigma}$. On renvoie finalement un code pour l'arbre $T = \lim_i U_i$.

**Solution 6.2.** Soit $U$ un arbre $\Sigma_1^1$ bien fondé. Soit $U_\sigma$ l'arbre bien fondé ssi $\sigma \notin U$. On calcule uniformément en $X$ l'arbre bien fondé $T^X = \bigcup_{\sigma<\chi} U_\sigma$. On calcule finalement l'arbre c. e. $T$ suivant : pour chaque chaîne $\sigma \in 2^{<\mathbb{N}}$ telle qu'un nœud $m$ de taille 1 est énuméré dans $T^\sigma$, on énumère le nœud $\langle m, b(\sigma) \rangle$ de taille 1 dans $T$, en utilisant une bijection $b : 2^{<\mathbb{N}} \to \mathbb{N}$. Pour tout nœud $\langle \tau, b(\sigma_1) \dots b(\sigma_n) \rangle$ énuméré dans $T$ avec $|\tau| = n$, si une chaîne $\tau m$ est énumérée dans $T^{\sigma_{n+1}}$ pour une chaîne $\sigma_{n+1} \succeq \sigma_n$, on énumère alors $\langle \tau m, b(\sigma_1) \dots b(\sigma_n) b(\sigma_{n+1}) \rangle$ dans $T$.

**Solution 6.5.** Il suffit de montrer que le lemme 6.3 peut être obtenu uniformément. Soit $\mathcal{A}$ une classe $\Sigma_1^1$ telle que $\forall X \in \mathcal{A} \exists a \in \mathcal{O}^X \mathcal{B}(a, X)$, où $\mathcal{B}$ est un prédicat $\Pi_1^1$. Soit $e$ le code de l'arbre $X$-c. e. $T_e^X$ qui est bien fondé ssi $X \notin \mathcal{A}$. Soit $w_1$ le code de l'arbre $X$-c. e. $T_{w_1}^X$ qui est bien fondé ssi $a \in \mathcal{O}^X$. On peut supposer de plus $|T_{w_1}^X| \ge |a|$ pour $a \in \mathcal{O}^X$. Soit $w_2$ le code de l'arbre $X$-c. e. $T_{w_2}^X$, qui est bien
fondé ssi $\mathcal{B}(a, X)$. Soit $T^X$ l'arbre c. e. défini par

$$T_e^X \lor \bigvee_{a \in \omega} T_{w_1}^X \wedge T_{w_2}^X.$$

Notons que $T^X$ est bien fondé pour tout $X$. On définit finalement en utilisant une bijection $b: 2^{\mathbb{N}} \to \mathbb{N}$ :

$$T = \{\langle \sigma, b(\tau_1) \dots b(\tau_k) \rangle : |\sigma| = k, \tau_1 \le \dots \le \tau_k \text{ et } \sigma \in T^{\tau_k}\}.$$

On laisse au lecteur le soin de vérifier que l'ordinal $|T|$ vérifie bien la propriété demandée.

**Solution 7.7.** Il suffit de montrer $\omega_1^X > \omega_1^{ck}$. On utilise le théorème 4.3 pour voir $X$ comme un ensemble que l'on énumère le long des ordinaux calculables. On définit la fonction $f: \mathbb{N} \to \omega_1^{ck}$ qui à $n$ associe le plus petit ordinal $\alpha < \omega_1^{ck}$ tel que $X[\alpha] \upharpoonright_n = X \upharpoonright_n$. Ici, $X[\alpha]$ est « l'énumération » de $X$ jusqu'à l'étape $\alpha$. On a nécessairement $\sup_n f(n) = \omega_1^{ck}$, car sinon l'énumération de $X$ serait achevée à une étape $\alpha < \omega_1^{ck}$, et $X$ serait alors $\Delta_1^1$. Comme $f$ est totale, son image est $\Delta_1^1(X)$. D'après le lemme 5.3 de majoration de Spector relativisé à $X$, on a donc $\omega_1^{ck} < \omega_1^X$.

## Chapitre 30

**Solution 4.4.** Soit $\mathcal{A} = \{X : \forall n \exists \alpha < \omega_1^{ck} \Phi_e(X, n) \in \mathcal{O}_{<\alpha}^X\}$ pour $e \in \mathbb{N}$. Supposons $\lambda(\mathcal{A}) \ge r$ pour $r \in \mathbb{Q}$. Soit la fonction $f$ qui a $n$ associe le plus petit $\alpha < \omega_1^{ck}$ tel que $\lambda(\bigcap_{m \le n} \{X : \Phi_e(X, m) \in \mathcal{O}_{<\alpha}^X\}) \ge r - 2^{-n}$. En utilisant l'exercice 28-4.7, la fonction $f$ est $\Pi_1^1$. Par l'hypothèse $\lambda(\mathcal{A}) \ge r$, la fonction $f$ est totale, et donc de graphe $\Delta_1^1$. Donc, son image est $\Delta_1^1$ et, par le lemme 29-5.3 de majoration de Spector, $\sup_n f(n) = \alpha < \omega_1^{ck}$. On a alors

$$\lambda(\bigcap_n \{X : \Phi_e(X, n) \in \mathcal{O}_{<\alpha}^X\}) \ge r.$$

Comme c'est le cas pour tout rationnel $r < \lambda(\mathcal{A})$, on en déduit que les éléments $X \in \mathcal{A}$ pour lesquels $(\Phi_e(X, n))_{n \in \mathbb{N}}$ est co-final dans $\omega_1^{ck}$, est de mesure nulle. Comme c'est le cas pour tout $e$ alors l'ensemble des éléments $X$ capables de calculer une suite $(a_n)_{n \in \mathbb{N}}$ d'éléments de $\mathcal{O}_{<\omega_1^{ck}}^X$ qui soit co-final dans $\omega_1^{ck}$ est de mesure nulle. Si $\omega_1^X > \omega_1^{ck}$ alors $X$ doit être capable de calculer une telle suite, donc $\lambda(\{X : \omega_1^X > \omega_1^{ck}\}) = 0$.

**Solution 4.5.** Soit $\mathcal{S} = \{X : \omega_1^X > \omega_1^{ck}\}$. D'après le corollaire 29-3.7, une classe $\Pi_1^1 \mathcal{A}$ est de la forme $\bigcup_{\alpha < \omega_1} \mathcal{A}_\alpha$. On peut de plus supposer que les classes $\mathcal{A}_\alpha$ sont deux à deux disjointes. On s'assure ainsi que pour tout $\alpha \ge \omega_1^{ck}$ et $X \in \mathcal{A}_\alpha$, on a $X \notin \bigcup_{\beta < \omega_1^{ck}} \mathcal{A}_\beta$, donc $\omega_1^X > \omega_1^{ck}$. Autrement dit, $\bigcup_{\omega_1^{ck} \le \alpha < \omega_1} \mathcal{A}_\alpha \subseteq \mathcal{S}$. La classe $\mathcal{A}$ est de mesure nulle ssi chaque $\mathcal{A}_\alpha$ pour $\alpha < \omega_1^{ck}$ est de mesure nulle. Notons que chaque classe $\mathcal{A}_\alpha$ pour $\alpha < \omega_1^{ck}$ est $\Delta_1^1$.
Soit $A \subseteq \mathbb{N}$ l'ensemble $\Pi_1^1$ des paires $(a, n) \in \mathbb{N}$ telles que $a \in O$ et telles que $\lambda(\{X : n \in H_{2^a}^X\}) = 0$. Notons que d'après le théorème 28-4.4 toute classe $\Delta_1^1$ de mesure nulle a un code dans $A$.

La plus grande classe $\Pi_1^1$ de mesure nulle est alors donnée par

$$ \mathcal{S} \cup \bigcup_{(a,n) \in A} \{X : n \in H_{2^a}^X\}. $$
Bibliographie

[1] *Cabal Seminar 76-77*, volume 689, 1976.

[2] Uri ABRAHAM et Richard A. SHORE : Initial Segments of the Degrees of Size ℵ₁. *Israel Journal of Mathematics*, 53(1), 1986.

[3] Wilhelm ACKERMANN : Zum Hilbertschen Aufbau Der Reellen Zahlen. *Math. Ann.*, 99(1):118-133, 1928.

[4] J. W. ADDISON : Separation Principles in the Hierarchies of Classical and Effective Descriptive Set Theory. *Fundamenta Mathematicae*, 46: 123-135, 1958. Publisher : Instytut Matematyczny Polskiej Akademii Nauk.

[5] Klaus AMBOS-SPIES, Carl G. JOCKUSCH, Richard A. SHORE et Robert I. SOARE : An Algebraic Decomposition of the Recursively Enumerable Degrees and the Coincidence of Several Degree Classes with the Promptly Simple Degrees. *Transactions of the American Mathematical Society*, 281(1):109-109, janvier 1984.

[6] Klaus AMBOS-SPIES, Bjørn KJOS-HANSSEN, Steffen LEMPP et Theodorøe A. SLAMAN : Comparing DNR and WWKL. *Journal of Symbolic Logic*, pages 1089-1104, 2004.

[7] Uri ANDREWS, Peter GERDES et Joseph S. MILLER : The Degrees of Bi-Hyperhyperimmune Sets. *Ann. Pure Appl. Logic*, 165(3):803-811, 2014.

[8] Marat Mirzaevich ARSLANOV : Some Generalizations of a Fixed-Point Theorem. *Izvestiya Vysshikh Uchebnykh Zavedenii. Matematika*, (5):9-16, 1981. Publisher : Kazan (Volga region) Federal University.

[9] Theodore BAKER, John GILL et Robert SOLOVAY : Relativizations of the P=NP Question. *SIAM Journal on computing*, 4(4):431-442, 1975.

[10] Jack BARONE et Albert NOVIKOFF : A History of the Axiomatic Formulation of Probability from Borel to Kolmogorov : Part I. *Achive for History of Exact Sciences*, 18(2):123-190, 1978. Publisher : Springer.

[11] James E. BAUMGARTNER : A Short Proof of Hindman's Theorem. *Journal of Combinatorial Theory, Series A*, 17(3):384-386, 1974.

[12] Jean-Pierre BELNA : *Cantor*, volume 20. Belles Lettres, 2000.
[13] Laurent BIENVENU, Adam R DAY, Noam GREENBERG, Antonín KUČERA, Joseph S. MILLER, André NIES et Dan TURETSKY : Computing K-Trivial Sets by Incomplete Random Sets. *The Bulletin of Symbolic Logic*, pages 80–90, 2014. Publisher : JSTOR.

[14] Laurent BIENVENU et Rod DOWNEY : Kolmogorov Complexity and Solovay Functions. *In 26th International Symposium on Theoretical Aspects of Computer Science*, 2009.

[15] Laurent BIENVENU, Noam GREENBERG, Antonín KUČERA, André NIES et Dan TURETSKY : K-Triviality, Oberwolfach Randomness, and Differentiability. 2012.

[16] Laurent BIENVENU, Noam GREENBERG, Antonín KUČERA, Joseph S. MILLER, André NIES et Dan TURETSKY : Joining Non-Low c.e. Sets with Diagonally Non-Computable Functions. *J. Logic Comput.*, 23(6):1183–1194, 2013.

[17] Laurent BIENVENU, Noam GREENBERG, Antonín KUČERA, André NIES et Dan TURETSKY : Coherent Randomness Tests and Computing the K-Trivial Sets. *J. Eur. Math. Soc. (JEMS)*, 18(4):773–812, 2016.

[18] Laurent BIENVENU, Rupert HÖLZL, Joseph S MILLER et André NIES : The Denjoy Alternative for Computable Functions. *In 29th International Symposium on Theoretical Aspects of Computer Science*, page 543, 2012.

[19] Laurent BIENVENU, Rupert HÖLZL, Joseph S. MILLER et André NIES : Denjoy, Demuth and Density. *Journal of Mathematical Logic*, 14(01):1450004, 2014. Publisher : World Scientific.

[20] Laurent BIENVENU, Wolfgang MERKLE et Andre NIES : Solovay Functions and K-Triviality. *In 28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011)*, 2011.

[21] Andreas R. BLASS, Jeffry L. HIRST et Stephen G. SIMPSON : Logical Analysis of some Theorems of Combinatorics and Topological Dynamics. *Logic and Combinatorics, S. Simpson, ed.*, Contemporary Math, 69:125–156, 1987.

[22] Émile BOREL : Les «paradoxes» de la théorie des ensembles. *In Annales Scientifiques De L'École Normale Supérieure*, volume 25, pages 443–448, 1908.

[23] M Émile BOREL : Les probabilités dénombrables et leurs applications arithmétiques. *Rendiconti del Circolo Matematico di Palermo (1884-1940)*, 27(1):247–271, 1909. Publisher : Springer.

[24] V. BRATTKA, G. GHERARDI et A. PAULY : Weihrauch Complexity in Computable Analysis. *ArXiv*, abs/1707.03202, 2017.
[25] Vasco BRATTKA et Tahina RAKOTONIAINA : On the Uniform Com-
putational Content of Ramsey's Theorem. *J. Symb. Log.*, 82(4):1278-
1316, 2017.

[26] Cristian S. CALUDE, Peter H. HERTLING, Bakhadyr KHOUSSAINOV et Yongge WANG : Recursively Enumerable Reals and Chaitin's Numbers. *In Annual Symposium on Theoretical Aspects of Computer Science*, pages 596-606. Springer, 1998.

[27] Georg CANTOR : Fondements d'une théorie générale des ensembles.
*Acta Mathematica*, 2(1):381-408, 1883. Publisher : Springer.

[28] Olivier CARTON : *Langages formels, calculabilité et complexité*, volume 28. Vuibert, 2008.

[29] Gregory J. CHAITIN : A Theory of Program Size Formally Identical to Information Theory. *Journal of the ACM (JACM)*, 22(3):329-340, 1975. Publisher : ACM New York, NY, USA.

[30] Gregory J. CHAITIN : Information-Theoretic Characterizations of Recursive Infinite Strings. *Theoretical Computer Science*, 2(1):45-48, 1976. Publisher : Elsevier.

[31] Gregory J. CHAITIN : Incompleteness Theorems for Random Reals. *Advances in Applied Mathematics*, 8(2):119-146, 1987. Publisher : Elsevier.

[32] David G. CHAMPERNOWNE : The Construction of Decimals Normal in the Scale of Ten. *Journal of the London Mathematical Society*, 1(4):254-260, 1933.

[33] Peter A. CHOLAK, Carl G. JOCKUSCH et Theodore A. SLAMAN : On the Strength of Ramsey's Theorem for Pairs. *The Journal of Symbolic Logic*, 66(1):1-55, 2001. Publisher : Cambridge University Press.

[34] Peter A. CHOLAK et Ludovic PATEY : Thin Set Theorems and Cone Avoidance. Transactions of the AMS. To appear., 2019.

[35] Chi Tat CHONG et Liang YU : *Recursion Theory : Computational Aspects of Definability*, volume 8. Walter de Gruyter GmbH & Co KG, 2015.

[36] Alonzo CHURCH et Stephen C. KLEENE : Formal Definitions in the Theory of Ordinal Numbers. *Fundamenta Mathematicae*, 28(1):11-21, 1937.

[37] Paul J. COHEN : The Independence of the Continuum Hypothesis, II. *Proceedings of the National Academy of Sciences of the United States of America*, 51(1):105, 1964. Publisher : National Academy of Sciences.

[38] Joshua A COLE et Stephen G SIMPSON : Mass Problems and Hyperarithmeticity. *Journal of Mathematical Logic*, 7(02):125-143, 2007.
[39] W Wistar COMFORT : Ultrafilters : Some Old and some New Results. *Bulletin of the American Mathematical Society*, 83(4):417–455, 1977.

[40] Barry S. COOPER : Degrees of Unsolvability Complementary between Recursively Enumerable Degrees. *Annals of Mathematical Logic*, 4(1): 31–73, 1972.

[41] Barry S. COOPER : *Computability Theory*. CRC Press, 2003.

[42] René CORI et Daniel LASCAR : *Logique mathématique, Volume II. Masson, 1993.*

[43] Adam R. DAY et Joseph S. MILLER : Density, Forcing, and the Covering Problem. *Mathematical Research Letters*, 22(3):719–727, 2015. Publisher : International Press of Boston.

[44] Patrick DEHORNOY : La théorie des ensembles. *Calvage et Mounet, Paris*, 2017.

[45] Osvald DEMUTH et Antonín KUČERA : Remarks on 1-Genericity, Semigenericity and Related Concepts. *Commentationes Mathematicae Universitatis Carolinae*, 28(1):85–94, 1987. Publisher : Charles University in Prague, Faculty of Mathematics and Physics.

[46] Rod DOWNEY, Noam GREENBERG, Matthew HARRISON-TRAINOR, Ludovic PATEY et Dan TURETSKY : Relationships between Computability-Theoretic Properties of Problems, 2019.

[47] Rod DOWNEY, Denis HIRSCHFELDT, Steffen LEMPP et Reed SOLOMON : A $\Delta_0^2$ Set with no Infinite Low Subset in either it or its Complement. *Journal of Symbolic Logic*, 66(3):1371–1381, 2001.

[48] Rod DOWNEY, André NIES, Rebecca WEBER et Liang YU : Lowness and $Π_2^0$ Nullsets. *Journal of Symbolic Logic*, 71(3):1044–1052, 2006.

[49] Rodney G. DOWNEY : Abstract Dependence, Recursion Theory, and the Lattice of Recursively Enumerable Filters. *Bulletin of the Australian Mathematical Society*, 27(3):461–464, 1983.

[50] Rodney G. DOWNEY et Denis R. HIRSCHFELDT : *Algorithmic Randomness and Complexity*. Springer Science & Business Media, 2010.

[51] Arnaud DURAND et Paul ROZIÈRE : Calculabilité et incomplétude - Notes de cours.

[52] Damir D. DZHAFAROV : Cohesive Avoidance and Strong Reductions. *Proceedings of the American Mathematical Society*, 143(2):869–876, 2014.

[53] Damir D. DZHAFAROV, Denis R. HIRSCHFELDT et Sarah C. REITZES : Reduction Games, Provability, and Compactness, 2020.

[54] Damir D. DZHAFAROV et Carl G. JOCKUSCH : Ramsey's Theorem and Cone Avoidance. *The Journal of Symbolic Logic*, 74(2):557–578, 2009. Publisher : Cambridge University Press.
[55] Calvin C. ELGOT et Abraham ROBINSON : Random-Access Stored-Program Machines, an Approach to Programming Languages. *In Selected Papers*, pages 17–51. Springer, 1982.

[56] Herbert ENDERTON et Hilary PUTNAM : A Note on the Hyperarithmetical Hierarchy. *The Journal of Symbolic Logic*, 35(3):429–430, 1970. Publisher : Cambridge University Press.

[57] Andrei Petrovich ERSHOV : On Operator Algorithms. *In Doklady Akademii Nauk*, volume 122, pages 967–970. Russian Academy of Sciences, 1958.

[58] Solomon FEFERMAN et Clifford SPECTOR : Incompleteness along Paths in Progressions of Theories 1. *The Journal of Symbolic Logic*, 27(4):383–390, 1962. Publisher : Cambridge University Press.

[59] Michael R. FELLOWS : *Computer Science and Mathematics in the Elementary Schools*. Citeseer, 1991.

[60] Lance FORTNOW et Michael SIPSER : Are there Interactive Protocols for Co-Np Languages ? *Information Processing Letters*, 28(5):249–251, 1988.

[61] Johanna FRANKLIN et Keng Meng NG : Difference Randomness. *Proceedings of the American Mathematical Society*, 139(1):345–360, 2011.

[62] Richard FRIEDBERG : A Criterion for Completeness of Degrees of Unsolvability. *The Journal of Symbolic Logic*, 22(2):159–160, 1957.

[63] Richard M. FRIEDBERG : Two Recursively Enumerable Sets of Incomparable Degrees of Unsolvability (Solution of Post's Problem, 1944). *Proceedings of the National Academy of Sciences of the United States of America*, 43(2):236–238, 1957. Publisher : National Academy of Sciences.

[64] Richard M. FRIEDBERG : Three Theorems on Recursive Enumeration. I. Decomposition. II. Maximal Set. III. Enumeration without Duplication. *J. Symbolic Logic*, 23:309–316, 1958.

[65] Harvey FRIEDMAN : Some Systems of Second Order Arithmetic and their Use. *In Proceedings of the International Congress of Mathematicians (Vancouver, BC, 1974)*, volume 1, pages 235–242. Citeseer, 1975.

[66] Harvey FRIEDMAN : Uniformly Defined Descending Sequences of Degrees. *The Journal of Symbolic Logic*, 41(2):363–367, 1976. Publisher : JSTOR.

[67] Harvey M. FRIEDMAN : Higher Set Theory and Mathematical Practice. *Mathematical Logic in the 20th Century*, 2(3):49, 2003.

[68] Harvey Martin FRIEDMAN : *Subsystems of Set Theory and Analysis*. PhD Thesis, Massachusetts Institute of Technology, 1967.
[69] Peter GÁCS : On the Symmetry of Algorithmic Information. *In Doklady Akademii Nauk*, volume 218, pages 1265-1267. Russian Academy of Sciences, 1974. Issue : 6.

[70] Péter GÁCS : Every Sequence is Reducible to a Random One. *Information and Control*, 70(2/3):186-192, 1986.

[71] GALILÉE : *Discours et démonstrations mathématiques concernant deux sciences nouvelles*. Masson Éditeur, 1972. Introduction, traduction, notes et index de Maurice Clavelin.

[72] Robin O. GANDY : On a Problem of Kleene's. *Bulletin of the American Mathematical Society*, 66(6):501-502, 1960.

[73] Guido GHERARDI et Alberto MARCONE : How Incomputable is the separable Hahn-Banach Theorem? *Notre Dame J. Form. Log.*, 50(4):393-425 (2010), 2009.

[74] Kurt GÖDEL : The Consistency of the Axiom of Choice and of the Generalized Continuum-Hypothesis. *Proceedings of the National Academy of Sciences of the United States of America*, 24(12):556, 1938. Publisher : National Academy of Sciences.

[75] Herman Heine GOLDSTINE et John VON NEUMANN : Planning and Coding of Problems for an Electronic Computing Instrument. 1947.

[76] Noam GREENBERG et Joseph S. MILLER : Lowness for Kurtz Randomness. *The Journal of Symbolic Logic*, 74(2):665-678, 2009. Publisher : Cambridge University Press.

[77] Marcia J. GROSZEK et Theodore A. SLAMAN : Independence Results on the Global Structure of the Turing Degrees. *Transactions of the American Mathematical Society*, 277(2):579-588, 1983.

[78] Marcia J. GROSZEK et Theodore A. SLAMAN : $Π_1^0$ Classes and Minimal Degrees. *Annals of Pure and Applied Logic*, 87(2):117-144, 1997.

[79] Marcia J GROSZEK et Theodore A SLAMAN : Moduli of Computation (Talk). *Buenos Aires, Argentina*, 2007.

[80] David GUASPARI : A Note on the Kondo-Addison Theorem. *The Journal of Symbolic Logic*, 39(3):567-570, 1974. Publisher : JSTOR.

[81] Petr HÁJEK et Pavel PUDLÁK : *Metamathematics of First-Order Arithmetic*. Perspectives in Mathematical Logic. Springer-Verlag, Berlin, 1998.

[82] Joel David HAMKINS et Andy LEWIS-PYE : Infinite Time Turing Machines. *Journal of Symbolic Logic*, pages 567-604, 2000. Publisher : JSTOR.

[83] Leo HARRINGTON et Saharon SHELAH : The Undecidibility of the Recursively Enumerable Degrees. *Bulletin of the American Mathematical Society*, 6, 1982.
[84] Joseph HARRISON : Recursive Pseudo-Well-Orderings. *Transactions of the American Mathematical Society*, 131(2):526-543, 1968. Publisher : JSTOR.

[85] Leon HENKIN : The Completeness of the First-Order Functional Calculus. *The Journal of Symbolic Logic*, 14(3):159-166, 1949.

[86] Neil HINDMAN : Finite Sums From Sequences within Cells of a Partition of N. *J. Combinatorial Theory Ser. A*, 17:1-11, 1974.

[87] Denis R HIRSCHFELDT : Slicing the Truth. *Lecture Notes Series, Institute for Mathematical Sciences, National University of Singapore*, 28, 2015. Publisher : World Scientific Publishing.

[88] Denis R. HIRSCHFELDT et Carl G. JOCKUSCH : On Notions of Computability-Theoretic Reduction between Π₂¹ Principles. *J. Math. Log.*, 16(1):1650002, 59, 2016.

[89] Denis R. HIRSCHFELDT, Carl G. JOCKUSCH, Bjørn KJOS-HANSSEN, Steffen LEMPP et Theodore A. SLAMAN : The Strength of some Combinatorial Principles Related to Ramsey's Theorem for Pairs. *Computational Prospects of Infinity, Part II : Presented Talks, World Scientific Press, Singapore*, pages 143-161, 2008.

[90] Denis R HIRSCHFELDT, André NIES et Frank STEPHAN : Using Random Sets as Oracles. *Journal of the London Mathematical Society*, 75(3):610-622, 2007. Publisher : Oxford University Press.

[91] Jeffry L. HIRST : *Combinatorics in Subsystems of Second Order Arithmetic*. Thèse de doctorat, Pennsylvania State University, août 1987.

[92] Greg HJORTH et André NIES : Randomness via Effective Descriptive Set Theory. *Journal of the London Mathematical Society*, 75(2):495-508, 2007.

[93] Wassily HOEFFDING : Probability Inequalities for Sums of Bounded Random Variables. *Journal of the American Statistical Association*, 58(301):13-30, 1963. Publisher : Taylor & Francis Group.

[94] Mathieu HOYRUP et Cristóbal ROJAS : Applications of Effective Probability Theory to Martin-Löf Randomness. *In International Colloquium on Automata, Languages, and Programming*, pages 549-561. Springer, 2009.

[95] Shamil ISHMIKHAMETOV : Weak Recursive Degrees and a Problem of Spector. *In Recursion Theory and Complexity (Kazan, 1997)*, volume 2 de *De Gruyter Ser. Log. Appl.*, pages 81-87. de Gruyter, Berlin, 1999.

[96] Carl JOCKUSCH et Robert SOARE : Degrees of Members of Π₁₀ Classes. *Pacific Journal of Mathematics*, 40:605-616, 1972.
[97] Carl G. JOCKUSCH : Relationships between Reducibilities. *Transactions of the American Mathematical Society*, 142:229-237, 1969.

[98] Carl G JOCKUSCH : Degrees in which the Recursive Sets are Uniformly Recursive. *Canadian Journal of Mathematics*, 24(6):1092-1099, 1972. Publisher : Cambridge University Press.

[99] Carl G. JOCKUSCH : Ramsey's Theorem and Recursion Theory. *The Journal of Symbolic Logic*, 37(2):268-280, 1972. Publisher : Cambridge University Press.

[100] Carl G. JOCKUSCH : Degrees of Generic Sets. *Recursion Theory : Its Generalizations and Applications*, pages 110-139, 1980. Publisher : Cambridge Univ. Press Cambridge.

[101] Carl G. JOCKUSCH, Manuel LERMAN, Robert I. SOARE et Robert M. SOLOVAY : Recursively Enumerable Sets modulo Iterated Jumps and Extensions of Arslanov's Completeness Criterion. *The Journal of Symbolic Logic*, 54(4):1288-1323, 1989. Publisher : Cambridge University Press.

[102] Carl G. JOCKUSCH et Richard A. SHORE : Pseudo-Jump Operators. II : Transfinite Iterations, Hierarchies and Minimal Covers. *The Journal of Symbolic Logic*, 49(4):1205-1236, 1984. Publisher : JSTOR.

[103] Carl G. JOCKUSCH et Frank STEPHAN : A Cohesive Set which is not High. *Mathematical Logic Quarterly*, 39(1):515-530, 1993. Publisher : Wiley Online Library.

[104] Carl G. JOCKUSCH, Jr. et Robert I. SOARE : $Π_1^0$ Classes and Degrees of Theories. *Trans. Amer. Math. Soc.*, 173:33-56, 1972.

[105] Carl G JOCKUSCH JR : Degrees of Functions with no Fixed Points. *In Studies in Logic and the Foundations of Mathematics*, volume 126, pages 191-201. Elsevier, 1989.

[106] Akihiro KANAMORI : Mathias and Set Theory. *Mathematical Logic Quarterly*, 62(3):278-294, 2016.

[107] Loren KANTOR, Jean-Michel et Graham : *Au nom de l'infini. Une histoire vraie de mysticisme religieux et de création mathématique*. Belin, 2010.

[108] Steven M. KAUTZ : *Degrees of Random Sets*. PhD Thesis, Citeseer, 1991.

[109] Richard KAYE : *Models of Peano Arithmetic*. 1991.

[110] Alexander S. KECHRIS : The Theory of Countable Analytical Sets. *Transactions of the American Mathematical Society*, 202:259-297, 1975.

[111] Mushfeq KHAN et Joseph S. MILLER : Forcing with Bushy Trees. *Bulletin of Symbolic Logic*, 23(2):160-180, 2017. Publisher : Cambridge University Press.
[112] Bjørn KJOS-HANSSEN, Wolfgang MERKLE et Frank STEPHAN : Kolmogorov Complexity and the Recursion Theorem. *Transactions of the American Mathematical Society*, 363(10):5465-5480, 2011.

[113] Bjørn KJOS-HANSSEN, Wolfgang MERKLE et Frank STEPHAN : Kolmogorov Complexity and the Recursion Theorem. *Transactions of the American Mathematical Society*, 363(10):5465-5480, 2011.

[114] Stephen C. KLEENE : On Notation for Ordinal Numbers. *The Journal of Symbolic Logic*, 3(4):150-155, 1938. Publisher : JSTOR.

[115] Stephen C. KLEENE : Arithmetical Predicates and Function Quantifiers. *Transactions of the American Mathematical Society*, 79(2):312-340, 1955. Publisher : JSTOR.

[116] Stephen C. KLEENE : Hierarchies of Number-Theoretic Predicates. *Bulletin of the American Mathematical Society*, 61(3):193-213, 1955.

[117] Stephen C. KLEENE : On the Forms of the Predicates in the Theory of Constructive Ordinals (Second Paper). *American Journal of Mathematics*, 77(3):405-428, 1955. Publisher : JSTOR.

[118] Stephen C. KLEENE et Emil L. POST : The Upper Semi-Lattice of Degrees of Recursive Unsolvability. *Annals of Mathematics*, pages 379-407, 1954. Publisher : JSTOR.

[119] Andrej KOLMOGOROFF : Zur Deutung der Intuitionistischen Logik. *Mathematische Zeitschrift*, 35(1):58-65, 1932.

[120] Andrei KOLMOGOROV : Logical Basis for Information Theory and Probability Theory. *IEEE Transactions on Information Theory*, 14(5):662-664, 1968.

[121] Andrei N. KOLMOGOROV : On Tables of Random Numbers. *Sankhya*
*The Indian Journal of Statistics, Series A*, pages 369-376, 1963. Pub-
lisher : JSTOR.

[122] Andrei N. KOLMOGOROV : Three Approaches to the Quantitative Definition Of information'. *Problems of Information Transmission*, 1(1):1-7, 1965.

[123] Motokiti KONDÔ : Sur l'uniformisation des complémentaires analy-
tiques et les ensembles projectifs de la seconde classe. *In Japanese
Journal of Mathematics : Transactions and Abstracts*, volume 15,
pages 197-230. The Mathematical Society of Japan, 1939. Issue : 0.

[124] G. KREISEL : Analysis of the Cantor-Bendixson Theorem by Means of the Analytic Hierarchy. *Bull. Acad. Polon. Sci. Sér. Sci. Math. Astr. Phys.*, 7:621-626. (unbound insert), 1959.

[125] Masahiro KUMABE et Andrew LEWIS-PYE : A Fixed-Point-Free Minimal Degree. *Journal of the London Mathematical Society*, 80(3), 2009.
[126] Stuart A. KURTZ : *Randomness and Genericity in the Degrees of Unsolvability*. PhD Thesis, 1982.

[127] Antonin KUČERA et Theodore SLAMAN : Randomness and Recursive Enumerability. *SIAM Journal on Computing*, 31(1):199–211, 2001.
Publisher : SIAM.

[128] Antonín KUČERA : Measure, Π<sub>1</sub><sup>0</sup>-Classes and Complete Extensions of PA. *In Recursion Theory Week*, pages 245–259. Springer, 1985.

[129] A. H. LACHLAN : Lower Bounds for Pairs of Recursively Enumerable Degrees. *Proceedings of the London Mathematical Society*, s3-16(1): 537–569, 1966.

[130] Alistair H. LACHLAN : Complete Recursively Enumerable Sets. *Proceedings of the American Mathematical Society*, 19(1):99–102, 1968.

[131] Alistair H. LACHLAN : Embedding Nondistributive Lattices in the Recursively Enumerable Degrees. *In Conference in Mathematical Logic—London 70*, pages 149–177. Springer, 1972.

[132] Alistair H. LACHLAN : Uniform Enumeration Operations. *Journal of Symbolic Logic*, pages 401–409, 1975.

[133] Alistair H. LACHLAN et Robert LEBEUF : Countable Initial Segments of the Degrees of Unsolvability. *The Journal of Symbolic Logic*, 41(2): 289–300, 1976.

[134] Alistair H. LACHLAN et Robert I. SOARE : Not Every Finite Lattice is Embeddable in the Recursively Enumerable Degrees. *Advances in Mathematics*, 37(1):74–82, 1980.

[135] Joachim LAMBEK : How to Program an Infinite Abacus. *Canadian Mathematical Bulletin*, 4(3):295–302, 1961.

[136] Henri LEBESGUE : Sur une généralisation de l'intégrale définie. *CR Acad. Sci. Paris*, 132:1025–1028, 1901.

[137] Steffen LEMPP, André NIES et Theodore A. SLAMAN : The Pi0.3-Theory of the Computably Enumerable Turing Degrees is Undecidable. *Transactions of the American Mathematical Society*, pages 2719–2736, 1998.

[138] Manuel LERMAN : *Degrees of Unsolvability*, volume 11. Cambridge University Press, 2017.

[139] Leonid A. LEVIN : *Some Theorems on the Algorithmic Approach to Probability Theory and Information Theory*. Dissertation in Mathematics, Université de Moscou, 1971.

[140] Leonid A. LEVIN : On the Notion of a Random Sequence. *In Soviet. Math. Dokl.*, volume 14, pages 1413–1416, 1973. Issue : 5.

[141] Leonid A. LEVIN : The Concept of a Random Sequence. *In Dokl. Akad. Nauk SSSR*, volume 212, pages 2–2, 1973. Issue : 548-550.
[142] Leonid A. LEVIN: Laws of Information Conservation (Nongrowth) and Aspects of the Foundation of Probability Theory. *Problemy Peredachi Informatsii*, 10(3):30–35, 1974. Publisher: Russian Academy of Sciences.

[143] Andrew LEWIS-PYE: Strong Minimal Covers and a Question of Yates: The Story so Far. *In Logic Colloquium 2006*, volume 32 of *Lect. Notes Log.*, pages 213–228. Assoc. Symbol. Logic, Chicago, IL, 2009.

[144] Ming LI et Paul VITÁNYI: *An Introduction to Kolmogorov Complexity and its Applications*, volume 3. Springer, 2008.

[145] J. E. LITTLEWOOD: *Lectures on the Theory of Functions*. Oxford University Press, 1944.

[146] Jiayi LIU: $RT_2^2$ does not Imply $WKL_0$. *The Journal of Symbolic Logic*, pages 609–620, 2012. Publisher: JSTOR.

[147] Richard MANSFIELD: Perfect Subsets of Definable Sets of Real Numbers. *Pacific Journal of Mathematics*, 35(2):451–457, 1970. Publisher: Mathematical Sciences Publishers.

[148] Donald A. MARTIN: Classes of Recursively Enumerable Sets and Degrees of Unsolvability. *Mathematical Logic Quarterly*, 12(1):295–310, 1966. Publisher: Wiley Online Library.

[149] Donald A. MARTIN: Borel Determinacy. *Annals of Mathematics*, pages 363–371, 1975.

[150] Per MARTIN-LÖF: The Definition of Random Sequences. *Information and Control*, 9(6):602–619, 1966. Publisher: Elsevier.

[151] A. R. David MATHIAS: *On a Generalization of Ramsey's Theorem*. Thèse de doctorat, University of Cambridge, 1969.

[152] A. R. David MATHIAS: Happy Families. *Ann. Math. Logic*, 12(1):59–111, 1977.

[153] Kenneth McALOON: Paris-Harrington Incompleteness and Progressions of Theories. *In Recursion Theory (Ithaca, N.Y., 1982)*, volume 42 of *Proc. Sympos. Pure Math.*, pages 447–460. Amer. Math. Soc., Providence, RI, 1985.

[154] Yuri T. MEDVEDEV: Degrees of Difficulty of the Mass Problem. *In Doklady Akademii Nauk SSSR, Ns*, volume 104, pages 501–504, 1955.

[155] Zdzislaw Alexander MELZAK: An Informal Arithmetical Approach to Computability and Computation. *Canadian Mathematical Bulletin*, 4(3):279–293, 1961.

[156] Joseph R. MILETI: Partition Theorems and Computability Theory. *The Bulletin of Symbolic Logic*, 11(3):411–427, 2005. Publisher: JSTOR.
[157] Webb MILLER et Donald A. MARTIN : The Degrees of Hyperim-
mune Sets. *Mathematical Logic Quarterly*, 14(7-12):159-166, 1968.
Publisher : Wiley Online Library.

[158] Benoît MONIN : Higher Randomness and Forcing with Closed Sets.
*Theory of Computing Systems*, 60(3):421-437, 2017.

[159] Benoît MONIN et Ludovic PATEY : Pigeons do not jump high. *Advances in Mathematics*, 352:1066-1095, 2019.

[160] Benoît MONIN et Ludovic PATEY : SRT22 does not imply COH in Omega-Models, 2019.

[161] Benoît MONIN et Ludovic PATEY : The Weakness of the Pigeonhole Principle under Hyperarithmetical Reductions, 2019.

[162] Yiannis John MOSCHOVAKIS : Many-One Degrees of the Predicates Ha (X). *Pacific Journal of Mathematics*, 18(2):329-342, 1966. Publisher : Mathematical Sciences Publishers.

[163] Albert A. MUCHNIK : On the Unsolvability of the Problem of Reducibility in the Theory of Algorithms. *In Dokl. Akad. Nauk SSSR*, volume 108, pages 194-197, 1956. Issue : 1.

[164] Albert A. MUCHNIK : Solution of Post's Reduction Problem and of Certain Other Problems in the Theory of Algorithms. *Trudy Moskovskogo Matematicheskogo Obshchestva*, 7:391-405, 1958.

[165] Albert A. MUCHNIK : Strong and Weak Reducibility of Algorithmic Problems 1. *Computability : The Journal of the Association CiE*, 5(1):49-59, 2016. Traduction de l'article original de 1963.

[166] André NIES : Lowness Properties and Randomness. *Advances in Mathematics*, 197(1):274-305, 2005.

[167] André NIES : *Computability and Randomness*, volume 51. Oxford University Press, 2009.

[168] André NIES, Richard A. SHORE et Theodore A. SLAMAN : Interpretability and Definability in the Recursively Enumerable Degrees. *Proceedings of the London Mathematical Society*, 77(2):241-291, 1998.

[169] Piergiorgio ODIFREDDI : *Classical Recursion Theory : The Theory of Functions and Sets of Natural Numbers*. Elsevier, 1992.

[170] J. B. PARIS et L. A. S. KIRBY : $\Sigma_n$-Collection Schemas in Arithmetic, 1978.

[171] Charles PARSONS : On a Number Theoretic Choice Schema and its Relation to Induction. *In Intuitionism and Proof Theory (Proc. Conf., Buffalo, N.Y., 1968)*, pages 459-473. North-Holland, Amsterdam, 1970.

[172] Ludovic PATEY : The Weakness of Being Cohesive, Thin or Free in Reverse Mathematics. *Israel J. Math.*, 216(2):905-955, 2016.
[173] Ludovic PATEY et Keita YOKOYAMA : The Proof-Theoretic Strength of Ramsey's Theorem for Pairs and Two Colors. *Adv. Math.*, 330: 1034-1070, 2018.

[174] Rózsa PÉTER : Programmierung und Partiell-Rekursive Funktionen. *Acta Mathematica Academiae Scientiarum Hungarica*, 14(3-4):373-401, 1963.

[175] Von Rózsa PÉTER : Graphschemata und Rekursive Funktionen. *Dialectica*, 12(3-4):373-393, 1958.

[176] H. POINCARÉ : *Dernières pensées*. Flammarion, 1917.

[177] Henri POINCARÉ : L'intuition et la logique en mathématiques. *La valeur de la Science*.

[178] Henri POINCARÉ : *Science et méthode*. Flammarion, 1908.

[179] Christopher P. PORTER : *Mathematical and Philosophical Perspectives on Algorithmic Randomness*. University of Notre Dame, 2012.

[180] David B. POSNER et Robert W. ROBINSON : Degrees Joining to 0'. *Journal of Symbolic Logic*, pages 714-722, 1981. Publisher : JSTOR.

[181] Emil L. POST : Recursively Enumerable Sets of Positive Integers and their Decision Problems. *Bulletin of the American Mathematical Society*, 50(5):284-316, 1944.

[182] Tibor RADO : On Non-Computable Functions. *Bell System Technical Journal*, 41(3):877-884, 1962.

[183] Hartley ROGERS, Jr. : Gödel Numberings of Partial Recursive Functions. *J. Symbolic Logic*, 23:331-341, 1958.

[184] Barkley ROSSER : An Informal Exposition of Proofs of Godel's Theorems and Church's Theorem. *Journal of Symbolic Logic*, 4(2):53-60, 1939. Publisher : Association for Symbolic Logic.

[185] Gerald E. SACKS : A Minimal Degree less than 0'. *Bull. Amer. Math. Soc.*, 67:416-419, 1961.

[186] Gerald E. SACKS : On Suborderings of Degrees of Recursive Unsolvability. *Mathematical Logic Quarterly*, 7(1-5):46-56, 1961.

[187] Gerald E. SACKS : A Maximal Set which is not Complete. *Michigan Mathematical Journal*, 11(3):193-205, 1964.

[188] Gerald E. SACKS : *Degrees of Unsolvability*. Numéro 55. Princeton University Press, 1966.

[189] Gerald E. SACKS : Measure-Theoretic Uniformity in Recursion Theory and Set Theory. *Transactions of the American Mathematical Society*, 142:381-420, 1969.

[190] Gerald E. SACKS : Forcing with Perfect Closed Sets. *In Axiomatic Set Theory*, volume 1, pages 331-355. Amer. Math. Soc Providence, RI, 1971.
[191] Gerald E. SACKS · Countable Admissible Ordinals and Hyperdegrees. *Advances in Mathematics*, 20(2):213–262, 1976. Publisher: Academic Press.

[192] Gerald E. SACKS : *Higher Recursion Theory*, volume 2. Cambridge University Press, 2017.

[193] Claus-Peter SCHNORR : The Process Complexity and Effective Random Tests. In *Proceedings of the Fourth Annual ACM Symposium on Theory of Computing*, pages 168–176, 1972.

[194] Dana SCOTT : Algebras of Sets Binumerable in Complete Extensions of Arithmetic. In *Proc. Sympos. Pure Math*, volume 5, pages 117–121, 1962.

[195] David SEETAPUN et Theodore SLAMAN : On the Strength of Ramsey's Theorem. *Notre Dame Journal of Formal Logic*, 36(4):570–582, 1995. Publisher : University of Notre Dame.

[196] Adi SHAMIR : $IP = PSPACE$. *Journal of the ACM (JACM)*, 39(4): 869–877, 1992.

[197] John C. SHEPHERDSON et Howard E. STURGIS : Computability of Recursive Functions. *Journal of the ACM (JACM)*, 10(2):217–255, 1963.

[198] J. R. SHOENFIELD : A Theorem on Minimal Degrees. *J. Symbolic Logic*, 31:539–544, 1966.

[199] Richard A. SHORE : On the $\forall\exists$-Sentences of $\alpha$-Recursion Theory. *In Studies in Logic and the Foundations of Mathematics*, volume 94, pages 331–353. Elsevier, 1978.

[200] Richard A. SHORE et Theodore A. SLAMAN : Defining the Turing Jump. *Mathematical Research Letters*, 6(6):711–722, 1999.

[201] Stephen G. SIMPSON : First-Order Theory of the Degrees of Recursive Unsolvability. *Annals of Mathematics*, pages 121–139, 1977.

[202] Stephen G. SIMPSON : Partial Realizations of Hilbert's Program. *J. Symbolic Logic*, 53(2):349–363, 1988.

[203] Stephen G. SIMPSON : *Subsystems of Second Order Arithmetic*, volume 1. Cambridge University Press, 2009.

[204] Theodore A. SLAMAN : $\Sigma_n$-Bounding and $\Delta_n$-Induction. 132:2449–2449, 2004.

[205] Theodore A. SLAMAN et John R STEEL : Definable Functions on Degrees. *In Cabal Seminar 81–85*, pages 37–55. Springer, 1988.

[206] Theodore A. SLAMAN et William H. WOODIN : Definability in the Tu- ring Degrees. *Illinois Journal of Mathematics*, 30(2):320–334, 1986.

[207] Theodore A. SLAMAN et William H. WOODIN : Definability in Degree Structures. *Preprint*, 2005.
[208] Robert I. SOARE : Turing Computability. *Theory and Applications of Computability*. Springer, 2016.

[209] Ray J. SOLOMONOFF : A Preliminary Report on a General Theory of Inductive Inference. United States Air Force, Office of Scientific Research, 1960.

[210] Ray J. SOLOMONOFF : A Formal Theory of Inductive Inference. Part I. *Information and Control*, 7(1):1-22, 1964. Publisher : Elsevier.

[211] Robert M SOLOVAY : On the Cardinality of $\Sigma_2^1$ Sets of Reals. *In Foundations of Mathematics*, pages 58-73. Springer, 1969.

[212] Robert M. SOLOVAY : Draft of Paper (Or Series of Papers) on Chaitin's Work. mai 1975.

[213] Ernst SPECKER : Ramsey's Theorem does not hold in Recursive Set Theory. *In Studies in Logic and the Foundations of Mathematics*, volume 61, pages 439-442. Elsevier, 1971.

[214] Clifford SPECTOR : Recursive Well-Orderings. *The Journal of Symbolic Logic*, 20(2):151-163, 1955. Publisher : JSTOR.

[215] Clifford SPECTOR : On Degrees of Recursive Unsolvability. *Ann. of Math. (2)*, 64:581-592, 1956.

[216] John R. STEEL : Forcing with Tagged Trees. *Annals of Mathematical Logic*, 15(1):55-74, 1978. Publisher : Elsevier.

[217] John R STEEL : A Classification of Jump Operator. *The Journal of Symbolic Logic*, 47(2):347-358, 1982.

[218] Frank STEPHAN : Martin-Löf Random and PA-complete Sets. *In Logic Colloquium*, volume 2, pages 342-348. Association for Symbolic Logic and AK Peters, Ltd, 2006.

[219] Mikhail SUSLIN : Sur une définition des ensembles mesurables B sans nombres transfinis. *CR Acad. Sci. Paris*, 164(2):88-91, 1917.

[220] William W TAIT : Finitism. *The Journal of Philosophy*, pages 524-546, 1981.

[221] Hisao TANAKA et al. : A Basis Result for $\Pi_1^1$-Sets of Positive Measure. *Rikkyo Daigaku sugaku zasshi*, 16(2):115-127, 1967.

[222] S. A. TERWIJN et D. ZAMBELLA : Algorithmic Randomness and Lowness. *ILLC Technical Report*, ML-1997-07, 1997.

[223] Steven K. THOMASON : Sublattices of the Recursively Enumerable Degrees. *Mathematical Logic Quarterly*, 17(1):273-280, 1971.

[224] Henry TOWSNER : A Simple Proof and some Difficult Examples for Hindman's Theorem. *Notre Dame J. Form. Log.*, 53(1):53-65, 2012.

[225] John TROMP et Gunnar FARNEBÄCK : Combinatorics of Go. *In International Conference on Computers and Games*, pages 84-99. Springer, 2006.
[226] Alan Mathison TURING : Systems of Logic Based on Ordinals. *Proceedings of the London Mathematical Society*, 2(1):161–228, 1939. Publisher : Wiley Online Library.

[227] Michiel van LAMBALGEN : *Random Sequences*. Ph.D. Dissertation, University of Amsterdam, 1987.

[228] Jean VILLE : Étude critique de la notion de collectif. *Bull. Amer. Math. Soc*, 45(11):824, 1939.

[229] Hao WANG : A Variant to Turing’s Theory of Computing Machines. *Journal of the ACM (JACM)*, 4(1):63–92, 1957.

[230] Hao WANG : *Popular Lectures on Mathematical Logic*. Dover Publications, Inc., New York, seconde édition, 1993.

[231] Wei WANG : Some Logically Weak Ramseyan Theorems. *Advances in Mathematics*, 261:1–25, 2014.

[232] Wei WANG : The Definability Strength of Combinatorial Principles. *J. Symb. Log.*, 81(4):1531–1554, 2016.

[233] K. WEIHRAUCH : *Computable Analysis : An Introduction*. Texts in Theoretical Computer Science. An EATCS Series. Springer Berlin Heidelberg, 2000.

[234] Mike C. E. YATES : A Minimal Pair of Recursively Enumerable Degrees. *Journal of Symbolic Logic*, 31(2):159–168, juin 1966.

[235] Mike C. E. YATES : Initial Segments of the Degrees of Unsolvability Part II : Minimal Degrees. *The Journal of Symbolic Logic*, 35(2):243–266, 1970.

[236] Liang YU : Descriptive Set Theoretical Complexity of Randomness Notions. *Fundamenta Mathematicae*, 215(3):219–231, 2011.

[237] A. K. ZVONKIN et L. A. LEVIN : The complexity of finite objects and the basing of the concepts of information and randomness on the theory of algorithms. *Uspehi Mat. Nauk*, 25(6(156)):85–127, 1970.
Notations

<table>
  <tbody>
    <tr>
      <td>|E| = |F|</td>
      <td>Les ensembles E et F sont équipotents</td>
      <td>15</td>
    </tr>
    <tr>
      <td>|E| &le; |F|</td>
      <td>L'ensemble E est subpotent à l'ensemble F</td>
      <td>16</td>
    </tr>
    <tr>
      <td>&lang;n, m&rang;</td>
      <td>Le résultat de la bijection de Cantor sur n, m</td>
      <td>20</td>
    </tr>
    <tr>
      <td>&lang;x<sub>1</sub>, ..., x<sub>k</sub>&rang;</td>
      <td>Le résultat de la bijection de Cantor sur x<sub>1</sub>, ..., x<sub>k</sub></td>
      <td>20</td>
    </tr>
    <tr>
      <td>P(A)</td>
      <td>L'ensemble des sous-ensembles de A</td>
      <td>23</td>
    </tr>
    <tr>
      <td>2<sup>N</sup></td>
      <td>L'espace de Cantor</td>
      <td>25</td>
    </tr>
    <tr>
      <td>X(n)</td>
      <td>Le n-ième élément de X (en commençant à 0)</td>
      <td>26</td>
    </tr>
    <tr>
      <td>f(x) = g(x)</td>
      <td>Les fonctions calculables f et g s'arrêtent sur x et retournent la même valeur, ou bien ne s'arrêtent pas sur x.</td>
      <td>34</td>
    </tr>
    <tr>
      <td>&Phi;<sub>e</sub></td>
      <td>La fonction calculable de code e</td>
      <td>35</td>
    </tr>
    <tr>
      <td>&Phi;<sub>e</sub>(x)&downarrow;</td>
      <td>L'exécution de &Phi;<sub>e</sub> s'arrête sur l'entrée x</td>
      <td>35</td>
    </tr>
    <tr>
      <td>&Phi;<sub>e</sub>(x)&uparrow;</td>
      <td>L'exécution de &Phi;<sub>e</sub> ne s'arrête pas sur l'entrée x</td>
      <td>35</td>
    </tr>
    <tr>
      <td>&Phi;<sub>e</sub>(x)&downarrow;= y</td>
      <td>L'exécution de &Phi;<sub>e</sub> s'arrête sur l'entrée x et retourne la valeur y</td>
      <td>35</td>
    </tr>
    <tr>
      <td>&Phi;<sub>e</sub>(x) &uparrow;= y</td>
      <td>L'exécution de &Phi;<sub>e</sub> ne s'arrête pas sur l'entrée x ou bien s'arrête et retourne une valeur différente de y</td>
      <td>35</td>
    </tr>
    <tr>
      <td>&Phi;<sub>e</sub>(x)[t]&downarrow;</td>
      <td>L'exécution de &Phi;<sub>e</sub> s'arrête sur l'entrée x en moins de t étapes de calcul</td>
      <td>36</td>
    </tr>
    <tr>
      <td>&Phi;<sub>e</sub>(x)[t]&uparrow;</td>
      <td>L'exécution de &Phi;<sub>e</sub> ne s'arrête pas sur l'entrée x en moins de t étapes de calcul</td>
      <td>36</td>
    </tr>
    <tr>
      <td>&pi;<sub>0</sub>, &pi;<sub>1</sub></td>
      <td>Les fonctions inverses de (n, m) &mapsto; &lang;n, m&rang;</td>
      <td>37</td>
    </tr>
    <tr>
      <td>A[s]</td>
      <td>L'approximation de A à l'étape s</td>
      <td>47</td>
    </tr>
    <tr>
      <td>&emptyset;'</td>
      <td>Le problème de l'arrêt</td>
      <td>47</td>
    </tr>
    <tr>
      <td>2<sup>&lt;N</sup></td>
      <td>L'ensemble des chaînes binaires</td>
      <td>51</td>
    </tr>
    <tr>
      <td>&epsilon;</td>
      <td>La chaîne vide</td>
      <td>51</td>
    </tr>
    <tr>
      <td>&sigma;&tau;</td>
      <td>La concaténation de &sigma; et &tau;</td>
      <td>51</td>
    </tr>
    <tr>
      <td>&sigma; &le; &tau;</td>
      <td>La chaîne &sigma; est un préfixe de la chaîne &tau;</td>
      <td>51</td>
    </tr>
    <tr>
      <td>|&sigma;|</td>
      <td>La taille de &sigma;</td>
      <td>51</td>
    </tr>
    <tr>
      <td>&sigma;(n)</td>
      <td>Le bit numéro n de &sigma; (en commençant à 0)</td>
      <td>51</td>
    </tr>
    <tr>
      <td>&sigma;X</td>
      <td>La concaténation de &sigma; et X</td>
      <td>52</td>
    </tr>
    <tr>
      <td>&sigma; &lt; X</td>
      <td>La chaîne &sigma; est un préfixe de X</td>
      <td>52</td>
    </tr>
    <tr>
      <td>X |&sub;n</td>
      <td>Le préfixe de X de taille n</td>
      <td>52</td>
    </tr>
    <tr>
      <td>&Phi;<sub>e</sub>(A, n)</td>
      <td>Le résultat du calcul de la fonctionnelle &Phi;<sub>e</sub> avec l'oracle A et sur l'entrée n</td>
      <td>53</td>
    </tr>
    <tr>
      <td>&Phi;<sub>e</sub><sup>A</sup>(n)</td>
      <td>Autre notation pour &Phi;<sub>e</sub>(A, n)</td>
      <td>53</td>
    </tr>
    <tr>
      <td>&Phi;<sub>e</sub>(A, n)[t]&downarrow;</td>
      <td>La fonctionnelle &Phi;<sub>e</sub> avec l'oracle A, s'arrête en moins de t étapes sur l'entrée n</td>
      <td>53</td>
    </tr>
    <tr>
      <td>&Phi;<sub>e</sub>(A, n)[t]&uparrow;</td>
      <td>La fonctionnelle &Phi;<sub>e</sub> avec l'oracle A, ne s'arrête pas en moins de t étapes sur l'entrée n</td>
      <td>53</td>
    </tr>
  </tbody>
</table>
<table>
  <tbody>
    <tr>
      <td>Φ<sub>e</sub>(σ, n)↓</td>
      <td>La fonctionnelle Φ<sub>e</sub> avec le morceau d'oracle σ, s'arrête en moins de t étapes sur l'entrée n</td>
      <td>56</td>
    </tr>
    <tr>
      <td>Φ<sup>σ</sup><sub>e</sub>(n)↓</td>
      <td>La fonctionnelle Φ<sub>e</sub> avec le morceau d'oracle σ, ne s'arrête pas en moins de t étapes sur l'entrée n</td>
      <td>56</td>
    </tr>
    <tr>
      <td>use<sup>X</sup><sub>Φ</sub></td>
      <td>La fonction de l'usage de X sur la fonctionnelle Φ</td>
      <td>56</td>
    </tr>
    <tr>
      <td>≤<sub>T</sub></td>
      <td>Réduction Turing</td>
      <td>57</td>
    </tr>
    <tr>
      <td>deg<sub>T</sub>(X)</td>
      <td>Le degré Turing de X</td>
      <td>57</td>
    </tr>
    <tr>
      <td>≡<sub>T</sub></td>
      <td>Équivalence Turing</td>
      <td>57</td>
    </tr>
    <tr>
      <td>(D, ≤)</td>
      <td>La structure des degrés Turing</td>
      <td>57</td>
    </tr>
    <tr>
      <td>A ⊕ B</td>
      <td>La jointure de A et B</td>
      <td>59</td>
    </tr>
    <tr>
      <td>Φ<sub>e</sub>(X) = A</td>
      <td>∀n Φ<sub>e</sub>(X, n) ↓= A(n)</td>
      <td>59</td>
    </tr>
    <tr>
      <td>X'</td>
      <td>Le saut Turing de X</td>
      <td>60</td>
    </tr>
    <tr>
      <td>[σ]</td>
      <td>L'ensemble {X : σ ≺ X}</td>
      <td>69</td>
    </tr>
    <tr>
      <td>Σ<sup>0</sup><sub>n</sub> (ens.)</td>
      <td>Ensemble Σ<sup>0</sup><sub>n</sub></td>
      <td>82</td>
    </tr>
    <tr>
      <td>Π<sup>0</sup><sub>n</sub> (ens.)</td>
      <td>Ensemble Π<sup>0</sup><sub>n</sub></td>
      <td>82</td>
    </tr>
    <tr>
      <td>Δ<sup>0</sup><sub>n</sub> (ens.)</td>
      <td>Ensemble Δ<sup>0</sup><sub>n</sub></td>
      <td>83</td>
    </tr>
    <tr>
      <td>Σ<sup>0</sup><sub>1</sub> (ens.)</td>
      <td>Ensemble c. e.</td>
      <td>87</td>
    </tr>
    <tr>
      <td>Δ<sup>0</sup><sub>1</sub> (ens.)</td>
      <td>Ensemble calculable</td>
      <td>87</td>
    </tr>
    <tr>
      <td>Σ<sup>0</sup><sub>n</sub>(X) (ens.)</td>
      <td>Ensemble Σ<sup>0</sup><sub>n</sub> relativement à X</td>
      <td>88</td>
    </tr>
    <tr>
      <td>Π<sup>0</sup><sub>n</sub>(X) (ens.)</td>
      <td>Ensemble Π<sup>0</sup><sub>n</sub> relativement à X</td>
      <td>88</td>
    </tr>
    <tr>
      <td>Δ<sup>0</sup><sub>n</sub>(X) (ens.)</td>
      <td>Ensemble Δ<sup>0</sup><sub>n</sub> relativement à X</td>
      <td>89</td>
    </tr>
    <tr>
      <td>≤<sub>m</sub></td>
      <td>Réduction many-one</td>
      <td>89</td>
    </tr>
    <tr>
      <td>≡<sub>m</sub></td>
      <td>Équivalence many-one</td>
      <td>89</td>
    </tr>
    <tr>
      <td>X<sup>(n)</sup></td>
      <td>Le n-ième saut Turing de X</td>
      <td>91</td>
    </tr>
    <tr>
      <td>W<sub>e</sub></td>
      <td>L'ensemble c. e. de code e</td>
      <td>95</td>
    </tr>
    <tr>
      <td>W<sup>X</sup><sub>e</sub></td>
      <td>L'ensemble X-c. e. de code e</td>
      <td>95</td>
    </tr>
    <tr>
      <td>g(¯x)</td>
      <td>Un raccourci pour g(x<sub>1</sub>,...,x<sub>n</sub>) (avec g : N<sup>n</sup> → N)</td>
      <td>100</td>
    </tr>
    <tr>
      <td>dom f</td>
      <td>Le domaine de définition de la fonction f</td>
      <td>111</td>
    </tr>
    <tr>
      <td>Im f</td>
      <td>L'image de f</td>
      <td>111</td>
    </tr>
    <tr>
      <td>p<sup>n</sup><sub>i</sub></td>
      <td>Fonction primitive récursive de projection</td>
      <td>117</td>
    </tr>
    <tr>
      <td>c<sup>n</sup><sub>i</sub></td>
      <td>Fonction primitive récursive constante</td>
      <td>117</td>
    </tr>
    <tr>
      <td>succ</td>
      <td>Fonction primitive récursive successeur</td>
      <td>117</td>
    </tr>
    <tr>
      <td>≤<sub>tt</sub></td>
      <td>Réduction truth-table</td>
      <td>144</td>
    </tr>
    <tr>
      <td>≡<sub>tt</sub></td>
      <td>Équivalence truth-table</td>
      <td>144</td>
    </tr>
    <tr>
      <td>∀<sup>∞</sup><sub>x</sub></td>
      <td>Pour tout x sauf un nombre fini</td>
      <td>147</td>
    </tr>
    <tr>
      <td>∃<sup>∞</sup><sub>x</sub></td>
      <td>Pour une infinité de x</td>
      <td>147</td>
    </tr>
    <tr>
      <td>[T]</td>
      <td>L'ensemble des chemins de T</td>
      <td>154</td>
    </tr>
    <tr>
      <td>i<sup>∞</sup></td>
      <td>La suite infinie qui répète le bit i ∈ {0,1}</td>
      <td>158</td>
    </tr>
    <tr>
      <td>[W]</td>
      <td>L'ensemble ⋃<sub>σ∈W</sub>[σ]</td>
      <td>158</td>
    </tr>
    <tr>
      <td>Σ<sup>0</sup><sub>1</sub> (classe)</td>
      <td>Un ouvert effectif</td>
      <td>165</td>
    </tr>
    <tr>
      <td>Π<sup>0</sup><sub>1</sub> (classe)</td>
      <td>Un fermé effectif</td>
      <td>165</td>
    </tr>
    <tr>
      <td>f<sup>≤N</sup></td>
      <td>L'ensemble des chaînes σ ∈ N<sup>≤N</sup> telles que pour tout n &lt; |σ|, σ(n) &lt; f(n)</td>
      <td>182</td>
    </tr>
  </tbody>
</table>
<table>
  <tr>
    <td>Q</td>
    <td>L'arithmétique de Robinson</td>
    <td>203</td>
  </tr>
  <tr>
    <td>T ⊢ F</td>
    <td>F est démontrable dans T</td>
    <td>204</td>
  </tr>
  <tr>
    <td>T ⧸ F</td>
    <td>F n'est pas démontrable dans T</td>
    <td>204</td>
  </tr>
  <tr>
    <td>T ⊢⊥</td>
    <td>T est incohérente</td>
    <td>204</td>
  </tr>
  <tr>
    <td>M |= F</td>
    <td>M est modèle de F</td>
    <td>206</td>
  </tr>
  <tr>
    <td>Δ<sub>0</sub> (form.)</td>
    <td>Formule Δ<sub>0</sub></td>
    <td>213</td>
  </tr>
  <tr>
    <td>Σ<sub>n</sub> (form.)</td>
    <td>Formule Σ<sub>n</sub><sup>0</sup></td>
    <td>213</td>
  </tr>
  <tr>
    <td>Π<sub>n</sub> (form.)</td>
    <td>Formule Π<sub>n</sub><sup>0</sup></td>
    <td>213</td>
  </tr>
  <tr>
    <td>Coh(T)</td>
    <td>Formule qui exprime la cohérence de T</td>
    <td>220</td>
  </tr>
  <tr>
    <td>Σ<sub>n</sub><sup>0</sup> (form.)</td>
    <td>Formule Σ<sub>n</sub><sup>0</sup></td>
    <td>233</td>
  </tr>
  <tr>
    <td>Π<sub>n</sub><sup>0</sup> (form.)</td>
    <td>Formule Π<sub>n</sub><sup>0</sup></td>
    <td>233</td>
  </tr>
  <tr>
    <td>σ ⊢* R</td>
    <td>σ force le contrat R (cas Σ<sub>1</sub><sup>0</sup>/Π<sub>1</sub><sup>0</sup>)</td>
    <td>235</td>
  </tr>
  <tr>
    <td>σ⊥W</td>
    <td>Aucune extension de σ n'est dans W</td>
    <td>249</td>
  </tr>
  <tr>
    <td>W⊥</td>
    <td>L'ensemble {σ ∈ 2<sup>N</sup> : σ ⊥ W}</td>
    <td>249</td>
  </tr>
  <tr>
    <td>⊕<sub>n∈N</sub> A<sub>n</sub></td>
    <td>La jointure effective de (A<sub>n</sub>)<sub>n∈N</sub></td>
    <td>253</td>
  </tr>
  <tr>
    <td>σ ⊢ R</td>
    <td>σ force sémantiquement le contrat R</td>
    <td>260</td>
  </tr>
  <tr>
    <td>σ ⊢* R</td>
    <td>σ force le contrat R (cas général)</td>
    <td>260</td>
  </tr>
  <tr>
    <td>BΔU</td>
    <td>La classe (B \ U) ∪ (U \ B)</td>
    <td>263</td>
  </tr>
  <tr>
    <td>[c]∈</td>
    <td>L'ensemble des filtres maximaux contenant c</td>
    <td>274</td>
  </tr>
  <tr>
    <td>˙F</td>
    <td>L'élément correspondant au filtre maximal F dans un forcing de Cantor</td>
    <td>275</td>
  </tr>
  <tr>
    <td>[c]</td>
    <td>L'ensemble { ˙F : F ∈ [c] ∈ }</td>
    <td>276</td>
  </tr>
  <tr>
    <td>?|-</td>
    <td>Question de forcing (J.-S. ou S., cas Σ<sub>1</sub><sup>0</sup>/Π<sub>1</sub><sup>0</sup>)</td>
    <td>288</td>
  </tr>
  <tr>
    <td>?|-</td>
    <td>Question de forcing (J.-S. ou S., cas général)</td>
    <td>290</td>
  </tr>
  <tr>
    <td>?|-</td>
    <td>Question de forcing</td>
    <td>292</td>
  </tr>
  <tr>
    <td>≤<sub>w</sub></td>
    <td>Réduction de Muchnik</td>
    <td>306</td>
  </tr>
  <tr>
    <td>≤<sub>s</sub></td>
    <td>Réduction de Medvedev</td>
    <td>306</td>
  </tr>
  <tr>
    <td>0<sub>w</sub></td>
    <td>Le degré Muchnik de {Ø}</td>
    <td>306</td>
  </tr>
  <tr>
    <td>a ∪ b</td>
    <td>La borne supérieure de a et b</td>
    <td>343</td>
  </tr>
  <tr>
    <td>C<sub>M</sub>(σ)</td>
    <td>La complexité de Kolmogorov de σ pour la machine M</td>
    <td>370</td>
  </tr>
  <tr>
    <td>C(σ)</td>
    <td>La complexité de Kolmorogov de σ</td>
    <td>371</td>
  </tr>
  <tr>
    <td>C(n)</td>
    <td>La complexité de Kolmogorov de n</td>
    <td>374</td>
  </tr>
  <tr>
    <td>≤<sup>+</sup></td>
    <td>Inférieur ou égal à constante additive près</td>
    <td>374</td>
  </tr>
  <tr>
    <td>=<sup>+</sup></td>
    <td>Égal à constante additive près</td>
    <td>374</td>
  </tr>
  <tr>
    <td>K<sub>M</sub>(σ)</td>
    <td>La complexité sans préfixe de σ pour la machine M</td>
    <td>380</td>
  </tr>
  <tr>
    <td>K(σ)</td>
    <td>La complexité sans préfixe de σ</td>
    <td>380</td>
  </tr>
  <tr>
    <td>Ω</td>
    <td>Le nombre Ω de Chaitin</td>
    <td>382</td>
  </tr>
  <tr>
    <td>poids(A)</td>
    <td>Le poids d'un ensemble borné de requêtes A</td>
    <td>385</td>
  </tr>
  <tr>
    <td>Π<sub>2</sub><sup>0</sup> (classe)</td>
    <td>Une intersection effective d'ouverts effectifs</td>
    <td>400</td>
  </tr>
  <tr>
    <td>Σ<sub>n</sub><sup>0</sup> (classe)</td>
    <td>Classe borélienne Σ<sub>n</sub><sup>0</sup></td>
    <td>402</td>
  </tr>
  <tr>
    <td>Π<sub>n</sub><sup>0</sup> (classe)</td>
    <td>Classe borélienne Π<sub>n</sub><sup>0</sup></td>
    <td>402</td>
  </tr>
  <tr>
    <td>Δ<sub>n</sub><sup>0</sup> (classe)</td>
    <td>Classe borélienne Δ<sub>n</sub><sup>0</sup></td>
    <td>402</td>
  </tr>
</table>
<table>
  <tbody>
    <tr>
      <td>Σ<sub>n</sub><sup>0</sup> (classe)</td>
      <td>Classe borélienne effective Σ<sub>n</sub><sup>0</sup></td>
      <td>403</td>
    </tr>
    <tr>
      <td>Π<sub>n</sub><sup>0</sup> (classe)</td>
      <td>Classe borélienne effective Π<sub>n</sub><sup>0</sup></td>
      <td>403</td>
    </tr>
    <tr>
      <td>Δ<sub>n</sub><sup>0</sup> (classe)</td>
      <td>Classe borélienne effective Δ<sub>n</sub><sup>0</sup></td>
      <td>403</td>
    </tr>
    <tr>
      <td>λ</td>
      <td>La mesure de Lebesgue</td>
      <td>407</td>
    </tr>
    <tr>
      <td>λ(B | [σ])</td>
      <td>La mesure de B ∩ [σ] à l'intérieur de [σ]</td>
      <td>419</td>
    </tr>
    <tr>
      <td>K<sub>M</sub><sup>X</sup>(σ)</td>
      <td>La complexité sans préfixe de σ pour la machine M, relativisée à X</td>
      <td>433</td>
    </tr>
    <tr>
      <td>ρ(B | Z)</td>
      <td>La densité inférieure de Z dans B</td>
      <td>442</td>
    </tr>
    <tr>
      <td>ρ̄(B | Z)</td>
      <td>La densité supérieure de Z dans B</td>
      <td>442</td>
    </tr>
    <tr>
      <td>L<sub>Z<sub>2</sub></sub></td>
      <td>Le langage de l'arithmétique du second ordre</td>
      <td>482</td>
    </tr>
    <tr>
      <td>Z<sub>2</sub></td>
      <td>La théorie de l'arithmétique du second ordre</td>
      <td>485</td>
    </tr>
    <tr>
      <td>ω</td>
      <td>Les entiers standard</td>
      <td>488</td>
    </tr>
    <tr>
      <td>RCA<sub>0</sub></td>
      <td>La théorie RCA<sub>0</sub></td>
      <td>497</td>
    </tr>
    <tr>
      <td>ACA<sub>0</sub></td>
      <td>La théorie ACA<sub>0</sub></td>
      <td>501</td>
    </tr>
    <tr>
      <td>WKL<sub>0</sub></td>
      <td>La théorie WKL<sub>0</sub></td>
      <td>505</td>
    </tr>
    <tr>
      <td>WWKL<sub>0</sub></td>
      <td>La théorie WWKL<sub>0</sub></td>
      <td>509</td>
    </tr>
    <tr>
      <td>ACA<sub>0</sub><sup>+</sup></td>
      <td>La théorie ACA<sub>0</sub><sup>+</sup></td>
      <td>513</td>
    </tr>
    <tr>
      <td>ACA<sub>0</sub><sup>-</sup></td>
      <td>La théorie ACA<sub>0</sub><sup>-</sup></td>
      <td>514</td>
    </tr>
    <tr>
      <td>ATR<sub>0</sub></td>
      <td>La théorie ATR<sub>0</sub></td>
      <td>516</td>
    </tr>
    <tr>
      <td>Π<sub>1</sub><sup>-</sup>CA<sub>0</sub></td>
      <td>La théorie Π<sub>1</sub><sup>-</sup>CA<sub>0</sub></td>
      <td>516</td>
    </tr>
    <tr>
      <td>l<sub>ouvert</sub></td>
      <td>Le schéma d'axiomes d'induction pour les formules sans quantificateur</td>
      <td>523</td>
    </tr>
    <tr>
      <td>lΔ<sub>n</sub><sup>0</sup></td>
      <td>La théorie lΔ<sub>n</sub><sup>0</sup></td>
      <td>526</td>
    </tr>
    <tr>
      <td>x|y</td>
      <td>x divise y</td>
      <td>526</td>
    </tr>
    <tr>
      <td>x ∝ y</td>
      <td>x - y si x > y et 0 sinon.</td>
      <td>527</td>
    </tr>
    <tr>
      <td>lΣ<sub>n</sub><sup>0</sup></td>
      <td>Le schéma d'axiomes d'induction pour les formules Σ<sub>n</sub><sup>0</sup></td>
      <td>528</td>
    </tr>
    <tr>
      <td>lΠ<sub>n</sub><sup>0</sup></td>
      <td>Le schéma d'axiomes d'induction pour les formules Π<sub>n</sub><sup>0</sup></td>
      <td>528</td>
    </tr>
    <tr>
      <td>BΣ<sub>n</sub><sup>0</sup></td>
      <td>Le schéma d'axiomes de collection bornée pour les formules Σ<sub>n</sub><sup>0</sup></td>
      <td>528</td>
    </tr>
    <tr>
      <td>BΠ<sub>n</sub><sup>0</sup></td>
      <td>Le schéma d'axiomes de collection bornée pour les formules Π<sub>n</sub><sup>0</sup></td>
      <td>528</td>
    </tr>
    <tr>
      <td>LΣ<sub>n</sub><sup>0</sup></td>
      <td>Le schéma d'axiomes de minimum pour les formules Σ<sub>n</sub><sup>0</sup></td>
      <td>531</td>
    </tr>
    <tr>
      <td>LΠ<sub>n</sub><sup>0</sup></td>
      <td>Le schéma d'axiomes de minimum pour les formules Π<sub>n</sub><sup>0</sup></td>
      <td>531</td>
    </tr>
    <tr>
      <td>lΔ<sub>n</sub><sup>0</sup></td>
      <td>Le schéma d'axiomes d'induction pour les formules Δ<sub>n</sub><sup>0</sup></td>
      <td>533</td>
    </tr>
    <tr>
      <td>x ∈ y</td>
      <td>x appartient à l'ensemble codé par y</td>
      <td>539</td>
    </tr>
    <tr>
      <td>BCΣ<sub>n</sub><sup>0</sup></td>
      <td>Le schéma d'axiomes de compréhension borné pour les formules Σ<sub>n</sub><sup>0</sup></td>
      <td>541</td>
    </tr>
    <tr>
      <td>BCΠ<sub>n</sub><sup>0</sup></td>
      <td>Le schéma d'axiomes de compréhension borné pour les formules Π<sub>n</sub><sup>0</sup></td>
      <td>541</td>
    </tr>
    <tr>
      <td>BCΔ<sub>n</sub><sup>0</sup></td>
      <td>Le schéma d'axiomes de compréhension borné pour les formules Δ<sub>n</sub><sup>0</sup></td>
      <td>541</td>
    </tr>
    <tr>
      <td>Σ<sub>1</sub>-PA</td>
      <td>La théorie Σ<sub>1</sub>-PA</td>
      <td>546</td>
    </tr>
    <tr>
      <td>M[G]</td>
      <td>L'ω-extension de M constitué des ensembles définissables par des formules Δ<sub>1</sub><sup>0</sup> à paramètres dans M ∪ {G}</td>
      <td>548</td>
    </tr>
  </tbody>
</table>
<table>
  <tbody>
    <tr>
      <td>PR</td>
      <td>La classe des fonctions primitives récursives</td>
      <td>554</td>
    </tr>
    <tr>
      <td>PRA</td>
      <td>La théorie PRA</td>
      <td>554</td>
    </tr>
    <tr>
      <td>Π<sub>2</sub><sup>1</sup> (prob.)</td>
      <td>Un problème de la forme ∀X(F(X) → ∃Y G(X, Y))</td>
      <td>559</td>
    </tr>
    <tr>
      <td>ADS</td>
      <td>L'énoncé « Ascending-Descending Sequence »</td>
      <td>560</td>
    </tr>
    <tr>
      <td>≤<sub>ω</sub></td>
      <td>ω-réduction</td>
      <td>560</td>
    </tr>
    <tr>
      <td>KL</td>
      <td>Le problème associé au lemme de König</td>
      <td>561</td>
    </tr>
    <tr>
      <td>J</td>
      <td>Le problème du saut Turing</td>
      <td>561</td>
    </tr>
    <tr>
      <td>≤<sub>c</sub></td>
      <td>Réduction calculatoire</td>
      <td>565</td>
    </tr>
    <tr>
      <td>≤<sub>W</sub></td>
      <td>Réduction Weihrauch</td>
      <td>567</td>
    </tr>
    <tr>
      <td>LPO</td>
      <td>Le principe limité d'omniscience</td>
      <td>569</td>
    </tr>
    <tr>
      <td>LLPO</td>
      <td>Le principe très limité d'omniscience</td>
      <td>569</td>
    </tr>
    <tr>
      <td>Π̂</td>
      <td>La parallélisation de problème P</td>
      <td>570</td>
    </tr>
    <tr>
      <td>G(Q → P)</td>
      <td>Jeu de réduction entre les problèmes P et Q</td>
      <td>571</td>
    </tr>
    <tr>
      <td>P ≤<sub>ω</sub><sup>n</sup> Q</td>
      <td>Le joueur 2 possède une stratégie gagnante pour le jeu G(Q → P) en au plus n + 1 tours</td>
      <td>573</td>
    </tr>
    <tr>
      <td>≤<sub>sc</sub></td>
      <td>Réduction calculatoire forte</td>
      <td>573</td>
    </tr>
    <tr>
      <td>≤<sub>sW</sub></td>
      <td>Réduction forte de Weihrauch</td>
      <td>574</td>
    </tr>
    <tr>
      <td>[X]<sup>n</sup></td>
      <td>L'ensemble des sous-ensembles de X de taille n</td>
      <td>578</td>
    </tr>
    <tr>
      <td>RT<sub>k</sub><sup>n</sup></td>
      <td>Le théorème de Ramsey pour les n-uplets et k couleurs</td>
      <td>579</td>
    </tr>
    <tr>
      <td>cRT<sub>k</sub><sup>n</sup></td>
      <td>Variante du théorème de Ramsey pour la réduction Weihrauch</td>
      <td>581</td>
    </tr>
    <tr>
      <td>σ ∪ τ</td>
      <td>L'union des chaînes σ et τ vues comme des ensembles</td>
      <td>597</td>
    </tr>
    <tr>
      <td>τ − σ</td>
      <td>La différence des chaînes σ et τ vues comme des ensembles</td>
      <td>597</td>
    </tr>
    <tr>
      <td>?|</td>
      <td>Question de forcing pour le forcing de Dzhafarov-Jockusch</td>
      <td>600</td>
    </tr>
    <tr>
      <td>?|</td>
      <td>Négation de la question de forcing</td>
      <td>600</td>
    </tr>
    <tr>
      <td>COH</td>
      <td>Le principe d'existence d'ensemble cohésif</td>
      <td>612</td>
    </tr>
    <tr>
      <td>O (Kleene)</td>
      <td>L'ensemble O de Kleene</td>
      <td>636</td>
    </tr>
    <tr>
      <td><sub>o</sub></td>
      <td>L'ordre partiel sur les éléments de O</td>
      <td>636</td>
    </tr>
    <tr>
      <td>H<sub>a</sub></td>
      <td>L'itération du saut sur le code d'ordinal a</td>
      <td>637</td>
    </tr>
    <tr>
      <td>n</td>
      <td>L'ordinal fini n</td>
      <td>639</td>
    </tr>
    <tr>
      <td>α &lt; β</td>
      <td>L'ordinal α est plus petit que l'ordinal β</td>
      <td>640</td>
    </tr>
    <tr>
      <td>succ(α)</td>
      <td>Le successeur de l'ordinal α</td>
      <td>643</td>
    </tr>
    <tr>
      <td>sup<sub>i∈I</sub> α<sub>i</sub></td>
      <td>Le supremum des ordinaux (α<sub>i</sub>)<sub>i∈I</sub></td>
      <td>643</td>
    </tr>
    <tr>
      <td>Ord</td>
      <td>La classe des ordinaux</td>
      <td>643</td>
    </tr>
    <tr>
      <td>|<|</td>
      <td>L'ordinal isomorphe au bon ordre &lt;</td>
      <td>646</td>
    </tr>
    <tr>
      <td>Σ<sub>α</sub><sup>0</sup> (classe)</td>
      <td>Classe borélienne Σ<sub>α</sub><sup>0</sup></td>
      <td>647</td>
    </tr>
    <tr>
      <td>Π<sub>α</sub><sup>0</sup> (classe)</td>
      <td>Classe borélienne Π<sub>α</sub><sup>0</sup></td>
      <td>647</td>
    </tr>
    <tr>
      <td>ω<sub>1</sub></td>
      <td>Le plus petit ordinal indénombrable</td>
      <td>654</td>
    </tr>
    <tr>
      <td>ω<sub>n</sub></td>
      <td>Le plus petit ordinal non subpotent à ω<sub>n−1</sub></td>
      <td>657</td>
    </tr>
    <tr>
      <td>O<sub>&lt;α</sub></td>
      <td>L'ensemble des codes d'ordinaux inférieurs à α</td>
      <td>658</td>
    </tr>
    <tr>
      <td>O<sub>=α</sub></td>
      <td>L'ensemble des codes de l'ordinal α</td>
      <td>658</td>
    </tr>
    <tr>
      <td>ω<sub>1</sub><sup>ck</sup></td>
      <td>Le plus petit ordinal non-calculable</td>
      <td>658</td>
    </tr>
    <tr>
      <td>T|<sub>σ</sub></td>
      <td>L'arbre des nœuds de T comparables avec σ</td>
      <td>662</td>
    </tr>
    <tr>
      <td>T|<sub>σ</sub></td>
      <td>L'arbre T|<sub>σ</sub> mais en « prenant σ comme racine »</td>
      <td>662</td>
    </tr>
  </tbody>
</table>
<table>
  <tbody>
    <tr>
      <td>|T|</td>
      <td>L'ordinal codé par l'arbre bien fondé T</td>
      <td>662</td>
    </tr>
    <tr>
      <td>T</td>
      <td>L'ensemble des codes c. e. d'arbres bien fondés</td>
      <td>663</td>
    </tr>
    <tr>
      <td>T<sub>&lt;&alpha;</sub></td>
      <td>L'ensemble des codes c. e. d'arbres bien fondés tels que |T| &lt; &alpha;</td>
      <td>663</td>
    </tr>
    <tr>
      <td>T<sub>=&alpha;</sub></td>
      <td>L'ensemble des codes c. e. d'arbres bien fondés tels que |T| = &alpha;</td>
      <td>663</td>
    </tr>
    <tr>
      <td>&lt;KB</td>
      <td>L'ordre de Kleene-Brouwer</td>
      <td>663</td>
    </tr>
    <tr>
      <td>O<sup>X</sup></td>
      <td>L'ensemble O de Kleene relativisé à X</td>
      <td>664</td>
    </tr>
    <tr>
      <td>T<sup>X</sup></td>
      <td>L'ensemble T relativisé à X</td>
      <td>665</td>
    </tr>
    <tr>
      <td>&omega;<sup>X</sup><sub>1</sub></td>
      <td>Le plus petit ordinal non X-calculable</td>
      <td>665</td>
    </tr>
    <tr>
      <td>&Sigma;<sup>0</sup><sub>&alpha;</sub> (ens.)</td>
      <td>Ensemble &Sigma;<sup>0</sup><sub>&alpha;</sub></td>
      <td>667</td>
    </tr>
    <tr>
      <td>&Pi;<sup>0</sup><sub>&alpha;</sub> (ens.)</td>
      <td>Ensemble &Pi;<sup>0</sup><sub>&alpha;</sub></td>
      <td>667</td>
    </tr>
    <tr>
      <td>&Delta;<sup>0</sup><sub>&alpha;</sub> (ens.)</td>
      <td>Ensemble &Delta;<sup>0</sup><sub>&alpha;</sub></td>
      <td>667</td>
    </tr>
    <tr>
      <td>&emptyset;<sup>(&alpha;)</sup></td>
      <td>L'itération &alpha; du saut Turing</td>
      <td>675</td>
    </tr>
    <tr>
      <td>H<sup>X</sup><sub>a</sub></td>
      <td>L'itération du saut de X sur le code d'ordinal a</td>
      <td>677</td>
    </tr>
    <tr>
      <td>&Sigma;<sup>0</sup><sub>&alpha;</sub> (classe)</td>
      <td>Classe borélienne effective &Sigma;<sup>0</sup><sub>&alpha;</sub></td>
      <td>678</td>
    </tr>
    <tr>
      <td>&Pi;<sup>0</sup><sub>&alpha;</sub> (classe)</td>
      <td>Classe borélienne effective &Pi;<sup>0</sup><sub>&alpha;</sub></td>
      <td>678</td>
    </tr>
    <tr>
      <td>&Delta;<sup>0</sup><sub>&alpha;</sub> (classe)</td>
      <td>Classe borélienne effective &Delta;<sup>0</sup><sub>&alpha;</sub></td>
      <td>678</td>
    </tr>
    <tr>
      <td>&Sigma;<sup>1</sup><sub>1</sub> (ens.)</td>
      <td>Ensemble &Sigma;<sup>1</sup><sub>1</sub></td>
      <td>688</td>
    </tr>
    <tr>
      <td>&Pi;<sup>1</sup><sub>1</sub> (ens.)</td>
      <td>Ensemble &Pi;<sup>1</sup><sub>1</sub></td>
      <td>688</td>
    </tr>
    <tr>
      <td>&Delta;<sup>1</sup><sub>1</sub> (ens.)</td>
      <td>Ensemble &Delta;<sup>1</sup><sub>1</sub></td>
      <td>688</td>
    </tr>
    <tr>
      <td>&Sigma;<sup>1</sup><sub>1</sub> (classe)</td>
      <td>Classe analytique effective</td>
      <td>688</td>
    </tr>
    <tr>
      <td>&Pi;<sup>1</sup><sub>1</sub> (classe)</td>
      <td>Classe co-analytique effective</td>
      <td>688</td>
    </tr>
    <tr>
      <td>&Delta;<sup>1</sup><sub>1</sub> (classe)</td>
      <td>Classe &Delta;<sup>1</sup><sub>1</sub> effective</td>
      <td>688</td>
    </tr>
    <tr>
      <td>&Sigma;<sub>&sim;</sub><sup>1</sup> (classe)</td>
      <td>Classe analytique</td>
      <td>692</td>
    </tr>
    <tr>
      <td>&Pi;<sub>&sim;</sub><sup>1</sup> (classe)</td>
      <td>Classe co-analytique</td>
      <td>692</td>
    </tr>
    <tr>
      <td>&Vcirc;</td>
      <td>Fonction &lt;&lt; ou &gt;&gt; sur les arbres</td>
      <td>704</td>
    </tr>
    <tr>
      <td>&wcirc;</td>
      <td>Fonction &lt;&lt; et &gt;&gt; sur les arbres</td>
      <td>704</td>
    </tr>
    <tr>
      <td>&le;<sub>h</sub></td>
      <td>Réduction hyperarithmétique</td>
      <td>709</td>
    </tr>
    <tr>
      <td>HYP</td>
      <td>La classe des ensembles hyperarithmétiques</td>
      <td>720</td>
    </tr>
    <tr>
      <td>S</td>
      <td>La classe des ensembles qui calculent &omega;<sup>ck</sup><sub>1</sub></td>
      <td>721</td>
    </tr>
    <tr>
      <td>X &le;T &emptyset;<sup>(&alpha;)</sup></td>
      <td>&forall;Y (&alpha; &lt; &omega;<sup>Y</sup><sub>1</sub> &rarr; X &le;T Y<sup>(&alpha;)</sup>)</td>
      <td>722</td>
    </tr>
    <tr>
      <td>C</td>
      <td>La plus grande classe &Pi;<sup>1</sup><sub>1</sub> qui ne contient pas de fermé parfait</td>
      <td>722</td>
    </tr>
    <tr>
      <td>J<sub>a</sub></td>
      <td>L'hypersaut itéré sur le code a</td>
      <td>728</td>
    </tr>
    <tr>
      <td>&omega;<sup>ck</sup><sub>&alpha;</sub></td>
      <td>Le &alpha;-ième plus petit ordinal non X-calculable pour un certain X</td>
      <td>729</td>
    </tr>
    <tr>
      <td>WO(&lt;, A)</td>
      <td>L'ordre &lt; est bien fondé sur A</td>
      <td>733</td>
    </tr>
    <tr>
      <td>L<sub>O</sub>(a, X)</td>
      <td>a est un code d'ordre linéaire avec oracle X</td>
      <td>736</td>
    </tr>
    <tr>
      <td>W<sub>O</sub>(a, X)</td>
      <td>a est un code d'ordre bien fondé avec oracle X</td>
      <td>736</td>
    </tr>
    <tr>
      <td>PBO<sup>X</sup></td>
      <td>L'ensemble des X-pseudos bons ordres</td>
      <td>738</td>
    </tr>
    <tr>
      <td>SUPP<sub>X</sub></td>
      <td>L'ensemble des supports de saut</td>
      <td>739</td>
    </tr>
  </tbody>
</table>
# Index

1-aléatoire (ensemble), 436

1-générique (ensemble), 249

2-aléatoire (ensemble), 436

$\Pi_1^1-CA_0$, 516

$\beta$-modèle, 745

$\lambda$-calcul, 102

$\lambda$-fonction, 102

$\omega$-extension, 544, 547

$\omega$-réduction, 558

$\omega$-sous-structure, 544, 547

$\omega$-structure, 490

$n$-aléatoire (ensemble), 436

$n$-générique (ensemble), 253

$ACA_0^0$, 513

$ACA_0^1$, 514

$ACA_0$, 501

Ackermann
fonction, 121

addition
ordinale, 647

aléatoire
Chaitin/Levin, 382
différence, 439
Martin-Löf, 416
Martin-Löf relativisé, 432
Oberwolfach, 464

analytique
classe, 686, 690
ensemble, 686
hiérarchie, 516

anti-chaîne
degré Turing, 349

approchable
par la gauche, 383
par le dessus, 372

approximation
$\Delta_0^0$, 63
c. e., 46
par la gauche, 383
par le dessus, 372

arbre, 154, 179
bien fondé, 660
binaire, 154
branchement fini, 180
c. e., 339
calculable, 156
calculatoirement borné, 182
chemin, 154, 179
f-arbre, 140
feuille, 154
hauteur, 660
mesure positive, 508
morphisme, 701
nœud, 154
parfait, 164
stratégies, 329

arithmétique
formule, 197, 483
hiérarchie, 81
langage, 195
Peano, 203
primitive récursive, 554
Robinson, 203, 522
second ordre, 223, 232, 481
terme, 196
arrêt, 47
Arslanov
critère de complétude, 136

astuce de Posner, 324
atomique
formule, 197

$ATR_0$, 516

axiome
choix, 228, 229, 652, 710, 724
choix dénombrable, 653
collection, 528
compréhension, 225, 484, 496
compréhension bornée, 540
extensionnalité, 224
fondation, 227
induction, 485, 497, 523, 526, 528, 533
induction ordonnée, 532

infini, 225

minimum, 531

remplacement, 226

Baire

catégorie, 238, 240

espace, 179

fermé, 180

ouvert, 180

propriété, 263

base

base calculatoirement dominée,
170

base d'évitement de cône, 171

base d'évitement de cône hyper-
arithmétique, 714

base hyperlow, 711

base low, 169

classes $\Pi_1^0$ parfaites, 172

classe $\Pi_1^0$, 168

classe $\Sigma_1^1$, 711

pour l'aléatoire, 446

bien fondé

arbre, 660

ordre, 642

bijection, 15

Cantor, 119

blessure

finie, 312

infinie, 323

bon ordre, 515, 642

pseudo, 736

borne

inférieure, 336

supérieure, 336

Borélien

classe, 645

hiérarchie, 403, 645

hiérarchie effective, 403, 676

borélien

classe, 402

hiérarchie, 402

branchement fini (arbre), 180

c. e.

approximation, 46

arbre, 339, 661

degré, 136, 310

ensemble, 45

opérateur, 302

calculable

à la limite, 61

ensemble, 36

fonction, 32, 36

ordinal, 657

par programme goto, 112

par programme structuré, 112

relativement à X, 53

uniformément, 63

calculatoirement

borné (arbre), 182

dominé, 140

énumérable, 45, 136

indépendant, 347

réductible, 563

réductible (fortement), 571

vrai, 565

Cantor

bijection, 19, 119

compact, 160

cylindre, 158

ensemble triadique, 26

espace, 25, 158

fermé, 158

fonction continue, 162

forcing, 276

ouvert, 158

Cantor-Bernstein, 17

cappable

degré, 332

capture

test de différence, 439

test de Martin-Löf, 416

test de Solovay, 417

castor affairé, 373

catégorie

Baire, 238, 240

Cauchy

suite, 493
Chaitin

Ω (nombre), 382

théorème de Chaitin, 377

théorème KC, 386

chaîne

binaire, 51

compatible, 51

degré Turing, 349

extension, 51

incompatible, 51

chemin

arbre (espace de Baire), 179

arbre binaire, 154

f-arbre, 141

choix

axiome, 228, 229, 652, 710, 724

dénombrable, 653

Church-Turing (thèse), 104

classe, 153

C, 720

Δ₀, 403

Δ₁, 686

Π₀, 165

Π₁, 400

Π₀, 403

Π₁, 686

S, 719

Σ₀, 165

Σ₀, 403

Σ₁, 686

Δ₀, 402

Π₀, 402

Π₁, 690

Σ₀, 402

Σ₁, 690

HYP, 718

à oracle, 433

analytique, 690

analytique effective, 686

Borélienne, 645

co-analytique, 690

co-analytique effective, 686

co-maigre, 240

compacte, 160

dense, 239

fermée, 158

intérieur, 239

large, 602

maigre, 240

mesurable, 408, 695

ouverte, 158

parfaite, 164, 241

théorie des ensembles, 642

universelle, 177

clos

formule, 197

terme, 196

Club des cinq, 478, 517

clôture

formule, 483

universelle, 484

co-analytique

classe, 690

ensemble, 686

co-maigre (classe), 240

codage

acceptable, 39

listes, 123, 215, 536

programmes, 35

code

Δ₀ (ensemble), 95

Δ₀ (classe), 676

Δ₀ (ensemble), 665

Δ₀ (ensemble), 96

Π₀ (classe), 676

Π₀ (ensemble), 665

Σ₀ (ensemble), 95

Σ₀ (classe), 676

Σ₀ (ensemble), 665

Σ₀ (ensemble), 96

canonique d'un ensemble, 97,
131, 539

classe Π₁, 165

classe Σ₁, 165

de lowness, 96

de programme, 35

cohérence

Coh(T), 220

théorie, 174, 204

cohésif

ensemble, 610

principe, 610
collection

schéma, 528

coloriage (fonction), 576

compacité, 160

compact

classe, 160

question de forcing, 294

compatibilité

chaîne, 51

condition, 274

complet

théorie, 174, 209

Turing, 61

complexité

Kolmogorov, 370, 371

pleine, 371, 380

sans préfixe, 380

complétion

arithmétique de Peano, 174

complétude

théorème de Gödel, 209

compréhension

$\Delta_1^0$, 496

bornée, 540

schéma, 484, 732

condition

compatible, 274

Dzhafarov-Jockusch, 596

forcing, 273

incompatible, 274

Jockusch–Soare, 274

Mathias, 595

Sacks, 274

conjecture

Martin, 304

conservation

extension, 543

théorème, 543

continu

fonction, 162, 494

hypothèse, 229, 654, 716, 726

contrat, 66, 234

coupure, 531

couverture minimale, 341

couverture minimale forte, 342

coût

fonction, 461

fonction adaptative, 461

cylindre, 158

[W], 158

$[\sigma]$, 69, 158

problème, 572

cône (degré Turing), 171, 302

degré

c. e., 136, 310

calculatoirement dominé, 140

calculatoirement énumérable, 136

cappable, 332

complet/incomplet, 61

couverture minimale, 341

couverture minimale forte, 342

DNC, 132

$DNC_2$, 135, 175

$DNC_f$, 135

high, 74

hyperimmune, 138

low, 73

many-one, 89

Medvedev, 306

minimal, 336

Muchnik, 306

noncappable, 332

PA, 174

spectre, 176

truth-table, 144

Turing, 57

demi-treillis, 343

inférieur, 343

supérieur, 343

dense

classe, 239

ensemble, 236, 275

sous $\sigma$, 259

sous c, 276

densité

inférieure, 442

inférieure positive, 443

supérieure, 442

supérieure positive, 443

diagonalement non calculable, 132
diagramme de programmation, 109

différence

aléatoire, 439

test, 439

distributif

treillis, 361

DNC

degré, 132

fonction, 132

DNC₂, 135, 175

DNCᵢ, 135

domination, 138

définissable (dans une structure), 545

dénombrable

ensemble, 18

ordinal, 651

échappante

fonction, 246

effectivement immune, 131

énoncé, 197

ADS, 558

COH, 610

cRTₖⁿ, 579

J, 559

KL, 559

LLPO, 567

LPO, 567

RTₖⁿ, 577

WKL, 505

WWKL, 509

ensemble

1-aléatoire, 436

1-générique, 249

2-aléatoire, 436

K-trivial, 389

X-c. e., 53

X-calculable, 53

X-calculatoirement énumérable,

53

Δ₁ⁿ, 87

Δ₀ⁿ, 83

Δ₀ⁿ(X), 89

Δ₁ⁿ, 686

Πⁿ, 82

Πⁿ-complet, 91

Πⁿ(X), 88

Πⁿ(X)-complet, 91

Π₁ⁿ, 686

Σ₁ⁿ, 87

Σ₀ⁿ, 82

Σⁿ-complet, 91

Σ₀ⁿ(X), 88

Σⁿ(X)-complet, 91

Σ₁ⁿ, 686

n-aléatoire, 436

n-générique, 253

aléatoire de Chaitin/Levin, 382

analytique effectif, 686

bien ordonné, 515, 642

borné de requêtes, 385

c. e., 45

c. e. maximal, 49, 150

calculable, 36

calculatoirement dominé, 140

calculatoirement indépendant, 347

calculatoirement inséparable, 49

calculatoirement énumérable, 45

co-analytique effectif, 686

codé, 539

cohésif, 610

complet/incomplet, 61

d'entiers, 25, 26

dense, 236, 275

dense sous σ, 259

densité positive, 443

DNC₂, 175

définissable, 545

dénombrable, 18

effectivement immune, 131

équipotent, 15

faiblement 1-générique, 243, 245

faiblement n-générique, 245

fortement MLR, 427

générique, 236

high, 74

homogène, 576

hyperarithmétique, 665

hyperimmune, 131

immune, 130

indénombrable, 18

infini, 539
low, 73

low généralisé, 251

low<sub>n</sub> généralisé, 271

Martin-Löf aléatoire, 416

minimal, 410

MLR, 416, 419

promptement simple, 332

pré-homogène, 584

r.e., 45

récursif, 37

récursivement énumérable, 45

sans préfixe, 379

sans préfixe minimal, 410

simple, 389

sous-jacent, 205

subpotent, 16

sémantique de codes, 93

transitif, 638

triadique de Cantor, 26

ensemble complet

Π<sup>0</sup><sub>α</sub>, 671

Π<sup>0</sup><sub>n</sub>, 91

Π<sup>0</sup><sub>n</sub>(X), 91

Π<sup>1</sup><sub>1</sub>, 693

Σ<sup>0</sup><sub>α</sub>, 669, 671, 672

Σ<sup>0</sup><sub>n</sub>, 91

Σ<sup>0</sup><sub>n</sub>(X), 91

Σ<sup>1</sup><sub>1</sub>, 743

entier

non standard, 222, 488

standard, 488

Entscheidungsproblem, 99

équipotence, 15

équivalence

many-one, 89

truth-table, 144

Turing, 57

espace

Baire, 179

Cantor, 25, 158

étape de calcul, 36

évitement (chaînes), 249

exponentielle

ordinale, 647

extensible

nœud, 156

extension

ω-extension, 544, 547

chaîne, 51

compatible, 274

conservative, 543

consistante, 349

finie (méthode), 66

forcing, 273

f-arbre, 140, 281

Γ-scindé, 337

Γ-uni, 337

chemin, 141

sous-f-arbre, 141

uniforme, 337

faiblement

1-générique, 243

1-générique relativisé, 245

n-générique, 245

fermé

Baire, 180

classe, 158

effectif, 165

feuille, 154

filtre, 274

générique, 275

maximal, 274

suffisamment générique, 276

fonction

β de Gödel, 215

succ (entiers), 101, 117

c<sup>n</sup><sub>i</sub>, 101, 117

p<sup>n</sup><sub>i</sub>, 101, 117

Ackermann, 121

bijective, 15

calculable, 32, 36

continue, 162, 494

de calcul, 65

de coût, 461

de coût adaptative, 461

diagonalement non calculable,
132

DNC, 132

DNC<sub>2</sub>, 135, 175

DNC<sub>f</sub>, 135

domination, 138
échappante, 246

générale récursive, 100

hyperimmune, 138

injective, 15

libre de point fixe, 133

modulus, 675

primitive récursive, 100, 554

primitive récursive relativisée,
522

prouvablement totale, 520

représentée, 215

récursive, 100, 107

Solovay, 470

stable, 61

surjective, 15

fonctionnelle, 52

formule, 520

Turing, 52

force

syntaxiquement, 260, 278

sémantiquement, 260, 264, 277

forcing

Cohen, 231

condition, 273

de Cantor, 276

Dzhafarov-Jockusch, 596

extension, 273

f-arbre, 140

Jockusch-Soare, 279

Mathias, 595

question, 288, 290, 292

relation, 260, 277, 278

relation $\parallel$, 260, 264

relation $\parallel^*$, 235, 260

Sacks, 281

syntaxique, 278

sémantique, 260, 264, 277

forme

normale, 689

normale relativisée, 690

prénexe, 202

formule

$\Delta_0$, 213

$\mathbb{Z}_2$, 483

$\Pi_n^0$, 233

$\Pi_n$, 213

$\Sigma_n^0$, 233

$\Sigma_n$, 213

à paramètres, 490

arithmétique, 197, 483

arithmétique du second ordre,
483

atomique, 197

close, 197, 483

fonctionnelle, 520

forme prénexe, 202

littéral, 197

paramétrée, 206

prouvablement totale, 520

second ordre, 232

vraie, 206

fortement MLR, 427

fusionnable (Π-fusionnable), 295

Gödel

théorème d'incomplétude, 218,
220

goto (programme), 110

général récursif

fonction, 100

prédicat, 118

générique

ensemble, 236

filtre, 275

suffisamment, 237

Gödel

fonction $\beta$, 215

théorème de complétude, 209

hauteur

arbre, 660

Henkin

structure, 486

témoin, 210, 211

high, 74

Hilbert

programme, 553

hiérarchie

$\omega_\alpha^{ck}$ (ordinaux), 727

analytique, 516

arithmétique, 81

arithmétique relativisée, 88
Borélienne, 645

borélienne, 402

Borélienne effective, 403, 676

hyperarithmétique, 665

hypersaut, 726

Kleene, 665

homogène

ensemble, 576

hyperarithmétique

ensemble, 665

hiérarchie, 665

réduction, 707

hyperimmune

degré, 138

ensemble, 131, 138

fonction, 138

hyperlow, 711

hypersaut, 708, 726

hiérarchie, 726

hypothèse

du continu, 229, 654, 716, 726

idéal

de saut, 503

de Scott, 505

Turing, 498

immune, 130

imprédicativité, 192, 516

incompatibilité

chaîne, 51

induction

$\Delta_n^0$, 533

$\Pi_n^0$, 528

$\Sigma_1^0$, 497

$\Sigma_n^0$, 528

ordonnée, 532

schéma, 485

transfinie, 649

indénombrable

ensemble, 18

ordinal, 652

infini

ensemble, 539

injection, 15

instance

problème, 557

universelle, 614

intersection décroissante, 159

intérieur (classe), 239

invariant

opérateur, 302

uniformément, 302

isomorphisme

ordre, 643

itération transfinie

ATR₀, 515, 732

hypersaut, 726

saut Turing, 635

saut Turing relativisé, 675

jeu

Borélien, 226

de réduction, 569

détermination de Martin, 226

jointure

effective, 59, 253

treillis, 343

K-trivial, 389

König

lemme, 180

lemme faible, 155

KC (théorème), 386

Kleene

$O$, 634

$O$ relativisé, 663

hiérarchie, 665

ordinal, 656

point fixe, 41

Kleene-Brouwer

ordre, 662

Kolmogorov

complexité, 370, 371

langage

$\mathcal{L}_{Z_2}$, 482

arithmétique, 195

arithmétique du second ordre, 482

premier ordre, 196

large (classe), 602

Lebesgue

lemme de densité, 420

mesure, 399, 407

théorème de densité, 442
lemme

densité de Lebesgue, 420

déduction, 200, 210

Gauss, 535

König, 180

König faible, 155

limite de Shoenfield, 61

remplissage, 40

libre

variable, 197

libre de point fixe

fonction, 133

littéral

formule, 197

lié

variable, 197

low

ensemble, 73

généralisé, 251

hyperlow, 711

pour l'aléatoire de Martin-Löf, 435

pour-K, 445

low, généralisé

ensemble, 271

low-pour-K, 445

lowness, 445

machine, 370

à oracle, 54, 433

à registre, 107

de Turing, 103

sans préfixe, 379

universelle, 370

machine de Turing

universelle, 38, 127

maigre (classe), 240

majorant, 336

many-one

degré, 89

réduction, 89

Martin

conjecture, 304

théorème de détermination, 226

Martin-Löf

aléatoire, 416

aléatoire relativisé, 432

test, 416

test relativisé, 432

masse (problème), 306

Mathias

condition, 595

forcing, 595

maximalité

filtre, 274

Medvedev

degré, 306

réduction, 306

mesurable

classe, 408, 695

mesure

arbre, 508

Lebesgue, 399, 407

positive, 508

relative, 419

minimal

degré, 336

paire, 323

minimum

schéma, 531

minorant, 336

MLR, 419

approchable par la gauche, 441

fortement, 427

modulus, 65, 675

modèle

β-modèle, 745

non standard, 222, 488

standard, 488

structure, 207

morphisme

arbre, 701

Muchnik

degré, 306

réduction, 306

multiplication

ordinale, 647

méthode

de priorité, 312

des extensions finies, 66

permission, 311
non standard

entier, 222, 488

modèle, 222, 488

ordinal, 739

noncappable

degré, 332

normal

forme, 689

nœud, 154

branchant, 154, 179

extensible, 156

feuille, 154

successeur, 154

Oberwolfach

aléatoire, 464

test, 464

opérateur

c. e., 302

invariant, 302

uniformément invariant, 302

oracle, 52

ordinal

calculable, 657

calculable relativisé, 663

Church-Kleene, 656

constructif, 656

constructif relativisé, 663

de von Neumann, 638

dénombrable, 651

fini, 638

induction transfinie, 649

indénombrable, 652

Kleene, 656

limite, 637

non standard, 739

récursion transfinie, 650

récursivement inaccessible, 729

successeur, 637

ordre

bien fondé, 642

Kleene-Brouwer, 662

ordre partiel

plongement, 347

ouvert

Baire, 180

classe, 158

effectif, 165

PA

degré, 174

théorie, 203

paire

exacte, 345

minimale, 323

parallélisation

problème, 568

paramètre, 483

formule, 206, 490

parfait

arbre, 164

classe, 164

partie du premier ordre, 544

passe

test de différence, 439

test de Martin-Löf, 416

test de Solovay, 417

Peano

arithmétique, 203

permission

méthode, 311

plongement

ordre partiel, 347

point isolé, 164

Posner

astuce, 324

Post

problème, 297

problème de correspondance, 298

premier ordre

partie, 544

terme, 482

primitif récursif

fonction, 100

fonction relativisée, 522

prédicat, 118

principe

de cohésion, 610

des tiroirs infini, 577

limité d'omniscience, 567

très limité d'omniscience, 567

problème, 557

$\Pi_2^1$, 557

calculatoirement vrai, 565

correspondance de Post, 298
cylindre, 572
de l'arrêt, 47
de masse, 306
Hilbert, 299
parallélisation, 568
pavage du plan, 298
Post, 297
produit, 572
satisfaction, 558
uniformément vrai, 566

produit
problème, 572

programme
goto, 110
Hilbert, 553
propre, 115
structuré, 108
universel, 38, 127

promptement simple, 332

propriété
Borel-Lebesgue, 160
de Baire, 263
de faiblesse, 66, 560
de force, 66
de l'usage, 56
Heine-Borel, 160
syntaxique, 93
sémantique, 93

prouvablement
calculable, 520
total, 520

pré-ordre, 57

pré-homogène
ensemble, 584

prédicat, 37
Σ₀, 82
général récursif, 118
primitif récursif, 118

prénexe (forme), 202

préservation
k cônes, 562
forte, 616
forte d'un cône, 619
hiérarchie arithmétique, 292
propriété, 561

pseudo
bon ordre, 736

puissance du continu, 24

Q, 484

question
Π-fusionnable, 295
compacte, 294
forcing, 288, 290, 292
Sacks, 302

r.e.

ensemble, 45
RAM (machine), 107
RCA₀, 497
relation
forcing, 260, 277, 278
relativisation, 54
rencontre (chaîne), 236
réunion croissante, 159
Robinson
arithmétique, 203
récursion, 37
générale, 100
primitive, 100
transfinie, 515, 650, 732

récursivement
énumérable, 45
inaccessible, 729

réduction
ω-réduction, 558
calculatoire, 563
calculatoire forte, 571
forte de Weihrauch, 572
hyperarithmétique, 707
jeu, 569
many-one, 89
Medvedev, 306
Muchnik, 306
Solovay, 384
truth-table, 144
Turing, 57
Weihrauch, 565

Sacks
forcing, 281
stratégie de préservation, 323
théorème de densité, 360

sans préfixe
ensemble, 379
machine, 379
minimal, 410
satisfaction

approximation $\Delta_2^0$, 461
problème, 558

saut

hypersaut, 726
idéal, 503
itérations transfinies, 635
itéré relativisé, 675
support, 737
Turing, 60

schéma

$BC\Sigma_n^0/BC\Pi_n^0$, 541
$B\Sigma_n^0/B\Pi_n^0$, 528
$|\Delta_0^0|, 526$
$|\Delta_n^0|, 533$
$|\Sigma_n^0/\Pi_n^0|, 528$
$l\_ouvert, 523$
$L\Sigma_n^0/L\Pi_n^0$, 531
collection, 528
compréhension, 484, 732
compréhension bornée, 540
compréhension $\Delta_1^0$, 496
induction, 485
induction ordonnée, 532
induction $\Sigma_1^0$, 497
minimum, 531
récursion transfinie, 515, 732

scindé (f-arbre), 337

scission (Γ-scission), 337

Scott

idéal, 505

second ordre

arithmétique, 223, 232, 481
formule, 232, 483
terme, 482

segment

final, 350
initial, 350

simple

ensemble, 389

singleton

$\Pi_1^0$, 626
$\Pi_2^0$, 626
$\Pi_1^1$, 726

SMN (théorème), 39

Solovay

fonction, 470
réduction, 384
test, 417

solution

problème, 557

sous-f-arbre, 141

spectre (degré), 176

stable (fonction), 61

standard

$\omega$, 488, 519
entier, 488
modèle, 488
sémantique, 487

stratégie

arbre, 329
préservation de Sacks, 323

structure

$\omega$-structure, 490
arithmétique, 205
ensemble sous-jacent, 205
Henkin, 486
modèle, 207
pleine, 487

subpotence, 16

successeur

arbre, 154
fonction, 101, 117

suffisamment générique, 237, 276

suite

Catalan, 620
Cauchy, 493
finie de bits, 51
infinie de bits, 25
uniformément calculable, 46

support

de saut, 737

sur un cône, 302

surjection, 15

système

axiomatique (voir théorie), 202
de déduction, 198

sémantique

modèles pleins, 487
standard, 487
tableau c. e., 131

temps de calcul, 36

terme

arithmétique, 196

clos, 196

premier ordre, 482

second ordre, 482

test

différence, 439

Martin-Löf, 416

Martin-Löf relativisé, 432

Oberwolfach, 464

Solovay, 417

thèse

Church-Turing, 104

théorie, 202

ACA⁸, 513

ACA⁰, 514

ACA₀, 501

ATR₀, 516, 732

BCΣ₀/BCΠ₀, 541

BΣ₀/ΒΠ₀, 528

ΙΔ⁰, 526

ΙΔⁿ, 533

ΙΣⁿ/ΙΠⁿ, 528

l'ouvert, 523

LΣ⁰/LΠ⁰, 531

Π¹-CA₀, 516, 733

PRA, 554

Π¹ Comprehension Axiom, 516

RCA₀, 497

Q, 203, 484, 522

Σ₁-PA, 546

WKL₀, 505

WWKL₀, 509

Z₂, 485

Arithmetical Comprehension Axiom,
501

Arithmetical Transfinite Recursion, 516

arithmétique du second ordre,
485

catégorique, 487

cohérente, 174, 204

complète, 174, 209

PA, 203

Recursive Comprehension Axiom,
497

Weak König's Lemma, 505

Weak König's Lemma, 509

Zermelo, 224

ZF, 229

ZFC, 223, 229

théorème

Arslanov, 136

base, 168

base calculatoirement dominée,
170

base d'évitement de cône, 171

base de Gandy, 711

base de Kreisel, 714

base low, 169

Bolzano-Weierstrass, 503

Borel-Lebesgue, 507

Cantor-Bernstein, 17

Chaitin, 377

cohérence, 208

complétude de Gödel, 209

de codage, 388

densité de Lebesgue, 442

densité de Sacks, 360

domination de Martin, 147

détermination de Martin, 226

Friedberg-Muchnik, 312

Hindman, 514

incomplétude de Gödel, 218, 220

incomplétude de Gödel-Rosser,
219

inversion de saut de Friedberg,
256

KC, 386

Kleene, 41

Kučera/Gács, 422

Löwenheim-Skolem, 543

Liu, 601

point fixe, 41

Posner-Robinson, 256

Post, 92

Ramsey, 576

Ramsey fini, 578

restes chinois, 215

Rice, 44, 94
SMN, 39

Solovay, 390

valeurs intermédiaires, 500

transitif

ensemble, 638

treillis, 343

distributif, 361

inférieur, 343

jointure, 343

supérieur, 343

truth-table

degré, 144

réduction, 144

Turing

complet, 61

degré, 57

équivalence, 57

idéal, 498

machine, 103

réduction, 57

saut, 60

thèse, 104

témoin

Henkin, 210, 211

réduction Weihrauch, 565

uniformité, 46

uniformément

$\Sigma_n^0$, 85

calculable, 63

vrai, 566

universel

classe, 177

instance, 614

machine, 370

usage, 56

variable

libre, 197

liée, 197

vérité

formule, 206

Weihrauch

réduction, 565

réduction forte, 572

WKL₀, 505

WWKL₀, 509

Z₂, 485

ZF, 229

ZFC, 223, 229
<figure><img src="image_186.png" /></figure>
<figure><img src="image_187.png" /></figure>
Chez le même éditeur,
la collection *Im-et-Ker*

101. — Bernard Randé & Franck Taïeb. *Les clefs pour l'X*

102. — Roger Mansuy & Bernard Randé. *Les clefs pour l'X* (2)

103. — Françoise Fontanez & Bernard Randé. *Les clefs pour les Mines*

104. — Hervé Gianella, Romain Krust, Franck Taïeb & Nicolas Tosel. *Problèmes clefs pour mathématiques supérieures*

105. — Roger Mansuy & Bernard Randé. *Les clefs pour la PSI et la PSI*

106. — Éric Kouris. *Une année de colles en Math Sup MPSI*

107. — Philippe Gallic & Jean-Louis Grappin. *Les clefs pour les Hautes Études Commerciales*

108. — Jean-Denis Eiden. *Le jardin d'Eiden. Une année de colles en MP*

109. — Maxime Zavidovique. *Un Max de Maths*

110. — Jérôme Gärtner. *Mathématiques pour la voie économique et commerciale*

111. — Thierry Meyre. *Probabilités. Cours et exercices corrigés* (1)

112. — Bernard Randé, Alix Deleporte-Dumont, Quentin Guignard. *Les clefs pour l'écrit MP de mathématiques (session 2015)*

113. — Quentin Guignard et Bernard Randé. *Les clefs pour l'oral MP de mathématiques, ENS-X (session 2015)*

114. — Clément de Seguins Pazzis. *Les clefs pour l'écrit de mathématiques des concours 2016, filière MP*

115. — Ismael Belghiti, Roger Mansuy et Jill-Jènn Vie. *Les clefs pour l'Info*

116. — Bernard Randé. *Les nouvelles clefs pour les Mines-CCP (tome I). Oral MP, 2015-16*

117. — Georges Skandalis. *Agrégation interne. Algèbre générale, algèbre linéaire et un peu de géométrie*. Nouvelle édition revue et corrigée

118. — Jean-Louis Roque. *Florilège d'exercices de l'oral de HEC*

119. — Clément de Seguins Pazzis. *Les clefs pour l'écrit MP 2017 – Mathématiques*

120. — L. Cozar, N. Jousse, B. Randé, L. Sartre. *Les clefs pour l'écrit de mathématiques et d'informatique*. *Filière PSI 2015-2016*
121. — Georges Skandalis. *Agrégation interne. Analyse*

122. — Thomas Blomme, Louise Gassot, Quentin Guignard, Bernard Randé. *Les clefs pour l'oral MP de mathématiques, ENS-X (2016-2017)*

123. — Éric Kouris. *Une année de colles en MPSI (nouvelle édition)*

124. — Thierry Meyre. *Probabilités. Cours et exercices corrigés (2)*

125. — Philippe Caldero et Marie Peronnier. *Carnet de voyage en Algébrie*

126. — Bernard Randé. *Les clefs pour l'oral MP, mathématiques, ENS-X (session 2018)*

127. — Mohamed Amine Ben Boubakeur. *L'indispensable en analyse pour les Spé MP et MP*. *Concours Mines-Centrale-X*
Chez le même éditeur,
la collection *Mathématiques en devenir*

101. — Jacques Faraut. *Analyse sur les groupes de Lie – Une introduction.*
Nouvelle édition revue et augmentée

102. — Patrice Tauvel. *Corps commutatifs et théorie de Galois*. Troisième édition revue et bonifiée

103. — Jean Saint Raymond. *Topologie, calcul diff. et variable complexe*

104. — Clément de Seguins Pazzis. *Invitation aux formes quadratiques*

105. — Bruno Ingrao. *Coniques projectives, affines et métriques*

106. — Wolfgang Bertram. *Calcul différentiel topologique élémentaire*

107. — Henri Lombardi & Claude Quitté. *Algèbre commutative. Méthodes constructives*. Nouvelle édition revue et augmentée

108. — Frédéric Testard. *Analyse mathématique. La maîtrise de l'implicite*

109. — Grégory Berhuy. *Modules : théorie, pratique... et un peu d'arithmétique*. Nouvelle édition

110. — Bernard Candelpergher. *Théorie des probabilités. Une introduction élémentaire (Nouveau tirage bonifié)*

111. — Philippe Caldero et Jérôme Germoni. *Histoires hédonistes de groupes et de géométries. Tome premier*

112. — Gema-Maria Díaz-Toca, Henri Lombardi & Claude Quitté. *Modules sur les anneaux commutatifs*

113. — Philippe Caldero et Jérôme Germoni. *Histoires hédonistes de groupes et de géométries. Tome second – encores*

114. — Alain Debreil. *Groupes finis et treillis de leurs sous-groupes*

115. — François Rouvière. *Initiation à la géométrie de Riemann*

116. — Nikolaï Nikolski. *Matrices et opérateurs de Toeplitz*

117. — Philippe Caldero et Jérôme Germoni. *Nouvelles histoires hédonistes de groupes et de géométries. Tome premier (Nouveau tirage)*

118. — Martine et Hervé Queffélec. *Analyse complexe et applications*. Nouveau tirage, bonifié et corrigé

119. — Alain Debreil, Jean-Denis Eiden, Rached Mneimné et Tuong-Huy NGuyen. *Formes quadratiques et géométrie*

120. — Christian Leruste. *Topologie algébrique – Une introduction, et au-delà*
121. — Grégory Berhuy. Algèbre : le grand combat. Nouvelle édition

122. — Philippe Caldero et Jérôme Germoni. Nouvelles histoires hédonistes de groupes et de géométries. Tome second (Nouveau tirage)

123. — Charles-Michel Marle. Géométrie symplectique et géométrie de Poisson

124. — Pascal Boyer. Petit compagnon des nombres et de leurs applications

125 et 126. — Laurent Le Floch, Frédéric Testard. Probabilités 1 et 2 – Le hasard est la nécessité.

127. — David Chiron. Chemins d'analyse (1) - Espace de Schwartz, distributions Tempérées et transformation de Fourier.

128. — Gentiana Danila, Jean-Denis Eiden et Rached Mneimné. Algèbre éclectique

129. — Yves Coudène. La géométrie élémentaire d'Euclide à aujourd'hui
Chez le même éditeur,
la collection *Nano*

101. — Benoît Kloeckner. *Un bref aperçu de la géométrie projective*

102. — Michel Balazard. *Le théorème des nombres premiers*

103. — Bruno Kahn. *Fonctions zêta et L de variétés et de motifs*

104. — Patrick Dehornoy. *Le calcul des tresses*

105. — Alain Debreil et Rached Mneimné. *Le groupe symétrique $\mathfrak{S}_4$ et ses métamorphoses*

106. — Roger Mansuy. *Introduction aux graphes aléatoires (et à la méthode probabiliste)*

107. — François Berteloot. *Les familles normales*

108. — Antoine Chambert-Loir. *Théorie de l'information — Trois théorèmes de Claude Shannon*

109. — Anna Cadoret. *Catégories et représentations*

La collection *La perle et le harnais*

101. — Mauricion Garay. *Mathématiques pédestres, le monde pythagorique*

102. — Mauricio Garay. *Le monde selon Einstein. Années 1900-1014*

103. — Joanne Brueton, Antoine Houlou-Garcia et Bernard Randé. *Le compas et la lyre*
<figure><img src="image_188.png" /></figure>
Chez le même éditeur,
la collection *Orizzonti*

101. — Michèle Audin. *Souvenirs de Sofia Kowalevskaya*

102. — Maurice Kleman. *Chronologie d'un physicien*

103. — Rémi Goblot. *L'infini en mathématiques*

104. — Michel Garcia. *Mathématiques à travers les siècles (I). Géométrie et arithmétique de l'Antiquité à nos jours*

105. — Michel Garcia. *Mathématiques à travers les siècles (II). Essor des mathématiques du XVIIe au XIXe siècles*. Algèbre, analyse, topologie, probabilités
<figure><img src="image_189.png" /></figure>
<figure><img src="image_190.png" /></figure>
Imprimé en France et achevé sur les presses de Laballery

Dépôt légal mars 2022