PREUVE. Soit $T_n$ un arbre tel que $[T_n] = \mathcal{P}_n$. On peut supposer, sans perte de généralité, que $T_{n+1} \subseteq T_n$. Montrons que $\bigcap_n [T_n] = [\bigcap_n T_n]$. On a $X \in \bigcap_n [T_n]$ ssi $X_m \in T_n$ pour tout $m, n$, ou encore ssi $X \in [\bigcap_n T_n]$. Donc, $\bigcap_n [T_n] = [\bigcap_n T_n]$. Soit $T = \bigcap_n T_n$. En particulier, $[T] = \bigcap_n \mathcal{P}_n$.

Supposons par l'absurde que $[T] = \bigcap_n \mathcal{P}_n$ est vide. D'après le lemme de König, il y a donc un entier $a$ tel qu'aucune chaîne $\sigma$ de taille supérieure ou égale à $a$ n'est dans $T$. Comme les chaînes de taille $a$ sont en quantité finie et que la suite $(T_n)_{n \in \mathbb{N}}$ est décroissante par l'inclusion, il doit donc y avoir entier $m$ tel qu'aucune de ces chaînes n'appartient à $T_m$. Ainsi, $[T_m]$ est vide, ce qui contredit les hypothèses. $\blacksquare$

## 2.3. Continuité

Abordons une autre notion topologique que nous mentionnerons ça et là dans les chapitres à venir. La continuité, autre notion centrale de topologie, se cache de manière inattendue en calculabilité sous l'idée suivante.

Une fonctionnelle Turing $\Phi$ peut être vue comme une fonction partielle de $2^\mathbb{N}$ dans $2^\mathbb{N}$, dont l'entrée est un oracle $X$, et le résultat, que nous notons $\Phi^X$ ou $\Phi(X)$, est l'ensemble $Y$ tel que $\Phi^X(n) \downarrow= Y(n)$. Cette fonction de $2^\mathbb{N}$ vers $2^\mathbb{N}$ n'est bien entendu définie que pour les oracles $X$ tels que $\forall n \Phi^X(n) \downarrow \in \{0,1\}$.

Nous avons vu que quand $\Phi^X(n) \downarrow= v$, par la propriété de l'usage (voir la définition 4-4.2), seul un segment initial fini $\sigma$ de l'oracle $X$ est utilisé. Plus généralement, si $\Phi^X \succeq \tau$ (ce qui signifie $\forall n < |\tau| \Phi^X(n) \downarrow= \tau(n)$), seule une partie finie $\sigma$ de l'oracle est utilisée pour s'en rendre compte. Il s'ensuit que pour tout $X \in [\sigma]$, $\Phi^X \succeq \tau$, et donc $\{\Phi^X : X \in [\sigma]\} \subseteq [\tau]$.

Le lecteur ayant suivi un cours d'introduction à la topologie reconnaîtra dans cette idée la notion de continuité : pour tout ouvert de l'espace d'ar-rivée aussi « petit » que l'on veut — en pratique un cylindre $[\tau]$, il existe un ouvert de l'espace de départ suffisamment « petit » — en pratique un cylindre $[\sigma]$ — tel que tout $X \in [\sigma]$ est envoyé à l'intérieur de $[\tau]$ : concrètement, la chaîne $\sigma$ est « envoyée » vers la chaîne $\tau$.

**Définition 2.9.** Une fonction (éventuellement partielle) $f : 2^\mathbb{N} \to 2^\mathbb{N}$ est continue en $X \in \text{dom } f$ si pour tout cylindre $[\tau]$ contenant $f(X)$, il existe un cylindre $[\sigma]$ contenant $X$ tel que $f([\sigma]) \subseteq [\tau]$. On dira qu'une fonction est continue si elle est continue en $X$ pour tout $X \in \text{dom } f$. $\diamond$

On considérera en général des fonctions continues sur tout leur domaine de définition, qui admettent alors une caractérisation équivalente en termes de pré-image d'ouverts.
**Proposition 2.10.** Une fonction (éventuellement partielle) $f : 2^N \to 2^N$ est continue si, et seulement si, il existe pour tout ouvert $\mathcal{U} \subseteq 2^N$ un ouvert $\mathcal{V} \subseteq 2^N$ tel que $f^{-1}(\mathcal{U}) = \mathcal{V} \cap \text{dom } f$. Si la fonction est totale, on a alors $f^{-1}(\mathcal{U})$ ouvert pour tout ouvert $\mathcal{U}$.
\*

**PREUVE.** Soient $f : 2^N \to 2^N$ une fonction continue et $\mathcal{U} \subseteq 2^N$ un ouvert. Comme $\mathcal{U}$ est ouvert, pour tout $X \in f^{-1}(\mathcal{U})$ il existe un cylindre $[\tau_X]$ contenant $f(X)$ tel que $[\tau_X] \subseteq \mathcal{U}$. Par continuité de $f$, pour tout $X$, il existe un cylindre $[\sigma_X]$ contenant $X$ tel que $f([\sigma_X]) \subseteq [\tau_X]$. Alors,

$$ \text{dom } f \cap \bigcup_{X \in f^{-1}(\mathcal{U})} [\sigma_X] = f^{-1}(\mathcal{U}). $$

Réciproquement, supposons que pour tout ouvert $\mathcal{U} \subseteq 2^N$, il existe un ouvert $\mathcal{V}$ tel que $\text{dom } f \cap \mathcal{V} = f^{-1}(\mathcal{U})$. Soit $Y \in \text{Im } f$, et soit $[\tau]$ un cylindre contenant $Y$. Soit un ouvert $\mathcal{V}$ tel que $\text{dom } f \cap \mathcal{V} = f^{-1}([\tau])$. Comme $\mathcal{V}$ est un ouvert, il existe $W \subseteq 2^{<N}$ tel que $\bigcup_{\sigma \in W} [\sigma] = \mathcal{V}$. Notons que $W \neq \emptyset$, car $Y \in \text{Im } f \cap [\tau]$, donc il existe un cylindre $\sigma \in W$. On a

$$ f([\sigma]) = f(\text{dom } f \cap [\sigma]) \subseteq [\tau]. \quad \blacksquare $$

Une fonctionnelle calculable $\Phi$ est donc toujours aussi une fonction continue sur son domaine de définition, c'est-à-dire sur l'espace des $X$ tels que $\Phi(X, n) \downarrow \in \{0, 1\}$ pour tout $n$. En revanche, une fonction continue n'a *a priori* aucune raison d'être calculable : il se peut que n'importe quel morceau fini de la sortie de la fonction puisse être déterminé par un morceau fini de l'entrée, mais que ce « déterminisme » ne soit pas calculable. À titre d'exemple, considérons la fonction $\Phi$ qui sur n'importe quel ensemble $X$ associe $X \oplus \emptyset'$. Une telle fonction $\Phi$ est continue, mais pas calculable. Elle est en revanche calculable avec l'aide de $\emptyset'$.

En calculabilité, la fonction non continue par excellence est celle qui à $X$ associe $X'$ : en effet, pour savoir si $n \in X'$, il faut savoir si $\Phi_n(X, n) \downarrow$, et pour cela potentiellement connaître une infinité de bits de $X$ (en particulier, si $\Phi_n(X, n) \uparrow$). Nous verrons des versions effectives de certains théorèmes bien connus d'analyse, qui stipulent que toute fonction non continue, mais pas trop complexe, par exemple $X \mapsto X'$, est malgré tout continue sur un « large » ensemble de points, en particulier sur une classe co-maigre (voir le théorème 10-3.20) et sur une classe de mesure arbitrairement grande (voir le théorème 19-3.8).

## 2.4. Classes parfaites

Une dernière notion topologique que nous utiliserons est celle de classes parfaites. Ce sont les classes qui sont l'image d'une injection continue
de $2^N$ vers $2^N$, c'est-à-dire exactement les classes de la forme $[T]$ pour un f-arbre $T: 2^N \to 2^N$ (voir la section 7-5). Ces classes-là sont donc toujours fermées et peuvent se représenter par un arbre. Par extension, on parlera donc aussi d'arbre parfait.

**Définition 2.11.** Un arbre non vide $T \subseteq 2^N$ est parfait si tout nœud de $T$ a deux extensions incompatibles dans $T$. ◇

Nous avons vu avec l'exercice 1.7 qu'étant donné un fermé $\mathcal{F}$ représenté par un arbre $T$, on peut considérer sans perte de généralité — si l'on ne s'occupe pas de l'effectivité — que $T$ ne contient que des nœuds extensibles. En revanche, un nœud extensible n'a pas nécessairement deux extensions incompatibles dans le cas général. Quand cela arrive, cela signifie qu'il y a exactement un chemin infini passant par ce nœud. On appelle de tels chemins des points isolés. Pour une classe $\mathcal{A}$ arbitraire, la définition correspondante est la suivante.

**Définition 2.12.** Soit $\mathcal{A} \subseteq 2^N$. Un élément $X \in \mathcal{A}$ est un point isolé s'il existe un préfixe $\sigma \prec X$ tel que $[\sigma] \cap \mathcal{A} = \{X\}$. ◇

La définition usuelle de classe parfaite découle alors de celle de point isolé.

**Définition 2.13.** Une classe non vide $\mathcal{F} \subseteq 2^N$ est parfaite si elle est fermée et n'a pas de point isolé. De manière équivalente, $\mathcal{F} = [T]$ pour un arbre parfait $T \subseteq 2^N$. ◇

Les classes parfaites sont d'une grande importance, notamment car elles permettent de construire des arguments de cardinalité : toute classe parfaite est par définition en bijection continue avec $2^N$, et a donc la même cardinalité que $2^N$. Par ailleurs, si une classe $\mathcal{A} \subseteq 2^N$ contient une classe parfaite, alors on a une injection de $2^N$ dans $\mathcal{A}$. L'injection identité de $\mathcal{A}$ dans $2^N$ nous donne alors $|\mathcal{A}| = |2^N|$. Il s'agit en fait grosso modo de la seule manière de montrer qu'une classe $\mathcal{A} \subseteq 2^N$ a la puissance du continu. Nous en reparlerons dans la section 9-4, ainsi que dans la section 30-4.

Voici pour terminer une application simple de la notion de classe parfaite à l'étude de la cardinalité.

**Proposition 2.14.** Toute classe fermée dénombrable et non vide $\mathcal{F}$ contient des points isolés. On peut injecter $2^N$ dans toute classe fermée non vide ne contenant pas de point isolé. ★

**PREUVE.** Supposons que $\mathcal{F}$ ne contienne pas de point isolé. Soit $\mathcal{F} = [T]$ pour un arbre $T$ n'ayant que des nœuds extensibles. Comme $\mathcal{F}$ ne contient pas de point isolé, tous les nœuds de $T$ ont alors deux extensions incompatibles. On a alors une injection de $2^N$ dans $\mathcal{F}$. Si une classe fermée $\mathcal{F}$
est dénombrable, on ne peut injecter $2^N$ dans $\mathcal{F}$, et elle contient donc par contraposée des points isolés. ■

**Corollaire 2.15 (Cantor)**

L'hypothèse du continu est vraie pour les classes fermées de $2^N$ : elles sont soit finies, soit dénombrables, soit de cardinalité $|2^N|$.

PREUVE. Soit $\mathcal{F}$ un fermé, et soit $W \subseteq 2^{<N}$ l'ensemble des chaînes $\sigma$ telles que $\mathcal{F} \cap [\sigma]$ est fini ou dénombrable. Soit $\mathcal{F}' = \mathcal{F} \setminus \bigcup_{\sigma \in W}[\sigma]$. Notons que $\mathcal{F}' \subseteq \mathcal{F}$ est toujours une classe fermée. Si $\mathcal{F}'$ est vide, alors d'après le lemme de König (ou la compacité) il n'est besoin d'enlever à $\mathcal{F}$ qu'un nombre fini de chaînes $\sigma_0, \dots, \sigma_n \in W$ pour que $\mathcal{F}' = \mathcal{F} \setminus ([\sigma_0] \cup \dots \cup [\sigma_n])$ soit vide. Comme chaque classe $\mathcal{F} \cap [\sigma_i]$ est dénombrable, on a vidé $\mathcal{F}$ en lui enlevant une quantité dénombrable de points. Donc, $\mathcal{F}$ est dénombrable. Sinon, $\mathcal{F}'$ n'est pas vide, et en plus de cela il ne peut contenir de points isolés (car si $\mathcal{F}' \cap [\sigma]$ ne contient qu'un seul élément, alors $\mathcal{F} \cap [\sigma]$ est dénombrable). Par la proposition 2.14, on a une injection de $2^N$ vers $\mathcal{F}'$. ■

Ce résultat sera étendu avec le corollaire 30-3.3.

## 3. Classes $\Pi_1^0$

Nous nous intéressons à présent à la version *effective* des classes ouvertes et fermées. On emploie souvent le terme *effectif* plutôt que calculable pour ce genre d'objets, car ils ne sont pas nécessairement calculables dans le sens où l'on peut précisément en connaître les moindres détails, mais ils admettent malgré tout une certaine description tangible, effective, fournie par un algorithme.

**Définition 3.1.** Une classe $\mathcal{U} \subseteq 2^N$ est dite $\Sigma_1^0$ s'il existe un ensemble c. e. $W \subseteq 2^{<N}$ tel que $\mathcal{U} = \bigcup_{\sigma \in W}[\sigma]$. Une classe $\mathcal{P} \subseteq 2^N$ est dite $\Pi_1^0$ si son complémentaire est une classe $\Sigma_1^0$. ◇

Les $\Sigma_1^0$ et $\Pi_1^0$ sont respectivement les ouverts et fermés *effectifs* de l'espace de Cantor. On appellera *code* d'une classe $\Sigma_1^0 \mathcal{U}$ un entier $e$ tel que $\mathcal{U} = \bigcup_{\sigma \in W_e}[\sigma]$. De même, le *code* d'une classe $\Pi_1^0 \mathcal{P}$ est le code de la classe $\Sigma_1^0 \mathcal{U} = 2^N \setminus \mathcal{P}$. Cela nous permet de parler de calculabilité uniforme sur les suites de classes $\Sigma_1^0$ ou $\Pi_1^0$ en considérant la calculabilité de leur suite de codes. Les classes $\Pi_1^0$ sont un exemple important et très étudié en calculabilité.
**Remarque**

Il convient de bien distinguer les ensembles d'entiers $\Sigma_1^0$ et $\Pi_1^0$, qui sont les premiers niveaux de la hiérarchie arithmétique (voir le chapitre 5) des classes $\Sigma_1^0$ et $\Pi_1^0$ qui sont les ouverts et fermés effectifs respectifs de l'espace de Cantor. Il existe cependant des liens entre ces notions.

Commençons par le fait que la proposition 2.3, qui stipule qu'une intersection finie d'ouverts est un ouvert, fonctionne également avec les classes $\Sigma_1^0$.

**Proposition 3.2.** Les classes $\Sigma_1^0$ sont closes par intersection finie. Par passage au complémentaire, les classes $\Pi_1^0$ sont closes par réunion finie. ★

PREUVE. Soient $U_0 = \bigcup_{\sigma \in W_0} [\sigma]$ et $U_1 = \bigcup_{\sigma \in W_1} [\sigma]$ deux classes $\Sigma_1^0$. Alors, l'ouvert $U_0 \cap U_1$ est décrit par l'ensemble c. e. qui énumère la plus longue chaîne parmi $\sigma_0, \sigma_1$ pour tous $\sigma_0 \in W_0$ et $\sigma_1 \in W_1$ telles que $\sigma_0 \le \sigma_1$ ou telles que $\sigma_1 \le \sigma_0$. La chaîne ainsi énumérée correspond à $[\sigma_0] \cap [\sigma_1]$. ■

La première étape pour mieux appréhender la nature des classes $\Pi_1^0$ est sans doute de prouver la version effective du théorème 2.4 : les $\Pi_1^0$ sont exactement les chemins infinis d'arbres calculables.

**Proposition 3.3.** Une classe $\mathcal{P}$ est $\Pi_1^0$ si, et seulement si, il existe un arbre calculable $T \subseteq 2^{<\mathbb{N}}$ tel que $[T] = \mathcal{P}$. ★

PREUVE. Soit $T \subseteq 2^{<\mathbb{N}}$ un arbre calculable. La classe $[T]=\{X:\forall nX\upharpoonright_n T\}$ est alors bien $\Pi_1^0$. En effet, son complémentaire est la classe $\Sigma_1^0$ décrite par la réunion des cylindres $[\sigma]$ tels que $\sigma \notin T$.

Supposons que $\mathcal{P}$ est $\Pi_1^0$, et soit $U = \bigcup_{\sigma \in W} [\sigma]$ son complémentaire. On calcule l'arbre $T \subseteq 2^{<\mathbb{N}}$ suivant : à l'étape de calcul $t$, pour toute chaîne $\sigma \in 2^{<\mathbb{N}}$ de taille $t$, on décide $\sigma \in T$ ssi pour tout préfixe $\tau \le \sigma$ on a $\tau \notin W[t]$.

Il est clair que $T$ est clos par préfixe : si $\sigma$ de taille $t$ est dans $T$, alors aucun préfixe de $\sigma$ n'est dans $W$ à l'étape de calcul $t$, donc pour $s \le t$, aussi aucun préfixe de $\sigma \upharpoonright_s$ n'est dans $W$ à l'étape de calcul $s$. À présent, si $X \in \mathcal{P}$, alors aucun préfixe $\sigma$ de $X$ n'est dans $W$, et chacun de ces préfixes sera donc dans $T$. À l'inverse, si $X \notin \mathcal{P}$, alors un préfixe $\sigma$ de $X$ rentre dans $W$ à une certaine étape $t$. Par construction, aucune chaîne $\tau \ge \sigma$ de taille supérieure à $t$ ne sera dans $T$. Donc, $\mathcal{P} = [T]$. ■

Le code d'un arbre calculable $T \subseteq 2^{<\mathbb{N}}$ est un entier $e$ tel que $\Phi_e = T$. Notons que la preuve de la proposition 3.3 est uniforme, et permet de passer calculatoirement d'un code d'une classe $\Pi_1^0$ à un code de l'arbre correspondant, et inversement. On pourra donc considérer indistinctement le code des classes $\Pi_1^0$ et des arbres calculables dans les preuves à venir. La
proposition suivante établit un lien avec les classes $\Sigma_1^0$ et $\Pi_1^0$ et la hiérarchie arithmétique.

**Proposition 3.4.** Soit $\mathcal{P} \subseteq 2^{\mathbb{N}}$ une classe.

(1) La classe $\mathcal{P}$ est $\Sigma_1^0$ si, et seulement si, $\mathcal{P} = \{X \in 2^{\mathbb{N}} : \exists n \ R(X \upharpoonright_n)\}$ pour un prédicat calculable $R \subseteq 2^{<\mathbb{N}}$.

(2) La classe $\mathcal{P}$ est $\Pi_1^0$ si, et seulement si, $\mathcal{P} = \{X \in 2^{\mathbb{N}} : \forall n \ R(X \upharpoonright_n)\}$ pour un prédicat calculable $R \subseteq 2^{<\mathbb{N}}$. $\star$

**PREUVE.** Pour (2), étant donné $\mathcal{P}$ une classe $\Pi_1^0$, il suffit de considérer l'arbre calculable $T$ tel que $[T] = \mathcal{P}$. Le prédicat calculable est simplement $T$. À l'inverse, si $\mathcal{P} = \{X \in 2^{\mathbb{N}} : \forall n \ R(X \upharpoonright_n)\}$, alors l'arbre calculable donné par $\sigma \in T$ ssi $\forall \tau \leq \sigma \ R(\tau)$ est tel que $[T] = \mathcal{P}$.

On obtient (1) par passage au complémentaire. $\blacksquare$

Voyons à présent quelques généralités, en premier lieu la preuve que le lemme de König ne relève pas des mathématiques calculables : certaines classes $\Pi_1^0$ non vides — et donc certains arbres calculables infinis — ne contiennent aucun point calculable. Nous verrons tout au long des chapitres à venir de nombreux exemples de classes $\Pi_1^0$ ne contenant aucun point calculable. Nous anticipons en particulier pour la proposition suivante sur l'exemple le plus simple à définir : la classe des ensembles $\text{DNC}_2$ de la proposition 6.4.

**Proposition 3.5.** Il existe des classes $\Pi_1^0$ non vides ne contenant aucun ensemble calculable. $\star$

**PREUVE.** On définit la classe

$$ \mathcal{P} = \{X \in 2^{\mathbb{N}} : \forall e \ \forall t \ \Phi_e(e)[t] \uparrow \lor \Phi_e(e)[t] \downarrow \neq X(e)\}. $$

La classe $\mathcal{P}$ contient tous les ensembles $X$ tels que $X(n)$ peut prendre n'importe quelle valeur si $\Phi_n(n) \uparrow$, et qui sont toujours différents de $\Phi_n(n)$ si $\Phi_n(n) \downarrow$. Il est clair que cette classe est non vide (l'arrêt des programmes informatique calcule par exemple facilement un élément de $\mathcal{P}$). Par la proposition 3.4, $\mathcal{P}$ est une classe $\Pi_1^0$. De plus, la classe $\mathcal{P}$ ne contient aucun ensemble calculable : si $X$ est calculable, alors il doit exister $e$ tel que $\Phi_e(e) \downarrow= X(e)$. $\blacksquare$

Continuons à présent sur un autre aspect clef : les exemples de classes $\Pi_1^0$ non vides ne contenant aucun point calculable sont nécessairement indénombrables. Ils ne peuvent pas contenir de points isolés, c'est-à-dire des ensembles $X$ tels que pour un certain $n$, aucun autre ensemble que $X$ et étendant $X \upharpoonright_n$ n'appartient au $\Pi_1^0$.
**Proposition 3.6.** Si $\mathcal{P}$ est une classe $\Pi_1^0$ contenant exactement un élément $X$, alors, $X$ est calculable. ★

PREUVE. Soit $T \subseteq 2^{<N}$ l'arbre calculable tel que $[T] = \mathcal{P}$. Soit l'algorithme suivant : on cherche le plus petit $t$ tel que soit pour toute chaîne $\sigma \succeq 0$ de taille $t$ on a $\sigma \notin T$, soit pour toute chaîne $\sigma \succeq 1$ de taille $t$ on a $\sigma \notin T$. Notez qu'exactement un des deux événements doit nécessairement arriver : si les deux événements arrivent, la classe est vide. Si aucun des deux n'arrive, il y a une infinité de chaînes dans $T$ qui étendent 0 et aussi une infinité qui étendent 1. D'après le lemme de König, $T$ contient donc au moins deux chemins infinis : un qui étend 0 et un qui étend 1, ce qui contredit les hypothèses sur $\mathcal{P}$.

Une fois un des deux événements arrivés, on sait donc si $X$ commence par 0 ou 1. On voit aisément comment continuer par récurrence : une fois $X \upharpoonright_n$ calculé, on cherche le plus petit $t$ tel que pour toute chaîne $\sigma \succeq X \upharpoonright_n 0$ de taille $t$ on a $\sigma \notin T$, ou pour toute chaîne $\sigma \succeq X \upharpoonright_n 1$ de taille $t$ on a $\sigma \notin T$. Une fois l'un des deux événements arrivé, la valeur de $X(n)$ est connue. ■

**Corollaire 3.7**

Les points isolés de toute classe $\Pi_1^0$ sont calculables.

PREUVE. Soit $\mathcal{P}$ une classe $\Pi_1^0$, et soit $X \in \mathcal{P}$ un point isolé. Par définition, on a un préfixe $\sigma \prec X$ tel que $[\sigma] \cap \mathcal{P} = \{X\}$. En particulier, $[\sigma] \cap \mathcal{P}$ est une classe $\Pi_1^0$ contenant exactement un élément, et cet élément est donc calculable. ■

**Corollaire 3.8**

Toute classe $\Pi_1^0$ dénombrable contient un ensemble calculable.

PREUVE. Par la proposition 2.14 et le corollaire 3.7. ■

# 4. Théorèmes de base

Les membres d'une classe $\Pi_1^0$ peuvent être de degrés Turing très différents. Par exemple, l'espace de Cantor $2^N$ est une classe $\Pi_1^0$ contenant des ensembles de chaque degré Turing.

Étant donné une classe $\Pi_1^0$ non vide, on s'intéresse principalement au degré de difficulté du calcul de l'un de ses membres.
**Définition 4.1.** Une base pour les classes $\Pi_1^0$ est une classe d'ensembles $C$ telle que toute classe $\Pi_1^0$ non vide contient un élément de $C$. ◇

Dans cette section, nous allons prouver un certain nombre de théorèmes qui étant donné une propriété de faiblesse $P$ sont de la forme « Toute classe $\Pi_1^0$ non vide contient un membre satisfaisant $P$. » Ces théorèmes sont appelés « théorèmes de bases », car ils établissent que les membres de $P$ forment une base pour les classes $\Pi_1^0$. Inversement, les « théorèmes d'ant bases » énoncent l'existence d'une classe $\Pi_1^0$ non vide ne contenant aucun membre satisfaisant une propriété de faiblesse. Le tout premier théorème de base est dû à Kreisel [124], et est laissé en exercice.

**Exercice 4.2.** (⋆) Montrer que toute classe $\Pi_1^0$ non vide contient un élément $\emptyset'$-calculable. ◇

On peut faire encore mieux que l'exercice 4.2 via le théorème central dit de « base low », qui stipule que toute classe $\Pi_1^0$ non vide contient un ensemble low. Ce théorème a une importance fondamentale en calculabilité et en mathématique à rebours, notamment pour fournir nombre d'exemples et contre-exemples.

**Théorème 4.3 (Jockusch et Soare [104])**

Toute classe $\Pi_1^0$ non vide contient un ensemble low.

**PREUVE.** Soit $\mathcal{P}$ une classe $\Pi_1^0$ non vide. Nous allons utiliser $\emptyset'$ pour calculer un élément $Z \in \mathcal{P}$, tout en calculant son saut Turing $Z'$. Pour cela, définissons une suite décroissante uniformément $\emptyset'$-calculable de classes $\Pi_1^0$ non vides $\mathcal{P} = \mathcal{P}_0 \supseteq \mathcal{P}_1 \supseteq \mathcal{P}_2 \supseteq \dots$ comme suit. Soit $\mathcal{P}_0 = \mathcal{P}$; supposons $\mathcal{P}_n$ défini, et considérons la classe

$$ \mathcal{B}_n = \{X \in 2^{\mathbb{N}} : \forall t \Phi_n(X, n)[t] \uparrow\} \cap \mathcal{P}_n. $$

Notons que $\mathcal{B}_n$ est aussi une classe $\Pi_1^0$, et que le code d'un arbre calculable $T_n$ tel que $\mathcal{B}_n = [T_n]$ est calculable uniformément en $n$.

On pose à $\emptyset'$ la question de savoir si $\mathcal{B}_n$ est vide : d'après le lemme de König, c'est le cas ssi il existe $m$ tel qu'aucune chaîne $\sigma$ de taille $m$ n'appartient à $T_n$, ce qui est bien un événement $\Sigma_1^0$. Si $\emptyset'$ répond positivement, on note $Y(n) = 1$ et l'on définit $\mathcal{P}_{n+1} = \mathcal{P}_n$. Notons que, dans ce cas, tous les éléments $X \in \mathcal{P}_{n+1}$ sont tels que $\Phi_n(X, n) \downarrow$. Dans le cas inverse, on note $Y(n) = 0$ et l'on définit $\mathcal{P}_{n+1} = \mathcal{B}_n$. Notons que, dans ce cas-ci, tous les éléments de $X \in \mathcal{P}_{n+1}$ sont tels que $\Phi_n(X, n) \uparrow$.

Pour chaque $n$, $\mathcal{P}_n$ est un fermé non vide, et $\bigcap_n \mathcal{P}_n$ est donc non vide. Par construction, l'élément $Y$ calculé par $\emptyset'$ correspond au saut Turing de n'importe quel élément de $\bigcap_n \mathcal{P}_n$. ■
Nous avons déjà vu avec la proposition 4-9.1 l'existence d'ensembles low et non calculable. Nous en avons à présent une preuve alternative en combinant le théorème 4.3 et la proposition 3.5.

Nous nous attelons à présent au deuxième grand théorème de base pour les classes $\Pi_1^0$: les ensembles calculatoirement dominés. Nous avons besoin pour cela d'un lemme, qui a aussi son intérêt propre.

**Lemme 4.4.** Soit $\mathcal{P}$ une classe $\Pi_1^0$ non vide. Supposons qu'une fonctionnelle $\Phi$ est totale sur tous les chemins de $\mathcal{P}$. Alors, on peut définir uniformément en un code de la classe $\mathcal{P}$ une fonction calculable $g$ qui domine $n \mapsto \Phi(X, n)$ pour tout $X \in \mathcal{P}$.

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

**PREUVE.** Soit $T \subseteq 2^{<\mathbb{N}}$ un arbre calculable tel que $[T] = \mathcal{P}$. Montrons que pour tout entier $n$ il existe $t$ tel que $\Phi(\sigma, n)[|\sigma|] \downarrow$ pour toute chaîne $\sigma \in T$ de taille $t$. En effet, dans le cas inverse, il existe un entier $n$ tel que l'ensemble $\{\sigma \in T : \Phi(\sigma, n)[|\sigma|] \uparrow\}$ contient pour tout $t$ une chaîne de taille $t$ et est donc un sous-arbre infini de $T$, qui contient donc par le lemme de König un chemin infini $X$. On a donc $\forall t \Phi(X, n)[t] \uparrow$, ce qui contredit la totalité de $\Phi$ sur tous les oracles de $[T]$.

On peut donc calculer la fonction $g$ qui pour $n$ cherche le plus petit $t$ tel que $\Phi(\sigma, n)[t] \downarrow = v_\sigma$ pour toute chaîne $\sigma \in T$ de taille $t$. Une fois $t$ trouvé, on définit $g(n) = \sum_{|\sigma|=t} v_\sigma + 1$. Il est clair que $g$ domine toutes les fonctions calculables via $\Phi$ par un oracle de $[T]$.

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

Le théorème suivant est connu sous le nom de « théorème de base calculatoirement dominée ». Avec l'existence d'une classe $\Pi_1^0$ non vide ne possédant pas de membre calculable, ce théorème nous fournit une preuve alternative de l'existence d'ensembles calculatoirement dominés non calculables.

**Théorème 4.5 (Jockusch et Soare [104])**

Toute classe $\Pi_1^0$ non vide contient un ensemble calculatoirement dominé.

**PREUVE.** Soit $\mathcal{P}$ une classe $\Pi_1^0$ non vide. Nous allons définir une suite infinie décroissante de classes $\Pi_1^0$ non vides $\mathcal{P} = \mathcal{P}_0 \supseteq \mathcal{P}_1 \supseteq \mathcal{P}_2 \supseteq \dots$ de telle sorte que $\bigcap_n \mathcal{P}_n$ ne contienne que des ensembles calculatoirement dominés. Soit $\mathcal{P}_0 = \mathcal{P}$. Supposons $\mathcal{P}_n$ défini. Soit $\mathcal{B}_{n,m} = \{X : \Phi_n(X, m) \uparrow\}$. Notons que chaque classe $\mathcal{B}_{n,m}$ est $\Pi_1^0$. Supposons qu'il existe un entier $m$ tel que $\mathcal{P}_n \cap \mathcal{B}_{n,m} \neq \emptyset$. Alors, on définit $\mathcal{P}_{n+1} = \mathcal{P}_n \cap \mathcal{B}_{n,m}$. Notons que pour tout $X \in \mathcal{P}_{n+1}$ on a $\Phi_n(X, m) \uparrow$. Supposons à présent que pour tout $m$ on a $\mathcal{P}_n \cap \mathcal{B}_{n,m} = \emptyset$. Cela implique que la fonctionnelle $\Phi_n$ est totale pour tout $X \in \mathcal{P}_n$. On définit alors $\mathcal{P}_{n+1} = \mathcal{P}_n$. D'après le lemme 4.4, il existe
donc une fonction calculable $g : \mathbb{N} \to \mathbb{N}$ qui domine $m \mapsto \Phi_n(X, m)$ pour tout $X \in \mathcal{P}_{n+1}$.

En tant qu'intersection décroissante de fermés non vides, la classe $\bigcap_n \mathcal{P}_n$ est non vide. Soit $X \in \bigcap_n \mathcal{P}_n$. Par construction, pour tout $n$, si $\Phi_n$ est totale sur l'oracle $X$, alors $m \mapsto \Phi_n(X, m)$ est bornée par une fonction calculable. Donc, $X$ est calculatoirement dominé. ■

Nous voyons à présent un dernier théorème de base dit « d'évitement de cône » : étant donné un ensemble $X$, on appelle cône supérieur de $X$ la classe $\mathcal{C}_X = \{Y \in 2^\mathbb{N} : Y \geq_T X\}$. Jockusch et Soare [104] ont prouvé que, pour chaque ensemble non calculable $X$, la classe $2^\mathbb{N} \setminus \mathcal{C}_X$ est une base pour les classes $\Pi_1^0$. En d'autres termes, si $X$ est un ensemble non calculable, toute classe $\Pi_1^0$ non vide possède un élément qui ne calcule pas $X$. La contraposée, plus naturelle, énonce que si un ensemble est calculable par tous les membres d'une classe $\Pi_1^0$ non vide, il est nécessairement calculable. Notons que si une classe $\Pi_1^0$ a un membre calculable, le résultat est évident, et il ne devient intéressant que pour les classes $\Pi_1^0$ non vides qui n'en ont pas. Tout comme pour le théorème de base calculatoirement dominée, nous avons besoin d'un lemme pour régler le cas d'une fonctionnelle fixée.

**Lemme 4.6.** Soient $X$ un ensemble, $\mathcal{P}$ une classe $\Pi_1^0$ non vide et $\Phi$ une fonctionnelle. Si $\Phi^Y = X$ pour tout $Y \in \mathcal{P}$, alors $X$ est calculable. ★

**PREUVE.** Soit $T \subseteq 2^{<\mathbb{N}}$ un arbre calculable tel que $[T] = \mathcal{P}$. Supposons que pour tout $Y \in [T]$, $\Phi^Y = X$. Montrons que pour tout $n$, il existe un $t \in \mathbb{N}$ tel que $\Phi(\sigma, n)[|\sigma|] \downarrow = X(n)$ pour toute chaîne $\sigma \in T$ de taille $t$. En effet, dans le cas contraire, l'ensemble $S = \{\sigma \in T : \Phi(\sigma, n)[|\sigma|] \neq X(n)\}$ est un sous-arbre de $T$ qui contient des éléments de chaque longueur, et il existe donc par le lemme de König un chemin $Y \in [S] \subseteq [T]$ tel que $\Phi^Y(n) \neq X(n)$, contredisant ainsi notre hypothèse.

Soit $g : \mathbb{N} \to \mathbb{N}$ la fonction calculable qui sur l'entrée $n$ cherche $t$, $v_n \in \mathbb{N}$ tels que $\Phi(\sigma, n)[|\sigma|] \downarrow = v_n$ pour toute chaîne $\sigma \in T$ de taille $t$, et renvoie $v_n$. Nous avons montré que cette fonction était totale. De plus, on a nécessairement $v_n = X(n)$ pour tout $n$, car sinon chaque élément de $\mathcal{P}$ calcule autre chose que $X$ sur le bit $n$. Ainsi, $X$ est calculé par $g$, et est donc calculable. ■

**Théorème 4.7 (Jockusch et Soare [104])**

Soient $X$ un ensemble non calculable et $\mathcal{P}$ une classe $\Pi_1^0$ non vide. Alors, il existe un élément de $\mathcal{P}$ qui ne calcule pas $X$.
PREUVE. Nous allons définir une suite infinie décroissante de classes $\Pi_1^0$ non vides $\mathcal{P} = \mathcal{P}_0 \supseteq \mathcal{P}_1 \supseteq \mathcal{P}_2 \supseteq \dots$ de telle sorte qu'aucun élément de $\bigcap_n \mathcal{P}_n$ ne calcule $X$. Soit $\mathcal{P}_0 = \mathcal{P}$. Supposons $\mathcal{P}_n$ défini. Soit

$$ \mathcal{B}_{n,m} = \{Y : \Phi_n(Y,m) \uparrow \lor \Phi_n(Y,m) \neq X(m)\}. $$

Notons que chaque classe $\mathcal{B}_{n,m}$ est $\Pi_1^0$ (pas uniformément, bien sûr, car on ne connaît pas $X$). Montrons qu'il existe $m$ tel que $\mathcal{P}_n \cap \mathcal{B}_{n,m} \neq \emptyset$. Si ce n'était pas le cas, on aurait alors $\Phi_n^Y = X$ pour tout $Y \in \mathcal{P}_n$, contredisant dès lors le lemme 4.6. Il existe donc $m$ tel que $\mathcal{P}_n \cap \mathcal{B}_{n,m} \neq \emptyset$, et l'on définit alors $\mathcal{P}_{n+1} = \mathcal{P}_n \cap \mathcal{B}_{n,m}$ pour un tel entier $m$, ce qui nous assure $\Phi_n(X,m) \uparrow$ ou $\Phi_n(X,m) \downarrow \neq X(m)$ pour tout $X \in \mathcal{P}_{n+1}$.

En tant qu'intersection décroissante de fermés non vides, la classe $\bigcap_n \mathcal{P}_n$ est non vide. Soit $Y \in \bigcap_n \mathcal{P}_n$. Par construction, pour tout $n$, $\Phi_n^Y \neq X$, car $Y \in \mathcal{P}_n$. Donc, $X \not\leq_T Y$. ■

Hirschfeldt [87] a donné une élégante preuve alternative du théorème d'évitement de cône, comme simple conséquence du théorème 4.3 de base low et du théorème 4.5 de base calculatoirement dominée.

PREUVE ALTERNATIVE DU THÉORÈME 4.7. Deux cas se présentent.

▷ Cas 1. L'ensemble $X$ est $\Delta_2^0$. En particulier, par la proposition 7-4.7, $X$ est hyperimmune. Par le théorème 4.5 de base calculatoirement dominé, la classe $\mathcal{P}$ contient un ensemble calculatoirement dominé $P$. En particulier, $P$ ne calcule pas $X$.

▷ Cas 2. L'ensemble $X$ n'est pas $\Delta_2^0$. Par le théorème 4.3 de base low, la classe $\mathcal{P}$ contient un ensemble low $P$, donc $\Delta_2^0$. En particulier, $P$ ne calcule pas $X$.

Dans chacun des cas, $\mathcal{P}$ contient un élément qui ne calcule pas $X$. ■

Nous verrons dans les chapitres à venir de nombreux autres théorèmes concernant les classes $\Pi_1^0$.

# 5. Bases pour les classes $\Pi_1^0$ parfaites

Nous avons vu que les classes $\Pi_1^0$ sans élément calculable sont nécessairement des classes parfaites. Ces classes admettent des théorèmes de base renforcés, et l'on peut notamment y construire des sous-classes parfaites dont tous les éléments ont une propriété de faiblesse fixée à l'avance. Nous voyons ici un exemple avec les ensembles calculatoirement dominés.

L'idée est de recommencer la preuve de base calculatoirement dominée, mais en dupliquant la construction étape après étape.
**Théorème 5.1**

Soit $\mathcal{P}$ une classe $\Pi_1^0$ non vide ne contenant aucun élément calculable. Il existe une classe parfaite $\mathcal{B} \subseteq \mathcal{P}$ qui ne contient que des ensembles calculatoirement dominés.

PREUVE. Soit $P_{\epsilon} = \mathcal{P}$. Supposons que pour $n$ et chaque $\sigma \in 2^{<N}$ de taille $n$ on ait défini des classes $\Pi_1^0$ deux à deux disjointes et non vides $P_{\sigma} \subseteq \mathcal{P}$. On répète la construction du théorème 4.5 pour définir pour chaque $\sigma$ une classe $\Pi_1^0$ non vide $Q_{\sigma} \subseteq P_{\sigma}$ telle que soit l'on a un $m$ tel que $\Phi_n(X, m) \uparrow$ pour tout $X \in Q_{\sigma}$, soit l'on a une fonction calculable $g: \mathbb{N} \to \mathbb{N}$ telle que $\Phi_n(X, m) < g(m)$ pour tout $m$ et pour tout $X \in Q_{\sigma}$. Comme $\mathcal{P}$ ne contient aucun point calculable, alors pour tout $\sigma$, $Q_{\sigma} \subseteq \mathcal{P}$ non plus. Donc, d'après le corollaire 3.7, il doit exister $\tau_0, \tau_1$ incomparables telles que les classes $Q_{\sigma} \cap [\tau_0]$ et $Q_{\sigma} \cap [\tau_1]$ sont toutes les deux non vides. On définit alors $P_{\sigma 0} = Q_{\sigma} \cap [\tau_0]$ et $P_{\sigma 1} = Q_{\sigma} \cap [\tau_1]$.

Pour chaque $X \in 2^N$, la classe $\cap_n P_{X\upharpoonright n} \subseteq \mathcal{P}$ contient exactement un élément $G_X$ ; cet élément est calculatoirement dominé, et par construction $X \neq Y$ implique $G_X \neq G_Y$. La classe des $G_X$ pour $X \in 2^N$ forme en fait un arbre parfait, dont les nœuds sont déterminés par le choix des extensions incomparables $\tau_0, \tau_1$. $\blacksquare$

La technique de duplication du théorème précédent peut également être appliquée au théorème de base d'évitement de cône, mais il ne peut bien entendu pas être utilisé avec le théorème de la base low, car la classe des ensembles low est dénombrable. Le lecteur pourra essayer de l'appliquer quand même, afin de voir ce qui coince.

Notons enfin qu'il n'est bien entendu pas nécessaire de passer par des classes $\Pi_1^0$ pour construire une classe parfaite d'ensembles calculatoirement dominés, et l'on peut appliquer, comme suit, la même idée de duplication de construction à la preuve des f-arbres.

**Exercice 5.2.** (⋆) Construire une classe parfaite d'ensembles calculatoirement dominés via des f-arbres. ◇

**Exercice 5.3.** (⋆) Soit $\mathcal{P}$ une classe $\Pi_1^0$ non vide sans point calculable. Mélanger la construction ci-dessus avec la preuve du lemme 4.6 pour obtenir une sous classe parfaite de $\mathcal{P}$ dont tous les éléments sont calculatoirement dominés, et dont les degrés Turing sont deux à deux incomparables. ◇

**Exercice 5.4.** (⋆⋆) Soit $\mathcal{P}$ une classe parfaite. Construire une sous-classe parfaite de $\mathcal{P}$ dont les éléments sont deux à deux incomparables en termes de degrés Turing. ◇
**Exercice 5.5. (*)** Soit $\mathcal{P}$ une classe $\Pi_1^0$ non vide sans point isolé. Montrer que $\emptyset'$ calcule un élément non calculable de $\mathcal{P}$.

◇

Notons que le dernier exercice utilise nécessairement le fait que la classe $\mathcal{P}$ ne contient pas de point isolé. Nous verrons avec la proposition 30-3.5 une technique simple, mais très puissante, permettant de construire des classes $\Pi_1^0$ —avec points isolés— dont les éléments sont soit des ensembles finis, soit des ensembles de complexité calculatoire « très élevée ».

# 6. Degrés PA

Nous prenons ici un peu d'avance sur le chapitre 9, dans lequel nous exposons les notions de théorie logique du premier ordre, de système formel de l'arithmétique de Peano ainsi que du premier théorème d'incomplétude de Gödel : la notion de degré PA est née en lien direct avec ces notions. Nous allons toutefois rapidement nous abstraire de cet aspect historique pour donner avec le théorème 6.2 une caractérisation équivalente des degrés PA ne faisant appel qu'aux notions de calculabilité vues jusqu'ici.

L'étude des degrés PA —acronyme de « Peano Arithmetic »— remonte aux travaux de Gödel et de son fameux théorème d'incomplétude : il n'existe pas d'extension calculable, complète et cohérente des axiomes de l'arithmétique de Peano<fnref n="1" />. L'étude des degrés Turing se développant, la question de la puisance nécessaire pour calculer une telle extension s'est tout naturellement posée. Nous allons voir que les développements autour de cette question ont abouti à l'un des concepts les plus riches de la calculabilité, qui a sans doute trouvé l'apogée de sa force et de son intérêt à travers l'étude des mathématiques à rebours.

Dans ce qui suit, fixons une énumération calculable $\psi_0, \psi_1, \psi_2, \dots$ de toutes les formules de l'arithmétique. Supposons également qu'il existe une fonction calculable **neg** : $\mathbb{N} \to \mathbb{N}$ telle que $\psi_{\text{neg}(n)} = \neg \psi_n$. Pour le théorème qui suit, nous appellerons **théorie** un ensemble $T \subseteq \mathbb{N}$ tel que pour tout $m$, si $\{\psi_n : n \in T\} \vdash \psi_m$, alors $m \in T$.

En d'autres termes, une théorie est un ensemble de formules de l'arithmétique clos par conséquence logique. Une théorie $T$ est **cohérente** si le code de la formule $\prec 0 = 1 \succ$ n'appartient pas à $T$. Une théorie $T$ est **complète** si pour tout $n$: soit $n \in T$, soit $\text{neg}(n) \in T$. Le lecteur qui aborde ces notions pour la première fois trouvera plus de détails dans le chapitre 9.

<footnote n="1">1. Cette version du théorème est en fait un renforcement de celui de Gödel, qui fut établi par Rosser.</footnote>
**Définition 6.1.** Une complétion de l'arithmétique de Peano est une théorie complète $T$ contenant $\{n \in \mathbb{N} : PA \vdash \psi_n\}$. Un degré Turing est $PA$ s'il contient une complétion cohérente de l'arithmétique de Peano. ◇

Les degrés PA étant clos par le haut, il est équivalent pour un degré d'être PA et de contenir un ensemble qui calcule une complétion cohérente de l'arithmétique de Peano.

Nous montrons dès à présent une équivalence qui nous servira de caractérisation pour les degrés PA.

**Théorème 6.2 (Jockusch et Soare [96], Solovay (non publié))**

Soit $X$ un ensemble. Les deux énoncés suivants sont équivalents.

(1) $X$ est de degré PA.

(2) $X$ est de degré $\text{DNC}_2$, c'est-à-dire que l'ensemble $X$ calcule une fonction $f : \mathbb{N} \to \{0,1\}$ telle que $f(n) \neq \Phi_n(n)$ pour tout $n$.

Avant de passer à la preuve, nous renvoyons le lecteur à la définition 7-2.7, qui introduisait la notion de degré $\text{DNC}_f$ pour une fonction $f : \mathbb{N} \to \mathbb{N}$ telle que $2 \le f(n) \le f(n+1)$. La notion de degré $\text{DNC}_2$ est la plus forte possible de cet ordre : la fonction $f$ calculée ne dispose que de deux possibilités (0 ou 1) pour différer de chaque $\Phi_n(n)$. Nous verrons avec les corollaires 18-4.3 et 19-1.8 que de nombreux ensembles de degré $\text{DNC}$ ne sont pas $\text{DNC}_2$.

**PREUVE.** L'équivalence montrée par Jockusch et Soare utilise le théorème de base de Scott [194] pour les degrés PA, qui stipule que tout degré PA calcule un chemin infini dans toute classe $\Pi_1^0$ non vide. Nous montrons ici directement l'équivalence.

L'implication (1) ⇒ (2) est essentiellement le théorème de Gödel-Rosser, qui étend le premier théorème d'incomplétude de Gödel, et qui sera démontrée formellement avec le théorème 9-3.10 et le corollaire 9-3.11.

Montrons (2) ⇒ (1). Soit $f \le_T X$ une fonction à valeurs dans $\{0,1\}$ telle que $f(n) \neq \Phi_n(n)$ pour tout $n$. On définit $T_0 = \text{PA}$. Supposons $T_n$ cohérente, définie à l'étape $n$. On considère la formule de l'arithmétique $\psi_n$ de code $n$, et l'on définit le code de machine $e_n$ tel que

$$ \Phi_{e_n}(e_n)=1, \text{ si } T_n + \psi_n \vdash 0=1, \text{ et } \Phi_{e_n}(e_n)=0, \text{ si } T_n + \neg \psi_n \vdash 0=1. $$

Si $\Phi_{e_n}(e_n) \downarrow= 0$, alors $T_n + \neg \psi_n$ est incohérente, et $T_n + \psi_n$ est donc cohérente. Si $\Phi_{e_n}(e_n) \downarrow= 1$, alors $T_n + \psi_n$ est incohérente, et $T_n + \neg \psi_n$ est donc cohérente. Si $\Phi_{e_n}(e_n) \uparrow$, alors $T_n + \psi_n$ et $T_n + \neg \psi_n$ sont toutes les deux cohérentes. À présent, comme $f(e_n) \neq \Phi_{e_n}(e_n)$, on peut ainsi définir $T_{n+1}=T_n+\psi_n$ si $f(e_n)=1$ et $T_{n+1}=T_n+\neg \psi_n$ si $f(e_n)=0$. Dans tous les cas, on aura une théorie cohérente.
La théorie $T = \bigcup_n T_n$ est donc cohérente, et elle est par construction également complète. ■

**Remarque**

Notons que la direction (2) → (1) du théorème 6.2 fonctionne pour toute théorie $T_0$ cohérente dont les axiomes sont calculables. Ainsi, toute fonction DNC₂ est capable de calculer une complétion de toute théorie cohérente dont les axiomes sont calculables. La direction (1) → (2) est plus spécifique à l'arithmétique de Peano, car elle requiert une théorie suffisamment expressive pour coder des calculs par des formules.

Notons que $\emptyset'$ peut calculer une fonction DNC₂ et est donc de degré PA. La proposition suivante permet de déduire qu'il n'est pas du tout nécessaire d'être Turing complet pour calculer une extension complète et cohérente de l'arithmétique de Peano.

**Définition 6.3.** Le spectre de degrés d'une classe $\mathcal{P} \subseteq 2^\mathbb{N}$ est l'ensemble $\deg \mathcal{P} = \{\deg_T X : X \in [P]\}$. ◇

**Proposition 6.4.** Il existe une classe $\Pi_1^0$ dont le spectre de degrés correspond aux degrés PA. ★

PREUVE. Il s'agit d'une simple constatation, qui a déjà été utilisée pour la preuve du théorème 3.5. La classe des ensembles DNC₂ se décrit de la manière suivante :

$$ \mathcal{P} = \{X \in 2^{\mathbb{N}} : \forall e \ \forall t \ \Phi_e(e)[t] \uparrow \lor \Phi_e(e)[t] \downarrow \neq X(e)\}. \quad \blacksquare $$

**Corollaire 6.5**

Il existe des degrés PA qui sont low.

PREUVE. D'après la proposition 6.4 et le théorème 4.3. ■

**Corollaire 6.6**

Il existe des degrés PA calculatoirement dominés.

PREUVE. D'après la proposition 6.4 et le théorème 4.5. ■

**Corollaire 6.7**

Soit $A$ un ensemble non calculable. Alors, il existe un ensemble $X$ de degré PA qui ne calcule pas $A$.

PREUVE. D'après la proposition 6.4 et le théorème 4.7. ■
Voyons à présent une autre caractérisation importante des degrés PA, qui stipule que ces derniers capturent la puissance de calcul nécessaire et suf-fisante pour le lemme faible de König.

Théorème 6.8

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

(1) X est de degré PA.

(2) X calcule un ensemble dans chaque classe $\Pi_1^0$ non vide.

De plus, pour (2), le calcul est uniforme en un code de la classe $\Pi_1^0$.

PREUVE. Pour (2) $\Rightarrow$ (1), il suffit de remarquer qu'il existe une classe $\Pi_1^0$ non vide ne contenant que des ensembles de degrés PA (voir la proposition 6.4).

Montrons à présent (1) $\Rightarrow$ (2). Soit $f \le_T X$ à valeurs dans $\{0,1\}$, telle que $f(n) \ne \Phi_n(n)$ pour tout $n$. Soit $\mathcal{P}$ une classe $\Pi_1^0$ non vide, et soit $T$ un arbre calculable tel que $[T] = \mathcal{P}$. Soit $\sigma_0 = \epsilon$. Étant donné $\sigma_n$ défini tel que $[\sigma_n] \cap [T]$ est non vide, on calcule $\sigma_{n+1} = \sigma_n i$ pour $i \in \{0,1\}$ de la manière suivante : on calcule d'abord le code $e_n$ d'un programme qui sur toute entrée $m$ cherche le plus petit $t$ tel que pour $i=0$ ou $i=1$ aucune chaîne $\sigma$ de taille $t$ avec $\sigma \supseteq \sigma_n i$ n'appartient à $T$. D'après le lemme de König, cette condition est équivalente au fait que $[\sigma_n i] \cap [T]$ soit vide. Si le programme repère un des deux événements, il s'arrête avec comme valeur $i$. Il suffit alors de regarder la valeur de $f(n)$. On définit simplement $\sigma_{n+1} = \sigma_n f(n)$. Comme $f(e_n) \ne \Phi_{e_n}(e_n)$, on a la garantie que $[\sigma_{n+1}] \cap [T]$ est non vide. $\blacksquare$

Classe universelle

Notons que d'après la proposition 6.4, il existe une classe $\Pi_1^0$ non vide dont tous les membres sont de degré PA, et que d'après le théorème 6.8, tout degré PA calcule un membre de chaque classe $\Pi_1^0$ non vide. Une telle classe est donc « maximale » en termes de complexité calculatoire, au sens où si l'on sait calculer un membre de cette classe, alors on sait calculer un membre de toute classe $\Pi_1^0$ non vide.

On appelle *classe $\Pi_1^0$ universelle* une classe $\Pi_1^0$ non vide dont tous les membres sont de degré PA.

Dans la même veine que le théorème 7-7.1, on termine par une caractérisa-
tion qui combine à présent le fait d'être de degré high ou PA. Notez la
différence avec (1) $\leftrightarrow$ (3) du théorème 7-6.2, au sein duquel on considère
une suite $(X_n)_{n \in \mathbb{N}}$ contenant exactement les ensembles calculables, alors
qu'ici l'on considère seulement qu'elle contient les ensembles calculables.
**Théorème 6.9 (Jockusch [98])**

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

(1) L'ensemble $X$ est de degré high ou PA.

(2) L'ensemble $X$ calcule une suite $(X_n)_{n \in \mathbb{N}}$ contenant tous les ensembles calculables.

**PREUVE.** Montrons d'abord (1) implique (2). Si $X$ est high, alors l'implication est claire d'après le théorème 7-6.2. Supposons à présent que $X$ est de degré PA. Soit $g \leqslant_T X$ telle que $g(n) \neq \Phi_n(n)$ pour tout $n$. Notons que l'ensemble $X$ calcule aussi la fonction $f$ qui inverse les valeurs de $g$, c'est-à-dire telle que $\Phi_n(n) \downarrow \in \{0,1\}$ implique $f(n) = \Phi_n(n)$. Étant donné une fonction calculable $\Phi_e$ et un entier $n$, on peut calculer le code $a_n$ tel que $\Phi_{a_n}(a_n) = \Phi_e(n)$. En utilisant ce procédé et le fait que $\Phi_{a_n}(a_n) \downarrow \in \{0,1\}$ implique $f(a_n) = \Phi_{a_n}(a_n) = \Phi_e(n)$, on calcule aisément un ensemble $X_e$ tel que si $n \mapsto \Phi_e(n)$ est totale et à valeurs dans $\{0,1\}$ alors $X_e(n) = \Phi_e(n)$ pour tout $n$. On peut donc calculer notre suite $(X_e)_{e \in \mathbb{N}}$ contenant tous les ensembles calculables.

Montrons à présent (2) implique (1). Soit $(X_n)_{n \in \mathbb{N}}$ une suite $X$-calculable contenant tous les ensembles calculables. L'idée est de procéder au départ comme dans la preuve de (3) ⇒ (1) du théorème 7-6.2. Étant donné un prédicat $\Pi_2^0$ de la forme

$$P = \{e : \forall x_1 \exists x_2 R(e, x_1, x_2)\},$$

l'idée était de définir uniformément en $e$ une fonction partielle calculable $f_e$ telle que :

(a) $e \in P$ implique que $f_e$ est une fonction totale calculable;

(b) $e \notin P$ implique que $f_e$ est une fonction partielle qui n'a aucune complé-
tion totale calculable.

Il suffit de remarquer que dans le théorème 7-6.2, la définition de $f_e$ qui est donnée est telle que dans le cas (b), non seulement aucune complétion de $f_e$ n'est calculable, mais en plus une telle complétion est forcément de degré PA. La définition était la suivante.

Soit $e$ fixé. À l'étape de calcul $t$, pour toute valeur $n$ plus petite que $t$ et telle que $f_e$ ne n'arrête pour le moment pas sur $n$, on procède comme suit : si $\Phi_n(n)[t] \downarrow \neq 0$, on définit $f_e(n) = 0$. Sinon, si $\Phi_n(n)[t] \downarrow \neq 1$, on définit $f_e(n) = 1$. Sinon, si pour tous $k \leq n$ il existe $m_k \leq t$ tel que $R(e, k, m_k)$, alors on définit $f_e(n) = 0$.

Tout comme dans la preuve du théorème 7-6.2, si $e \in P$ alors $f_e$ est une fonction totale. Dans le cas contraire, on s'aperçoit que pour presque toutes les valeurs de $n$ telles que $\Phi_n(n) \downarrow$ on a $f_e(n) \neq \Phi_n(n)$. Toute complétion
de $f_e$ est donc une fonction $\mathrm{DNC}_2$, modulo un nombre fini de valeurs, et
est donc de degré PA.

Il y a à présent deux possibilités :

▷ soit $(X_n)_{n \in \mathbb{N}}$ contient un ensemble de degré PA, auquel cas on a (1);

▷ soit ce n'est pas le cas, et l'on peut alors donner une définition $\Sigma_2^0(X)$ de P comme dans la preuve du théorème 7-6.2, ce qui implique, appliquée à $P = \mathbb{N} \setminus \emptyset''$, que $\emptyset''$ est $\Delta_2^0(X)$, et que X est donc high. ■

Nous terminons cette section par un exercice qui constitue une caractérisation alternative et bien connue des degrés PA.

**Exercice 6.10.** (⋆) Montrer que $X$ est PA si, et seulement si, pour tous ensembles c. e. $A, B$ avec $A \cap B = \emptyset$, il existe un ensemble $X$-calculable $C$ tel que $A \subseteq C$ et $C \cap B = \emptyset$. ◇

**7. Arbres à branchement fini**

Nous introduisons ici l'espace de Baire : la classe $\mathbb{N}^{\mathbb{N}}$ de toutes les suites infinies à valeurs dans $\mathbb{N}$, ou autrement dit la classe de toutes les fonctions de $\mathbb{N}$ dans $\mathbb{N}$. Tout comme l'espace de Cantor a son ensemble de chaînes $2^{<\mathbb{N}}$, l'espace de Baire a son ensemble de chaînes $\mathbb{N}^{<\mathbb{N}}$ : les suites finies à valeurs dans $\mathbb{N}$. Les différentes opérations que nous avons vues sur les chaînes binaires (préfixe, concaténation, longueur, ...) s'étendent sans problème aux chaînes de l'espace de Baire. En particulier, étant donné une chaîne $\sigma \in \mathbb{N}^{<\mathbb{N}}$, on dénote par $[\sigma]$ la classe des suites $P \in \mathbb{N}^{\mathbb{N}}$ telles que $\sigma \prec P$. La notion d'arbre s'étend également aux sous-ensembles de $\mathbb{N}^{<\mathbb{N}}$ comme suit.

**Définition 7.1.** Un ensemble $T \subseteq \mathbb{N}^{<\mathbb{N}}$ est un *arbre* si $T$ est clos par préfixe, c'est-à-dire pour tout $\sigma \in T$ et tout $\tau \preceq \sigma$, alors $\tau \in T$. ◇

Contrairement aux arbres binaires, les nœuds peuvent avoir une infinité de successeurs. Un nœud $\sigma \in T$ est *branchant* s'il a au moins deux successeurs. Un chemin de $T$ est une suite $P \in \mathbb{N}^{\mathbb{N}}$ dont tous les segments initiaux sont dans $T$. On dénote par $[T]$ la classe des chemins de $T$. Le lemme de König ne fonctionne plus sur les arbres de l'espace de Baire, comme le montre contre-exemple suivant.

**Exemple 7.2.** Soit $T = \{\sigma \in \mathbb{N}^{<\mathbb{N}} : \forall n < |\sigma| \sigma(n) \ge |\sigma|\}$. L'arbre $T$ contient des nœuds de longueur arbitraire et est infini, mais $[T] = \emptyset$.
La puissance calculatoire des chemins d'un arbre calculable arbitraire de l'espace de Baire sera étudiée dans la partie IV sur l'hypercalculabilité. Dans cette section, nous allons nous restreindre à une sous-catégorie de ces arbres tombant sous la coupe du lemme de König. Les arbres $T \subseteq \mathbb{N}^<\mathbb{N}$ à *branchement fini*, c'est-à-dire au sein desquels chaque nœud a un nombre fini de successeurs.

**Lemme 7.3 (Lemme de König).** Soit $T \subseteq \mathbb{N}^<\mathbb{N}$ un arbre à branchement fini tel que $|T| = \infty$. Alors, $[T]$ est non vide. ★

**PREUVE.** On construit un chemin $X$ par récurrence sur $n$. Comme $T$ est infini, mais que la racine $\epsilon$ n'a qu'un nombre fini de successeurs, il existe d'après le principe des tiroirs un $i \in \mathbb{N}$ et une infinité de nœuds $\sigma \in T$ qui étendent $i$ (c'est-à-dire avec $i < \sigma$). On définit $X(0) = i$. Supposons que $\tau = X(0)X(1)\dots X(n)$ soit défini avec $\tau \in T$ et tel qu'il y a une infinité de nœuds $\sigma \in T$ pour lesquels $\tau \le \sigma$. Le nœud $\sigma$ n'ayant qu'un nombre fini de successeurs, le principe des tiroirs confirme qu'il existe $i \in \mathbb{N}$ et une infinité de nœuds $\sigma \in T$ qui étendent $\tau i$. On définit $X(n+1) = i$.

Par récurrence sur $n$, on définit donc de cette manière un ensemble $X$ tel que $X|_n \in T$ pour tout $n$. ■

## L'espace de Baire

Comme pour l'espace de Cantor, les ouverts de l'espace de Baire sont les classes $O \subseteq \mathbb{N}^<\mathbb{N}$ de la forme $O = \bigcup_{\sigma \in W}[\sigma]$ pour un ensemble $W \subseteq \mathbb{N}^<\mathbb{N}$, et les fermés $P \subseteq \mathbb{N}^<\mathbb{N}$ sont de la forme $[T]$ pour un arbre $T \subseteq \mathbb{N}^<\mathbb{N}$. En revanche, contrairement à l'espace de Cantor, les fermés de l'espace de Baire ne sont pas compacts en général. Les compacts de l'espace de Baire sont précisément les fermés $P$ de la forme $[T]$ pour un arbre $T \subseteq \mathbb{N}^<\mathbb{N}$ à branchement fini.

La preuve du lemme de König est quasiment la même que celle de sa version faible, et l'on pourrait s'attendre à première vue à ce que la puissance calculatoire nécessaire pour calculer un chemin d'un arbre calculable à branchement fini soit celle des degrés PA. Ce n'est cependant pas le cas, comme le montre la proposition 7.4.

**Proposition 7.4.** Soit $T \subseteq 2^<\mathbb{N}$ un arbre binaire $\Delta_2^0$. Il existe un arbre calculable à branchement fini $S$ tel que $\deg([T]) = \deg([S])$. ★

**PREUVE.** Soit $(T_n)_{n \in \mathbb{N}}$ une approximation $\Delta_2^0$ de l'arbre $T$. On peut poser sans perte de généralité que pour tout entier $n$, $T_n$ est clos par préfixe et $T_n \subseteq 2^{\le n}$ (l'ensemble des chaînes de taille inférieure ou égale à $n$). On montre aisément que toute réunion d'arbres est un arbre, ce qui implique que $\bigcup_n T_n$ est un arbre.
Montrons que $[\bigcup_n T_n] = [T]$. Clairement, $T \subseteq \bigcup_n T_n$, donc $[T] \subseteq [\bigcup_n T_n]$.
Soit $P \in [\bigcup_n T_n]$. Soit $s$ un entier $\ge 0$; montrons que $P \upharpoonright_s \in T$. L'approximation $(T_n)_{n \in \mathbb{N}}$ de $T$ étant $\Delta_2^0$, on a $P \upharpoonright_s \in T$ ssi $\forall t \exists n \ge t P \upharpoonright_s \in T_n$.
Soit $t \ge s$. Comme $P \upharpoonright_t \in \bigcup_n T_n$ et comme par hypothèse $\bigcup_{n<t} T_n \subseteq 2^{<t}$, on a $P \upharpoonright_t \in T_n$ pour $n \ge t$. Par clôture par le bas de $T_n$, il vient $P \upharpoonright_s \in T_n$.
Donc, $\forall t \exists n \ge t P \upharpoonright_s \in T_n$. Ainsi, $P \upharpoonright_s \in T$.

Soient $\sigma, \tau \in \mathbb{N}^{<\mathbb{N}}$ de même longueur. On note $\langle\sigma, \tau\rangle$ la chaîne $\rho$ de longueur $|\sigma|$ telle que pour tout $n < |\rho|$, $\rho(n) = \langle\sigma(n), \tau(n)\rangle$. L'opération s'étend naturellement aux suites infinies $P, Q$ pour lesquelles on écrira $\langle P, Q\rangle$.

Nous allons construire un arbre calculable $S \subseteq \mathbb{N}^{<\mathbb{N}}$ à branchement fini dont tous les chemins seront de la forme $\langle P, Q\rangle$ avec $P \in [\bigcup_n T_n] = [T]$ et $Q$ un « témoin » de $P \in [\bigcup_n T_n]$, au sens où pour tout $s$, $P \upharpoonright_s \in T_{Q(s)}$.

Définissons une fonction partielle calculable $f : \bigcup_n T_n \to \mathbb{N}^{<\mathbb{N}}$ qui envoie des chaînes vers des chaînes de même longueur inductivement comme suit.

$$ \triangleright f(\epsilon) = \epsilon. $$

► Si $\sigma i \in \bigcup_n T_n$, alors $f(\sigma i) = f(\sigma)^{\frown}s$, où $s$ est le plus petit entier tel que $\sigma i \in T_s$ et $\frown$ la concaténation.

► Par continuité, la fonction $f$ s'étend aux suites infinies de $[\bigcup_n T_n] = [T]$.

Soit $S = \{\langle\sigma, f(\sigma)\rangle : \sigma \in \bigcup_n T_n\}$. Notons que la réunion $\bigcup_n T_n$ n'est pas calculable en général, mais que $S$ l'est, car il est facile de vérifier que pour tout $\rho = \langle\sigma, \mu\rangle$, on a $f(\sigma) = \mu$. L'ensemble $S$ est clos par préfixe, car $\bigcup_n T_n$ l'est également et $f(\sigma i) \upharpoonright_{|\sigma|} = f(\sigma)$ pour tout $\sigma \in \bigcup_n T_n$. Ainsi, $S$ est un arbre calculable. Notons également que $S$ est 2-branchant, donc à branchement fini.

Montrons que $\deg([T]) = \deg([S])$. Soit $P \in [T]$; alors, $\langle P, f(P)\rangle \in [S]$ et $P \equiv_T \langle P, f(P)\rangle$. Soit $R \in [S]$; alors, $R = P \oplus f(P)$ pour un $P$ dans $[\bigcup_n T_n] = [T]$. De même, $R \equiv_T P$. Cela conclut la preuve de la proposition 7.4. ■

## Corollaire 7.5

Il existe un arbre calculable $T \subseteq \mathbb{N}^{<\mathbb{N}}$ à branchement fini et un degré PA $P$ ne calculant pas de chemin à travers $T$.

PREUVE. Soit $S = \{\emptyset' \upharpoonright_n : n \in \mathbb{N}\}$ l'arbre binaire $\Delta_2^0$ ayant $\emptyset'$ pour unique chemin infini. Par la proposition 7.4, il existe un arbre calculable $T \subseteq \mathbb{N}^{<\mathbb{N}}$ à branchement fini tel que $\deg([T]) = \deg([S])$. En particulier, tout chemin de $T$ calcule $\emptyset'$. Par le corollaire 6.5, il existe un degré à la fois PA et low. En particulier, ce degré ne calcule pas de chemin à travers $T$. ■
On peut relativiser la notion d'être DNC₂ relativement à un oracle $X$: on demande le calcul d'une fonction $f: \mathbb{N} \to \{0,1\}$ telle que $f(n) \neq \Phi_n(X, n)$ pour tout $n$. Le théorème 6.8 se relativise bien au sens où les degrés DNC₂ relativement à $X$, que l'on appellera aussi degrés PA relativement à $X$ ou PA($X$), coïncident avec ceux permettant de calculer un chemin dans toute classe $\Pi_1^0(X)$ non vide.

**Exercice 7.6.** Soit $Y$ un ensemble PA($X$). Montrer que $Y \geq_T X$. ◇

On en déduit qu'un degré PA relativement à $\emptyset'$ est nécessaire pour calculer un chemin dans tout arbre calculable infini à branchement fini. Notons que la situation de l'exercice 7.6 est différente lorsque l'on considère les degrés DNC au lieu des degrés DNC₂. Plus précisément, si $X$ est un ensemble non calculable, il existe un ensemble $Y$ de degré DNC relativement à $X$ qui ne calcule pas $X$ (voir le corollaire 18-4.4). Ce résultat fait intervenir des notions de théorie de l'aléatoire que nous aborderons au chapitre le chapitre 18.

## Arbre binaire vs arbre 2-branchant

L'arbre $T \subseteq \mathbb{N}^{<\mathbb{N}}$ construit dans la preuve de la proposition 7.4 est 2-branchant, au sens où chaque nœud a au plus deux successeurs. D'un point de vue purement structurel, il est donc isomorphe à un arbre binaire $S \subseteq 2^{<\mathbb{N}}$. Pourtant, il existe des degrés PA qui ne calculent pas de chemin dans cet arbre. La différence entre la puissance calculatoire de cet arbre et celle d'un arbre binaire ne provient donc pas d'une différence combinatoire, mais relève tout simplement d'un manque d'information sur les successeurs d'un nœud : étant donné un arbre calculable à branchement fini, on ne peut pas borner de manière calculable et uniforme la valeur maximale du successeur d'un nœud.

La remarque précédente nous conduit à la définition qui suit.

**Définition 7.7.** Un arbre $T \subseteq \mathbb{N}^{<\mathbb{N}}$ est calculatoirement borné s'il existe une fonction calculable $g: \mathbb{N} \to \mathbb{N}$ telle que pour tout $\sigma \in T$, et pour tout $n < |\sigma|$, on a l'inégalité $\sigma(n) < f(n)$. ◇

Il est clair que tout arbre calculatoirement borné est à branchement fini. La proposition suivante permet de réconcilier l'idée selon laquelle des objets combinatoirement similaires devraient avoir la même puissance calculatoire, en montrant que dès que l'arbre à branchement fini est accompagné d'une borne calculable sur son branchement, alors la puissance calculatoire nécessaire pour calculer un chemin est exactement celle des degrés PA.

Étant donné une fonction $f: \mathbb{N} \to \mathbb{N}$, nous noterons $f^{<\mathbb{N}}$ l'ensemble des chaînes $\sigma \in \mathbb{N}^{<\mathbb{N}}$ telles que pour tout $n < |\sigma|$, $\sigma(n) < f(n)$.
**Proposition 7.8.** Pour tout arbre $T \subseteq \mathbb{N}^{<\mathbb{N}}$ calculable et calculatoirement borné, il existe un arbre binaire $S \subseteq 2^{<\mathbb{N}}$ tel que $\deg([T]) = \deg([S])$. ★

**PREUVE.** L'idée de la preuve est tout simplement de définir un codage binaire des chaînes, en utilisant la borne calculatoire pour savoir combien de bits allouer à chaque niveau. Pour retirer toute ambiguïté, nous noterons $2^{=n}$ l'ensemble des chaînes binaires de longueur $n$, au lieu de $2^n$, qui désignera la $n$-ième puissance de 2. Soit $g : \mathbb{N} \to \mathbb{N}$ une fonction calculable telle que $T \subseteq g^{<\mathbb{N}}$. Sans perte de généralité, nous pouvons supposer que $g(n) = 2^{h(n)}$ pour tout $n$, avec $h : \mathbb{N} \to \mathbb{N}$ une fonction calculable.

Pour tout entier $n$, soit $e_n : 2^n \to 2^{=n}$ la bijection canonique. Par exemple, la fontion $e_2 : 4 \to \{00, 01, 10, 11\}$ vérifie

$$e_2(0) = 00, \quad e_2(1) = 01, \quad e_2(2) = 10 \quad \text{et} \quad e_3(3) = 11.$$

Ce codage s'étend en une bijection calculable $e : g^{<\mathbb{N}} \to 2^{<\mathbb{N}}$ définie par

$$e(\sigma) = e_{h(0)}(\sigma(0)) \wedge e_{h(1)}(\sigma(1)) \wedge \dots \wedge e_{h(|\sigma|-1)}(\sigma(|\sigma| - 1)),$$

où l'on dénote ici — comme d'usage — la concaténation par $\wedge$. Par exemple, si $h(n) = n + 1$, alors $g(n) = 2^{h(n)} = 2^{n+1}$, et

$$e(032) = e_1(0) \wedge e_2(3) \wedge e_3(2) = 0 \wedge 11 \wedge 010 = 011010.$$

Notons que l'ensemble $\hat{S} = \{e(\sigma) : \sigma \in T\}$ n'est pas un arbre, car il n'est clos par préfixe que pour les segments initiaux de longueur exactement Im $g$. Nous devons donc définir l'arbre $S$ comme la clôture par préfixe de $\hat{S}$, autrement dit $S = \{e(\sigma) |_n : \sigma \in T \wedge n \in \mathbb{N}\}$. La fonction de codage $e$ étant monotone sur les longueurs, et l'ensemble $T$ étant clos par préfixe, $\rho \in S$ si, et seulement si, il existe une chaîne $\sigma \in g^{<\mathbb{N}}$ de longueur au plus $|\rho|$ telle que $\rho < e(\sigma)$. Ainsi, $S$ est un arbre binaire calculable infini, dont les chemins sont exactement les suites infinies de la forme $e_{h(0)}(P(0)) \wedge e_{h(1)}(P(1)) \wedge \dots$, pour $P \in [T]$. Dès lors, $\deg([T]) = \deg([S])$. ■

**Corollaire 7.9**

Soit $T \subseteq \mathbb{N}^{<\mathbb{N}}$ un arbre infini calculable et calculatoirement borné. Tout degré PA calcule un chemin de $T$.

**PREUVE.** Par la proposition 7.8, il existe un arbre binaire $S \subseteq 2^{<\mathbb{N}}$ tel que $\deg([T]) = \deg([S])$. Par le théorème 6.8, tout degré PA calcule un chemin de $S$, donc tout degré PA calcule un chemin de $T$. ■

Nous voyons à présent la réciproque de la proposition 7.4, qui montre que les degrés PA relativement à $\emptyset'$ sont exactement ceux permettant de calculer un chemin dans un arbre calculable à branchement fini.
**Proposition 7.10.** Soit $T \subseteq \mathbb{N}^{<\mathbb{N}}$ un arbre calculable infini à branchement fini. Il existe $S \subseteq 2^{<\mathbb{N}}$ un arbre binaire $\Delta_2^0$ tel que $\deg([T]) = \deg([S])$. ★

PREUVE. Notons tout d'abord que tout arbre calculable infini à branchement fini $T \subseteq \mathbb{N}^{<\mathbb{N}}$ est $\emptyset'$-calculatoirement borné, c'est-à-dire qu'il existe une fonction $\emptyset'$-calculable $g : \mathbb{N} \to \mathbb{N}$ telle que $T \subseteq g^{<\mathbb{N}}$. La preuve de la proposition 7.8 se relativise à $\emptyset'$, et permet de définir $S \subseteq 2^{<\mathbb{N}}$ un arbre binaire $\Delta_2^0$ tel que $\deg([T]) = \deg([S])$. ■

Donnons pour finir quelques exercices. La clôture par préfixe d'un ensemble $S \subseteq \mathbb{N}^{<\mathbb{N}}$ est l'ensemble

$$ \hat{S} = \{ \tau \in \mathbb{N}^{<\mathbb{N}} : \exists \sigma \in S \ \tau \preceq \sigma \}. $$

**Exercice 7.11.** Montrer que pour tout ensemble infini $S \subseteq 2^{<\mathbb{N}}$, sa clôture par préfixe admet un chemin. ◇

**Exercice 7.12.** Montrer qu'il existe un ensemble infini calculable $S \subseteq 2^{<\mathbb{N}}$ tel que $[\hat{S}] = \{\emptyset'\}$. ◇

**Exercice 7.13. (★★)** Montrer que pour tout arbre $T \subseteq 2^{<\mathbb{N}}$ infini et $\emptyset'$-calculable, il existe un ensemble infini $S \subseteq 2^{<\mathbb{N}}$ contenant exactement une chaîne de chaque longueur, tel que $[T] = [\hat{S}]$. ◇
Schéma Récapitulatif

Voici une figure qui récapitule les différentes notions abordées jusqu'ici.

<figure><img src="image_63.png" /><figcaption>FIGURE 7.14 – Récapitulatif sur les degrés Turing vus jusqu'ici. Les points (1) à (6) renvoient vers des exemples d'ensembles de chaque type. Les points de (7) à (15) renvoient vers l'existence d'une classe parfaite d'ensembles de chaque type (et donc d'après l'exercice 5.4 vers l'existence d'une classe parfaite de degrés Turing de chaque type).</figcaption></figure>
Les points de (1) à (15) qui suivent utilisent pour certains des concepts qui ne seront vus que dans les chapitres suivants.

(1) Il existe un degré Turing $\Delta_2^0$ non DNC et high : il suffit de mixer la preuve de l'exercice 4-10.6 avec celle de l'exercice 7-2.9 pour obtenir un ensemble high qui en plus d'être incomplet, ne soit pas DNC.

(2) Il existe un degré Turing $\Delta_2^0$ DNC, non PA et high : On part d'un ensemble $X$ DNC, non PA et low (par le théorème 18-4.1 et le corollaire 18-2.3, on peut prendre par exemple un aléatoire au sens de Martin-Löf low). On peut ensuite broder sur la construction de l'exercice 4-10.6 et sur celle aussi de l'exercice 7-2.9 pour construire un ensemble $Y$ $\Delta_2^0$ high tel que $X \oplus Y$ est non PA (en utilisant en particulier le fait que $X' \le_T \emptyset'$).

(3) Il existe un degré Turing $\Delta_2^0$ incomplet, PA et high : on part d'un ensemble $X$ PA et low (voir le corollaire 6.5). On brode ensuite sur la construction de l'exercice 4-10.6 pour construire un ensemble $Y$ $\Delta_2^0$ high tel que $X \oplus Y$ est incomplet.

(4) Il existe un degré Turing $\Delta_2^0$ non DNC, hyperimmune et non high : il suffit de construire un ensemble non DNC et low, en mélangeant la proposition 4-9.1 et l'exercice 7-2.9.

(5) Il existe un degré Turing $\Delta_2^0$ DNC, non PA, hyperimmune et non high : il suffit de considérer un ensemble aléatoire au sens de Martin-Löf et low. D'après le théorème 18-4.1, un tel ensemble est DNC. D'après le théorème 19-1.7, il n'est pas PA. D'après la proposition 7-4.7, il est hyperimmune. Enfin, comme il est low il ne peut être high.

(6) Il existe un degré Turing $\Delta_2^0$ PA, hyperimmune et non high : d'après la proposition 7-4.7, il suffit de considérer un degré PA low donné par le corollaire 6.5.

(7) Il existe une classe parfaite d'ensembles high et non DNC. Il suffit d'utiliser le théorème 10-3.21 et de broder sur Posner/Robinson (voir le corollaire 10-3.34) pour construire un classe parfaite d'ensembles 1-génériques et high.

(8) Il existe une classe parfaite d'ensembles hyperimmunes, non high et non DNC. D'après le théorème 10-3.2, la proposition 10-3.38 et le corollaire 10-3.34 tout ensemble suffisamment générique sera dans ce cas-là.

(9) Il existe une classe parfaite d'ensembles calculatoirement dominés et non DNC. Il faut reprendre la construction d'ensembles calculatoirement dominés via des f-arbres, et la modifier pour produire des ensembles non DNC à la manière dont cela est fait dans l'exercice 7-2.9.

(10) Il existe une classe parfaite d'ensembles high, DNC et non PA. On peut appliquer le théorème 18-3.4 de Kučera/Gács relativisé à $\emptyset'$ sur l'arbre des 2-aléatoires pour construire des ensembles high et 2-aléatoires. Par
le théorème 18-4.1, de tels ensembles sont DNC. Par le théorème 19-1.7, ils ne sont pas PA.

(11) Il existe une classe parfaite d'ensembles hyperimmunes, non high, DNC et non PA. D'après le théorème 18-4.1, le corollaire 19-3.9 et le corollaire 19-1.8, c'est le cas pour tout ensemble suffisamment aléatoire.

(12) Il existe une classe parfaite d'ensembles calculatoirement dominés, DNC et non PA. Il s'agit du théorème 5.1 appliqué à une classe $\Pi_1^0$ ne contenant que des aléatoires au sens de Martin-Löf. D'après le théorème 19-1.7, les ensembles MLR et calculatoirement dominés ne peuvent être PA.

(13) Il existe une classe parfaite d'ensembles incomplets, high et PA. On fixe un ensemble $X$ high et incomplet. On élabore ensuite sur le théorème 4.7 de base d'évitement de cône relativisé à $X$, pour construire une classe parfaite d'ensembles PA $Y$ tel que $X \oplus Y$ est incomplet.

(14) Il existe une classe parfaite d'ensembles hyperimmunes, non high et PA. Soit $X$ un ensemble hyperimmune et non high. On utilise la relativisation à $X$ du théorème 5.1, appliqué à la classe $\Pi_1^0$ des ensembles $DNC_2$, pour construire une classe parfaite d'ensembles $Y$ tels que toute fonction calculée par $X \oplus Y$ est dominée par une fonction calculée par $X$.

(15) Il existe une classe parfaite d'ensembles calculatoirement dominés et PA. Il s'agit du théorème 5.1 appliqué à la classe $\Pi_1^0$ des ensembles $DNC_2$.
<figure><img src="image_64.png" /></figure>
Chapitre 9

Interlude formel

1. Un peu d'histoire : la crise des fondements

Les mathématiques se sont développées naturellement au fil des siècles en tant qu'outil au service d'une représentation abstraite de la réalité. Cet état de fait est par exemple flagrant en sciences physiques pour lesquelles les mathématiques rendent compte avec précision d'un ensemble varié de phénomènes. Avec le temps, les notions étudiées sont devenues de plus en plus complexes, de plus en plus abstraites, et les connexions entre les mathématiques et le monde réel sont devenues de plus en plus incertaines. Pendant longtemps, la discipline a cependant pu compter sur le sens logique inné de l'esprit humain pour parler de choses que l'on ne « voyait plus » tout en gardant un cadre rigoureux. Les nombres complexes en constituent un exemple frappant : les nombres de carré négatif qui n'existent a priori que dans l'imagination du mathématicien sont baptisés en 1545 par Cardan « quantités sophistiquées ». De la sophistication il en fallait sans doute pour accepter cet ovni comme objet d'étude sérieux. Pourtant ces « quantités sophistiquées » trouvent leur utilité dans la résolution de problèmes, eux, très concrets. Raphaël Bombelli en donne une première formalisation en 1572, et montre comment utiliser ces nombres pour résoudre certaines équations du troisième degré. Ils trouveront au fil des siècles de nombreuses utilités en mathématiques, ainsi qu'en physique, où ils sont utilisés avec succès au sein d'équations représentant le monde réel.

Il a fallu un certain saut conceptuel pour accepter le développement d'un cadre mathématique rigoureux et cohérent autour des nombres complexes. Disons, malgré tout, que ce concept pour aussi surprenant qu'il soit, reste encore « relativement simple ». Les véritables problèmes arrivent avec les
travaux de Cantor sur la cardinalité et les nombres transfinis. Cantor ouvre grand la porte sur un gouffre sans fond, qui nous emmène bien au-delà de ce que peut appréhender avec confiance l'esprit humain : l'étude de l'infini. Bien sûr, l'infini est présent en mathématique depuis l'antiquité, en premier lieu via la considération qu'il n'existe pas de plus grand nombre entier. Mais la révolution épistémologique de Cantor consiste à considérer l'infini comme un objet d'étude à part entière. Cette considération amènera aux balbutiements de ce qui deviendra un siècle plus tard la Théorie des ensembles avec un grand 'T'.

Avec les travaux de Cantor, la question de savoir *ce qu'est* l'activité mathématique s'est faite de plus en plus pressante : peut-on raisonner vraiment sur tout, et même sur l'infini, concept qui nous dépasse ? Mais si l'on accepte, comme c'est le cas aujourd'hui que l'on peut raisonner sur l'infini, on ne peut certainement pas le faire n'importe comment. Au fond, qu'est-ce faire des mathématiques ? En particulier quand on commence à manipuler des objets sur lesquels nous n'avons plus tellement d'intuition, comment être sûr que ce dont on parle a réellement un sens ? Ces considérations ont trouvé leur apogée lors de la fameuse « crise des fondements », qui va de la fin du XIXe siècle au début du XXe. Il s'agit alors de définir des règles pour encadrer l'activité mathématique. Il s'agit en fait de définir précisément l'étude mathématique non pas d'objets comme les entiers, les réels ou encore les fonctions, mais de définir l'étude mathématique des mathématiques elles-mêmes. Il est a posteriori remarquable de constater le succès de cette entreprise : les mathématiques sont un outil suffisamment puissant pour pouvoir se définir et s'étudier elles-mêmes, avec la rigueur inhérente à la discipline ! Ce ne fut évidemment pas un chemin aisé. Dans cette entreprise, les trois mousquetaires — qui comme on le sait sont en fait au nombre de quatre — s'appellent Frege, Russell, Zermelo et Hilbert.

## Frege

Philosophe et mathématicien allemand de la fin du XIXe siècle, Gottlob Frege est mu par une certitude : la logique précède les mathématiques. Mais la logique de l'époque est encore très pauvre, et se cantonne essentiellement aux travaux de George Boole sur ce que l'on appelle aujourd'hui *le calcul propositionnel* : la manipulation de propositions, vraies ou fausses, que l'on peut connecter entres elles via les « et » et « ou » logiques, bien connus des informaticiens. Pour l'ambition de Frege, ce système est trop restreint pour asseoir les mathématiques sur des fondations logiques. En particulier, rien dans le calcul propositionnel ne permet de parler d'objets spécifiques à travers les relations qu'ils entretiennent les uns avec les autres. Il formalise alors dans son ouvrage le « Begriffsschrift » un nouveau langage afin de
palier aux carences de la logique de l'époque, langage qui évoluera pour de-
venir ce que l'on appelle aujourd'hui *le calcul des prédicats*, omniprésent en
mathématiques.

Frege est aujourd'hui considéré comme
le père de la logique moderne, no-
tamment via son concept de variables
quantifiées ∀x..., ∃x... Il utilise son
formalisme pour s'atteler dans ses
ouvrages suivants, « Fondements de
l'arithmétique » (1884) et « Lois fonda-
mentales de l'arithmétique I et II » (pa-
rus en 1893 et 1903), à fonder
l'arithmétique sur la logique. Il crée
pour cela une définition des entiers na-
turels qui peut être vue aujourd'hui
comme reposant sur le concept d'en-
semble et sur celui du schéma d'axiomes
de compréhension : si Ψ(x) est une for-
mule mathématique qui peut être vraie
ou fausse en fonction de x, alors l'en-

semble {x : Ψ(x)} des éléments qui satisfont cette formule est bien défini.

<figure><img src="image_65.png" /><figcaption>Gottlob Frege, 1848-1925</figcaption></figure>

Russell

En 1902, Russell dans une lettre
adressée à Frege lui fait part d'un doute
concernant ses travaux. Soit y l'en-
semble des ensembles qui ne s'appar-
tiennent pas : y = {x : x ∉ x}. A-t-on
alors y ∈ y ou bien y ∉ y ? On com-
prend aisément la situation paradoxale
à laquelle on arrive. Cet exemple res-
tera célèbre comme étant *le paradoxe de
Russell*. À 53 ans, Frege comprend alors
que le paradoxe de Russell implique l'ef-
fondrement du système qu'il a mis des
années à échafauder. Un coup dur dont
il aura beaucoup de mal à se remettre.

Malgré ce paradoxe, Russell accueille
avec beaucoup d'enthousiasme les tra-
vaux de Frege, et contribue largement à

en faire reconnaître la valeur. Tout comme Frege, Russell sent le besoin
d'appuyer les mathématiques sur des bases solides. Tout comme Frege,

<figure><img src="image_66.png" /><figcaption>Bertrand Russell, 1872-1970</figcaption></figure>
Russell a cette intuition que la logique précède les mathématiques. Il va s'atteler dix ans durant, avec son ancien professeur Alfred Whitehead, à cette recherche de fondements logiques, qui aboutiront à leur fameux ouvrage « Principia Mathematica » : un travail titanesque qui s'étend sur plus de 2000 pages, dont l'ambition est de décrire un ensemble d'axiomes logiques et de règles d'inférence à partir desquelles toute vérité mathématique pourrait être démontrée. Ces travaux posent les fondements de ce que l'on appelle aujourd'hui la théorie des types, un système encore étudié aujourd'hui, présentant des liens très forts avec les langages de programmation. En parallèle, s'est développée la théorie des ensembles dont l'axiomatisation a été initiée par Zermelo, et complétée plus tard par Fraenkel et Skolem indépendamment, pour donner le système axiomatique ZF, du nom de Zermelo-Fraenkel.

## Zermelo

Un fait absolument remarquable est que le système ZF, auquel il est parfois nécessaire de rajouter l'axiome du choix, donne un cadre au sein duquel peuvent se formaliser la totalité des mathématiques modernes, si l'on exclut les récents développements de la théorie des ensembles, dont l'objectif est jument de sortir de ce système. Zermelo trouve le moyen d'éviter le fameux paradoxe de Russell — comme Russell lui-même avec sa théorie des types — en bornant l'axiome de compréhension. L'ensemble $\{x : \Psi(x)\}$ n'est désormais plus valide, il convient de partir d'un ensemble existant $y$, auquel cas on peut à présent définir l'ensemble des éléments

de $y$ qui satisfont $\Psi : \{x \in y : \Psi(x)\}$. Pourtant, cette théorie ne fait pas tout de suite consensus. Poincaré, s'il n'a jamais activement pris part à la crise des fondements, en a suivi les développements avec intérêt. Comme tous les protagonistes de l'époque, il est très conscient du danger qui se cache derrière le paradoxe de Russell. Il théorise même le problème sous le nom d'imprédicativité<fnref n="1" /> : une définition imprédicative est en substance une définition circulaire dans laquelle l'objet qui est défini est lui-même susceptible d'être utilisé dans la définition. C'est ce qui se passe quand on définit $y = \{x : x \notin x\}$ : l'ensemble $y$ défini à gauche de l'égalité est aussi

<figure><img src="image_67.png" /><figcaption>Ernst Zermelo, 1871-1953</figcaption></figure>

<footnote n="1">1. Utilisé auparavant par Russell dans un sens légèrement différent.</footnote>
concerné à droite du signe égal, puisque l'on considère potentiellement tous les ensembles. Si l'axiomatique de Zermelo évite le paradoxe de Russell, il reste néanmoins, indirectement imprédicatif, comme le remarquera Poincaré qui écrira [176] :

> « *En posant d'avance son ensemble M* [Poincaré parle alors de la borne utilisée par Zermelo dans l'axiome de compréhension, qui permet de définir pour un ensemble M existant {$x \in M : \Psi(x)$}, il [Mr. Zermelo] a élevé un mur de clôture qui arrête les gêneurs qui pourraient venir du dehors. Mais il ne se demande pas s'il peut y avoir des gêneurs du dedans qu'il a enfermés avec lui dans son mur. Si l'ensemble M a une infinité d'éléments, cela veut dire non que ces éléments puissent être conçus comme existant d'avance tout à la fois, mais qu'il peut sans cesse en naître de nouveaux; ils naîtront à l'intérieur du mur, au lieu de naître dehors, voilà tout. »

Le système de Zermelo considère que si un ensemble A existe, alors l'ensemble de ses parties $P(A)$ existe également. Cet axiome combiné avec l'axiome de compréhension restreint permet de faire des définitions circulaires. Ainsi, dans la définition $A = \{n \in \mathbb{N} : \forall S \in P(\mathbb{N}) n \notin S\}$, le quantificateur $\forall S$ va prendre pour valeur tous les sous-ensembles de $\mathbb{N}$, et en particulier l'ensemble A lui-même. L'ensemble A est donc défini en fonction de lui-même. Poincaré ajoute alors à la fin de son argumentation :

> « Mais s'il [Mr. Zermelo] a bien fermé sa bergerie, je ne suis pas sûr qu'il n'y ait pas enfermé le loup. Je ne serais tranquille que s'il avait démontré qu'il est à l'abri de la contradiction. »

On peut difficilement donner tort à Poincaré : comment être sûr au fond qu'un paradoxe de Russell ne surgira pas de nulle part, au détour d'une définition circulaire cachée ? Zermelo lui-même est conscient du problème, et cherchera à démontrer sans succès que son système axiomatique est *cohérent*, c'est-à-dire exempt de paradoxe. Cette recherche de preuve de la cohérence des mathématiques a connu son apogée vers 1920, sous l'impulsion de David Hilbert.

## Hilbert

Hilbert est certainement — tout comme Poincaré — un des derniers mathématiciens à avoir une connaissance approfondie de l'ensemble des mathématiques de son époque. Son œuvre est considérable, et il a profondément influencé les développements de la discipline durant le XXe siècle. Il participe activement à la crise des fondements en opposant à Russell une vision *formaliste* des mathématiques, plutôt qu'une vision *logiciste*. Pour Hilbert, les mathématiques doivent pouvoir se réduire à un ensemble de règles, que l'on doit pouvoir appliquer de façon purement mécanique et déconnectée de toute psychologie du mathématicien. Il imagine ainsi des systèmes de preuve, au sein desquels il différencie les axiomes, qui sont les
phrases mathématiques que l'on suppose vraies, par exemple les axiomes de Zermelo-Fraenkel, et les règles de déduction, qui permettent de combiner les axiomes entre eux pour en déduire des théorèmes. C'est la vision de Hilbert qui finira par s'imposer, même si cela ne se sera pas accompli sans remous. L'objectif ultime pour Hilbert est de montrer via des systèmes de déduction considérés comme sûr — en particulier via des raisonnements finis sur des objets finis — que l'ensemble des mathématiques, qui elles font appel à des objets infinis dont la pertinence est sujette à caution, forme un système cohérent, c'est-à-dire exempt de paradoxe : c'est ce que l'on appellera le programme de Hilbert, dont le Entscheidungsproblem évoqué dans la section 6-1 constitue l'un des aspects. Ce programme connaîtra un coup d'arrêt brutal avec les travaux de Gödel, qui démontre dix ans plus tard son fameux théorème d'incomplétude : l'arithmétique elle-même est impuissante à démontrer qu'elle est exempte de paradoxe.

David Hilbert, 1862–1943

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

## Le cinquième mousquetaire

Les travaux de Gödel apportent une conclusion aussi magistrale qu'inattendue à la crise des fondements. Gödel montre deux choses : même les systèmes les plus simples et les mieux compris, comme l'arithmétique, qui ne parle que d'objets finis, contiennent des vérités indémontrables. En particulier, et à supposer qu'il soit vrai que les axiomes de l'arithmétique forment un système exempt de paradoxes, alors la cohérence de l'arithmétique est elle-même l'une de ces vérités indémontrables. Gödel montre enfin — avec l'aide de Rosser — que l'ajout d'axiomes ne change rien à l'affaire : n'importe quel système d'axiomes cohérent, contenant l'arithmétique, et « dont on peut connaître les axiomes » ne peut démontrer sa propre cohérence. Gödel développe pour cela les premières versions de ce qui sera plus tard la calculabilité : « dont on peut connaître les axiomes » signifie calculable, dans un sens similaire au sens moderne.

Le retentissement dans le monde mathématique est colossal. Le programme de Hilbert est à terre, et les mathématiques n'auront jamais de fondations entièrement satisfaisantes.
Encore aujourd'hui, on ne sait pas si le système ZF qui axiomatise l'ensemble des mathématiques est cohérent : et pour cause, si comme on l'espère il est bien exempt de paradoxe, on ne pourra jamais le démontrer mathématiquement, ou en tout cas tant que l'on se cantonne aux axiomes de ZF. L'impact épistémologique est considérable. Les mathématiques, mère des sciences exactes, sont non seulement tributaires d'une *croyance*, mais sont en plus capables de démontrer qu'il en sera toujours ainsi !

<figure><img src="image_69.png" /><figcaption>Kurt Gödel, 1906-1978</figcaption></figure>

## 2. La logique du premier ordre

De Frege et Russell on retiendra le langage logique moderne utilisé en mathématiques, de Hilbert on retiendra un système de preuve à base d'axiomes et de règles de déductions applicables aux énoncés mathématiques, et de Zermelo on retiendra le système axiomatique ZF ou ZFC, suffisant pour formaliser l'ensemble des mathématiques traditionnelles. Nous présentons à présent sans rentrer dans trop de détails les principes de base de la logique du premier ordre, notre objectif étant de présenter de manière un peu plus précise le théorème de Gödel et ses conséquences. Pour cette raison, le fil rouge de notre présentation sera l'exemple spécifique de l'arithmétique de Peano.

### 2.1. Langage de l'arithmétique

La première étape pour formaliser nos démonstrations mathématiques est de fixer le langage utilisé. Nous allons pour cela définir le langage de l'arithmétique de Peano.

**Définition 2.1.** Le langage $\mathcal{L}_{PA}$ de l'arithmétique de Peano comprend les symboles spécifiques au calcul des prédicats :

(1) des symboles de variables $x, y, z, ...$ : elles représentent des entiers naturels;

(2) les parenthèses () et les symboles de connecteurs logiques : $\wedge, \vee, \rightarrow, \neg$;

(3) des symboles de quantificateurs : $\forall, \exists$.
Et ceux spécifiques à l'arithmétique de Peano :

(1) les symboles de fonctions binaires suivantes : +, × ;

(2) les symboles de relations binaires suivantes : =, < ;

(3) des symboles de constantes $\dot{0}, \dot{1}$.

◇

Un langage n'est rien d'autre qu'une liste de symboles, mais ces symboles ont vocation à être utilisés avec un sens précis. En ce qui concerne le calcul des prédicats, il s'agit du sens usuel : par exemple, « $\land$ » est le et logique ou encore « $\exists$ » est la quantification existentielle. En ce qui concerne les symboles spécifiques à l'arithmétique de Peano, il y a d'abord les fonctions + et × qui représentent respectivement l'addition et la multiplication, les symboles d'égalité et d'inégalité qui ont leurs sens usuels sur les entiers, et enfin les constantes $\dot{0}, \dot{1}$ qui chacune représente l'entier respectif correspondant.

## Langages du premier ordre

On voit sans peine comment généraliser la définition précédente pour obtenir d'autres langages. Les symboles spécifiques au calcul des prédicats sont les mêmes dans tous les langages du premier ordre, auxquels on ajoute un nombre arbitraire de symboles de fonctions (n-aire pour des entiers n arbitraires), un nombre arbitraire de symboles de relations (également n-aire pour des entiers n arbitraires) et un nombre arbitraire de symboles de constantes.

Les symboles de fonctions sont soumis à des règles d'agencement pour former ce que l'on appelle les termes du langage.

**Définition 2.2.** Les termes du calcul des prédicats de l'arithmétique sont définis inductivement de la manière suivante.

(1) Une variable ou une constante est un terme.

(2) Si $t_1, t_2$ sont des termes, alors $(t_1 + t_2)$ et $(t_1 \times t_2)$ sont des termes. ◇

**Exemple 2.3.** Les expressions suivantes sont des termes :

$$x, (((((x + \dot{1}) + \dot{1}) + \dot{1}) + \dot{1}), (\dot{1} + \dot{0})), (x + (y \times z)).$$

Comme nous pouvons le voir, le langage de l'arithmétique est assez minimaliste, et les expressions valides sont très structurées pour ôter toute ambiguïté.

En pratique, on utilisera un certain nombre de raccourcis de notation pour améliorer la lisibilité, tant que la traduction en termes valides est non ambigüe. Par exemple, $t_0 + t_1 + t_2$ est un raccourci pour $((t_0 + t_1) + t_2)$. De même, $x + \dot{3}$ est un raccourci pour $(x + ((\dot{1} + \dot{1}) + \dot{1}))$.
**Définition 2.4.** Un terme est clos s'il ne contient aucune variable, et donc uniquement des constantes et les opérations $+$ et $\times$. ◇

Intuitivement, un terme clos de l'arithmétique est une manière de représenter un entier naturel. Par exemple, $(\dot{1} + \dot{1}) \times \dot{0}$ est un nom pour l'entier 0. Les entiers possèdent chacun une infinité de noms.

**Exemple 2.5.** Le terme $x+\dot{1}$ n'est pas clos, contrairement à $(\dot{1}+\dot{1}) \times \dot{0}$.

Si les symboles de fonctions sont utilisés pour créer les termes du langage, les symboles de relations sont eux utilisés pour créer les *formules* du langage.

**Définition 2.6.** Les *formules de l'arithmétique* sont définies comme suit.

(1) Pour tous termes $t_1, t_2$, alors $t_1 = t_2$ et $t_1 < t_2$ sont des formules. Ces formules sont appelées *formules atomiques*. Les formules atomiques auxquelles on ajoute leurs négations, ici, $\neg t_1 = t_2$ et $\neg t_1 < t_2$, sont appelées *littéraux*.

(2) Pour toutes formules $F_1, F_2$, alors $(F_1 \land F_2), (F_1 \lor F_2), (F_1 \rightarrow F_2)$ et $\neg F_1$ sont des formules.

(3) Pour toute formule $F$, alors $\forall xF$ et $\exists xF$ sont des formules. ◇

Là encore, on aura recours au sucre syntaxique en notant $t_1 \le t_2$ la formule $(t_1 < t_2) \lor (t_1 = t_2)$ et $F_1 \leftrightarrow F_2$ la formule $(F_1 \rightarrow F_2) \land (F_2 \rightarrow F_1)$.

## Formules de premier ordre

Ici aussi, on généralise sans peine la formation de formules et de termes dans n'importe quel langage : les symboles de fonction du langage servent à créer les termes, qui servent ensuite avec l'aide des symboles de relation à créer des formules atomiques, qui peuvent ensuite être composées entre elles avec l'aide des symboles du calcul des prédicats comme dans (2) et (3) de la définition précédente.

Avec les quantificateurs apparaissent les notions de variables *libres* et de variables *liées* : les variables *liées* sont sans surprise celles qui sont liées à un quantificateur, et les variables libres sont celles qui ne le sont pas. La définition formelle est assez lourde, mais quelques exemples suffisent à s'en créer une intuition.

**Exemple 2.7.** Dans la formule $\prec \forall x \exists y (y = x + \dot{1})$, les variables $x$ et $y$ sont liées, alors que dans la formule $\prec \exists y (y = x + 1)$ seule la variable $y$ est liée, contrairement à la variable $x$ qui est libre.
**Définition 2.8.** Une formule close ou un énoncé est une formule dans laquelle aucune variable n’est libre. ◇

**Notation**

Étant donné une formule *F* ayant pour variables libres *x*₁, ..., *x*ₙ, on écrira *F*(*x*₁, ..., *x*ₙ) pour signifier que les variables libres de *F* sont *x*₁, ..., *x*ₙ.

Intuitivement, une formule close est une affirmation qui aura une valeur de vérité (vraie ou fausse) une fois évaluée sur les entiers. Les formules possédant des variables libres définissent quant à elles des prédicats sur les entiers.

## 2.2. Les systèmes de déduction à la Hilbert

Afin de formaliser mathématiquement la notion de démonstration, Hilbert a imaginé un système de règles bien précises qui suffisent à montrer « tout ce qui est démontrable ». Comment le sait-on ? Cette idée sera rendue précise avec le théorème de complétude de Gödel à venir. Par la suite, de nombreux autres systèmes de démonstration ont été développés, tous équivalents et plus ou moins adaptés à certains objectifs.

### 2.2.1. Axiomes et règles

Dans un système à la Hilbert, une démonstration est une liste finie de phrases mathématiques $F_0, F_1, F_2, \dots, F_n$ — des formules dans le langage considéré — satisfaisant les règles suivantes : pour tout $i \le n$, soit $F_i$ est un axiome, soit $F_i$ est produit à partir de règles d'inférence appliquées à des formules $F_{j_1}, \dots, F_{j_m}$ pour $\hat{j}_1, \dots, \hat{j}_m < i$. Chaque phrase $F_i$ dans cette liste sera alors démontrée, l'objectif étant normalement d'obtenir $F_n$, la dernière d'entre elles. Voyons à présent un exemple précis de système à la Hilbert suffisamment puissant pour démontrer tout ce qui est démontrable.

**Les axiomes** : les axiomes que nous pouvons toujours utiliser sont les tautologies de la logique du premier ordre. Ainsi, par exemple $A \lor \neg A$ pourra être utilisé comme axiome. On en distingue trois types.

1. Les tautologies de la logique propositionnelle. Par exemple, $(F \rightarrow G) \rightarrow (\neg G \rightarrow \neg F)$ est une tautologie de la logique propositionnelle : elle sera vraie pour n'importe quelle formule *F* ou *G* indépendamment de leur valeur de vérité.

2. Les tautologies du calcul des prédicats. En pratique, seuls quatre schémas d'axiomes sont nécessaires :

(a) $\forall x(F \rightarrow G) \rightarrow (F \rightarrow \forall xG)$ pour toute formule *F* ne contenant pas la variable *x*, et toute formule *G*;
(b) $\exists x(F \rightarrow G) \rightarrow (\exists xF \rightarrow G)$ pour toute formule $F$, et toute formule $G$ ne contenant pas la variable $x$;

(c) $\forall xF \rightarrow F_{t/x}$ pour tout terme $t$ et toute formule $F$ ne contenant aucune variable de $t$;

(d) $F_{t/x} \rightarrow \exists xF$ pour tout terme $t$ et toute formule $F$ ne contenant aucune variable de $t$.

Ci-dessus, $F_{t/x}$ désigne la formule $F$ pour laquelle chaque occurrence de $x$ est remplacée par le terme $t$.

3. Les axiomes de l'égalité :

(e) $t = t$ pour tout terme $t$;

(f) $t_1 = q_1 \wedge \dots \wedge t_n = q_n \rightarrow f(t_1, \dots, t_n) = f(q_1, \dots, q_n)$ pour tout $n$, tous termes $(t_i)_{1 \le i \le n}$, $(q_i)_{1 \le i \le n}$ et tout symbole de fonction $n$-aire $f$;

(g) $t = q \rightarrow (F(t/z) \rightarrow F(q/z))$ pour tous termes $t, q$ et toute formule $F(z)$ ne faisant pas intervenir des variables de $t$ ou $q$.

Ci-dessus, $F(t/z)$ et $F(q/z)$ désignent la formule $F$ dans laquelle chaque occurrence de $z$ est remplacée respectivement par $t$ et $q$.

Notons que ces schémas d'axiomes dépendent du langage considéré, chaque langage utilisant des symboles de fonctions et relations qui leur sont spécifiques pour construire respectivement les termes et les formules atomiques.

**Symbole d'égalité**

Nous considérons ici que le symbole d'égalité fait nécessairement partie du langage que l'on utilise, et aura toujours son sens usuel, ce qui justifie les axiomes de l'égalité mentionnés ci-dessus.

**Les règles d'inférence.** Les règles d'inférence permettent de combiner des phrases déjà démontrées dans notre liste, pour en obtenir de nouvelles. Les deux règles suivantes sont suffisantes.

1. **Règle 1 : le Modus Ponens, à la base de tout raisonnement déductif.** Si $A \rightarrow B$ est démontré et si $A$ est démontré, alors on peut en déduire $B$.

2. **Règle 2 : la généralisation.** Si $F(x)$ est démontré pour une variable $x$ libre dans $F$, on peut alors en déduire $\forall xF(x)$. Cette règle est très utilisée en mathématiques : si l'on veut prouver par exemple que pour tous rationnels $x < y$, il existe un rationnel $z$ tel que $x < z < y$, on commence par fixer des variables rationnelles $x, y$ sur lesquelles on ne suppose rien d'autre que $x < y$. Si l'on arrive à déduire l'existence d'un rationnel $z$ tel que $x < z < y$, sans utiliser aucune propriété spécifique de $x, y$, on en déduit par la règle de généralisation que pour tous rationnels $x < y$, il existe un rationnel $z$ tel que $x < z < y$.
Cela conclut la description de notre système à la Hilbert. Voyons tout de
suite un exemple de démonstration.

**Exemple 2.9.** Montrons $\forall xF(x) \rightarrow \exists xF(x)$. Pour plus de lisibilité, on notera $A \equiv \forall xF(x)$, $B \equiv F(y)$ et $C \equiv \exists xF(x)$.

(1) $A \to B$ (axiome (c)).

(2) $B \to C$ (axiome (d)).

(3) $(A \to B) \to ((B \to C) \to ((A \to B) \land (B \to C)))$ (tautologie).

(4) $(B \to C) \to ((A \to B) \land (B \to C))$ (Modus Ponens sur (1) et (3)).

(5) $(A \to B) \land (B \to C)$ (Modus Ponens sur (2) et (4)).

(6) $((A \to B) \land (B \to C)) \to (A \to C)$ (tautologie).

(7) $A \to C$ (Modus Ponens sur (5) et (6)).

Quid des univers vides ?

Le lecteur pourra être surpris par la phrase $\forall xF(x) \rightarrow \exists xF(x)$ — que l’on a démontrée. Que se passe-t-il si l’on se place dans un univers vide ? À ce moment, $\forall xF(x)$ est bien vérifié, mais pas $\exists xF(x)$. L’axiome (d) ci-dessus implique effectivement que les formules démontrées ne seront valides que s’il existe au moins un élément dans notre univers. La notion d’univers sera rendue précise dans la section 2.4 à venir. Il est de fait nécessaire d’avoir une telle restriction si l’on veut démontrer que toute formule est équivalente à une formule sous forme prénexe (voir la définition 2.12).

2.2.2. Premiers outils

Nous prétendons que le système à la Hilbert décrit ci-dessus permet de
montrer tout ce qui est démontrable, et nous le verrons formellement avec
le théorème de complétude à venir. Le système est volontairement minima-
liste, et difficile à manipuler tel quel. Le lecteur pourra par exemple essayer
de démontrer $\neg\forall xF(x) \rightarrow \exists x \neg F(x)$ pour se rendre compte de la difficulté
d’utilisation du système en l’état. Le mathématicien qui veut faire ce genre
de preuve procèdera naturellement comme pour toute démonstration : en
supposant que $\neg\forall xF(x)$ est vrai, et en essayant d’en déduire $\exists x \neg F(x)$. Le
problème est que si l’on veut respecter le formalisme d’un système à la Hil-
bert, $\neg\forall xF(x)$ n’est pas nécessairement un axiome que l’on peut supposer
vrai afin d’en dériver une conclusion. Nous voyons alors notre premier outil
fondamental, qui va nous permettre de procéder comme on en a l’habitude.

**Lemme 2.10 (Lemme de déduction).** Soit $F$ une formule close. Si l’on peut faire une démonstration de $G$ en utilisant $F$ comme axiome, il existe alors une démonstration de $F \to G$ (qui n’utilise pas $F$ comme axiome). ★
PREUVE. Soit $G_1, \dots, G_n$ une démonstration de $G_n$ utilisant $F$ comme axiome. Montrons par récurrence sur la taille d'une démonstration que l'on peut faire quelques insertions dans la suite $F \to G_1, \dots, F \to G_n$ afin d'en faire une démonstration valide n'utilisant pas $F$ comme axiome.

Si $G_i$ est l'énoncé $F$, alors $F \to F$ est un axiome de la logique propositionnelle. Si $G_i$ est un axiome de la logique propositionnelle, alors c'est aussi le cas de $F \to G_i$. Si $G_i$ est l'un des axiomes (a), (b), (c), (d) du calcul des prédicats, alors $G_i \to (F \to G_i)$ est un axiome de la logique propositionnelle. En utilisant le Modus Ponens sur $G_i$ et $G_i \to (F \to G_i)$, on obtient bien $F \to G_i$. Si $G_i = \forall x G_j$ pour $j < i$ est obtenu par la règle de généralisation, alors $\forall x (F \to G_j)$ est obtenu à partir de $F \to G_j$ (que l'on a par hypothèse de récurrence) par la règle de généralisation. Par l'axiome (a), on a

$$ \forall x(F \to G_j) \to (F \to \forall x G_j), $$

de sorte que par Modus Ponens on obtient $F \to \forall x G_j$. Enfin, si $G_i = G_b$ est obtenu par Modus Ponens sur $G_a$, alors $G_a \to G_b$ pour $a, b < i$. Alors, on a $F \to G_a$ et $F \to (G_a \to G_b)$, par hypothèse de récurrence. La formule

$$ (F \to (G_a \to G_b)) \to ((F \to G_a) \to (F \to G_b)) $$

est une tautologie du calcul des prédicats.

Par Modus Ponens, on en déduit $(F \to G_a) \to (F \to G_b)$ et, par une deuxième application du Modus Ponens, on en déduit $F \to G_b$. ■

Voyons tout de suite un exemple d'application du lemme de déduction pour démontrer $\neg\forall x F(x) \to \exists x \neg F(x)$.

**Exemple 2.11.** Montrons $\neg\exists x F(x) \to \forall x \neg F(x)$. D'après le lemme de déduction, on peut supposer $\neg\exists x F(x)$ comme axiome.

(1) $\neg\exists x F(x)$ (axiome).

(2) $F(x) \to \exists x F(x)$ (axiome (d)).

(3) $(F(x) \to \exists x F(x)) \to (\neg\exists x F(x) \to \neg F(x))$ (tautologie).

(4) $\neg\exists x F(x) \to \neg F(x)$ (Modus Ponens sur (2) et (3)).

(5) $\neg F(x)$ (Modus Ponens sur (1) et (4)).

(6) $\forall x \neg F(x)$ (généralisation sur (5)).

Montrons à présent $\forall x \neg\neg F(x) \to \forall x F(x)$.

(1) $\forall x \neg\neg F(x)$ (axiome).

(2) $\forall x \neg\neg F(x) \to \neg\neg F(x)$ (axiome (c)).

(3) $\neg\neg F(x)$ (Modus Ponens sur (1) et (2)).

(4) $\neg\neg F(x) \to F(x)$ (tautologie).

(5) $F(x)$ (Modus Ponens sur (3) et (4)).

(6) $\forall x F(x)$ (généralisation sur (5)).
On laisse au lecteur le soin d'utiliser la contraposée pour en déduire

$$ \neg\forall x F(x) \rightarrow \exists x \neg F(x). $$

### 2.2.3. Forme prénexe

Ce système de démonstration nous permet d'établir que toute formule — dans un langage quelconque — est prouvablement équivalente à une formule sous forme prénexe.

**Définition 2.12.** Une formule est sous forme prénexe si elle est de la forme $Q_1x_1...Q_nx_n F(x_1,..., x_n, y_1,..., y_m)$ où chaque $Q_i$ est un quantificateur $\forall$ ou $\exists$ et $F(x_1,..., x_n, y_1,..., y_m)$ est une formule sans quantificateur. ◇

On laisse au lecteur le soin de montrer les équivalences suivantes :

$$ \Delta \forall x F \wedge G \equiv \forall x (F \wedge G); $$

$$ \Delta \forall x F \vee G \equiv \forall x (F \vee G); $$

$$ \Delta \exists x F \wedge G \equiv \exists x (F \wedge G); $$

$$ \Delta \exists x F \vee G \equiv \exists x (F \vee G). $$

Chacune de ces équivalences, couplées à l'exemple 2.11, permet de transformer n'importe quelle formule en une formule prénexe prouvablement équivalente dans notre système de déduction, en déplaçant petit à petit les quantificateurs vers la gauche.

Notons que les équivalences ci-dessus ne tiennent que si l'on se place dans un univers possédant au moins un élément. Ainsi, par exemple, aura-t-on $(\forall x (x = x) \wedge (\exists y (y \neq y)))$ manifestement faux dans un univers vide, alors que $\forall x (x = x \wedge (\exists y (y \neq y)))$ est toujours vrai.

## 2.3. Théories logiques et arithmétique de Peano

Une fois un langage fixé — dans notre cas celui de l'arithmétique — et le système de démonstration spécifié, on peut alors considérer une théorie mathématique dans ce langage, et l'utiliser pour démontrer des théorèmes concernant la structure décrite par cette théorie.

**Définition 2.13.** Une théorie $T$ dans un langage $\mathcal{L}$ est une collection de formules closes de ce langage. On utilise aussi souvent le terme système axiomatique ou plus simplement système pour désigner une théorie. ◇

La théorie est alors vue comme une liste d'axiomes, que l'on peut utiliser dans nos démonstrations, en plus des axiomes présents dans le système de démonstration.

Voyons tout de suite les axiomes de l'arithmétique qui furent mis au point par Peano vers la fin du XIXe siècle.
### 2.3.1. Axiomes de l'arithmétique de Peano

Les axiomes de Peano permettent de spécifier le comportement des entiers naturels. La première série d'axiomes définit le comportement des entiers vis-à-vis du successeur.

(1) $\forall x \neg(x + \dot{i} = \dot{0}) : 0$ n'a pas de prédécesseur.

(2) $\forall x (x = \dot{0} \lor \exists y (x = y + \dot{i})) : \text{tout entier différent de 0 a un prédécesseur.}$

(3) $\forall x \forall y (x + \dot{i} = y + \dot{i} \rightarrow x = y) : \text{la fonction successeur pour les entiers est injective.}$

Les axiomes suivants donnent des règles pour calculer l'addition et la multiplication :

(4) $\forall x (x + \dot{0} = x)$;

(5) $\forall x \forall y (x + (y + \dot{i}) = (x + y) + \dot{i})$;

(6) $\forall x (x \times \dot{0} = \dot{0})$;

(7) $\forall x \forall y (x \times (y + \dot{i}) = (x \times y) + x)$.

Enfin, on définit le comportement des entiers vis-à-vis de l'ordre :

(8) $\forall x \forall y (x < y \leftrightarrow (\exists z (z \neq \dot{0} \land x + z = y)))$.

**Notation**

On note $\mathbb{Q}$ la théorie composée des axiomes (1)-(8), qui forment ce que l'on appelle l'arithmétique de Robinson.

Pour obtenir l'arithmétique de Peano, on ajoute l'axiome suivant, pour toute formule de l'arithmétique $F(x)$ :

$$ (9) \quad (F(0) \land (\forall x (F(x) \rightarrow F(x + \dot{i})))) \rightarrow \forall x F(x) $$

Notons que l'axiome (9) n'est pas un unique axiome. Tout comme pour les axiomes (a), (b), (c), (d) de notre système de démonstration, il s'agit d'un schéma d'axiomes, c'est-à-dire d'une infinité d'axiomes paramétrés par une formule, ici $F(x)$.

L'énoncé (9) est l'axiome bien connu de l'induction sur les entiers : si une formule $F$ est vraie pour l'entier $0$, et si le fait qu'elle soit vraie pour $n$ implique qu'elle le soit pour $n + 1$, alors elle est vraie pour tout entier $n$.

**Notation**

On note PA la théorie composée de $\mathbb{Q}$ et du schéma d'axiome (9) pour toute formule de l'arithmétique. C'est cette théorie que l'on appelle *arithmétique de Peano*.

Nous verrons dans le chapitre 23 comment utiliser les axiomes de PA pour montrer quelques faits élémentaires sur les entiers naturels. Nous verrons
en particulier que le schéma d'induction est équivalent au schéma suivant : pour toute formule $F$ vraie pour au moins un entier, il existe un plus petit entier $x$ tel que $F(x)$ est vrai. Cela peut bien entendu sembler parfaitement évident, car nous avons en tête la structure des entiers naturels $\mathbb{N}$ que nous connaissons bien, mais une démonstration n'utilise pas cette structure : elle utilise uniquement les axiomes, et dans le cas de l'arithmétique, ceux-ci sont précisément faits pour que toute structure mathématique les vérifiant se comporte comme les entiers naturels. Cela nous amènera à la notion de *modèle*, dans la section suivante.

### 2.3.2. Démonstrations dans une théorie

Une fois que l'on a fixé une théorie, on peut en utiliser les axiomes au sein d'un système à la Hilbert pour démontrer des énoncés mathématiques.

**Notation**

On écrira $T \vdash F$ pour signifier qu'il existe une démonstration de la formule $F$ à partir des axiomes de $T$ via le système à la Hilbert exposé dans la section 2.2. S'il n'existe pas de telle démonstration, on écrira alors $T \nvDash F$.

Parmi les tautologies de la logique propositionnelle, on trouve pour toutes formules $F, G$ la formule $(F \land \neg F) \rightarrow G$, appelée « ex falso quodlibet », signifiant qu'à partir d'une contradiction $(F \land \neg F)$ on peut déduire ce que l'on veut. Il s'ensuit que si une théorie permet de prouver une formule et son contraire, tout énoncé est prouvable dans cette théorie, ce qui lui retire tout intérêt. On attendra donc avant tout d'une théorie qu'elle soit *cohérente*.

**Définition 2.14.** Une théorie $T$ est *cohérente* s'il n'existe aucune formule $F$ telle que $T \vdash F \land \neg F$. ◇

**Notation**

On écrira $T \vdash \bot$ pour signifier $T \vdash F \land \neg F$ pour une certaine formule $F$, la notation $T \nvDash \bot$ signifiant alors logiquement que pour toute formule $F$ on a $T \nvDash F \land \neg F$. Comme le symbole d'égalité fait partie de notre langage, on peut considérer sans perte de généralité $\bot$ comme étant $\neg x = x$. Comme $x = x$ est un axiome, si $T \vdash \neg x = x$, alors $T \vdash x = x \land \neg x = x$.

Nous avons vu dans l'introduction de notre interlude que l'incohérence trouvée par Russell dans le travail de Frege fut une pierre angulaire dans la crise des fondements. Aussi les mathématiciens aimeraient-ils autant que possible être certains de ne travailler qu'avec des théories cohérentes. Mais comment peut-on vérifier la cohérence d'une théorie ? Sans même parler de théorie, qu'en est-il de la cohérence du système à la Hilbert lui-même et
de ses axiomes de la logique, présentés dans la section 2.2 ? La notion de
*modèle* permet de résoudre ces questions.

**2.4. Structures, modèles et théorème de cohérence**

La notion de structure peut se définir de manière très générale pour tout
langage fixé. Commençons par l'exemple qui nous intéresse plus spécifiquement, à savoir le langage de l'arithmétique.

**Définition 2.15.** Une *structure* $\mathcal{M} = (M, +^M, \times^M, <^M, =^M, 0^M, 1^M)$
dans $\mathcal{L}_{\text{PA}}$ est donnée par :

▷ nn ensemble non vide $M$;

▷ des fonctions $+^M, \times^M : M \times M \to M$ correspondant aux symboles de fonction $+, \times$;

▷ une relation $<^M \subseteq M \times M$ correspondant au symbole de relation $<$;

▷ une relation $=^M \subseteq M \times M$ correspondant au symbole de relation $=$, et qui correspond à « la vraie égalité », c'est-à dire telle que

$$
(x, y) \in =^M \leftrightarrow x = y.
$$

▷ Des éléments $0^M, 1^M \in \mathcal{M}$ correspondant respectivement aux symboles de constante $0$ et $1$.

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

Une structure est donc un ensemble, ainsi que des fonctions, relations et constantes sur cet ensemble, constituant une interprétation des symboles du langage.

Par abus de notation, on confondra parfois $\mathcal{M}$ avec son *ensemble sous-jacent* $M$ (on notant par exemple $x \in \mathcal{M}$). Pour simplifier les notations, on supprimera parfois les exposants $^M$ lorsqu'il sera clair que l'on parle des fonctions et relations de la structure et non de symboles du langage.

**Structure du premier ordre**

On voit sans peine comment généraliser la définition précédente pour obtenir des structures pour tout langage du premier ordre. On a toujours un ensemble $M$ non vide. Chaque symbole de fonction $n$-aire $f$ correspond à une fonction de $f^M : M^n \to M$, chaque symbole de relation $n$-aire $R$ correspond à une relation $R^M \subseteq M^n$ et chaque symbole de constante $c$ correspond à une constante $c^M \in M$. La relation d'égalité sera toujours présente et correspondra toujours à « la vraie égalité ».

Une formule, comme par exemple

$$
F(x) = \exists y \ y \times (\dot{i} + \dot{i}) = x,
$$
n'est qu'une suite de symboles. Une fois fixée une structure $\mathcal{M}$, chaque symbole a vocation à être interprété par l'objet qui lui correspond dans $\mathcal{M}$; de plus, les variables libres pourront également être remplacées par divers paramètres — c'est-à-dire divers éléments — de la structure.

**Définition 2.16 (Formules paramétrées)**

Soit $\mathcal{L}$ un langage, et soit $\mathcal{M}$ une structure pour $\mathcal{L}$. Étant donné une formule $F(x_1, \dots, x_n)$ de $\mathcal{L}$ ayant comme variables libres $x_1, \dots, x_n$, et étant donné $a_1, \dots, a_n \in \mathcal{M}$, l'expression $F(a_1, \dots, a_n)$ désigne une formule paramétrée par $a_1, \dots, a_n$: il s'agit de la formule $F$ au sein de laquelle chaque occurrence libre de $x_i$ est remplacée par $a_i$ pour $1 \le i \le n$. Une formule paramétrée sans variable libre sera une formule paramétrée close. ◇

Une formule paramétrée close n'est plus une simple suite de symboles, mais un énoncé qui sera *vrai* ou *faux* dans la structure considérée.

**Remarque**

Notons que la notion de formule paramétrée induit celle de termes paramétrés. Ainsi, dans la structure usuelle des entiers pour le langage de l'arithmétique, $(5+4) \times 2$ sera un terme paramétré par les éléments 5, 4 et 2 de notre structure.

Nous définissons à présent la satisfaction dans une structure, pour les formules closes ou bien paramétrées dans cette structure.

**Définition 2.17.** Soit $\mathcal{L}$ un langage, et soit $\mathcal{M} = (M, \dots)$ une structure pour $\mathcal{L}$. On dit qu'une formule $F(x_1, \dots, x_n)$ de $\mathcal{L}$ est *vraie* dans $\mathcal{M}$ pour des paramètres $a_1, \dots, a_n \in \mathcal{M}$, et l'on note $\mathcal{M} \models F(a_1, \dots, a_n)$, si $F(a_1, \dots, a_n)$ est de fait vérifiée dans la structure. La définition se fait formellement par induction sur les formules (dans ce qui suit, $\bar{x}$ et $\bar{a}$ sont des raccourcis pour $x_1, \dots, x_n$ et $a_1, \dots, a_n$).

* Cas de base : $\mathcal{M} \models R(t_1(\bar{a}), \dots, t_m(\bar{a}))$, où $R$ est un symbole de relation $m$-aire du langage correspondant à la relation $R^\mathcal{M} \subseteq M^m$ et chaque $t_i(\bar{x})$ est un terme, ssi $(t_1^\mathcal{M}(\bar{a}), \dots, t_n^\mathcal{M}(\bar{a})) \in R^\mathcal{M}$, où chaque $t_i^\mathcal{M}(\bar{a})$ est l'élément de $M$ obtenu en appliquant les fonctions correspondant à chaque symbole de fonction utilisé dans $t_1(\bar{a})$.

* Quantification universelle : $\mathcal{M} \models \forall y G(y, \bar{a})$ ssi $\mathcal{M} \models G(b, \bar{a})$ pour tout $b \in M$.

* Quantification existentielle : $\mathcal{M} \models \exists y G(y, \bar{a})$ ssi il existe $b \in M$ tel que $\mathcal{M} \models G(b, \bar{a})$.
▷ Négation : $\mathcal{M} \models \neg G(\bar{a})$ ssi $\mathcal{M} \not\models G(\bar{a})$.

▷ Conjonction : $\mathcal{M} \models G_1(\bar{a}) \wedge G_2(\bar{a})$ ssi $\mathcal{M} \models G_1(\bar{a})$ et $\mathcal{M} \models G_2(\bar{a})$.

▷ Disjonction : $\mathcal{M} \models G_1(\bar{a}) \vee G_2(\bar{a})$ ssi $\mathcal{M} \models G_1(\bar{a})$ ou $\mathcal{M} \models G_2(\bar{a})$.

La satisfaction de l'implication se déduit de celle de la négation et de la disjonction. ◇

Une fois fixée une théorie, on peut considérer des modèles de cette théorie, c'est-à-dire des structures au sein desquelles chaque axiome de la théorie sera vrai.

**Définition 2.18.** Soit $T$ une théorie dans un langage $\mathcal{L}$. Une structure $\mathcal{M}$ dans le langage $\mathcal{L}$ est un modèle de $T$ si chaque axiome de $T$ est vrai dans $\mathcal{M}$. ◇

**Exemple 2.19.** ▷ L'ensemble $\mathbb{Z}$ muni des opérations usuelles n'est pas un modèle de l'arithmétique de Peano, car il ne satisfait pas l'axiome (1) : $0$ n'a pas de prédécesseur.

▷ L'ensemble $2\mathbb{N}$ des entiers pairs, où $\O$ est interprété par 0 et $\I$ est interprété par 2, n'est pas non plus un modèle de l'arithmétique de Peano, car il ne vérifie pas l'axiome (7) : $2 \times (2 + 2) \neq (2 \times 2) + 2$.

▷ Le modèle par excellence de l'arithmétique de Peano est bien entendu celui des entiers naturels $\mathbb{N}$, munis des opérations et relations usuelles.

Les théories forment l'aspect *syntaxique* des mathématiques, les modèles en forment eux l'aspect *sémantique*. Les avantages à réfléchir sur les modèles d'une théorie sont multiples.

En premier lieu, les modèles sont ce sur quoi ont naturellement travaillé les mathématiciens depuis les origines. Aujourd'hui, les mathématiques sont tellement avancées dans l'abstraction que c'est un aspect des choses que l'on perd parfois de vue, mais cette science n'est au départ pas si éloignée que cela de la physique, en ce sens qu'il s'agit d'abord d'un travail d'observation de la réalité de certains phénomènes afin d'en extraire les lois logiques qui les régissent. Chaque mathématicien sait par expérience qu'il ne décide pas de la vérité, celle-ci réside parfois bien cachée dans les structures abstraites étudiées, autrement dit dans les modèles. Cette méthodologie d'observation et de recherche basée sur la logique donne son caractère universel et transcendant à la vérité mathématique, constituant en quelque sorte le ci-ment qui lie la communauté des mathématiciens. Si la syntaxe est bien sûr importante, car elle constitue le langage permettant de transmettre
les mathématiques, la sémantique précède cette syntaxe<fnref n="2" /> : c'est de là que partent les intuitions et sur elle que portent les théorèmes.

Il y a enfin un avantage plus prosaïque à l'étude des modèles : par essence, si une formule close F est vraie dans un modèle, alors sa négation $\neg F$ ne peut pas y être vraie. Un modèle est toujours une structure cohérente et complète : chaque formule close y est soit vraie soit fausse, et aucune formule ne peut y être vraie en même temps que sa négation. On peut utiliser cela pour montrer le théorème de cohérence.

**Théorème 2.20**

Soit $T$ une théorie, et soit $F(x_1, \dots, x_n)$ une formule dans le langage de cette théorie. Si $T \vdash F(x_1, \dots, x_n)$, alors tout modèle de $T$ est aussi un modèle de $\forall x_1 \dots \forall x_n F(x_1, \dots, x_n)$.

**PREUVE.** On procède sans peine par induction sur la taille d'une démonstration. Supposons que ce soit le cas pour toute démonstration $G_1, \dots, G_n$ dans $T$. Soit $G_1, \dots, G_{n+1}$ une démonstration dans $T$. Par hypothèse d'induction, tout modèle de $T$ est modèle de chaque formule $\forall \bar{x} G_i$ pour $i<n+1$, où la notation $\forall \bar{x} G_i$ signifie que l'on quantifie universellement sur chaque variable libre de $G_i$ (quand il y en a). Soit $\mathcal{M}$ un modèle de $T$. Si $G_{n+1}$ est un axiome de $T$, alors c'est une formule close, et $\forall \bar{x} G_{n+1}$ est bien évidemment vraie dans $\mathcal{M}$. Si $G_{n+1}$ est un axiome de l'égalité (de type (e) (f) ou (g), ci-dessus), alors $\forall \bar{x} G_{n+1}$ est vraie dans $\mathcal{M}$ par le fait que l'égalité de $\mathcal{M}$ est toujours la vraie égalité.

Si $G_{n+1}$ est une tautologie de la logique propositionnelle ou un axiome de type (a)(b)(c) ou (d) du calcul des prédicats, alors $\forall \bar{x} G_{n+1}$ est vraie par définition de la satisfaction dans un modèle (les détails sont laissés au lecteur ; notons que pour (d) on utilise le fait que le modèle soit non vide).

Si $G_{n+1}$ est obtenue par généralisation sur $G_i$ pour $i < n + 1$ — en particulier, $G_{n+1}$ est de la forme $\forall y G_i$, alors $\mathcal{M}$ vérifiant $\forall \bar{x} G_i$, vérifie également $\forall \bar{x} G_{n+1}$ (qui est en fait la même formule). Enfin, si $G_{n+1}$ est obtenu par Modus Ponens via $G_i \rightarrow G_{n+1}$ et $G_i$ pour $i < n + 1$, alors $\mathcal{M}$ vérifie $\forall \bar{x} G_i$ et $\forall \bar{x} (G_i \rightarrow G_{n+1})$. Par définition de la satisfaction, $\mathcal{M}$ vérifie donc $\forall \bar{x} G_{n+1}$. ■

Le théorème précédent peut se résumer de la manière suivante : « on ne peut démontrer que des choses vraies ». C'est une bonne nouvelle, de laquelle on peut déduire notre théorème de cohérence.

<footnote n="2">2. Aphorisme cher au professeur René Cori, qui enseigna aux auteurs de ce livre les principes du présent chapitre.</footnote>
**Corollaire 2.21 (Théorème de cohérence)**

Si un système axiomatique admet un modèle, alors il est cohérent.

PREUVE. On le montre par contraposée. Si $T \vdash F \wedge \neg F$ pour une formule close $F$, alors tout modèle de $T$ est modèle de $F \wedge \neg F$. Comme il n'existe aucun modèle de $F \wedge \neg F$, alors $T$ n'a pas de modèle. $\blacksquare$

On vérifie sans peine l'existence d'un modèle des axiomes de la logique : l'ensemble $\{1\}$ avec la relation d'égalité $1 = 1$. Cela montre que les axiomes de la logique sont cohérents et ne peuvent démonter $\perp$.

On vérifie aussi sans peine l'existence d'un modèle pour l'arithmétique de Peano, à savoir $\mathbb{N}$ muni des fonctions usuelles d'addition et de multipli-cation, ainsi que des relations usuelles $<$ et $=$ sur les entiers. Voilà une deuxième bonne nouvelle, les axiomes de l'arithmétique de Peano sont eux aussi cohérents. Nous examinerons le sens de cette affirmation un peu plus loin, notamment à la lumière du deuxième théorème d'incomplétude de Gödel et de ses implications.

## 2.5. Modèles et théorème de complétude

Si le système de déduction à la Hilbert que nous avons donné — avec ses axiomes de la logique et ses règles de déduction — est bien cohérent, com-ment savoir en revanche qu'il est suffisamment puissant ? Après tout, les deux règles d'inférence semblent former un outil de travail bien maigre. Peut-on réellement tout démontrer avec ce système ? Nous allons voir que c'est le cas, via un théorème démontré, par Gödel dans sa thèse de docto-rat, qui peut être vu comme la réciproque du théorème de cohérence : tout ce qui est universellement vrai est démontrable.

**Théorème 2.22 (Théorème de complétude de Gödel)**

Soit $T$ une théorie dans un langage dénombrable. Si $T$ est cohérente, alors $T$ a un modèle.

Notons que le théorème de complétude pour des langages indénombrables peut aussi se démontrer en utilisant l'axiome du choix. Nous n'en mon-trons que la version dénombrable, qui nous suffira amplement. Le théorème de complétude de Gödel est plus difficile à montrer que le théorème de cohérence, lequel est une simple vérification de routine. Il s'agit ici de construire un modèle d'une théorie $T$, à partir du simple fait que $T \nvDash \perp$. L'idée de la preuve passe par la création d'une théorie dite complète.
**Définition 2.23.** Une théorie $T$ est dite *complète* si $T \vdash F$ ou $T \vdash \neg F$ pour toute formule close $F$ dans le langage de $T$. ◇

**Proposition 2.24.** Soit $\mathcal{L}$ un langage dénombrable. Toute théorie de $\mathcal{L}$ cohérente peut être étendue en une théorie complète et cohérente. ★

La preuve de la proposition ci-dessus utilise le lemme 2.10 que nous reformulons ici avec la notation $\vdash$ introduite depuis.

**Lemme (Lemme 2.10 de déduction).** Soit $T \cup \{F\}$ une théorie et $G$ une formule. Supposons $T \cup \{F\} \vdash G$. Alors, $T \vdash F \rightarrow G$. ★

**PREUVE DE LA PROPOSITION 2.24.** Étant donné une théorie $T$ cohérente dans un langage dénombrable, on en construit inductivement une extension $T'$ complète et cohérente. Soit $T_0 = T$. À l'étape $n$, supposons qu'une théorie cohérente $T_n$ soit définie. Soit $F_n$ la $n$-ième formule close de notre langage. Si $T_n \vdash F_n$, on définit $T_{n+1} = T_n \cup \{F_n\}$. Si $T_n \vdash \neg F_n$, on définit $T_{n+1} = T_n \cup \{\neg F_n\}$. Dans ces deux premiers cas, la cohérence de $T_{n+1}$ découle de la cohérence de $T_n$ et du lemme de déduction.

Si jamais $T_n$ ne prouve ni $F_n$ ni $\neg F_n$, alors on définit $T_{n+1} = T_n \cup \{F_n\}$. Supposons par l'absurde que $T_n \cup \{F_n\} \vdash \bot$. Alors, d'après le lemme de déduction, $T_n \vdash F_n \rightarrow \bot$, et donc $T_n \vdash \neg F_n$ (par contraposée et Modus Ponens), ce qui contredit le fait que $T$ ne prouve pas $\neg F_n$. Notons que l'on pourrait tout aussi bien définir $T_{n+1} = T_n \cup \{\neg F_n\}$.

On définit enfin $T' = \bigcup_n T_n$. La cohérence de $T'$ vient alors du fait qu'une démonstration dans une théorie n'utilise qu'un nombre fini de ses axiomes : si $T' \vdash \bot$, alors il existe forcément $n$ tel que $T_n \vdash \bot$, Comme chaque théorie $T_n$ est cohérente, alors $T'$ doit être cohérente. ■

**PREUVE DU THÉORÈME DE COMPLÉTUDE.** La preuve que nous donnons est due à Léon Henkin [85], et repose sur la création d'une théorie complète, cohérente, et possédant ce que l'on appelle des témoins de Henkin. Nous allons d'abord montrer l'affirmation suivante.

« Soit $T$ une théorie dans un langage $\mathcal{L}$, et soit $c$ un symbole de constante qui n'apparaît pas dans $\mathcal{L}$. Supposons $T \cup \{\exists x F(x) \rightarrow F(c)\} \vdash \bot$. On a alors $T \vdash \bot$. »

Comme $T \cup \{\exists x F(x) \rightarrow F(c)\} \vdash \bot$, on a alors, par le lemme de déduction, contraposée et Modus Ponens, $T \vdash \exists x F(x) \wedge \neg F(c)$. En particulier, $T \vdash \neg F(c)$. Soit à présent une variable $z$ qui n'intervient pas dans la preuve de $\neg F(c)$. Comme la constante $c$ n'apparaît pas dans la théorie $T$, elle ne peut être introduite dans la démonstration que par un axiome de la logique. Chacun de ces axiomes reste valide en remplaçant $c$ par $z$. On
laisse au lecteur le soin de vérifier que si l'on remplace $c$ par $z$ pour chaque étape de la démonstration, on obtient une démonstration valide de $\neg F(z)$. Par la règle de généralisation, on obtient finalement $T \vdash \forall x \neg F(x)$. Comme également $T \vdash \exists x F(x)$, alors $T \vdash \bot$.

Passons à présent à la preuve du théorème de complétude. Soit $T$ une théorie dans un langage dénombrable $\mathcal{L}$. Montrons comment construire un modèle. On définit $T_0 = T$ et $\mathcal{L}_0 = \mathcal{L}$. À l'étape $n \in \mathbb{N}$, supposons que l'on a défini une théorie cohérente $T_{2n}$ dans un langage $\mathcal{L}_{2n}$. Soit $\mathcal{L}_{2n+1}$ le langage $\mathcal{L}_{2n}$ auquel on ajoute un nouveau symbole de constante $c_G$ pour toute formule $G$ de $T_{2n}$ de la forme $\exists x F(x)$. Soit $T_{2n+1}$ la théorie $T_{2n}$ à laquelle on ajoute les énoncés $\exists x F(x) \to F(c_G)$ pour tout énoncé $G$ de $T_{2n}$ de la forme $\exists x F(x)$. Notons que par l'affirmation ci-dessus, comme $T_{2n}$ est cohérente, à chaque ajout d'axiome de la forme $\exists x F(x) \to F(c_G)$, la théorie reste cohérente. Donc, $T_{2n+1}$ est cohérente. Finalement, soit $\mathcal{L}_{2n+2}$ égal à $\mathcal{L}_{2n+1}$, et en utilisant la proposition 2.24, soit $T_{2n+2}$ la complétion de $T_{2n+1}$ pour le langage $\mathcal{L}_{2n+2}$. Soient $\mathcal{T}_\omega = \bigcup_n T_n$ et $\mathcal{L}_\omega = \bigcup_n \mathcal{L}_n$. Notons que $\mathcal{T}_\omega$ est une théorie complète et cohérente dans le langage $\mathcal{L}_\omega$, qui contient de plus un énoncé de la forme $\exists x F(x) \to F(c)$ pour chacun des énoncés de la forme $\exists x F(x)$ de $T_\omega$, où $c$ est un symbole de constante de $\mathcal{L}_\omega$. Les fameux témoins de Henkin sont les nouveaux symboles de constantes ainsi introduits.

L'ensemble sous-jacent $M$ de notre modèle $\mathcal{M}$ est l'ensemble des termes clos de $\mathcal{L}_\omega$, quotienté par la relation d'égalité. Formellement, si $(t_n)_{n \in \mathbb{N}}$ est la liste des termes clos de $\mathcal{L}_\omega$, alors $M = \{t_n : \forall i < n (\neg t_i = t_n) \in T_\omega\}$.

Notons que les symboles de fonctions de $\mathcal{L}$ ont une interprétation claire dans $M$. Par exemple, si $f$ est un symbole de fonction unaire de $\mathcal{L}$, alors sa fonction correspondante $f^M : M \to M$ est définie par $f^M(t) = q$ pour $q$ l'élément de $M$ qui est égal au terme clos $f(t) \in \mathcal{L}_\omega$, c'est-à-dire tel que $(f(t) = q) \in T_\omega$.

La théorie $T_\omega$ étant complète et cohérente, pour tout symbole de relation $m$-aire $R$ de $\mathcal{L}$ et tout élément $t_1, \dots, t_m \in M$, exactement un des énoncés parmi $R(t_1, \dots, t_m)$ ou $\neg R(t_1, \dots, t_m)$ est dans $T_\omega$. Cela induit une interprétation $R^M$ du symbole de relation $R$ de $\mathcal{L}$ dans $\mathcal{M}$.

Il reste à montrer par induction sur les formules que tous les énoncés de $T_\omega$ sont satisfaits dans $\mathcal{M}$ (et donc aussi ceux de $T$). Sans perte de généralité, on ne traite que les formules sous forme prénexe et où le symbole de négation n'apparaît que devant les formules atomiques. Par définition des relations dans $\mathcal{M}$, c'est bien le cas pour les formules atomiques et leurs négations. Si $F_1 \wedge F_2 \in T_\omega$, alors comme $T_\omega$ est complète $F_1, F_2 \in T_\omega$. Par hypothèse d'induction, $\mathcal{M} \models F_1$ et $\mathcal{M} \models F_2$, et donc $\mathcal{M} \models F_1 \wedge F_2$.
Si $F_1 \lor F_2 \in T_\omega$, alors comme $T$ est complète $F_1 \in T_\omega$ ou $F_2 \in T_\omega$ (si-non, par compléture, $\neg F_1$, $\neg F_2 \in T_\omega$, ce qui contredit $F_1 \lor F_2$). Par hypothèse d'induction, $\mathcal{M} \models F_1 \lor F_2$. Si $\forall x F(x) \in T_\omega$, alors comme $T_\omega$ est complète $F(t)$ est dans $T_\omega$ pour tout terme clos $t$ de $\mathcal{L}_\omega$, et donc tout élément de $M$. Par hypothèse d'induction, $\mathcal{M} \models F(t)$ pour tout $t \in M$, et donc $\mathcal{M} \models \forall x F(x)$. Si $\exists x F(x) \in T_\omega$, alors $\exists x F(x) \rightarrow F(c) \in T_\omega$ pour un symbole de constante $c \in \mathcal{L}_\omega$. En particulier, $F(c) \in T_\omega$ par Modus Ponens. Soit $t \in M$ un terme clos de $\mathcal{L}_\omega$ tel que $(t = c) \in T_\omega$. Par les axiomes de l'égalité, on a $F(t)$. Par hypothèse d'induction, $\mathcal{M} \models F(t)$. Donc, $\mathcal{M} \models \exists x F(x)$. ■

Le théorème de compléture est souvent utilisé sous la forme du corollaire suivant.

**Corollaire 2.26**

Si tout modèle d'une théorie $T$ est modèle d'une formule $F$, alors $T \vdash F$.

**PREUVE.** Si l'on a $T \cup \{\neg F\} \vdash \bot$, alors $T \vdash \neg F \rightarrow \bot$ par le lemme de déduction, et donc $T \vdash F$.

Supposons à présent $T \not\vdash F$; alors, par la ligne ci-dessus $T \cup \{\neg F\} \not\vdash \bot$. D'après le théorème de compléture, il existe donc un modèle de $T \cup \{\neg F\}$, c'est-à-dire un modèle de $T$ qui ne soit pas modèle de $F$. ■

Le théorème de compléture implique en particulier que l'on ne peut pas faire mieux que le système à la Hilbert que nous avons présenté : supposons que dans ce système les axiomes seuls de la logique ne suffisent pas à démontrer une formule $F$, autrement dit $\not\vdash F$ (à partir d'une théorie vide). Supposons qu'un système de démonstration plus puissant et cohérent existe tel que $\vdash^* F$, où $\vdash^*$ est la notion de preuve dans ce système. Alors également, $\vdash^* \neg F \rightarrow \bot$, et donc $\neg F \vdash^* \bot$. À présent, comme $\not\vdash F$, il existe d'après le théorème de compléture un modèle de $\neg F$, et notre modèle est donc d'après le théorème de cohérence pour $\vdash^*$ un modèle de $\bot$, ce qui est impossible.

## 3. Théorèmes d'incomplétudes de Gödel

Nous rentrons à présent dans le vif du sujet, via les théorèmes d'incomplétudes de Gödel, qui reposent entre autres choses sur un codage des ensembles calculatoirement énumérables par des formules de l'arithmétique.
### 3.1. Formules de l'arithmétique de Peano

Nous avons défini dans le chapitre 5 une hiérarchie de complexité sur les ensembles, appelée hiérarchie arithmétique. Nous allons maintenant donner tout son sens à cette appellation en définissant une hiérarchie syntaxique des formules de l'arithmétique, qui coïncide avec la hiérarchie arithmétique, dans le sens où un ensemble $A$ est $\Sigma_n^0$ ssi il est définissable par une formule $\Sigma_n$ de l'arithmétique de Peano.

**Définition 3.1.** Une formule de l'arithmétique de Peano est $\Delta_0$ si les quantifications qu'elle comporte sont toutes bornées, c'est-à-dire de la forme $\exists x < t \ \forall x < t$, avec $t$ un terme où la variable $x$ n'apparaît pas librement. Notons que les formules $\exists x < t \ F(x)$ et $\forall x < t \ F(x)$ se traduisent respectivement par $\exists x(x < t \land F(x))$ et $\forall x(x < t \rightarrow F(x))$. ◇

Étant donné $F(x_1, \dots, x_n)$ une formule $\Delta_0$ de l'arithmétique de Peano, la restriction sur les quantifications fait de l'ensemble

$$ \{(x_1, \dots, x_n) \in \mathbb{N} : F(x_1, \dots, x_n)\} $$

un ensemble calculable. Cela découle par exemple directement de la clôture des prédicats primitifs récursifs par conjonction, disjonction et quantification bornée (voir l'exemple 6-3.16 et l'exercice 6-3.19). On définit une hiérarchie de complexité sur les formules de l'arithmétique de Peano analogue à la hiérarchie arithmétique de la définition 5-1.1.

### Définition 3.2

1. Une formule $F(x_1, \dots, x_m)$ de l'arithmétique de Peano est $\Sigma_n$ si $n$ quantificateurs

$$ F(x_1, \dots, x_m) = \overbrace{\exists y_1 \forall y_2 \dots Q y_n}^n G(x_1, \dots, x_m, y_1, \dots, y_n) $$

pour $G(x_1, \dots, x_m, y_1, \dots, y_n)$ une formule $\Delta_0$, où $Q$ vaut $\exists$ si $n$ est impair, et $\forall$ si $n$ est pair.

2. Une formule $F(x_1, \dots, x_m)$ de l'arithmétique de Peano est $\Pi_n$ si $n$ quantificateurs

$$ F(x_1, \dots, x_m) = \overbrace{\forall y_1 \exists y_2 \dots Q y_n}^n G(x_1, \dots, x_m, y_1, \dots, y_n) $$

pour $G(x_1, \dots, x_m, y_1, \dots, y_n)$ une formule $\Delta_0$, où $Q$ vaut $\forall$ si $n$ est impair, et $\exists$ si $n$ est pair. ◇

Nous verrons que les ensembles définissables par une formule $\Sigma_n$ (resp. $\Pi_n$) de l'arithmétique de Peano coïncident avec les ensembles $\Sigma_n^0$ (resp. $\Pi_n^0$) de la définition 5-1.1. Nous commençons pour cela par montrer quelques propriétés de clôture analogues à celles des propositions 5-1.6 à 5-1.9.
**Proposition 3.3.** Soient $F(\bar{a}, x)$, $F_1(\bar{a}, x)$ et $F_2(\bar{a}, x)$ des formules $\Sigma_n$ (resp $\Pi_n$). Alors, chacune des formules suivantes est prouvablement équiva-
lente (en usant des axiomes de l'arithmétique) à une formule $\Sigma_n$ (resp. $\Pi_n$) :

$$
\triangleright F_1(\bar{a}, x) \wedge F_2(\bar{a}, x), F_1(\bar{a}, x) \vee F_2(\bar{a}, x);
$$

$$
\triangleright \exists x < b F(\bar{a}, x), \forall x < b F(\bar{a}, x);
$$

$$
\triangleright \exists x F(\bar{a}, x) (\text{resp. } \forall x F(\bar{a}, x)).
$$

*

PREUVE. Soient les équivalences suivantes :

$$
F(\bar{a}, x) \equiv \exists y G(\bar{a}, x, y), F_1(\bar{a}, x) \equiv \exists y G_1(\bar{a}, x, y) \text{ et } F_2(\bar{a}, x) \equiv \exists y G_2(\bar{a}, x, y).
$$

Il s'en déduit alors les nouvelles équivalences suivantes :

$$
F_1(\bar{a}, x) \wedge F_2(\bar{a}, x) \leftrightarrow \exists y \exists y_1, y_2 < y (G_1(\bar{a}, x, y_1) \wedge G_2(\bar{a}, x, y_2))
$$

$$
F_1(\bar{a}, x) \lor F_2(\bar{a}, x) \leftrightarrow \exists y (G_1(\bar{a}, x, y) \lor G_2(\bar{a}, x, y))
$$

$$
\exists x < b F(\bar{a}, x) \leftrightarrow \exists y \exists x < b G(\bar{a}, x, y)
$$

$$
\forall x < b F(\bar{a}, x) \leftrightarrow \exists z \forall x < b \exists y < z G(\bar{a}, x, y)
$$

$$
\exists x F(\bar{a}, x) \leftrightarrow \exists z \exists x < z \exists y < z G(\bar{a}, x, y).
$$

À présent, si $F, F_1, F_2$ sont $\Sigma_1$ avec $G, G_1, G_2 \Delta_0$, les équivalences ci-dessus montrent la proposition pour le cas $\Sigma_1$. Par passage à la négation, les équivalences tiennent aussi pour le cas $\Pi_1$. Supposons la proposition vraie pour les cas $\Sigma_n$ et $\Pi_n$. Alors, les équivalences ci-dessus pour $F, F_1, F_2$ des formules $\Sigma_{n+1}$, avec $G, G_1, G_2 \Pi_n$, impliquent —en utilisant les hypothèses d’induction sur $G, G_1, G_2$— la proposition pour le cas $\Sigma_{n+1}$. Par négation, la proposition est vraie pour le cas $\Pi_{n+1}$. $\blacksquare$

Notons que la quatrième équivalence dans la preuve ci-dessus, en l'occu-
rence l'équivalence $\forall x < b F(\bar{a}, x) \leftrightarrow \exists z \forall x < b \exists y < z G(\bar{a}, x, y)$, est
la moins triviale de toutes : les quatre autres utilisent simplement le fait
que deux entiers ont toujours un majorant, alors que celle-ci requiert l'uti-
lisation de l'induction. C'est quelque chose que nous étudierons en détail
dans la section 23-3.

Passons à présent à l'équivalence annoncée. Étant donné $\exists y F(x_1, \dots, x_n, y)$ une formule $\Sigma_1$ de l'arithmétique de Peano avec $F$ qui est $\Delta_0$, l'ensemble

$$
\{(x_1, \dots, x_n) \in \mathbb{N} : \exists y F(x_1, \dots, x_n, y)\}
$$

est un ensemble calculatoirement énumérable : on teste petit à petit la
formule *F* sur tous les (n + 1)-uplets *x*₁, ..., *x*ₙ, *y* et, quand on en trouve
un pour lequel *F* est vraie, on énumère (x₁, ..., xₙ). Gödel a montré que
tout ensemble calculatoirement énumérable pouvait en fait être représenté
sous cette forme.
**Théorème 3.4 (Gödel)**

Un ensemble d'entiers $A \subseteq \mathbb{N}$ est c. e. si, et seulement si, il existe $F(n)$ une formule $\Sigma_1$ de $\mathcal{L}_{\text{PA}}$ telle que $n \in A \text{ssi } \mathbb{N} \models F(n)$.

Nous allons montrer le théorème 3.4 en nous basant sur le modèle des fonctions générales récursives, qui coïncident, comme nous l'avons vu dans le chapitre 6, avec les fonctions calculables. Nous allons montrer que toute fonction partielle générale récursive $f: \mathbb{N}^k \to \mathbb{N}$ est représentée par une formule $\Sigma_1$ de l'arithmétique $F(n_1, \dots, n_k)$, c'est-à-dire

$$ \{(\bar{n}, r) \in \mathbb{N}^{k+1} : f(\bar{n}) \downarrow = r\} = \{(\bar{n}, r) \in \mathbb{N}^{k+1} : \mathbb{N} \models F(\bar{n}, r)\}. $$

Comme tout ensemble c. e. est le domaine d'une fonction partielle, cela démontre le théorème. La difficulté principale se trouve dans la gestion du schéma de récursion primitive, pour lequel nous avons besoin de coder des listes d'entiers par des formules de l'arithmétique. Gödel a recours pour cela à une utilisation astucieuse d'un résultat d'arithmétique modulaire : le théorème des restes chinois.

**Lemme 3.5 (Théorème des restes chinois).** Soit une suite quelconque d'entiers $(a_0, \dots, a_n)$, et soit $(p_0, \dots, p_n)$ une suite d'entiers deux à deux premiers entre eux avec $p_i \ge a_i$ pour $i \le n$. Alors, il existe un entier $b$ tel que $a_i$ est le reste de la division euclidienne de $b$ par $p_i$ pour tout $i$. $\star$

Le théorème des restes chinois va permettre à Gödel de coder des listes d'entiers de taille arbitraire. Notons que ce n'est pas la seule manière d'établir un système de codage/décodage des listes par des formules de l'arithmétique, et nous en verrons une autre dans la section 23-4.

**Lemme 3.6 (Fonction $\beta$ de Gödel).** Il existe une fonction

$$ \beta : \mathbb{N}^3 \to \mathbb{N} $$

représentée par une formule $\Delta_0$ telle que pour tout $n$ et toute suite d'entiers $(a_0, \dots, a_n)$ il existe des entiers $a, b \in \mathbb{N}$ pour lesquels $\beta(a, b, i) = a_i$ pour tout $i \le n$. $\star$

**PREUVE.** La formule $B(a, b, i, r)$ qui représente $\beta$ est la suivante : $\ll r$ est le reste de la division euclidienne de $b$ par $a(i+1)+1 \gg$. La formule est bien $\Delta_0 : r < a \times (i+1)+1 \land \exists c < b \ c \times (a \times (i+1)+1)+r = b$. Soit une suite d'entiers $(a_0, \dots, a_n)$. Montrons l'existence d'entiers $a, b$ tels que cette formule définit bien la fonction $(a, b, i) \mapsto a_i$.

Soit $m$ tel que $m > \max\{a_i : i \le n\}$ et $m > n$. Posons $a = m!$. Nous allons utiliser le théorème des restes chinois avec $p_i = a(i+1)+1$. Montrons que ces nombres sont deux à deux premiers.
Supposons par l'absurde qu'un nombre premier $p$ divise $p_i$ et $p_j$ avec $i < j$. Alors aussi, $p$ divise $p_j - p_i = a(j - i)$. Comme $p$ est premier, alors $p$ divise $a$ ou $p$ divise $j - i$. Comme $a = m!$ avec $m > n \ge j > i$ alors $j - i$ divise $a$ et donc dans tous les cas $p$ divise $a$. Donc, $p$ divise $a(i + 1)$. Comme $p$ divise également $a(i + 1) + 1$, alors, $p$ divise $a(i + 1) + 1 - a(i + 1) = 1$, ce qui est une contradiction. Les nombres $p_i$ sont donc premiers entre eux.

On a bien $p_i = a(i + 1) + 1 > m > a_i$ pour tout $i$. D'après le théorème des restes chinois, il existe un entier $b$ tel que pour tout $i$ l'entier $a_i$ est le reste de la division euclidienne de $b$ par $a(i + 1) + 1$. ■

### PREUVE DU THÉORÈME 3.4.
On montre que toute fonction générale récursive partielle est représentée par une formule $\Sigma_1$ de l'arithmétique. On laisse au lecteur le soin de montrer que c'est bien le cas pour les fonctions de base (projections, fonctions constantes et fonction successeur). On utilise sans le mentionner pour chacun des trois schémas à venir la proposition 3.3 afin d'obtenir une formule $\Sigma_1$ qui représente notre fonction.

**Schéma de composition.** Soit

$$f(\bar{x}) = g(h_1(\bar{x}), \dots, h_k(\bar{x}))$$

pour des fonctions $g, h_1, \dots, h_k$ représentées par des formules $G, H_1, \dots, H_k$. Alors, $f$ est représentée par la formule

$$F(\bar{x}, r) \equiv \exists y_1, \dots, y_k \ H_1(\bar{x}, y_1) \wedge \dots \wedge H_k(\bar{x}, y_k) \wedge G(y_1, \dots, y_k, r).$$

**Schéma de minimisation.** Soit

$$f(\bar{x}) = \min\{a \in \mathbb{N} : \forall i \le a \ g(\bar{x}, i) \downarrow \wedge g(\bar{x}, a) = 0\}$$

pour $g$ représentée par une formule $G$. Alors, $f$ est représentée par la formule :

$$F(\bar{x}, a) \equiv G(\bar{x}, a, 0) \wedge \forall i < a \ \exists r \neq 0 \ G(\bar{x}, i, r).$$

**Schéma de récursion primitive.** C'est ici que nous aurons besoin de la fonction $\beta$ de Gödel, représentée par la formule $B$. Soit $f$ défini par :

$$f(\bar{x}, 0) = g(\bar{x}) \\ f(\bar{x}, n+1) = h(\bar{x}, n, f(\bar{x}, n))$$

pour des fonctions $g, h$ représentées par des formules $G, H$. Alors, $f$ est représentée par la formule $F(\bar{x}, n, r)$ suivante :

$$\exists a, b \quad B(a, b, n, r) \wedge \exists a_0 \ (B(a, b, 0, a_0) \wedge G(\bar{x}, a_0)) \wedge \forall i < n \\ \quad \exists a_i, a_{i+1} \ (B(a, b, i, a_i) \wedge B(a, b, i + 1, a_{i+1}) \wedge H(\bar{x}, i, a_i, a_{i+1})).$$

Afin de voir que $f$ est bien représentée par $F$, il nous faut remarquer que $B$ tel que définie dans le lemme précédent est toujours une formule fonctionnelle.
En effet, quelles que soient les valeurs de $a, b, i$, il y a toujours au plus un élément $r$ tel que $B(a, b, i, r)$ est vrai. Ainsi, si la formule $F(\bar{x}, n, r)$ est vérifiée, il existe bien une suite $a_0, \dots, a_n$ telle que $g(\bar{x})=a_0$ et $h(\bar{x}, i, a_i)=a_{i+1}$, avec $a_n = r$, le résultat de $f(\bar{x}, n)$. D'après le lemme précédent, il existe bien pour tout $n$ des entiers $a, b$ qui codent via la fonction $\beta$ la suite de valeurs $(f(\bar{x}, 0), f(\bar{x}, 1), \dots, f(\bar{x}, n))$. La formule $F$ représente donc bien la fonction $f$.

On montre facilement à partir du théorème 3.4 qu'un ensemble d'entiers est $\Sigma_n^0$ (resp. $\Pi_n^0$) si, et seulement si, il est décrit par une formule $\Sigma_n$ (resp. $\Pi_n$) de l'arithmétique.

## Codage des suites finies

Il existe de nombreuses manières de coder des suites finies d'entiers à l'aide d'entiers naturels. La plupart de ces techniques ont recours à des fonctions primitives récursives, ce qui demande de montrer au préalable qu'elles sont représentables par des formules simples de l'arithmétique. Le théorème des restes chinois permet de réaliser un codage simple des suites finies à base de la division euclidienne, qui s'exprime par un prédicat $\Delta_0$ immédiat (voir le lemme 3.6).

## 3.2. Démonstrations et calcul

Une démonstration dans notre système de déduction à la Hilbert repose sur un système de règles bien précis, et il est aisé de créer un programme informatique qui prend en paramètre une démonstration — via un codage approprié — et qui vérifie en un temps fini si la démonstration est valide ou non. En effet, les règles d'inférence sont claires, quant aux axiomes de la logique, nous avons les tautologies du calcul propositionnel, quatre schémas d'axiomes pour le calcul des prédicats, et trois schémas d'axiomes pour l'égalité. Il est aisé de vérifier si une phrase du calcul propositionnel — par exemple, de la forme $(F \rightarrow G) \leftrightarrow (\neg G \rightarrow \neg F)$ — est une tautologie, en s'assurant que la phrase est toujours vraie pour n'importe quelle valeur de vérité pour $F$ et $G$. Il est également facile de vérifier si une phrase correspond à l'un des schémas d'axiomes de l'égalité ou du calcul des prédicats. On en déduit le théorème suivant.

### Théorème 3.7 (Gödel)

Étant donné une théorie calculatoirement énumérable $T$ dans le langage $\mathcal{L}_{PA}$, l'ensemble des formules $F$ telles que $T \vdash F$ est calculatoire-ment énumérable.

Il suffit en effet de faire une recherche sur toutes les démonstrations possibles à partir des axiomes de $T$ et de lister toutes les formules qu'elles démontrent.
L'objectif de Hilbert était de montrer que toute vérité arithmétique était prouvable, l'arithmétique de Peano étant supposément un système suffisant pour le faire. Si tel était le cas, alors on pourrait créer un algorithme permettant de décider si un énoncé mathématique $F$ est prouvable ou réfutable : il suffirait de lister tous les énoncés prouvés par l'arithmétique de Peano jusqu'à trouver $F$ ou $\neg F$.

Gödel a montré que ce n'était pas possible, ni pour l'arithmétique de Peano, ni pour aucune théorie calculatoirement énumérable et cohérente contenant l'arithmétique de Peano (il fallut toutefois l'aide de Rosser pour cette dernière étape). Nous commençons par prouver un lemme qui nous aidera dans la suite.

**Lemme 3.8.** Si $N \models F$ où $F$ est une formule close $\Sigma_1$, alors $PA \vdash F$. ★

**PREUVE.** La formule $F$ est de la forme $\exists x_1 \dots \exists x_n G(x_1, \dots, x_n)$ pour $G$ une formule $\Delta_0$. Si $F$ est vraie dans $N$, alors il existe des entiers $a_1, \dots, a_n \in N$ tels que $G(a_1, \dots, a_n)$ est vrai dans $N$. On montre facilement par induction que si une formule $\Delta_0$ et paramétrée dans $N$ est vraie dans $N$, alors elle est démontrable dans PA. À titre informel, pour une quantification existentielle bornée, il suffit de prendre un entier témoin pour cette quantification et de montrer la formule avec ce témoin; et, pour une quantification universelle bornée par un entier $a$, il suffit de montrer que la formule est vraie pour chaque entier inférieur à $a$. ■

Nous avons à présent les ingrédients nécessaires pour montrer le premier théorème d'incomplétude.

**Théorème 3.9 (Premier théorème d'incomplétude de Gödel)**

Soit $T \supseteq PA$ une théorie c. e. cohérente, telle que si $T$ démontre une formule $\Sigma_1$, alors $N$ est modèle de cette formule. Alors, il existe $F$ une formule $\Sigma_1$ telle que $T \vdash F$ et $T \not\vdash \neg F$.

**PREUVE.** Soit $(\Phi_e)_{e \in N}$ une énumération des fonctions calculables. D'après le théorème 3.4, il existe $F(e)$ une formule $\Sigma_1$ de $\mathcal{L}_{PA}$ telle que

$$ \{e \in N : N \models F(e)\} = \{e \in N : \exists t \Phi_e(e)[t] \downarrow\}. $$

Supposons que pour tout $e$ on ait $T \vdash F(e)$ ou $T \vdash \neg F(e)$. Notons que si $\exists t \Phi_e(e)[t] \downarrow$, alors $N \models F(e)$, et donc $PA \vdash F(e)$ d'après le lemme 3.8. Comme $PA \subseteq T$, on a aussi $T \vdash F(e)$.

À présent, si $\forall t \Phi_e(e)[t] \uparrow$, alors on a $N \models \neg F(e)$. D'après notre hypothèse, on ne peut avoir $T \vdash F(e)$, car on aurait alors $N \models F(e)$ ce qui contredit $N \models \neg F(e)$. Comme $T$ est complète, on a donc $T \vdash \neg F(e)$.
Il s'ensuit que l'ensemble c. e. {$e \in \mathbb{N} : T \vdash \neg F(e)$} coïncide avec l'ensemble {$e \in \mathbb{N} : \forall t \Phi_e(e)[t] \uparrow$}, ce qui fait du complémentaire de l'arrêt un ensemble c. e. On a là une contradiction. ■

Nous remarquons plusieurs choses. En premier lieu, nous avons été obligés de nous restreindre aux théories $T$ dites 1-cohérentes, c'est-à-dire ne démontrant pas de formules $\Sigma_1$ fausses dans $\mathbb{N}$. Nous verrons bientôt qu'il existe bien d'autres modèles possibles que $\mathbb{N}$ pour PA, et autant de théories non 1-cohérentes que l'on souhaite. Il s'agit donc d'une restriction bien ennuyeuse.

Ensuite, la preuve montre en substance qu'une théorie complète et 1-cohérente permet de calculer $\emptyset'$. Nous avons déjà vu que n'importe quel degré PA permet de calculer une extension complète et cohérente de PA, et comme il y a des degrés PA qui ne calculent pas $\emptyset'$, il n'y a en fait aucun espoir de montrer le théorème de Gödel en réduisant le problème de l'arrêt à toute théorie complète et cohérente qui étend PA. L'astuce pour se sortir de cette situation fut trouvée par Rosser, l'idée étant en substance d'utiliser le fait que si une théorie démontre $\exists t \Phi_e(e)[t] \downarrow= 0$ (que ce soit vrai dans $\mathbb{N}$ ou pas), alors elle ne peut pas montrer dans le même temps $\exists t \Phi_e(e)[t] \downarrow= 1$, à supposer bien entendu que les formules $\Sigma_1$ permettant de parler des fonctions calculables intègrent bien le fait qu'une fonction a au plus une valeur sur son entrée, ce qui est bien le cas en pratique.

**Théorème 3.10 (Théorème d'incomplétude de Gödel-Rosser)**

Soit $T \supseteq \mathbb{PA}$ une théorie c. e. et cohérente. Alors, il existe $F$ une formule $\Sigma_1$ telle que $T \nvDash F$ et $T \nvDash \neg F$.

**PREUVE.** Soit $(\Phi_e)_{e \in \mathbb{N}}$ une énumération des fonctions calculables. Supposons par l'absurde que l'on ait $T \vdash F$ ou $T \vdash \neg F$ pour toute formule $F \in \Sigma_1$. Nous allons alors calculer une fonction totale $f : \mathbb{N} \to \{0,1\}$ qui est $\text{DNC}_2$, c'est-à-dire telle que pour tout entier $e$ on ait $\Phi_e(e) \downarrow$ implique $f(e) \neq \Phi_e(e)$. Notons qu'il s'agit alors d'une contradiction : si $f$ est calculable, alors il existe un code $e$ tel que $\Phi_e(n) \downarrow= f(n)$ pour tout $n$, et donc en particulier tel que $\Phi_e(e) \downarrow= f(e)$.

Les ensembles $\{\exists t \Phi_e(e)[t] \downarrow= 0\}$ et $\{\exists t \Phi_e(e)[t] \downarrow= 1\}$ sont c. e., et donc d'après le théorème 3.4 il existe $F_0(e)$ et $F_1(e)$ des formules $\Sigma_1$ telles que

$$ \{e \in \mathbb{N} : \mathbb{N} \models F_0(e)\} = \{e \in \mathbb{N} : \exists t \Phi_e(e)[t] \downarrow= 0\} $$

$$ \{e \in \mathbb{N} : \mathbb{N} \models F_1(e)\} = \{e \in \mathbb{N} : \exists t \Phi_e(e)[t] \downarrow= 1\}. $$

Notons que PA démontre aussi $F_0(e) \rightarrow \neg F_1(e)$ et $F_1(e) \rightarrow \neg F_0(e)$ : autrement dit, $e \mapsto \Phi_e(e)$ est une fonction partielle qui ne peut avoir à la fois 0 et 1 comme valeur pour le même élément.
**Théorème 3.12 (Second théorème d'incomplétude de Gödel)**

Soit $T$ une théorie cohérente calculatoirement énumérable contenant $PA$.
Alors, $T \not\models Coh(T)$.

PREUVE. La première étape est de voir que la preuve du théorème 3.10 peut être formalisée, via un codage approprié, dans l'arithmétique de Peano : il existe $F$ une formule $\Sigma_1$ telle que

$$PA \vdash Coh(T) \rightarrow (T \not\models F^{\neg} \wedge T \not\models \neg F^{\neg}).$$

Les notations $\neg\Psi^{\neg}$ indiquent la transformation de $\Psi$ en un énoncé de l'arithmétique.

Supposons par l'absurde $T \vdash Coh(T)$. Alors, par la règle du Modus Ponens, on a $T \vdash \neg T \not\models F^{\neg} \wedge \neg T \not\models \neg F^{\neg}$, et donc $T \vdash \neg T \not\models \neg F^{\neg}$ ainsi que $T \vdash \neg T \not\models F^{\neg}$.

Il faut ensuite constater que la preuve du lemme 3.8 également peut se faire dans l'arithmétique de Peano, c'est-à-dire que l'arithmétique de Peano montre que si une formule $\Sigma_1$ fixée est vraie, alors elle est démontrable dans l'arithmétique de Peano — et donc dans $T$. Cela donne donc formellement avec la formule $F$

$$T \vdash F \rightarrow \neg T \vdash F^{\neg}.$$

On a alors par contraposée (en utilisant l'équivalence entre la négation et le codage de la négation) :

$$T \vdash \neg T \not\models F^{\neg} \rightarrow \neg F.$$

Comme $T \vdash \neg T \not\models F^{\neg}$, alors par Modus Ponens on obtient

$$T \vdash \neg F.$$

Il suffit enfin de voir que si $T$ démontre une formule quelle qu'elle soit, alors $PA$ — et donc $T$ — démontre que $T$ démontre cette formule. C'est encore une fois une application de la formalisation de la preuve du lemme 3.8 dans $T$, la phrase $T \vdash F$ étant $\Sigma_1$. On a donc finalement

$$T \vdash \neg T \vdash \neg F^{\neg},$$

ce qui contredit $T \vdash \neg T \not\models \neg F^{\neg}$.

## 3.3. Conséquence des théorèmes d'incomplétude

Souvenons-nous du théorème, lui, de complétude de Gödel : $T \vdash F$ ssi tout modèle de $T$ est un modèle de $F$. Vu le second théorème d'incomplétude, aucune théorie $T$ cohérente et calculatoirement énumérable contenant l'arithmétique ne peut démontrer sa propre cohérence : $T \not\models Coh(T)$. On en déduit donc par exemple qu'il existe des modèles de l'arithmétique de Peano au sein desquels la phrase Coh(PA) est fausse : dans ces modèles, il existe en
particulier une démonstration de $0 = 1$. Nous avons pourtant montré que PA avait des modèles, et donc, d'après le théorème de cohérence, que PA ne pouvait pas démontrer $0 = 1$. Cette situation qui semble paradoxale est résolue avec la considération suivante : la preuve de $0 = 1$ dans un modèle de PA $\cup \{\neg \text{Coh}(\text{PA})\}$ n'est pas une vraie preuve. La phrase Coh(PA) une fois exprimée dans le langage de l'arithmétique est de la forme : « il existe un entier qui code pour une démonstration valide de $0=1$ dans PA ». Un tel modèle contiendra donc un tel entier, mais cet entier ne sera pas un véritable entier — sinon, en déroulant la démonstration codée par cet entier, on aurait une vraie démonstration de $0 = 1$.

Un tel modèle de PA est dit *non standard* : il comporte des entiers dits eux aussi non standard. Tout modèle de PA contient $0$ et $1$. Par les axiomes régissant l'addition, on montre aisément que tout modèle de PA contient bien sûr les entiers standard : $0, 1, 2, 3, 4, \dots$. Un modèle non standard de PA contiendra des entiers *plus grands* que tous les entiers standard, et du point de vue du modèle, rien ne permet de distinguer ces entiers-là des autres.

Prenons un entier non standard $a$ d'un tel modèle. En utilisant les axiomes de l'arithmétique de Peano, on voit que les entiers $a+1, a+2, a+3, \dots$ existent également dans le modèle. Par l'axiome qui stipule que tout entier autre que $0$ admet un prédécesseur, on voit aussi que les différents entiers $a-1, a-2, a-3, \dots$ sont dans le modèle. Comme $a > n$ pour tout $n \in \mathbb{N}$, alors également $a + a > a + n$ pour tout $n \in \mathbb{N}$. Il existe donc aussi un entier non standard plus grand que tous les $a+n$. En jouant ainsi avec les axiomes de PA, on arrive au théorème suivant.

**Théorème 3.13**

L'ordre < pour les modèles dénombrables et non standard de l'arithmétique est constitué d'une copie de $\mathbb{N}$, suivie de $\mathbb{Q}$ copies de $\mathbb{Z}$.

On connaît donc bien à quoi ressemble l'ordre des éléments dans un modèle non standard. On ne connaît en revanche malheureusement pas à quoi ressemblent ni l'addition ni la multiplication.

**Théorème 3.14 (Tennenbaum)**

Soit $\mathcal{M}$ un modèle non standard dénombrable de PA. Soit

$$+, \times : \mathbb{N} \times \mathbb{N} \rightarrow \mathbb{N}$$

des fonctions qui représentent les fonctions d'addition et de multiplication de $\mathcal{M}$, une fois établie une bijection entre $\mathcal{M}$ et $\mathbb{N}$. Alors, $ni + ni \times ne$ sont calculables.

Nous reparlerons un peu des modèles non standard de l'arithmétique dans l'étude des mathématiques à rebours, et notamment dans la section 23-3.
# 4. Système ZFC

Nous avons donné une preuve de la cohérence de l'arithmétique de Peano, en utilisant le théorème de cohérence (voir le corollaire 2.21) et en fournissant un modèle pour cette théorie. D'après le deuxième théorème d'accomplitude de Gödel, nous avons nécessairement utilisé une théorie plus puissante que PA pour créer ce modèle. De quelle théorie s'agit-il ? On peut donner plusieurs réponses à cette question. La théorie la plus naturelle permettant de montrer la consistance de l'arithmétique du premier ordre est sans doute la théorie de l'arithmétique du second ordre, qui sera abordée plus en détail dans le chapitre 22.

## 4.1. Motivations

En arithmétique du second ordre, on s'autorise non seulement à travailler avec des entiers, mais également avec des ensembles d'entiers. L'existence d'ensembles d'entiers arbitraires est sujette à caution, davantage en tout cas que l'existence des entiers eux-mêmes : il s'agit d'objets infinis, qui sont en quantité indénombrable, et s'il y a un aspect « légitime » à accepter l'existence d'ensembles d'entiers calculables (après tout, on peut écrire des algorithmes qui les produisent, et leur existence théorique est donc doublée d'une certaine forme d'existence pratique), on peut questionner plus facilement celle des autres ensembles. Certains d'entre eux sont malgré tout accessibles, dans le sens où ils ont une définition claire, par exemple le saut Turing. Ce qui rend $\emptyset'$ plus légitime qu'un autre ensemble non calculable arbitraire, c'est le fait qu'il soit définissable, et qui plus est par une formule assez simple — en particulier $\Sigma_1 : \{e \in \mathbb{N} : \Phi_e(e) \downarrow\}$. En arithmétique du second ordre, on s'autorisera l'existence de tous les ensembles définissables par une formule de l'arithmétique arbitraire, en particulier les formules $\Sigma_n^0$ pour un certain $n$ : cela s'appelle *l'axiome de compréhension*. Une fois que l'on a admis l'existence d'un ensemble $X$, il serait absurde de ne pas accepter l'existence d'ensembles calculables avec $X$ comme oracle, et si l'on accepte l'axiome de compréhension, il serait tout aussi absurde de ne pas accepter l'existence des ensembles définissables par une formule de l'arithmétique arbitraire, qui pourrait utiliser $X$ comme oracle.

L'arithmétique du second ordre consiste donc en l'arithmétique de Peano, à laquelle on ajoute l'axiome de compréhension qui permet de valider l'existence des ensembles définissables via une formule de l'arithmétique, éventuellement à l'aide d'un oracle — un ensemble déjà existant. Une très grande partie des mathématiques peut déjà se formaliser de cette manière, mais pas toutes les mathématiques. En particulier, rien ne permet dans
l'arithmétique du second ordre de parler de l'ensemble de tous les sous-ensembles d'entiers, ou même de sous-ensembles arbitraires de ce dernier. On a besoin pour cela d'un autre axiome : étant donné un ensemble $X$, l'ensemble $\mathcal{P}(X)$ des parties de $X$ —c'est-à-dire l'ensemble de tous les sous-ensembles de $X$ — est légitime, il existe et on peut l'utiliser. L'ensemble des parties de $X$ n'est pas de même nature que $X$. L'un est un ensemble d'entiers et l'autre un ensemble d'ensembles d'entiers. La théorie des ensembles permet de traiter ces deux éléments de manière homogène : tout élément ne sera plus qu'ensemble, y compris les entiers. Informellement, l'entier 0 sera l'ensemble vide, l'entier 1 sera l'ensemble qui contient 0, l'entier 2 sera l'ensemble qui contient 0 et 1, et inductivement l'ensemble $n+1$ sera l'ensemble qui contient $m$ pour tout $m \le n$. On peut bien sûr imaginer d'autres manières de représenter les entiers par des ensembles, et avec la pratique ces dernières n'ont aucune importance, mais il faut bien en choisir une, et cette manière-là est celle qui est devenue standard, sous l'impulsion du mathématicien John von Neumann. Nous en reparlerons avec l'étude des ordinaux dans le chapitre 27.

## 4.2. Système de Zermelo

À présent que l'on ne travaille plus qu'avec des ensembles, nous ne sommes plus dans le langage de l'arithmétique. Notre unique symbole de relation est celui de l'appartenance $\in$ — auquel on ajoute tout de même celui de l'égalité. Il nous faut quelques axiomes basiques afin de régir les manipulations élémentaires des ensembles.

(1) *L'axiome de l'ensemble vide* : l'ensemble vide existe.

(2) *L'axiome de paire* : si $a$ et $b$ sont des ensembles, alors $\{a, b\}$ est un ensemble.

(3) *L'axiome de réunion* : l'idée est que si $(a_i)_{i \in I}$ est une collection d'ensembles indexée par un ensemble $I$, alors l'ensemble $\bigcup_{i \in I} a_i$ existe. La notion « indexée » n'étant pas formellement définie en théorie des ensembles, on dira à la place que si $b$ est un ensemble dont les éléments sont les $a_i$, alors la réunion de tous ces $a_i$ existe. Pour être tout à fait formel, l'axiome est : $\forall b \exists c \forall x (x \in c \leftrightarrow \exists a \in b \ x \in a)$.

On a également besoin d'un axiome qui régisse l'égalité entre deux ensembles.

(4) *L'axiome d'extensionnalité* : deux ensembles sont égaux si, et seulement si, ils ont les mêmes éléments.

Il y a finalement notre axiome fauteur de troubles, qui nous a poussé dans cette théorie des ensembles permettant — par exemple — de traiter de l'ensemble des parties de $\mathbb{N}$.
(5) *L'axiome de l'ensemble des parties* : pour tout ensemble $a$, l'ensemble des parties de $a$, noté $P(a)$ existe. Formellement :

$$ \forall a \exists b \forall c (c \in b \leftrightarrow c \subseteq a), \\ \text{où } c \subseteq a \text{ peut s'écrire comme } \forall x (x \in c \rightarrow x \in a). $$

Nous pouvons enfin ajouter notre axiome de compréhension, permettant de construire des ensembles à partir de formules du premier ordre utilisant éventuellement d'autres ensembles comme paramètres. Comme il existe une infinité de formules du premier ordre, il ne s'agit pas d'un seul axiome, mais d'un schéma d'axiome : un axiome par formule.

(6) *Le schéma d'axiome de compréhension* : pour $F(y, x_1, \dots, x_n)$, formule fixée dans le langage de la théorie des ensembles, pour tout $n$-uplet d'ensembles $b_1, \dots, b_n$ et pour tout ensemble $a$, l'ensemble

$$ \{y \in a : F(y, b_1, \dots, b_n)\} \\ \text{existe.} $$

On peut vérifier sans peine que les axiomes précédents impliquent l'existence de tous les ensembles héréditairement finis, c'est-à-dire des ensembles finis, dont les éléments sont eux-mêmes des ensembles finis, etc., jusqu'à arriver en déroulant l'arbre décrivant les relations d'appartenance d'un ensemble avec ses éléments, à l'ensemble vide pour toute feuille de cet arbre. Rien ne nous permet pour le moment de parler de l'ensemble de tous les entiers. Nous avons de fait besoin pour cela d'un axiome.

(7) *L'axiome de l'infini* : il existe un ensemble infini. Formellement :

$$ \exists x (\emptyset \in x \land \forall y \in x \ y \cup \{y\} \in x). $$

L'axiome de l'infini asserte moralement l'existence de $\mathbb{N}$ en tant qu'ensemble. Via le codage que nous avons donné des entiers, on peut vérifier que l'ensemble codant l'entier $n+1$ est égal à l'ensemble $n \cup \{n\}$, où $n$ est l'ensemble codant l'entier $n$. L'axiome de l'infini nous dit donc qu'il existe un ensemble contenant tous les entiers. Il pourrait éventuellement contenir d'autres éléments, mais en utilisant les autres axiomes on définit $\mathbb{N}$ comme le plus petit ensemble $x$ — plus petit pour l'inclusion — tel que

$$ \emptyset \in x \land \forall y \in x \ y \cup \{y\} \in x. $$

### 4.3. L'axiome de remplacement et les jeux boréliens

Les axiomes de (1) à (7) forment la théorie Z de Zermelo. Ils sont suffisants pour développer une large partie des mathématiques. Fraenkel et Skolem vont introduire un nouvel axiome, à la fois intuitif et formellement
nécessaire pour développer les théories des ordinaux et des hiérarchies d'in-
finis. Il s'agit plus exactement un schéma d'axiomes, qui dit essentiellement
que l'image d'une formule fonctionnelle existe. Une formule $F(y, r)$ est fonc-
tionnelle si pour tout $y$ la formule $F(y, r_y)$ est satisfaite pour exactement
un ensemble $r_y$. Il s'énonce formellement comme suit.

(8) *Le schéma d'axiome de remplacement* : pour une formule fonctionnelle $F(y, x_1, \dots, x_n, z)$ fixée dans le langage de la théorie des ensembles, pour tout $n$-uplet d'ensembles $b_1, \dots, b_n$, pour tout ensemble $a$, l'ensemble
$$ \{z : \exists y \in a \ F(y, b_1, \dots, b_n, z)\} $$
existe.

La théorie des ensembles devient strictement plus puissante avec le schéma d'axiome de remplacement, qui permet en particulier de montrer l'existence de l'ensemble $\mathbb{N} \cup P(\mathbb{N}) \cup P(P(\mathbb{N})) \dots$, dont la construction est impossible sans cet axiome.

Il est remarquable de noter qu'une utilisation conjointe de l'axiome de
l'ensemble des parties et du schéma d'axiome de remplacement est indis-
pensable pour construire certains ensembles d'entiers — qui seront néces-
sairement d'une complexité extrême en termes de degré Turing. L'exemple
emblématique est le théorème de détermination des jeux boréliens de Mar-
tin. Voyons de quoi il s'agit : considérons une classe $\mathcal{B} \subseteq 2^\mathbb{N}$ pour le moment
arbitraire, et considérons le jeu à deux joueurs suivant : le joueur 1 choisit
un bit $x_0 \in \{0,1\}$, puis le joueur 2 choisit à son tour un bit $x_1 \in \{0,1\}$, et
ainsi de suite, à l'étape $2n$ le joueur 1 choisit le bit $x_{2n}$ et à l'étape $2n+1$
le joueur 2 choisit le bit $x_{2n+1}$. À « la fin » du jeu, on obtient un en-
semble $X = x_0x_1x_2\dots$ Le joueur 1 gagne le jeu si $X \in \mathcal{B}$, sinon c'est le
joueur 2 qui remporte la partie. La question est alors : un des deux joueurs
a-t-il une stratégie gagnante ? Une stratégie pour le joueur 1 est une fonc-
tion $f$ qui prend en paramètre une chaîne $\sigma$ de taille paire, correspondant
à ce qui a été joué jusque-là, le dernier coup étant le dernier bit de $\sigma$ joué
par le joueur 2, et qui renvoie le coup suivant $f(\sigma)$. Une telle stratégie est
gagnante si l'ensemble obtenu en jouant les coups donnés par la fonction $f$
est toujours dans $\mathcal{B}$, quels que soient les coups joués par le joueur 2.

Nous verrons dans le chapitre 17 des classes $\mathcal{B} \subseteq 2^{\mathbb{N}}$ — d’une variété fort
riche — ne nécessitant pas l’axiome de l’ensemble des parties pour être ma-
nipulées : nous en avons déjà un exemple avec les classes $\Pi_1^0$ ou $\Sigma_1^0$. Nous
mènerons des constructions itérées de classes de plus en plus complexes, qui
peuvent se coder par un objet dénombrable, d’une manière analogue au co-
dage des classes $\Pi_1^0$ par des arbres : il s’agira des classes dites *boréliennes*.
Le mathématicien Donald A. Martin, dont nous reparlerons dans le cha-
pitre 12, a montré le remarquable théorème suivant.
**Théorème 4.1 (Martin [149])**

Soit $\mathcal{B}$ une classe borélienne. Alors, pour le jeu décrit ci-dessus avec la classe $\mathcal{B}$, un des deux joueurs a une stratégie gagnante.

La stratégie d'un jeu borélien est une fonction $f : 2^{<\mathbb{N}} \to \{0,1\}$, qui peut donc être représentée par un ensemble d'entiers. Friedman [67] a montré que pour certains boréliens, de complexité relativement simple, une telle stratégie ne pouvait être construite sans l'utilisation de l'axiome de l'ensemble des parties, et même sans itération arbitraire de l'application de cet axiome. Ainsi, pour montrer l'existence de certains réels, nous faut-il faire appel à l'axiome de l'ensemble des parties utilisé conjointement à celui de remplacement afin de construire $\mathbb{N} \cup P(\mathbb{N}) \cup P(P(\mathbb{N})) \dots$, indispensable à la définition de notre réel — la stratégie gagnante pour un certain borélien.

**4.4. L'axiome de fondation et le codage**

Un autre axiome a été rajouté par Fraenkel et Skolem, ainsi que par von Neumann. Contrairement aux autres axiomes, ce dernier est à peu près inutile pour la construction de l'univers mathématique, mais on l'ajoute simplement parce que cela correspond à notre conception des choses : l'axiome dit en substance qu'étant donné un ensemble $x$, si l'on considère un élément $x_1 \in x$, puis un élément $x_2 \in x_1$, en continuant ainsi inductivement avec un élément $x_{n+1} \in x_n$, on arrivera nécessairement au bout d'un certain $n \in \mathbb{N}$ à l'ensemble vide : il n'y a pas d'autres ensembles que ceux que l'on peut construire inductivement via les autres axiomes en partant de l'ensemble vide. En particulier, il n'y a aucun ensemble $x$ tel que $x \in x$. Cela peut paraître évident ou pas selon chacun, mais reflète en tout cas la conception généralement adoptée dans la communauté sur la nature des ensembles.

Afin d'étayer notre propos, rappelons que l'un des intérêts de la théorie des ensembles est de pouvoir y formaliser la totalité des mathématiques. Cette formalisation passe par le codage des structures mathématiques usuelles par des ensembles, et ce codage ne se fait de toute façon qu'avec des ensembles qui respectent l'axiome de fondation — que ce dernier soit adopté ou pas. Aussi, s'il n'est pas contradictoire de penser qu'il existe d'autres ensembles qui ne respectent pas cet axiome, on n'en a en pratique pas besoin, et de tels objets ne correspondent à priori à rien de tangible.

Terminons en insistant sur le fait que si l'on peut coder le reste des mathématiques par des ensembles, ce n'est en revanche pas une raison pour le faire, et l'on est évidemment bien plus à l'aise à travailler avec des entiers, des réels ou autre. Ce qui est intéressant c'est l'existence de ce codage, et le fait que si un énoncé est indécidable en théorie des ensembles, il en devient alors indécidable << tout court >>.
### 4.5. L'axiome du choix et la cardinalité

La théorie Z de Zermelo plus l'axiome de remplacement et celui de fondation donne la théorie ZF, de Zermelo/Fraenkel.

Un dernier axiome, sans doute le plus célèbre, est l'axiome du choix, qui faisait originellement partie de la théorie de Zermelo. La nécessité de cet axiome devrait être aisée à comprendre via l'analogie que l'on peut en faire en calculabilité. Nous avons par exemple vu que toute classe $Π_1^0$ non vide et dénombrable contient un ensemble calculable. En revanche, il n'est pas possible, étant donné le code d'une classe $Π_1^0$ non vide, de trouver uniformément un algorithme permettant d'en calculer un élément. En particulier, étant donné une suite $(F_n)_{n \in \mathbb{N}}$ de classes $Π_1^0$ dénombrables non vides, il n'existe pas nécessairement de fonction calculable permettant de choisir un élément dans chacune de ces classes. La question clef est ici celle de l'uniformité. Évidemment, à l'aide de $\emptyset'$, on pourra créer cette fonction de choix, mais que se passe-t-il si l'on considère des classes plus complexes ? Peut-on toujours construire une fonction de choix ? La réponse est non, sans l'aide d'un nouvel axiome.

(9) *L'axiome du choix* : étant donné une collection $(A_i)_{i \in I}$ d'ensembles non vides, il existe une fonction $f : I \to \bigcup_{i \in I} A_i$ telle que $f(i) \in A_i$ pour tout $i$.

L'axiome du choix apparaît nécessaire pour développer une théorie complète de la cardinalité des ensembles. En particulier, avec l'axiome du choix, on peut montrer que pour tous ensembles $A, B$ on a $|A| \le |B|$ ou $|B| \le |A|$ (nous en reparlerons avec l'étude détaillée des ordinaux dans le chapitre 27). Ce n'est plus du tout vrai sans l'axiome du choix, l'exemple par excellence en calculabilité étant certainement celui des degrés Turing. Il est facile de construire une injection de $2^N$ dans les degrés Turing, mais il est en revanche impossible de construire une injection des degrés Turing dans $2^N$ sans l'axiome du choix (il est en particulier impossible de montrer l'existence d'une fonction $f: 2^N \to 2^N$ telle que $X \equiv_T Y \leftrightarrow f(X) = f(Y)$).

Une première réaction est de se simplifier la vie et d'utiliser l'axiome du choix si nécessaire. Cette approche n'est toutefois pas dans l'esprit de la calculabilité, de laquelle la théorie des ensembles est moins éloignée que l'on ne pourrait le croire : les axiomes autres que l'axiome du choix nous permettent de construire des objets de plus en plus complexes à partir d'objets existants, un peu à la manière dont on construit des degrés Turing de plus en plus complexes en itérant le saut. L'axiome du choix est quant à lui fondamentalement non constructif, et n'est de ce point de vue là pas aussi légitime que les autres. Il conduit en plus à des théorèmes qui semblent paradoxaux, l'exemple le plus connu étant le *paradoxe de Banach/Tarski*, une
construction qui à l'aide de l'axiome du choix montre comment découper
une boule de l'espace $\mathbb{R}^3$ en un nombre fini de morceaux, et comment ré-
assembler ces moreaux pour obtenir deux boules strictement identiques à
la première.

En n'acceptant pas l'axiome du choix, on sort bien entendu de ce monde
idéal où la cardinalité de tout ensemble est comparable, mais il s'agit en fait
d'une situation « artificielle », dont nous n'avons pas réellement besoin.

4.6. Résultats d'indépendances

La théorie obtenue avec les axiomes (1)-(8) est la théorie ZF, et si on lui
ajoute l'axiome du choix, on a alors la théorie dite ZFC.

4.6.1. L'axiome du choix

La question de savoir si l'axiome du choix est démontrable à partir des
autres axiomes, ou même celle de savoir s'il ne risque pas d'introduire de
contradiction, est longtemps restée ouverte. Le théorème de complétude
de Gödel permet la technique suivante : si l'on fait l'hypothèse que ZF
est cohérent, et donc a un modèle, et qu'à l'aide de ce modèle on peut
construire un modèle de ZFC, on aura montré que la cohérence de ZF
implique celle de ZFC, et en particulier que ZF ne peut pas démontrer que
l'axiome du choix est faux (à moins bien sûr que ZF ne soit incohérent).
C'est exactement ce qu'a fait Gödel quelques années plus tard [74], via son
modèle dit de l'univers des constructibles. Ce n'est qu'encore plus tard,
en 1962, avec sa fameuse technique de Forcing dont nous verrons certains
aspects dans le chapitre 11, que Cohen [37] réussira le tour de force de
construire un modèle de ZF dans lequel l'axiome du choix est faux : l'axiome
du choix ne peut donc être ni démontré ni réfuté dans ZF.

4.6.2. L'hypothèse du continu

La question qui obséda Cantor tout au long de sa vie (et de nombreux
mathématiciens durant presque un siècle) est elle aussi indépendante des
autres axiomes de la théorie des ensembles (avec ou sans l'axiome du choix).
L'univers des constructibles de Gödel constitue également un modèle de
ZFC dans lequel l'hypothèse du continu est vérifiée, c'est-à-dire qu'il n'existe
aucun ensemble $A$ pour lequel $|N| < |A| < |2^N|$. Toujours avec sa technique
de forcing, Cohen a construit des modèles de ZFC dans lesquels on a un
nombre arbitraire d'infinis strictement compris entre $|N|$ et $|2^N|$.

Notons ici que l'on peut donner plusieurs versions de l'hypothèse du continu.
Celle formulée originellement par Cantor portait sur les ensembles de réels :
existe-t-il un ensemble $\mathcal{A} \subseteq \mathbb{R}$ tel que $|N| < |A| < |\mathbb{R}|$ ? Plus tard, la question
sera étendue à n'importe quel ensemble, et en particulier aux ordinaux, que
nous verrons formellement dans le chapitre 26. Quelle que soit la version
de l'hypothèse du continu, il s'agit d'une question indépendante des autres
axiomes de la théorie des ensembles.
Chapitre 10

Forcing de Cohen

Le forcing est une technique inventée
par le mathématicien Paul Cohen
au début des années 60 pour mon-
trer l'indépendance de l'hypothèse du
continu et de l'axiome de choix de
la théorie de Zermelo/Fraenkel. Cette
technique a révolutionné la théorie des
ensembles, et joue également un rôle
prépondérant en calculabilité, où elle
s'est imposée comme l'une des deux
techniques principales de construction
d'ensembles, aux côtés de la méthode
de priorité (voir le chapitre 13).

Historiquement, cette technique a été
conçue pour étendre un modèle M de
la théorie de ZF en lui ajoutant un nou-
vel objet G pour former un nouveau
modèle M[G] tout en permettant aux

éléments du modèle M de contrôler les propriétés du modèle étendu M[G].
Plus généralement, la technique de forcing permet de créer des objets
mathématiques à l'aide d'approximations de plus en plus précises, tout
en étant capable de contrôler certaines propriétés de l'objet final avant que
la construction ne soit terminée. Une notion de forcing est avant tout la
définition d'un ordre partiel d'approximations (P, ≤), où la relation d ≤ c
signifie que l'approximation d est plus précise que l'approximation c. Lors-
qu'une propriété (ou contrat) R sur l'objet final est déjà déterminée par

<figure><img src="image_71.png" /><figcaption>Paul Joseph Cohen, 1934-2007</figcaption></figure>
une approximation $c \in \mathbb{P}$, autrement dit lorsque quelle que soit la suite de la construction, l'objet final satisfera $\mathcal{R}$, on dit alors que $c \text{ force } \mathcal{R}$. Le cœur de la technique du forcing réside dans la capacité à forcer des propriétés complexes sur l'objet final à partir de simples approximations.

Le forcing est souvent considéré comme une technique difficile à appréhender aux premiers abords. Son application à la calculabilité, plus simple, permet d'une part de l'aborder en douceur, et d'autre part de comprendre plus facilement le détail de ses mécanismes sous-jacents. Cette simplicité est due essentiellement aux deux choses suivantes.

▷ À l'instar de la méthode des extensions finies, nous allons principalement nous servir du forcing pour créer des ensembles d'entiers, tout en contrôlant leurs puissances calculatoires. On s'intéressera donc à forcer des formules simples, du type $\llcorner \Phi^G(n) \downarrow \urcorner$ ou $\llcorner \Phi^G(n) \uparrow \urcorner$, où $G$ désigne l'ensemble final. Il s'agit donc de forcer des formules $\Sigma_1^0$ ou $\Pi_1^0$. Nous verrons que plusieurs constructions, notamment celles avec la méthode des extensions finies, sont des utilisations simplifiées du forcing. Nous verrons également comment étendre le forcing à des formules de complexité arbitraires, ce qui présente un premier niveau de complexité supplémentaire.

▷ Contrairement à la théorie des ensembles, nous ne forceons que des propriétés dont les quantificateurs portent sur les entiers. La création d'un ensemble d'entiers par forcing ne modifie pas la nature des entiers, et donc la portée des quantificateurs. En théorie des ensembles en revanche, les quantificateurs portent sur les ensembles, et la création d'un nouvel ensemble ajoute une grande quantité d'ensembles au modèle, et change donc la portée des quantificateurs. Il est alors nécessaire d'utiliser des *noms*, pour parler des objets de notre modèle étendu à l'intérieur de notre modèle de base. Nous n'aurons pas besoin d'avoir recours aux noms en calculabilité, ce qui rend la présentation plus abordable.

# 1. Formules de l'arithmétique du second ordre

Les énoncés que l'on $\llcorner \text{force} \urcorner$ en calculabilité sont toujours des formules de l'arithmétique du premier ordre avec des variables libres d'ensembles. Ces formules sont un cas particulier de l'arithmétique du second ordre, dont nous parlerons plus en détail dans le chapitre 22. Une formule de l'arithmétique du second ordre possède deux types de variables : des variables dites *du premier ordre* représentant des entiers et que l'on notera en minuscule, et des variables dites *du second ordre* représentant des ensembles d'entiers et que l'on notera en majuscule. Le langage se voit augmenté du symbole d'appartenance $\in$, et de la formule atomique
« $x \in A$ » . En arithmétique du second ordre, les quantifications peuvent être sur les entiers, et sur les ensembles d'entiers. Par exemple, l'énoncé « $\forall A \forall n \exists m (m > n \land m \in A)$ » affirme que tout ensemble d'entiers est infini.

L'arithmétique du premier ordre avec variables libres d'ensembles est une restriction de l'arithmétique du second ordre, où seules les quantifications sur les entiers sont autorisées<fnref n="1" />. Lors de l'évaluation d'une formule de l'arithmétique du second ordre dans un modèle donné, ses variables libres d'ensembles sont remplacées par des paramètres, c'est-à-dire des éléments du modèle considéré. Ainsi, l'énoncé $F(G) = \forall n \exists m (m > n \land m \in G)$ est une formule de l'arithmétique du premier ordre avec $G$ comme variables libres d'ensemble, et tout ensemble infini $X \subseteq \mathbb{N}$ est un paramètre pour lequel $F(X)$ est vrai.

Nous avons vu dans la section 9-3 les formules $\Delta_0^0$ de l'arithmétique : celles ne contenant que des quantifications bornées, c'est-à-dire des quantifications de la forme $\forall x \le y$ et $\exists x \le y$. Nous pouvons définir une hiérarchie sur les formules de l'arithmétique avec variables libres d'ensembles, similaire à la hiérarchie de la définition 9-3.2.

**Définition 1.1**

1. Une formule $F(Y_1, \dots, Y_k, x_1, \dots, x_m)$ de l'arithmétique du second ordre est $\Sigma_n^0$ si

$$F(Y_1, \dots, Y_k, x_1, \dots, x_m) = \underbrace{\exists y_1 \forall y_2 \dots Q y_n}_{n \text{ quantificateurs}} G(Y_1, \dots, Y_k, x_1, \dots, x_m, y_1, \dots, y_n),$$
pour $G(Y_1, \dots, Y_k, x_1, \dots, x_m, y_1, \dots, y_n)$ une formule $\Delta_0^0$, où $Q$ vaut $\exists$ si $n$ est impair, et $\forall$ si $n$ est pair.

2. Une formule $F(Y_1, \dots, Y_k, x_1, \dots, x_m)$ de l'arithmétique du second ordre est $\Pi_n^0$ si

$$F(Y_1, \dots, Y_k, x_1, \dots, x_m) = \underbrace{\forall y_1 \exists y_2 \dots Q y_n}_{n \text{ quantificateurs}} G(Y_1, \dots, Y_k, x_1, \dots, x_m, y_1, \dots, y_n),$$
pour $G(Y_1, \dots, Y_k, x_1, \dots, x_m, y_1, \dots, y_n)$ une formule $\Delta_0^0$, où $Q$ vaut $\forall$ si $n$ est impair, et $\exists$ si $n$ est pair. $\diamond$

Nous avons jusqu'ici implicitement utilisé les formules de l'arithmétique du second ordre, via l'utilisation de fonctionnelles. Le théorème 9-3.4 se décline en l'équivalence suivante.

<footnote n="1">1. Nous ne verrons que très tard dans cet ouvrage, dans la partie IV, la grande complexité calculatoire qui se cache derrière les quantifications du second ordre.</footnote>
**Théorème 1.2**

Soient $A, Z \in 2^N$. Les énoncés suivants sont équivalents.

(1) $A \subseteq \mathbb{N}$ est Z-c. e.

(2) Il existe $F(X, n)$ une formule $\Sigma_1^0$ de l'arithmétique du second ordre telle que $A = \{n \in \mathbb{N} : \mathbb{N} \models F(Z, n)\}$.

(3) Il existe une fonctionnelle Turing $\Phi(Z, n)$ telle que

$$A = \{n \in \mathbb{N} : \Phi(Z, n) \downarrow\}.$$

## 2. Forcing $\Sigma_1^0/\Pi_1^0$

Nous allons maintenant commencer notre immersion dans l'univers du forcing en étudiant une notion de forcing spécifique, à savoir le forcing de Cohen. Comme expliqué dans l'introduction, une notion de forcing est spécifiée par la donnée de son ordre partiel d'approximations. Dans notre cas, il s'agira de l'ordre partiel des chaînes, muni de la relation de préfixe. Il s'agit d'une des notions de forcing les plus simples conceptuellement, mais qui contient déjà les concepts fondamentaux du forcing.

Il existe plusieurs manières d'aborder le forcing, avec différents niveaux d'abstraction. Il est possible de le voir comme une élaboration de la méthode des extensions finies, cherchant à systématiser la satisfaction de contrats, et à en extraire une construction générale. Nous présenterons cette approche dans la section 2.1.

Il est également possible de formuler le forcing dans un cadre topologique. La topologie permet de définir une notion de classe d'ensembles $\llcorner$ négligeable $\urcorner$, ou maigre. La construction d'un ensemble par forcing consiste alors à choisir un élément $\llcorner$ typique $\urcorner$, c'est-à-dire évitant un ensemble négligeable de propriétés indésirables. Nous verrons cette approche dans la section 2.2.

### 2.1. L'approche par extensions finies

Reconsidérons à présent la méthode des extensions finies développée dans la section 4-8. Le but est de construire un ensemble $G \in 2^N$ satisfaisant une infinité de contrats $(R_e)_{e \in \mathbb{N}}$. Chaque contrat est traité indépendamment, et doit donc être satisfait tout en laissant suffisamment de degrés de liberté dans la construction pour satisfaire les autres contrats.
**Point sur les contrats**

Les contrats — que nous avons vus jusqu'ici de manière informelle — peuvent être vus comme des formules dans le langage de l'arithmétique du premier ordre avec variables d'ensembles, comportant une variable libre du second ordre représentant l'ensemble $G$ qui doit satisfaire le contrat. La méthode des extensions finies consiste à construire $G \in 2^N$ en spécifiant des segments initiaux de plus en plus longs, représentés sous forme de chaînes $\sigma \in 2^{<N}$. Les contrats $\Sigma_1^0$ sont ceux correspondant à des formules $\Sigma_1^0$ ou de manière équivalente ceux que l'on peut toujours mettre sous la forme $\llcorner \Phi_e(G, 0) \downarrow \gg$ pour une fonctionnelle $\Phi_e$. Les contrats $\Pi_1^0$ sont ceux correspondant à des formules $\Pi_1^0$ ou de manière équivalente ceux que l'on peut toujours mettre sous la forme $\llcorner \Phi_e(G, 0) \uparrow \gg$ pour une fonctionnelle $\Phi_e$.

**Satisfaction d'un contrat.** La procédure générale pour satisfaire un contrat $\mathcal{R}_e$ est la suivante : étant donné une chaîne $\sigma \in 2^{<N}$ représentant un segment initial de $A$ déjà spécifié pour satisfaire les contrats précédents, il s'agit de trouver une chaîne $\tau \supseteq \sigma$ telle que le contrat $\mathcal{R}_e$ est satisfait. L'ensemble final $G$ n'étant pas alors connu, le contrat doit être satisfait quelle que soit la suite de la construction, autrement dit il doit être satisfait pour tout $G \in [\tau] = \{X \in 2^N : \tau \prec X\}$.

**Ordre partiel des chaînes.** Prenons de la hauteur, et considérons la méthode des extensions finies d'un point de vue plus abstrait. Nous avons un ordre partiel ($2^{<N}, \leq$) qui correspond à l'ensemble $2^{<N}$ des chaînes finies, muni de la relation de préfixe. Nous avons aussi une fonction d'interprétation $[\cdot] : 2^{<N} \to \mathcal{P}(2^N)$ définie par $[\sigma] = \{X \in 2^N : \sigma \prec X\}$. Intuitivement, les éléments de $2^{<N}$ représentent des approximations de l'ensemble $G$ en construction. Étant donné une approximation $\sigma$, $[\sigma]$ est la classe des ensembles que l'on pourrait potentiellement obtenir à la fin de la construction. Plus on avance dans la construction, plus l'approximation s'affine et la classe des ensembles candidats se restreint. Ainsi, nous avons la propriété suivante : si $\sigma \leqprec \tau$, alors $[\tau] \subseteq [\sigma]$. Voyons une première définition de la relation de forcing.

**Définition 2.1.** Soit $\mathcal{R}$ un contrat $\Sigma_1^0$ ou $\Pi_1^0$. Une chaîne $\sigma$ force $\mathcal{R}$, que l'on notera par $\sigma \Vdash^* \mathcal{R}$, si le contrat est satisfait pour tout $G \in [\sigma]$. $\diamond$

**Densité.** Nous pouvons nous abstraire de la notion de contrat en représentant un contrat $\mathcal{R}_e$ comme l'ensemble $P_e \subseteq 2^{<N}$ des chaînes qui le forcent. Notons que si $\sigma$ force $\mathcal{R}_e$, alors tout $\tau \supseteq \sigma$ force également $\mathcal{R}_e$, car $[\tau] \subseteq [\sigma]$. L'ensemble $P_e$ est donc clos par suffixe. La procédure de satisfaction du contrat $\mathcal{R}_e$ consiste à montrer que pour toute chaîne $\sigma \in 2^{<N}$,
il existe une extension $\tau \supseteq \sigma$ telle que $\tau \in P_e$. Si c'est le cas, on dira que l'ensemble $P_e$ est dense.

**Définition 2.2.** Un ensemble $W \subseteq 2^{<\mathbb{N}}$ est dense si pour tout $\sigma \in 2^{<\mathbb{N}}$, il existe une extension $\tau \supseteq \sigma$ telle que $\tau \in W$. ◇

Intuitivement, un ensemble $W \subseteq 2^{<\mathbb{N}}$ est dense si quelle que soit la construc-
tion en cours $\sigma_0 \preceq \sigma_1 \preceq \dots \preceq \sigma_n$ à l'aide de la méthode des extensions
finies, il n'est jamais trop tard pour trouver une extension $\sigma_{n+1} \supseteq \sigma_n$
dans W. Il s'ensuit que si nous avons un ensemble dénombrable de contrats
représentés par des ensembles $(P_n)_{n \in \mathbb{N}}$, dès lors que ces ensembles sont
denses, il existe une suite infinie $\sigma_0 \preceq \sigma_1 \preceq \sigma_2 \preceq \dots$ telle que pour tout $n$, il
existe un entier $m$ pour lequel $\sigma_m \in P_n$. En particulier, soit $\{G\} = \bigcap_n[\sigma_n]$,
alors $G$ possèdera des segments initiaux dans chaque ensemble $P_e$.

Remarque

Si les ensembles $(P_n)_{n \in \mathbb{N}}$ sont uniformément c.e, alors la construction de
la suite infinie $\sigma_0 \preceq \sigma_1 \preceq \sigma_2 \preceq \dots$ peut se faire de manière calculable,
et l'ensemble $G$ résultant l'est également.

**Généricité.** Nous pouvons formaliser la construction de la méthode des extensions finies en un théorème trivial au vu des intuitions précédentes.

**Définition 2.3.** On dit qu'un ensemble $G \in 2^{<\mathbb{N}}$ rencontre un ensemble $W \subseteq 2^{<\mathbb{N}}$ si $G \upharpoonright_n \in W$ pour un certain $n \in \mathbb{N}$. Soit $\vec{D} = (D_n)_{n \in \mathbb{N}}$ une suite d'ensembles de chaînes; un ensemble $G \in 2^{<\mathbb{N}}$ est $\vec{D}$-générique s'il rencontre chaque $D_n$. ◇

Théorème 2.4

Soit $\vec{D} = (D_n)_{n \in \mathbb{N}}$ une suite dénombrable d'ensembles de chaînes denses et soit $\sigma \in 2^{<\mathbb{N}}$. Il existe un ensemble $\vec{D}$-générique qui étend $\sigma$.

PREUVE. Soit $\sigma_0 < \sigma_1 < \sigma_2 < \dots$ la suite infinie strictement croissante de
chaînes définies inductivement comme suit. Initialement, $\sigma_0 = \sigma$. Si $\sigma_n$ est
défini, $\sigma_{n+1}$ est une extension stricte de $\sigma_n$ dans $D_n$. Une telle extension
existe par densité de $D_n$. Soit $\{G\} = \bigcap_n[\sigma_n]$; alors, $G$ est $\vec{D}$-générique et
étend $\sigma$. ■

Nous verrons la contrepartie topologique du théorème précédent avec le
lemme 2.14. Le théorème 2.4 dit entre autre que si $(D_n)_{n \in \mathbb{N}}$ est une suite
d'ensembles denses correspondants aux contrats $(R_n)_{n \in \mathbb{N}}$, alors il existe des
ensembles $\vec{D}$-génériques, qui satisfont donc tous les contrats simultanément.
Il existe une quantité indénombrable d'ensembles de chaînes denses, et un ensemble $G \in 2^N$ ne peut pas être générique pour tous ces ensembles simultanément, simplement parce que l'ensemble $\{\sigma \in 2^N : \sigma \not\subset G\}$ est un ensemble dense que $G$ ne rencontre pas. La notion de généricité est donc dépendante d'une collection $\vec{D}$ dénombrable d'ensembles de chaînes denses.

## Suffisamment générique

Il est courant d'énoncer des résultats de la forme « tout ensemble suffisamment générique satisfait telle propriété ». Cela signifie qu'il existe une suite dénombrable $\vec{D} = (D_n)_{n \in \mathbb{N}}$ d'ensembles de chaînes denses telle que tout ensemble $\vec{D}$-générique satisfait la propriété. Notons qu'étant donné n'importe quelle autre suite dénombrable d'ensembles de chaînes denses $\vec{E} = (E_n)_{n \in \mathbb{N}}$, la suite $\{\vec{D}, \vec{E}\}$ est toujours une suite dénombrable d'ensembles de chaînes denses et l'on pourra donc produire un ensemble $\{\vec{D}, \vec{E}\}$-générique. C'est cela qui justifie l'appellation de suffisamment générique.

Nous allons reformuler la preuve de la proposition 4-8.2 en termes de densité et de généricité. Nous avons besoin pour cela d'étendre la relation de forcing aux contrats $\Sigma_2^0$, ce qui ne présente pas de difficulté : une chaîne $\sigma$ force un tel contrat si ce dernier est satisfait pour tout $G \in [\sigma]$. Nous verrons dans la section 4 que cette idée ne fonctionne plus pour les contrats $\Pi_2^0$.

**Proposition (4-8.2).** Pour tout ensemble non calculable $A$, il existe un ensemble $B$ tel que $B \subsetneq_T A$ et $A \subsetneq_T B$. ★

**PREUVE.** Soit $A$ un ensemble non calculable. Nous voulons construire un ensemble $B$ satisfaisant les contrats $(R_e)_{e \in \mathbb{N}}$ et $(S_e)_{e \in \mathbb{N}}$ :

$$ \mathcal{R}_e : \exists x \Phi_e^A(x) \uparrow \lor \exists x \Phi_e^A(x) \downarrow \neq B(x) \quad \mathcal{S}_e : \exists x \Phi_e^B(x) \uparrow \lor \exists x \Phi_e^B(x) \downarrow \neq A(x). $$

Soient $R_e \subseteq 2^{<N}$ et $S_e \subseteq 2^{<N}$ l'ensemble des chaînes forçant respectivement $R_e$ et $S_e$.

**Densité de l'ensemble $R_e$.** Soit $\sigma \in 2^{<N}$, et soit $x = |\sigma|$. Deux cas se présentent.

▷ Cas 1. On a $\Phi_e^A(x) \downarrow = i$ pour $i \in \{0, 1\}$. Il suffit alors de définir $\tau$ comme l'unique chaîne de longueur $|\sigma| + 1$ étendant $\sigma$ telle que $\tau(x) = 1 - i$. Pour tout $X \in [\tau]$, $X(x) = 1 - i \neq \Phi_e^A(x)$, donc $\tau \in R_e$.

▷ Cas 2. On a $\Phi_e^A(x) \uparrow$. Dans ce cas, $R_e = 2^{<N}$, et $\sigma \in R_e$.

**Densité de l'ensemble $S_e$.** Soit $\sigma \in 2^{<N}$. Trois cas se présentent.

▷ Cas 1. Il existe une entrée $x$ et un ensemble $X \supseteq \sigma$ tels que

$$ \Phi_e^X(x) \downarrow \neq A(x). $$
Dans ce cas, par la propriété de l'usage, il existe une chaîne finie $\tau \supseteq \sigma$
telle que $\Phi_e^X(x) \downarrow \neq A(x)$ pour tout $X \in [\tau]$. La chaîne $\tau$ force donc le
contrat $S_e$, donc $\tau \in S_e$.

▷ Cas 2. Il existe une entrée $x$ telle que pour tout ensemble $X \supseteq \sigma$, on a $\Phi_e^X(x) \uparrow$. Dans ce cas, la chaîne $\sigma$ force déjà le contrat $S_e$ en s'assurant que $\Phi_e^B(x) \uparrow$. Donc, $\sigma \in S_e$.

▷ Cas 3. Aucun des deux cas précédents n'apparaît. Nous avons alors montré dans la preuve initiale de la proposition 4-8.2 que ce cas ne pouvait pas arriver, car l'ensemble $A$ serait calculable, contrairement à notre hypothèse.

Soit $B$ un ensemble $(R_e, S_e)_{e \in \mathbb{N}}$-générique. Un tel ensemble existe par le théorème 2.4. En particulier, $B$ satisfait tous les contrats $R_e$ et $S_e$ singularément, donc $B \subsetneq_T A$ et $A \subsetneq_T B$. Cela conclut la preuve de la proposition 4-8.2. ■

## 2.2. L'approche topologique

La genèse de la méthode des extensions finies, de la généricité, et plus généralement du forcing, se trouve dans les travaux de René Baire, au début du XXe siècle. Une des motivations de Baire est à l'époque de comprendre un peu mieux certaines fonctions « bizzarres », mais qui surviennent naturellement en analyse. Si nous revenons un peu en arrière, dans la première moitié du XIXe siècle émerge la prise de conscience, notamment aux travers des travaux de Cauchy et Bolzano, qu'une suite $(f_n : \mathbb{R} \to \mathbb{R})_{n \in \mathbb{N}}$ de fonctions continues qui converge point par point n'a pas nécessairement pour limite une fonction continue, et pour cause, une fois les notions de calculabilité correctement étendues pour travailler dans $\mathbb{R}$, les limites de fonctions *effectivement continues* — c'est-à-dire calculables — sont exactement les fonctions $\Delta_2^0$, c'est-à-dire celles pour lesquelles $f(r)$ est calculable uniformément en $r'$, le saut de $r$. Il s'agit d'une simple application du lemme de Schoenfield.

Quelques décennies plus tard, Baire se penche sur ce phénomène, et es-
saye de mieux comprendre ces fonctions que sont les limites de fonctions
continues, et dont les irrégularités les rendent difficile à manipuler et même

<figure><img src="image_72.png" /><figcaption>René Baire, 1874-1932</figcaption></figure>
à appréhender avec clarté. Il présentera ses résultats dans le cours Pec-cot « leçons sur les fonctions discontinues », où il développe son fameux outillage mathématique des *catégories de Baire* pour montrer notamment qu'une fonction limite de fonctions continues, si elle n'est plus forcément continue, le sera malgré tout sur un « grand ensemble de points ». Selon la terminologie moderne, les points de discontinuité d'une telle fonction seront une classe maigre ou encore de *catégorie 1*. Le théorème 3.20 à venir peut être vu comme une version effective de ce résultat.

Nous avons défini dans la section 8-2 la notion d'ouvert de l'espace de Cantor, comme étant une classe de la forme $\bigcup_{\sigma \in U}[\sigma]$ pour un ensemble $U \subseteq 2^{<N}$ quelconque. La densité d'un ensemble de chaînes se traduit par une notion de densité de l'ouvert correspondant dans l'espace de Cantor.

**Définition 2.7.** Une classe $\mathcal{B} \subseteq 2^N$ est dite *dense* si elle intersecte tout cylindre $[\sigma]$, c'est-à-dire $[\sigma] \cap \mathcal{B} \neq \emptyset$ pour tout $\sigma \in 2^{<N}$. ◇

L'exercice suivant lie la notion de densité sur les ouverts de l'espace de Cantor, et sur l'ordre partiel des chaînes binaires.

**Exercice 2.8.** Étant donné $U \subseteq 2^{<N}$, on note $U^c$ la clôture par suffixe de $U$, c'est-à-dire $U^c = \{\tau \in 2^{<N} : \exists \sigma \in U \tau \supseteq \sigma\}$.

Soit $U \subseteq 2^N$. Montrer que $U^c$ est dense dans $2^N$ ssi l'ouvert $\bigcup_{\sigma \in U}[\sigma]$ est dense dans l'espace de Cantor. ◇

Notre but est de définir une notion de classe « négligeable » ou maigre pour donner une définition topologique du forcing. On part de l'intuition qu'un cylindre $[\sigma]$ n'est pas maigre. La notion de classe négligeable devrait être close par sous-classe. Ainsi, si une classe contient un ouvert non vide de l'espace de Cantor, elle n'est pas négligeable. On introduit pour formaliser cela la notion d'intérieur.

**Définition 2.9.** On appelle *intérieur* d'une classe $\mathcal{F} \subseteq 2^N$ — que l'on note $\text{int}(\mathcal{F})$ — le plus grand ouvert inclus dans $\mathcal{F}$, c'est-à-dire la réunion de tous les cylindres $[\sigma]$ tels que $[\sigma] \subseteq \mathcal{F}$. ◇

Une classe négligeable doit donc en particulier posséder un intérieur vide.

**Exemple 2.10.** La classe $\{X \in 2^N : \forall n X(2n) = 0\}$ est un fermé d'intérieur vide : il est en effet clair qu'elle ne contient aucun cylindre $[\sigma]$, car il existe toujours des $X \in [\sigma]$ tels que $X(2n) = 1$ pour $n$ suffisamment grand. Son complémentaire $\{X \in 2^N : \exists n X(2n) \neq 0\}$ est donc un ouvert dense, décrit par la réunion des cylindres $[\sigma 1]$ pour toute chaîne $\sigma$ de taille paire.
Nous avons maintenant les éléments en main pour définir la notion de classe maigre.

**Définition 2.11.** Une classe $\mathcal{B} \subseteq 2^\mathbb{N}$ est dite maigre si $\mathcal{B}$ est incluse dans une réunion dénombrable de classes fermées d'intérieur vide. Le complémentaire d'une classe maigre est dite *co-maigre*. ◇

Notons que, par passage au complémentaire, une classe est co-maigre si elle contient une intersection dénombrable d'ouverts denses. On laisse au lecteur le soin de montrer dans les deux exercices suivants que pour une suite d'ensembles $\vec{W} = (W_n)_{n \in \mathbb{N}}$ de chaînes denses, la classe des ensembles $\vec{W}$-génériques est une classe co-maigre.

**Exercice 2.12.** Soit $\vec{W} = (W_n)_{n \in \mathbb{N}}$ une suite d'ensembles de chaînes telles que chaque $W_n^c$ est dense (en reprenant la notation de l'exercice 2.8). Montrer que la classe $\cap_n[W_n]$ est co-maigre, où $[W_n] = \cup_{\sigma \in W_n}[\sigma]$. ◇

**Exercice 2.13.** Soit $\vec{W} = (W_n)_{n \in \mathbb{N}}$ une suite d'ensembles de chaînes denses. Montrer que la classe $\cap_n[W_n]$ contient exactement les ensembles $\vec{W}$-génériques. ◇

Les deux exercices précédents établissent donc un lien entre l'approche du forcing par la méthode des extensions finies et l'approche topologique : si $(\mathcal{R}_n)_{n \in \mathbb{N}}$ est une suite de contrats tels que les ensembles de chaînes correspondants $(W_n)_{n \in \mathbb{N}}$ sont denses, alors la classe des ensembles $\vec{W}$-génériques — qui satisfont tous les contrats simultanément — est co-maigre.

**Digression**

Historiquement, Baire appelle *classes de catégorie 1* les classes maigres, et *classes de catégorie 2* celles qui ne le sont pas. Cela donnera le nom de « théorie des catégories de Baire » à l'étude de ces notions. Notons qu'une classe n'est pas forcément maigre ou co-maigre. En particulier, les classes de catégorie 2 ne sont pas nécessairement co-maigres. En ce qui nous concerne, ce sont réellement les notions de maigre et co-maigre qui nous intéressent, et c'est donc ce vocabulaire que nous utiliserons.

**Fait**

D'après la définition 2.11, il est clair qu'une réunion dénombrable de classes maigres est maigre, et qu'une intersection dénombrable de classes co-maigres est co-maigre.