Paradoxe de Russell

On peut formuler le paradoxe ainsi : l'ensemble des ensembles n'appartenant pas à eux-mêmes appartient-il à lui-même ? Si on répond oui, alors, comme par définition les membres de cet ensemble n'appartiennent pas à eux-mêmes, il n'appartient pas à lui-même : contradiction. Mais si on répond non, alors il a la propriété requise pour appartenir à lui-même : contradiction à nouveau. On a donc une contradiction dans les deux cas, ce qui rend paradoxale l'existence d'un tel ensemble. Réécrit plus formellement, si l'on pose :

${\displaystyle y=\{x|x\notin x\}}$

on a immédiatement que y ∈ y ⇔ y ∉ y, donc chacune des deux possibilités, y ∈ y et y ∉ y, mène à une contradiction (formellement, toute théorie contenant le théorème A ⇔ non-A est incohérente). C'est la raison pour laquelle, la remarque de Russell est plus qu'un simple paradoxe, elle est une antinomie, une véritable contradiction logique.

Le paradoxe utilise très peu de propriétés de l'appartenance, une relation binaire suffit, ce qui a permis à Bertrand Russell[2] de l'illustrer sous la forme plus imagée, mais qui a la même structure, du paradoxe du barbier. Un barbier se propose de raser tous les hommes qui ne se rasent pas eux-mêmes, et seulement ceux-là. Le barbier doit-il se raser lui-même ?

Pourquoi les choses ne sont-elles pas simples en théorie des ensembles ? Un principe qui semble assez naturel est de considérer que toute propriété, plus précisément tout prédicat du langage, définit un ensemble : celui des objets qui vérifient cette propriété. Mais si l'on utilise ce principe, dit principe de compréhension sans restriction, on doit admettre l'existence de l'ensemble paradoxal, défini par le prédicat « ne pas appartenir à soi-même » : c'est ce que l'on a fait justement en « définissant » l'ensemble y = {x | x ∉ x}. Plus simplement (l'existence d'un tel ensemble suffit, l'unicité est indifférente), on a utilisé le cas particulier suivant du principe de compréhension non restreint :

∃y ∀x (x ∈ y ⇔ x ∉ x)

La théorie qui contient ce seul axiome, et donc a fortiori toutes les instances du principe de compréhension non restreint, est contradictoire ; la démonstration est la même que celle donnée ci-dessus.

Russell décrivit ce paradoxe dans une lettre adressée en 1902 à Gottlob Frege[3], où il montrait à ce dernier que l'une des règles introduite dans ses Grundgesetze der Arithmetik, la compréhension non restreinte, rendait la théorie de Frege contradictoire. Le paradoxe est alors bel et bien une antinomie : une contradiction interne à la théorie. Frege souhaitait dans cet ouvrage fonder les mathématiques sur des bases purement logiques, tâche à laquelle devait également s'atteler Russell (voir logicisme), avec les Principia Mathematica. Il fait paraître ce paradoxe, (et d'autres) dans son ouvrage The Principles of Mathematics publié en 1903, tandis que, la même année, Frege adjoint au second volume de Grundgesetze der Arithmetik un appendice où il l'expose en faisant précéder l'analyse du paradoxe de cet aveu d'une grande honnêteté : « Pour un écrivain scientifique, il est peu d'infortunes pires que de voir l'une des fondations de son travail s'effondrer alors que celui-ci s'achève. C'est dans cette situation inconfortable que m'a mis une lettre de M. Bertrand Russell, alors que le présent volume allait paraître »[4].

La théorie des ensembles de Georg Cantor était également concernée par le paradoxe de Russell. Contrairement à la théorie de Frege, la théorie des ensembles de Cantor est une théorie mathématique, et ne s'attaque pas à la formalisation de la logique elle-même (qui est le véritable succès de Frege). Cependant la théorie n'était pas formalisée, ce qui la rend d'ailleurs potentiellement sujette aux paradoxes qui font intervenir le langage, comme le paradoxe de Richard ou le paradoxe de Berry. Le paradoxe de Russell montrait que l'ensemble paradoxal en jeu ne peut exister, et laissait craindre que la théorie soit contradictoire. Mais le paradoxe de Russell n'était pas le premier paradoxe à apparaître dans la théorie des ensembles de Cantor[5]. Le paradoxe de Burali-Forti, découvert par ce dernier en 1897, est très clairement interprété par Georg Cantor dans une lettre de 1899 à Richard Dedekind[6] comme montrant que l'« ensemble » paradoxal en jeu, que nous appelons aujourd'hui la classe de tous les ordinaux, n'est pas un ensemble, plus exactement est de nature différente. De même pour le paradoxe de Cantor (1899) sur le plus grand cardinal[7]. Il n'y a donc aucun doute, qu'à cette époque, Cantor ne pense pas que tout prédicat définisse un ensemble, même s'il ne donne pas de définition précise de la différence entre ce que nous appelons aujourd'hui « ensemble » et « classe propre », et qu'il évoque sous les termes de « multiplicité [Vielheit] consistante et inconsistante »[8]. Mais la solution de Cantor aux paradoxes ensemblistes, trop peu formelle, n'a pas vraiment réussi à convaincre Richard Dedekind, l'un des premiers à utiliser la notion d'ensemble, et qui reste très ébranlé par la découverte des paradoxes.

Par ailleurs, le paradoxe de Russell a l'avantage d'être particulièrement simple : nul besoin des notions de bon ordre, d'ordinal ou de cardinal en jeu dans les paradoxes de Burali-Forti et de Cantor. Il posa de façon encore plus cruciale la nécessité d'une formalisation de la théorie des ensembles (qui bien sûr doit éviter les paradoxes connus), et il joua un rôle important dans les débats autour de la mise au point de celle-ci.

Les principales solutions apportées pour éluder ce paradoxe furent :

• La restriction du principe de compréhension, due à Zermelo (1908) : un prédicat ne définit pas un ensemble mais ce que l'on appelle une classe et son intersection avec un ensemble donne un sous-ensemble de celui-ci. Il est possible d'écrire le prédicat « x ∉ x », mais celui-ci ne définit plus un ensemble. Il peut définir un sous-ensemble d'un ensemble donné, mais cela ne conduit pas à un paradoxe (voir plus loin). Il est nécessaire, pour développer les mathématiques, d'introduire un certain nombre d'autres instances du principe de compréhension général comme axiomes particuliers (paire, réunion, ensemble des parties, ...). Plus tard Abraham Fraenkel et Thoralf Skolem introduisirent (indépendamment) le schéma d'axiomes de remplacement, qui est toujours une restriction du principe de compréhension général, mais étend encore le schéma d'axiomes de compréhension introduit par Zermelo. Ils précisèrent également la notion de prédicat, et, en particulier Skolem, le contexte logique (le calcul des prédicats du premier ordre).
• la théorie des types de Russell, esquissée en appendice de l'ouvrage déjà cité de 1903. Russell la développe véritablement dans un article de 1908 (voir références). Il poursuit, en compagnie de Whitehead, avec les Principia Mathematica parus en 1910. Selon cette théorie, les ensembles sont de types hiérarchisés. À un ensemble ne peuvent appartenir que des objets, qui peuvent être des ensembles, mais sont de types strictement inférieurs au type de l'ensemble initial, de sorte qu'on ne peut tout simplement plus écrire l'énoncé paradoxal (on ne peut plus écrire le prédicat d'auto-appartenance « x ∈ x », a fortiori sa négation). Russell n'a pas immédiatement développé la théorie des types après 1903. Il a d'abord pensé à des solutions alternatives, comme la théorie « pas de classe », qu'il tente d'esquisser dans son article de 1906. Dans ce même article, Russell ne cite d'ailleurs même pas la théorie des types parmi les solutions qu'il a explorées.

La démonstration du paradoxe de Russell repose sur un argument diagonal, elle est très semblable à la démonstration du théorème de Cantor : le cardinal de l'ensemble des parties d'un ensemble (infini) E est strictement plus grand que celui de cet ensemble. Rappelons que pour démontrer ce théorème, on montre qu'une fonction f de E dans P(E), l'ensemble des parties de E, ne peut être surjective. En effet B = {x ∈ E | x ∉ f(x)} n'appartient pas à l'image de f : sinon pour un certain y, B=f(y), et y ∈ f(y) ⇔ y ∉ f(y), ce qui mène à une contradiction.

Cela rend impossible l'existence d'un plus grand cardinal. Or le cardinal de l'« ensemble » de tous les ensembles ne peut être que le plus grand cardinal. Plus précisément, l'« ensemble » de tous les ensembles contiendrait son ensemble des parties, et donc serait de cardinal supérieur ou égal à celui-ci.

Russell a déclaré qu'il était arrivé au paradoxe qui porte son nom en analysant soigneusement le paradoxe de Cantor. D'ailleurs, il peut paraître naturel pour un ensemble de ne pas appartenir à lui-même. Si l'on introduit un axiome qui interdit à un ensemble de s'appartenir à lui-même (comme l'axiome de fondation), cela ne résout pas le paradoxe : si une théorie est contradictoire, toute théorie obtenue en ajoutant des axiomes le sera également. On peut toujours définir l'ensemble {x| x ∉ x} des ensembles qui n'appartiennent pas à eux-mêmes, qui dans ce cas devient l'ensemble de tous les ensembles.

Le paradoxe de Russell repose sur un énoncé démontrable, ou encore universellement valide, du calcul des prédicats du premier ordre avec un symbole de relation binaire, soit R, à savoir :

¬ ∃y ∀x (x R y ⇔ ¬ x R x)

puisque l'existence d'un tel y mène à une contradiction. C'est ce que l'on a déjà remarqué à propos du paradoxe du barbier. On a ainsi une version très épurée d'une certaine forme d'argument diagonal. On peut remarquer que, si la démonstration donnée ci-dessus repose sur le principe du tiers exclu, il n'est pas très difficile de la réaliser en logique intuitionniste.

Dans la théorie des ensembles de Zermelo, en fait dans toute théorie qui admet le schéma d'axiomes de compréhension (restreint), on montre, en réinterprétant le paradoxe, que pour tout ensemble A, il existe un ensemble y qui n'appartient pas à A, à savoir :

${\displaystyle y=\{x\in A|x\notin x\}}$

En effet, on peut se demander de quelle manière le schéma de compréhension restreint résout concrètement le paradoxe en posant à nouveau frais la question qui menait initialement à la contradiction pour le schéma de compréhension non restreint : « y appartient-il à lui-même? »

${\displaystyle \quad \quad \quad {\begin{array}{lcr}y\in y\Leftrightarrow (y\in A\ \mathrm {et} \ y\notin y)\\y\notin y\Leftrightarrow (y\notin A\ \mathrm {ou} \ y\in y)\end{array}}}$

La première ligne mène à une contradiction. On en déduit que si un tel y existe, il n'appartient pas à lui-même et n'appartient pas non plus à A.

On montre ainsi qu'il ne peut y avoir d'ensemble de tous les ensembles et on dit que le rassemblement de tous les ensembles est une classe propre.

• Crise des fondements
• Logicisme
• Paradoxe de Burali-Forti
• Paradoxe de Cantor
• Paradoxe de Richard
• Paradoxe de Berry
• Signification (philosophie)