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 époque1, mais ce dernier ne l'a pas publié.
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 :
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).
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.
