Voir la source de 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<ref>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 référence citée, traduction anglaise 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 ». </ref>, 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 :
{{énoncé|paradoxe de Russell,|<math>y = \{ x | x \notin x \}</math>}}
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 [[Cohérence_(logique)|incohérente]]).

Le paradoxe utilise très peu de 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 (logique mathématique)|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 [[schéma d'axiomes de compréhension|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 :
{{énoncé|∃''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]]<ref>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 {{harvsp|id=''A Source Book…''|texte=''From Frege to Godel: A Source Book in Mathematical Logic, 1879-1931''|p=124 -128}}. Traduction et présentation en français dans {{ouvrage|titre=Logique et fondements de mathématique|sous-titre=Anthologie (1850-1914)|auteur1=François Rivenc|auteur2=[[Philippe de Rouilhan]]|directeur1=oui|directeur2=oui|editeur=Payot|collection=Bibliothèque scientifique Payot |année=1992|isbn=2228884839|passage=237-243}}</ref>, où il montrait à ce dernier que l'une des règles introduite dans ses ''Grundgesetze der Arithmetik'', la [[schéma d'axiomes de compréhension|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 en faisant précéder l'analyse 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 »<ref>Appendice de ''Grundgesetze der Arithmetik'', vol. II, in [https://books.google.com/books?id=4ktC0UrG4V8C&pg=PA279#v=onepage&q=&f=false ''The Frege Reader'', p.279] </ref>.

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<ref>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.</ref>. 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]]<ref>Lettre du 28 juillet 1899, traduite en anglais dans {{harvsp|id=''A Source Book…''|texte=''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 {{harvsp|Cavaillès|1962|p=238-246}}. Cantor ne fait pas référence à Burali-Forti, ni ne parle de paradoxe.</ref> comme montrant que l'« ensemble » paradoxal en jeu, que nous appelons aujourd'hui la [[classe (mathématiques)|classe]] de tous les [[ordinal|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<ref>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]]</ref>. 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é [''{{Lang|de|Vielheit}}''] consistante et inconsistante »<ref>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]].</ref>. 
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 [[nombre cardinal|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 [[schéma d'axiomes de compréhension|restriction du principe de compréhension]], due à [[Ernst Zermelo|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 [[#Versions positives du paradoxe|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 ([[axiome de la paire|paire]], [[axiome de la réunion|réunion]], [[axiome de l'ensemble des parties|ensemble des parties]], ...). Plus tard [[Abraham Adolf Fraenkel|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 :
{{énoncé|¬ ∃''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 :
{{énoncé|<math>y = \{ x \in A | x \notin x \}</math> }}
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 (mathématiques)|classe]] propre.

== Notes et références ==
=== Notes ===
<references />

=== Références ===
* {{en}} {{Lien|langue=de|fr=Godehard Link}}, ''One Hundred Years Of Russell's Paradox: Mathematics, Logic, Philosophy'', de Gruyter, 2004, 672 p.{{ISBN|978-3110174380}}
* {{ouvrage|id=''A Source Book…''|lang=en|nom1=[[Jean van Heijenoort]]|titre=From Frege to Gödel, A Source Book in Mathematical Logic 1879-1931|éditeur=Harvard Univ. Press|lieu=Cambridge|année=1967|isbn=0-674-32449-8|présentation en ligne=https://books.google.fr/books?id=v4tBTBlU05sC}}
* {{en}} [[Bertrand Russell]], ''The principles of mathematics'', vol. 1, Cambridge Univ. Press, 1903,[http://fair-use.org/bertrand-russell/the-principles-of-mathematics version en ligne disponible] <small>(incomplète au 4 janvier 2007)</small> et [http://quod.lib.umich.edu/cgi/b/bib/bibperm?q1=AAT1273 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|url=https://gallica.bnf.fr/ark:/12148/bpt6k11064n}} sur [[Gallica]]
* {{en}} Bertrand Russell, « Mathematical logic as based on the theory of types », dans ''American Journal of Mathematics'', vol. 30, 1908, repris dans {{harvsp|''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 {{harvsp|''A Source Book…''|p=183-198}}
* {{article|lang=de|lien auteur=Ernst Zermelo|prénom=Ernst|nom= Zermelo|année=1908|titre=Untersuchungen über die Grundlagen der Mengenlehre I|journal=Mathematische Annalen |volume=65|numéro=2|pages= 261–281|doi= 10.1007/BF01449999}}
* {{ouvrage|auteur=[[Jean Cavaillès]]|titre=Philosophie mathématique|édition=Hermann|année=1962}}{{commentaire biblio|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}}{{commentaire biblio|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)]]

{{Portail|Mathématiques}}

[[Catégorie:Paradoxe de la théorie naïve des ensembles|Russell]]
[[Catégorie:Paradoxe auto-référentiel|Russell]]