Paradoxe de Burali-Forti - Définition

Les raisons du paradoxe

Pour en dire plus, on est obligé d'être un peu plus précis sur les propriétés des bons ordres et des ordinaux. Tout d'abord on peut définir une notion d'isomorphisme d'ordre. Deux ensembles bien ordonnés (A, <_A) et (B, <_B) sont isomorphes s'il existe une bijection f de A dans B qui transporte la structure d'ordre, c’est-à-dire une bijection croissante de A dans B :

x <_A y ⇔ f(x) <_B f(y) .

Un ordinal est, si l'on veut, un bon ordre « à isomorphisme près » ; on parle parfois de type d'ordre. Sans entrer dans des détails formels, Les ordinaux doivent être définis de façon que pour tout bon ordre, il existe un et un seul ordinal isomorphe à ce bon ordre.

Une notion utile sur les bons ordres, qui permet de les comparer, est celle de section commençante ou segment initial. On appelle section commençante ou segment initial d'un ensemble ordonné (E, <) (on choisit l'ordre strict) un sous-ensemble F de E qui, s'il contient un élément de E, contient tous les éléments plus petits :

x ∈ F ⇒ (∀ y < x) y ∈ F .

Une section commençante propre de (E, <) est une section commençante non vide et différente de l'ensemble E. Une section commençante non vide d'un ensemble bien ordonné est bien ordonnée par l'ordre restreint à celle-ci. Pour comparer deux bons ordres, on pourra dire qu'un ensemble bien ordonné (A, <_A) est strictement inférieur à un ensemble bien ordonné (B, <_B) quand (A, <_A) est isomorphe à une section commençante propre de (B, <_B). Cette relation est un ordre strict, elle est transitive, par composition des deux morphismes en jeu, et irréflexive.

Proposition (irreflexivité). Un ensemble bien ordonné ne peut être isomorphe à une de ses sections commençantes propres.

Cette proposition se démontre par induction sur le bon ordre en jeu (c’est-à-dire essentiellement en utilisant la définition même de bon ordre).

Une propriété essentielle, due à Cantor, est celle de trichotomie. Elle énonce que si l'on restreint l'ordre strict précédent aux ordinaux, il définit un ordre total (ou qu'il définit un ordre total sur les bons ordres à isomorphisme près, ce qui revient au même).

Proposition (trichotomie). Étant donnés deux ensembles bien ordonnés (A, <_A) et (B, <_B),

• soit (A, <_A) est isomorphe à une section commençante propre de (B, <_B),
• soit (A, <_A) est isomorphe à (B, <_B),
• soit (B, <_B) est isomorphe à une section commençante propre de (A, <_A).

et ces trois cas sont exclusifs.

Cette propriété se démontre en utilisant le principe de définition par induction sur un bon ordre.

On a donc montré comment définir un ordre total sur un ensemble d'ordinaux : un ordinal α est strictement inférieur à un ordinal β s'il est isomorphe à une section commençante propre de β. Mais cet ordre est également un bon ordre. En effet, soit A un ensemble non vide d'ordinaux et α un élément de A. On montre que l'ensemble des ordinaux de A inférieurs ou égal à α est, à isomorphisme près, inclus dans α donc a un plus petit élément qui est le plus petit élément de A.

Proposition (plus petit élément). Tout ensemble d'ordinaux non vide a un plus petit élément.

Un ensemble d'ordinaux est donc naturellement bien ordonné : tous ses sous-ensembles non vides ont bien un plus petit élément. On peut dériver le paradoxe de Burali-Forti, restreint à cet ensemble, en lui demandant de vérifier ces deux propriétés de clôture (la première suffirait en fait) :

• Un ensemble d'ordinaux est clos par le bas si, quand il contient un ordinal, il contient tous les ordinaux qui lui sont inférieurs (c'est une autre façon de parler de section commençante).
• Un ensemble d'ordinaux est clos par successeur s'il contient le successeur de chacun de ses éléments.

Un successeur d'un bon ordre (E, <) est un bon ordre obtenu en ajoutant « au bout » de E un nouvel élément, soit e, c’est-à-dire que tout élément de E est strictement inférieur à e. Il est par définition strictement supérieur au bon ordre (E, <). Tous les bons ordres successeurs de (E, <) sont bien-sûr isomorphes, et on peut donc définir le successeur d'un ordinal.

La première propriété assure que le bon ordre obtenu sur l'ensemble d'ordinaux est supérieur ou égal à tous ses éléments, la seconde que, s'il vérifie aussi la première, il leur est strictement supérieur, puisqu'il est supérieur au successeur de chacun de ses éléments.

L'ensemble de tous les ordinaux vérifierait forcément ces deux propriétés de clôture, donc ne peut exister sous peine de paradoxe. Or la propriété « être un ordinal », doit pouvoir se définir formellement. Une utilisation non restreinte du schéma d'axiomes de compréhension conduit donc à une contradiction.