Les conditions de possibilité du paradoxe de Russell

Le paradoxe de Russell

Le plus célèbre paradoxe de la logique est celui de Bertrand Russell, découvert en 1901. Ce paradoxe touche de plein fouet la théorie dite « naïve » des ensembles, alors développée par Gottlob Frege. Il porte sur le caractère justement ensembliste de la logique fregéenne, selon laquelle, avoir un prédicat est appartenir à un ensemble, c’est-à-dire appartenir à une boîte définie par compréhension. Le problème de cette approche est qu’elle n’est pas universelle, et qu’il existe un ensemble monstrueux dont Frege autorise la construction (l’ensemble des ensembles qui n’appartiennent pas à eux-mêmes).

Observons attentivement quelles sont les conditions de possibilité de cet ensemble. Tout d’abord, il faut des ensembles qui appartiennent à eux-même et des ensembles qui n’appartiennent pas à eux- même. Il est aisé de trouver des ensembles qui n’appartiennent pas à eux-même (l’ensemble des chats n’est pas un chat, donc n’appartient pas à l’ensemble des chats). En revanche, peu d’ensembles appartiennent à eux-même (l’ensemble des ensembles appartient à lui-même).

Une fois construits ces ensembles, nous pouvons construire l’ensemble des ensembles qui n’ap- partiennent pas à eux-même. Dedans, il y a la plupart des ensembles, ceux des chiens, des chats, des humains, des thermostats et des chauves-souris par exemple. Le paradoxe survient lorsqu’on se demande si cet ensemble appartient à lui-même. S’il appartient à lui-même, il satisfait ses propres conditions d’appartenance (ne pas s’appartenir), donc il n’appartient pas à lui-même. La réciproque est également immédiate. La conclusion est A ↔ ¬A, qui est une antilogie :

w = { x ; x ∉ x } → ( w ∈ w ↔ w ∉ w )

Voici la fin de la lettre qui mit Frege dans un très grand désarroi :

Conditions de possibilité

Mais alors, quelles sont les conditions de possibilité d’un tel paradoxe? Il semble que le paradoxe porte sur une confusion entre être un ensemble et être tout court. En effet, dire « Socrate est un homme » et dire « Socrate appartient à l’ensemble des hommes » n’est fondamentalement pas la même chose. Là où la première proposition énonce un état de fait, humble, la deuxième suppose a priori que la notion d’ensemble est réelle, ce qui est hautement problématique.

1- La solution de la théorie des ensembles

Une première manière de sortir du paradoxe est de bricoler un axiome pour interdire que tout puisse être un ensemble. Ce fut la solution des mathématiciens d'après-guerre qui distinguent les ensembles des collections (ou classes) même si on sent bien qu'au fond ce n'est pas si différent, et que la seule utilité de cette distinction est d'éviter le paradoxe de Russell tout en autorisant la définition par compréhension (ce qui préserve le paradis des mathématiciens).

Il y a traditionnellement deux manières de définir un ensemble, l'extension et la compréhension (ou intension). L'extension est le plus intuitive : on se contente de lister ce qui appartient à l'ensemble, et le risque de paradoxe semble très faible. On peut rapprocher l'extension d'une liste d'états de fait (que l'on formalise à l'ordre 0 en logique des prédicats) : « Socrate est un homme, Platon est un homme, Aristote est un homme ». La définition par compréhension est bien plus problématique : elle consiste à définir un ensemble par des caractéristiques. L'erreur de Frege fut d'autoriser les caractéristiques « second ordre » telles que « être une proposition » ou « être un ensemble ».

La théorie de ensembles moderne (développée par Zermelo et Fraenkel, et très bien expliquée de Théorie des ensembles de Krivine) apporte une solution pour ne pas que toute collection (qui provient de la logique des prédicats, qui est un peu le terrain miné) puisse devenir un ensemble, une solution que l'on nomme schéma de compréhension :

∀x1 . . .∀xk∀x∃y∀z[z ∈ y ⇔(z ∈ x et A(z, x1,x2, . . . ,xk))]

De cette manière, il existe des collections qui ne sont pas des ensembles (par exemple la collection x ∉ x). Ce qui sauve de manière ad hoc la théorie des ensembles du paradoxe de Russell.

2- La solution de la théorie des types

Une deuxième solution, moins paradisiaque pour les mathématiciens, est celle adoptée par Bertrand Russell lui-même. Il la développe dans son opus magna, les Principia mathematica. L'idée est de hierarchiser non plus seulement les collections et les ensembles, mais tous les objets. Cette manière de faire a une grande postérité en informatique où on considère que les langages typés sont plus expressifs que les langages non typés.