Paradoxe de Russell

Le paradoxe de Russell, ou antinomie de Russell, est un paradoxe très simple de la théorie des ensembles qui a joué un rôle important dans la formalisation de celle-ci. Il fut découvert par Bertrand Russell vers 1901 et publié en 1903. Il était en fait déjà connu à Göttingen, où il avait été découvert indépendamment par Ernst Zermelo à la même époque[1], mais ce dernier ne l'a pas publié.

Énoncé du paradoxe

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 solutions du paradoxe

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.

Origines du paradoxe

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.

Versions positives du paradoxe

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.

Notes et références

Notes

1. Selon une note de Zermelo lui-même, qui discute des objections à sa première preuve du fait que tout ensemble peut être bien ordonné, dans son article de 1908 (voir Jean van Heijenoort 1967, p. 191). Zermelo avait discuté de ce paradoxe avec entre autres David Hilbert. Ce dernier d'ailleurs, dans son article über das Unendliche (Sur l'infini) paru en 1926 aux Mathematische Annalen, mentionne une « contradiction, découverte par Zermelo et par Russell ».
2. (en) The Philosophy of Logical Atomism, repris dans The Collected Papers of Bertrand Russell, 1914-19, Vol 8., p. 228 ; Russell affirme qu’il tient cet exemple d’un collègue qu’il ne nomme pas.
3. Précisément le 16 juin 1902, lettre à laquelle Frege répond le 22 juin 1902. L'échange de lettres est traduit en anglais et présenté dans From Frege to Godel: A Source Book in Mathematical Logic, 1879-1931, p. 124 -128. Traduction et présentation en français dans François Rivenc (dir.) et Philippe de Rouilhan (dir.), Logique et fondements de mathématique : Anthologie (1850-1914), Paris, Payot, coll. « Bibliothèque scientifique Payot », 1992, 447 p. (ISBN 2-228-88483-9), p. 237-243
4. Appendice de Grundgesetze der Arithmetik, vol. II, in The Frege Reader, p.279
5. ce qui est une raison possible pour laquelle Zermelo, qui travaillait dans ce contexte et ne connaissait pas les travaux de Frege, ne chercha pas à le diffuser plus largement.
6. Lettre du 28 juillet 1899, traduite en anglais dans A source book in mathematical Logic ..., p. 113-117. Les lettres du 28 juillet, 28 et 31 août 1899 sont traduites en français dans Cavaillès 1962, p. 238-246. Cantor ne fait pas référence à Burali-Forti, ni ne parle de paradoxe.
7. la classe de tous les cardinaux n'est pas un ensemble. Dans la même lettre, Cantor relie ce résultat au précédent en utilisant implicitement l'axiome du choix, et le schéma d'axiomes de remplacement
8. Pour Cantor, une multiplicité est toujours définie, mais inconsistante quand le fait de considérer la totalité de ses éléments conduit à une contradiction. Ce n'est pas une définition formellement satisfaisante. Mais il peut énoncer, par exemple que les deux notions, multiplicité consistante et inconsistante, sont stables par « équipotence », ce qui est, comme le remarque Jean Heijenoort (préface de la traduction de la lettre de 1899 à Dedekind), une version encore informelle du schéma d'axiomes de remplacement. De façon générale il utilise ces notions de façon cohérente avec la formalisation qui en sera faite plus tard dans ZFC.

Références

• (en) Godehard Link (de), One Hundred Years Of Russell's Paradox: Mathematics, Logic, Philosophy, de Gruyter, 2004, 672 p. (ISBN 978-3110174380)
• (en) Jean van Heijenoort, From Frege to Gödel, A Source Book in Mathematical Logic 1879-1931, Cambridge, Harvard Univ. Press, 1967 (ISBN 0-674-32449-8, présentation en ligne)
• (en) Bertrand Russell, The principles of mathematics, vol. 1, Cambridge Univ. Press, 1903,version en ligne disponible (incomplète au 4 janvier 2007) et fac simile sur le site de l'université du Michigan
• Bertrand Russell, « Les paradoxes de la logique », dans Revue de métaphysique et de morale vol. 14, n° 5, 1906, p. 627-650, [lire en ligne] sur Gallica
• (en) Bertrand Russell, « Mathematical logic as based on the theory of types », dans American Journal of Mathematics, vol. 30, 1908, repris dans A Source Book…, p. 150-182
• (de) Ernst Zermelo, « Neuer Beweis für die Möglichkeit einer Wohlordnung », dans Mathematische Annalen, vol. 65, 1908, p. 107-128, traduit sous le titre (en) « A new proof of the possibility of a well-ordering », dans A Source Book…, p. 183-198
• (de) Ernst Zermelo, « Untersuchungen über die Grundlagen der Mengenlehre I », Mathematische Annalen, vol. 65, n^o 2,‎ 1908, p. 261–281 (DOI 10.1007/BF01449999)
• Jean Cavaillès, Philosophie mathématique, Hermann, 1962
  Contient, entre autres, les Remarques sur la formation de la théorie abstraite des ensembles de 1938, et une traduction de la correspondance Dedekind-Cantor qui avait été rassemblée et publiée par Jean Cavaillès et Emmy Noether en 1937.
• Logicomix, édition française Vuibert, 2010
  Scénario : Apóstolos K. Doxiàdis, Christos Papadimitriou - Dessin : Alecos Papadatos - Couleurs : Annie Di Donna [détail des éditions]
  Roman graphique sur la quête des fondements des mathématiques, dont le narrateur est Bertrand Russell.

Articles connexes

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