Paradoxe de Russell
Un article de Wikipédia, l'encyclopédie libre.
Vous avez de 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 indépendemment par Ernst Zermelo, qui ne le publia pas, vers 1899 ou 1900.
Sommaire |
[modifier] É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ême, 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 paradoxale. Redit dans le langage formel actuel, 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éfinit 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} -- et la théorie devient contradictoire.
Russell décrivit ce paradoxe dans une lettre adressée en 1902 à Gottlob Frege, 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 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). 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, cependant elle n'était pas vraiment formalisée. Le paradoxe de Russell montrait que l'ensemble paradoxal en jeu ne peut exister, et laissait craindre que la théorie soit contradictoire. Le paradoxe de Russell n'était pas le premier paradoxe à apparaître dans la théorie des ensembles de Cantor, ce qui est une raison probable pour laquelle Zermelo, qui travaillait dans ce contexte et ne connaissait pas les travaux de Frege, ne le publia pas. Le paradoxe de Burali-Forti, découvert par ce dernier en 1897, est interprété par Georg Cantor comme montrant que l'ensemble paradoxal en jeu (l'ensemble de tous les ordinaux) n'existe pas. De même pour le paradoxe de Cantor (1899) sur le plus grand cardinal. Le paradoxe de Russell est cependant particulièrement simple, et pose de façon peut-être encore plus cruciale la nécessité d'une formalisation de la théorie des ensembles (qui bien-sûr doit éviter les paradoxes connus).
[modifier] Les solutions du paradoxe
Les principales solutions apportées pour éluder ce paradoxe furent :
- la théorie des types de Russell, qu'il esquisse dans l'ouvrage déjà mentionné de 1903, puis qu'il développe en 1908 et (en compagnie de Whitehead) dans les Principia Mathematica parus en 1910. Selon cette théorie, les ensembles sont de types hiérarchisés. Un ensemble ne peut contenir que des objets de types strictement inférieurs à lui-même, de sorte qu'on ne peut tout simplement plus écrire l'énoncé paradoxal (on ne peut plus écrire le prédicat d'auto-appartenance).
- 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 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, ...). Boris Fraenkel et Thoralf Skolem introduisirent le schéma d'axiomes de remplacement, qui est toujours une restriction du principe de compréhension général, mais étend le schéma d'axiomes de compréhension introduit par Zermelo.
[modifier] 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 ensembles ne peut être que le plus grand cardinal. Plus précisément, l'« ensemble » de tous ensembles contiendrait son ensemble de 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, l'ensemble de tous les ensembles qui n'appartiennent pas à eux-mêmes est intuitivement proche de l'ensemble de tous les ensembles.
[modifier] Versions positives du paradoxe
Remarquons tout d'abord que 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 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, 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.
[modifier] Articles connexes
- Paradoxe de Burali-Forti
- Paradoxe de Cantor
- Paradoxe du menteur
- Logicisme
[modifier] Références
- Justin T Miller -- An historical account of set-theoretic antinomies caused by the axiom of abstraction [1] visitée le 24/09/2006
