Dans l'article précédent on a évoqué le paradoxe du Menteur, qui a montré que « la tendance à l'universalisme propre au langage quotidien » (Tarski) y rendait les paradoxes inévitables et apparemment insolubles (mais d'ailleurs sans gravité, comme on l'a vu). Au 20-ième siècle, on a rencontré des paradoxes logiques dans des théories mathématiques, comme on va en voir un exemple maintenant : là, un langage précis, propre à une théorie formalisée, permet de les résoudre.

Russell/Zermelo

Définir un ensemble d'objets par compréhension consiste à donner une propriété caractéristique de ses éléments. Dans les premières versions de la théorie des ensembles (qualifiées aujourd'hui de naïves) on pensait pouvoir toujours définir « l'ensemble $X$ des objets $x$ qui satisfont à la propriété $P$ » : $$X=\{x:\, P(x)\}.$$ Russell1 (1903) et (indépendamment, peut-être même avant) Zermelo2 trouvent un paradoxe en considérant « l'ensemble des ensembles qui ne sont pas éléments d'eux-mêmes » : $$X=\{x:\, x\notin x\}$$ (où $x$ est lui-même un ensemble3). Est-ce que $X$ est élément de lui-même ? On voit que la question conduit à la contradiction : $X\in X\Leftrightarrow X\notin X$.

Zermelo résout le problème en 1908 en formulant une théorie des ensembles où la définition par compréhension est toujours limitée à un ensemble : pour tout ensemble $A$ et toute propriété $P$ définie pour les éléments de $A$, on peut définir l'ensemble des $x$ dans $A$ qui satisfont à la propriété $P$ : $$X=\{x\in A:\, P(x)\}.$$ Dans la théorie de Zermelo, le paradoxe disparaît ; ou plutôt, il devient une preuve que l'ensemble $X=\{x\in A:\, x\notin x\}$ n'est pas un élément de $A$ : car si on suppose que $X\in A$ (et seulement sous cette supposition) on retrouve la contradiction $X\in X\Leftrightarrow X\notin X$, et la seule échappatoire est que $X\notin A$. En particulier, il n'y a pas d'ensemble de tous les ensembles (car en prenant pour $A$ l'ensemble de tous les ensembles l'échappatoire $X\notin A$ disparaîtrait). On retrouve ainsi le slogan selon lequel un paradoxe dans une théorie mal formalisée devient une preuve par l'absurde de quelque chose dans une théorie bien formalisée.

Remarque 1 : En fait, le paradoxe de Russell-Zermelo est déjà inspiré d'une preuve par l'absurde d'un théorème de Cantor : il s'agissait de montrer que pour tout ensemble $X$, il n'existe pas de surjection de $X$ sur ${\mathcal P}(X)$ (l'ensemble des parties de $X$) ; c'est-à-dire qu'il n'existe pas de fonction $f:X\to {\mathcal P}(X)$ dont l'image soit égale à tout l'ensemble ${\mathcal P}(X)$. L'argument de Cantor est essentiellement le suivant : soit $f:X\to {\mathcal P}(X)$ une fonction et posons $Y=\{x\in X:\, x\notin f(x)\}$. Il est clair qu'il n'existe aucun $y\in X$ tel que $Y=f(y)$, car on aurait la contradiction $y\in Y\Leftrightarrow y\notin Y$ ; donc $f$ n'est pas surjective. On note que cette preuve est valable dans la théorie de Zermelo, puisque $Y$ est défini avec des éléments de l'ensemble donné $X$.

Remarque 2 : Russell a proposé une autre solution aux paradoxes de la théorie naïve des ensembles, la théorie des types : dans cette théorie, on doit pouvoir attribuer à chaque ensemble un « type » unique et le type d'un ensemble doit toujours être différent des types de ses éléments. On ne peut donc jamais avoir $x\in x$. Dans ce cadre, $X=\{x:\, x\notin x\}$ ne peut pas définir un ensemble car son type devrait être différent de ceux de tous ses éléments, c'est-à-dire de tous les ensembles (puisque tous vérifient la propriété $x\notin x$) : le paradoxe s'est transformé en une preuve d'invalidité d'une formule. (Les types utilisés aujourd'hui en informatique sont inspirés de la théorie de Russell.) Comme théorie des ensembles, on préfère habituellement celle de Zermelo, qui est plus simple, ou des versions un peu plus riches (comme la théorie de Zermelo-Fraenkel-Skolem). Notons que la théorie de Zermelo n'interdit pas que $x\in x$ : cette éventualité n'y pose aucun problème connu. Certaines extensions de la théorie de Zermelo contiennent toutefois un axiome de fondation qui interdit notamment que $x\in x$.

Richard

$\bullet$ Rappel : indénombrabilité des réels par l'argument diagonal de Cantor. Avant d'exposer le paradoxe de Richard, rappelons comment l'argument diagonal de Cantor4 permet de prouver que $\mathbb R$ n'est pas dénombrable (c'est-à-dire qu'on ne peut pas former une suite de réels qui les contienne tous). Donnons-nous une suite de réels écrits en base 10 (par exemple) : \begin{equation}\notag \begin{split} x_1&=e_1,c_{11}c_{12}c_{13}c_{14}\dots\\ x_2&=e_2,c_{21}c_{22}c_{23}c_{24}\dots\\ x_3&=e_3,c_{31}c_{32}c_{33}c_{34}\dots\\ x_4&=e_4,c_{41}c_{42}c_{43}c_{44}\dots\\ \ldots & \end{split} \end{equation} (les entiers $e_i$ sont les parties entières ; les $c_{ij}$ sont des chiffres ; pour les nombres décimaux, on choisit le développement qui se termine par des chiffres 0). Formons le réel \begin{equation}\notag \begin{split} x&=0,c_{1}c_{2}c_{3}c_{4}\dots\\ \end{split} \end{equation} où $c_i=1$ si $c_{ii}\ne 1$ et $c_i=0$ si $c_{ii}=1$ : on a donc $c_i\ne c_{ii}$ pour tout $i$ et par conséquent $x\ne x_i$ pour tout $i$. Cela montre qu'aucune suite de réels ne contient tous les réels.

$\bullet$ Énoncé du paradoxe de Richard. Le paradoxe de Jules Richard5 utilise le même argument sur une autre suite. Appelons longueur d'un texte (fini) en français le nombre de lettres et autres signes (chiffres, ponctuation, espaces,...) qu'il contient. Énumérons tous les textes par longueur croissante et, pour une longueur donnée, selon l'ordre lexicographique (on munit l'alphabet de son ordre usuel, qu'on prolonge comme on le veut aux autres signes). Certains de ces textes définissent un nombre réel (par exemple : « la racine carrée positive de 2 » ou « le plus petit nombre premier qui s'écrive avec au moins cent chiffres en base 10 ») : conservons-les et supprimons tous les autres. Dans l'énumération restante, le premier texte définit un nombre $x_1$, le deuxième un nombre $x_2$, etc. Chacun de ces nombres possède un développement décimal (unique, si on choisit pour les nombres décimaux le développement qui se termine par des chiffres 0). Appliquons l'argument diagonal comme ci-dessus : $c_i=1$ si $c_{ii}\ne 1$ et $c_i=0$ si $c_{ii}=1$, pour tout $i\in\mathbb N^*$. Cela définit, par la suite de ses chiffres décimaux, un nombre $x$ de $[0,1\mathclose[$ bien déterminé, qui n'est aucun des $x_i$ : donc il ne peut pas être défini par un texte — mais c'est pourtant ce qu'on vient de faire !

$\bullet$ Explication/solution. L'explication proposée par Richard est la suivante : quand on examine un à un les textes en français pour décider s'ils définissent un réel, on arrive à un certain moment au texte ci-dessus, censé définir $x$. Doit-on l'accepter ou le rejeter ? La définition de $x$ est valide si la suite $x_1,x_2,...$ est bien définie. Or, dit Richard, elle ne l'est pas encore puisqu'on est en train de la constituer (il reste une infinité de textes à examiner). On définit $x$ à partir de la suite $(x_i)$ alors que la définition de $x$ fait partie des textes à examiner pour définir cette suite : il y a là un cercle vicieux, les définitions de $x$ et de la suite $(x_i)$ se présupposant l'une l'autre.

Cela signifie que la notion de « réel définissable par un texte en français » est mal définie : elle dépend du contexte. En effet, passons en revue une première fois tous les textes possibles : celui qui est censé définir $x$ (ci-dessus) doit être rejeté car la liste $(x_i)$ qu'il présuppose n'existe pas encore (et donc ce texte ne définit pas un nombre)6. Après avoir terminé l'examen de tous les textes, on a une liste $(x_i)$. Si alors on recommence depuis le début l'examen de tous les textes, cette fois le texte censé définir $x$ doit être accepté puisque la liste $(x_i)$ requise existe. Après avoir terminé ce second examen exhaustif, on a une nouvelle liste dont $x$ fait partie, mais il n'y a plus de paradoxe : car le paradoxe était

le nombre $x$ n'est pas sur la liste et il est sur la liste

et maintenant on a

le nombre $x$ n'est pas sur la première liste et il est sur la deuxième.

Si on passe en revue une troisième fois tous les textes, le texte censé définir $x$ définit un nouveau nombre, différent du précédent (car hors de la deuxième liste) ! Ainsi, dans ce processus, le même texte ne définit d'abord pas un nombre, puis il en définit un, puis il en définit un autre, etc. Chaque nouveau « scan » modifie le nombre défini par le même texte ! La notion de « définition » d'un nombre par un texte donné change d'un « scan » à l'autre et le paradoxe surgit quand on veut appliquer la même notion à $x$ et aux $x_i$.

Pour préciser tout cela on peut formaliser : les textes énumérés sont alors les formules d'un langage formel $L$ ; la définition de $x$ est écrite dans un métalangage de $L$, donc $x$ n'a aucune raison de figurer dans la liste des nombres qui sont définis (en un sens précis, cette fois) par une formule de $L$ ; et le paradoxe devient une preuve par l'absurde qu'en effet il n'y figure pas.

$\bullet$ Une variante du paradoxe de Richard. Énumérons tous les textes en français et conservons seulement ceux qui énoncent une propriété d'une variable entière $n$ (par exemple : « $n$ est pair » ou « $n$ est un carré »). On obtient une liste : \begin{equation}\tag{$**$} A_0(n),\, A_1(n),..., \, A_m(n),... \end{equation} Posons $B(n)=\mathrm{NON\, } A_n(n)$ : c'est une propriété de l'entier $n$ (qui dit que $n$ n'a pas la propriété $A_n$). Elle doit donc faire partie de la liste $(**)$ : on l'y cherche et on trouve que $B(n)=A_N(n)$ pour un certain $N\in\mathbb N$. Alors $A_N(N)=B(N)=\mathrm{NON\, } A_N(N)$ : ainsi $A_N(N)$ est sa propre négation, donc elle est vraie si et seulement si elle est fausse ! Là encore, la définition de $A_N$ et de toute la suite $(A_n)$ se présupposent l'une l'autre. Si on formalise, les $A_n$ sont des formules écrites dans un langage $L$ tandis que $B$ s'écrit dans un métalangage $L'$ (qui permet de parler des formules de $L$ et de ranger celles qui nous intéressent ici en une suite $(A_n)$) : il n'y a donc pas de raison à priori que $B$ soit formulable dans le langage $L$ lui-même, et le paradoxe devient une preuve par l'absurde qu'en effet il ne l'est pas (si le langage $L$ est cohérent).

$\bullet$ Le problème de l'arrêt. Voici une preuve d'impossibilité en informatique théorique basée sur la variante ci-dessus du paradoxe de Richard. On aimerait avoir un moyen automatique de savoir si un programme $P$ (écrit dans un langage de programmation donné) dans lequel on introduit une entrée $e$ va s'arrêter sur un résultat ou s'il va tourner indéfiniment. Une entrée est une chaîne finie de bits $0$ ou $1$, qu'on peut considérer comme un entier écrit en base 2 après l'avoir préfixée d'un chiffre 1 pour éviter toute confusion7. Les programmes peuvent aussi être réduits à des chaînes finies de bits $0$ ou $1$ ; on peut donc les énumérer : $P_1,P_2,...$ Imaginons qu'on ait mis au point un programme $\texttt{halt}$ (dans le même langage de programmation) dans lequel il suffirait de mettre en entrée le couple $(n,e)$ (ou l'entier $2^{n}3^{e}$, si on veut que là aussi les entrées soient des entiers) pour qu'il nous dise, en un temps fini, si le programme $P_n$ avec l'entrée $e$ va s'arrêter ou non. Définissons le programme $\texttt{anti}$ comme suit : $\texttt{anti}$ s'arrête pour l'entrée $n$ (et sort par exemple la valeur $1$) si $\texttt{halt}$ dit que $P_n$ lancé avec l'entrée $n$ tournera indéfiniment, et $\texttt{anti}$ se met à boucler indéfiniment si $\texttt{halt}$ dit que $P_n$ lancé avec l'entrée $n$ s'arrêtera. Le programme $\texttt{anti}$ (écrit dans le même langage) doit faire partie de la liste $P_1,P_2,...$ : disons que c'est $P_N$. On voit que si on introduit l'entrée $N$ dans ce programme $P_N$, celui-ci s'arrêtera si et seulement si $\texttt{halt}$ dit qu'il ne s'arrêtera pas. Donc $\texttt{halt}$ ne répond pas toujours correctement, contrairement à l'hypothèse (on dit que le problème de l'arrêt n'est pas décidable algorithmiquement). Ce résultat est dû à Alan Turing8, 1936.

Berry

$\bullet$ Énoncé. Le paradoxe de Berry est une variante de celui de Richard, où l'argument diagonal est remplacé par un argument de minimum. Il peut s'énoncer ainsi : « le plus petit entier naturel qui ne peut être défini en moins de seize mots » ; le paradoxe est que cette définition tient en quinze mots !9 Là encore, il y a un cercle vicieux : la phrase suppose une notion de « définition » et le paradoxe surgit lorsqu'on applique cette notion à la phrase elle-même. Pour le résoudre, il faut formaliser un peu.

$\bullet$ Solution. On se donne un langage formel $L$ basé sur un alphabet10fini. Certaines formules définissent un entier (« définissent » : en un sens propre au langage $L$). Comme il y a un nombre fini de formules à moins de $n$ symboles, il y a un nombre fini d'entiers qui peuvent être définis en moins de $n$ symboles dans le langage $L$. Considérons « le plus petit entier naturel qui ne peut être défini en moins de $100$ symboles dans le langage $L$ ». Cette définition caractérise un entier bien précis, qui dépend de $L$ : disons $n(L)$. Elle tient en moins de $100$ symboles mais il n'y a pas de contradiction car elle n'est pas exprimée dans le langage $L$ : elle est écrite en français, qui n'est pas un langage rigoureusement formalisé... On peut la formaliser, mais comme elle parle du langage $L$, elle sera écrite à priori dans un métalangage $L'$ de $L$. Et si la formalisation de cette définition dans $L'$ tient encore en moins de $100$ symboles, cela prouvera seulement que $n(L)$ n'est pas $n(L')$ (« le plus petit entier naturel qui ne peut être défini en moins de $100$ symboles dans le langage $L'$ »). Le paradoxe venait de la confusion de $L$ et $L'$ (et du langage courant, non formalisé), et donc de $n(L)$ et $n(L')$ qui sont à priori deux nombres différents. Il se peut qu'il existe un moyen de traduire dans le langage $L$ la définition de $n(L)$ : dans ce cas, le paradoxe de Berry devient simplement une preuve par l'absurde que cette traduction dans le langage $L$ ne s'écrira pas en moins de $100$ symboles (si $L$ est cohérent).