Paradoxe de russell

Le paradoxe de Russell, ou antinomie de Russell, est un paradoxe très simple de la théorie des ensembles (Russell lui-même parle de théorie des classes, en un sens équivalent), 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é.

Sommaire 1 Énoncé du paradoxe 2 Les solutions du paradoxe 3 Origines du paradoxe 4 Versions positives du paradoxe 5 Notes 6 Articles connexes 7 Voir aussi 8 Références

É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 de nouveau. On a donc une contradiction dans les deux cas, ce qui rend l'existence d'un tel ensemble paradoxal. Réécrit plus formellement, si l'on pose :

y = {x | x ∉ x}

on a immédiatement que y ∈ y ⇔ y ∉ y, donc chacune des deux possibilités, y ∈ y et y ∉ y, mène a une contradiction.

Le paradoxe utilise très peu des propriétés de l'appartenance, une relation binaire suffit, ce qui a permis à Bertrand Russell 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 ? L'étude des deux possibilités conduit de nouveau à une contradiction. On résout le problème en affirmant qu'un tel barbier ne peut exister (ou, en jouant sur les mots, qu'il n'est pas un homme), ce qui ne surprendra personne : il n'y a pas vraiment de paradoxe. Plus exactement la démonstration qui précède constitue justement une démonstration de la non-existence d'un tel barbier.

Pourquoi les choses ne sont-elles pas aussi 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^[2], 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.

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^[3]. 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^[4]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^[5]. 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 »^[6]. 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 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 restriction du principe de compréhension, due à Zermelo (1908) : un prédicat ne définit pas un ensemble mais sépare, dans un ensemble déjà donné, les objets qui ont une certaine propriété. 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).

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 :

y = {x ∈ A | x ∉ x}

On montre ainsi qu'il ne peut y avoir d'ensemble de tous les ensembles.

Notes

Articles connexes

• Paradoxe de Burali-Forti
• Paradoxe de Cantor
• Paradoxe de Richard
• Paradoxe de Berry

Voir aussi

• Logicisme

Références

• (en) A source Book in Mathematical Logic 1879-1931, Heijenoort J. van (ed.), (Harvard Univ. Press, Cambridge, 1967), ISBN 0-674-32450-1, ISBN 0-674-32449-8.
• (en) Bertrand Russell (1903), The principles of mathematics, vol 1, Cambridge Univ. Press (version en ligne disponible, incomplète au 4 janvier 2007), en fac simile sur le site de l'université du Michigan.
• Bertrand Russell (1906), Les paradoxes de la logique, revue de métaphysique et de morale 14, VOL 5, pp627-650 (1906) ; accessible sur le site de la BNF, au format "image" [1] (24 pages).
• (en) Bertrand Russell (1908), Mathematical logic as based on the theory of types, American journal of mathematics 30, repris dans A source Book in Mathematical Logic 1879-1931, pp 150-182.
• (en) Ernst Zermelo (1908), Neuer Beweis für di Möglichkeit einer Wohlordnung, Mathematische Annalen 65, 107-128, traduit en anglais sous le titre A new proof of the possibility of a well-ordering, dans A source Book in Mathematical Logic 1879-1931 (ouvrage cité), pp 183-198.
• (de) Ernst Zermelo (1908), référence à compléter (axiomatisation de la théorie des ensembles)
• 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.

• Portail des mathématiques