Paradoxe de Burali-Forti

En mathématiques, le paradoxe de Burali-Forti, paru en 1897, désigne une construction qui conduit dans certaines théories des ensembles ou théories des types trop naïves à une antinomie, c’est-à-dire que la théorie est contradictoire (on dit aussi incohérente ou inconsistante). Dit brièvement, il énonce que, comme on peut définir la borne supérieure d'un ensemble d'ordinaux, si l'ensemble de tous les ordinaux existe, on peut définir un ordinal supérieur strictement à tous les ordinaux, d'où une contradiction.

L'argument utilise donc la notion d'ordinal, c’est-à-dire essentiellement celle de bon ordre : il est plus technique que le paradoxe de Russell, bien que son argument ne soit pas si éloigné de ce dernier qui est plus simple à comprendre et à formaliser. Cependant, le paradoxe de Burali-Forti est le premier des paradoxes de la théorie des ensembles à être publié, six ans avant le paradoxe de Russell, et Georg Cantor en fait état dans sa correspondance, ainsi que du paradoxe du plus grand cardinal (dit paradoxe de Cantor), dans les mêmes années. Par ailleurs, le paradoxe de Burali-Forti met directement en jeu la notion d'ordre, et non celle d'appartenance (même si aujourd'hui ces deux notions coïncident pour les ordinaux tels qu'ils sont définis en théorie des ensembles). Ainsi l'incohérence de certaines théories a été établie en dérivant directement le paradoxe de Burali-Forti. C'est ainsi que John Barkley Rosser a démontré en 1942 l'inconsistance d'une des premières versions des New Foundations de Willard Van Orman Quine.

Énoncé du paradoxe

Le paradoxe utilise la notion d'ordinal, une généralisation de la notion de nombre entier naturel, en tant qu'il représente un bon ordre. À tout bon ordre on associe un et un seul ordinal qui a la « même » structure d'ordre. Les entiers sont les ordinaux finis. L'ensemble des entiers naturels est bien ordonné, et son ordinal est noté usuellement $\omega$. La notion de nombre ordinal diffère de celle de nombre cardinal dès que l'on passe à l'infini (des ordinaux infinis distincts peuvent avoir même cardinal).

Pour des raisons qui tiennent à la notion même d'ordinal, on sait qu'un ensemble d'ordinaux est lui-même bien ordonné de façon naturelle. Si on admet que l'ensemble de tous les ordinaux existe, on montre qu'à cause de propriétés de clôture que vérifierait forcément un tel ensemble, l'ordinal correspondant à ce bon ordre serait strictement supérieur à celui de chacun de ses éléments. On est donc face à une contradiction : l'ordinal associé doit être strictement supérieur à lui-même.

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 ${\textstyle (A,<_{A})}$ et $(B,<_{B})$ sont isomorphes s'il existe une bijection $f$ de ${\textstyle A}$ dans ${\textstyle B}$ qui transporte la structure d'ordre, c’est-à-dire une bijection croissante de ${\textstyle A}$ dans ${\textstyle B}$ :

$$x<_{A}y\Leftrightarrow 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é ${\textstyle (E,<)}$ (on choisit l'ordre strict) un sous-ensemble ${\textstyle F}$ de ${\textstyle E}$ qui, s'il contient un élément de ${\textstyle E}$, contient tous les éléments plus petits :

$$x\in F\Rightarrow (\forall y<x),y\in F.$$

Une section commençante propre de ${\textstyle (E,<)}$ est une section commençante non vide et différente de l'ensemble ${\textstyle 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é ${\textstyle (A,<_{A})}$ est strictement inférieur à un ensemble bien ordonné $(B,<_{B})$ quand ${\textstyle (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 (irréflexivité). 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 ${\textstyle (A,<_{A})}$ et $(B,<_{B})$,

• soit ${\textstyle (A,<_{A})}$ est isomorphe à une section commençante propre de $(B,<_{B})$,
• soit ${\textstyle (A,<_{A})}$ est isomorphe à $(B,<_{B})$,
• soit $(B,<_{B})$ est isomorphe à une section commençante propre de ${\textstyle (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 ${\textstyle \alpha }$ est strictement inférieur à un ordinal ${\textstyle \beta }$ s'il est isomorphe à une section commençante propre de ${\textstyle \beta }$. Mais cet ordre est également un bon ordre. En effet, soit ${\textstyle A}$ un ensemble non vide d'ordinaux et ${\textstyle \alpha }$ un élément de ${\textstyle A}$. On montre que l'ensemble des ordinaux de ${\textstyle A}$ inférieurs ou égal à ${\textstyle \alpha }$ est, à isomorphisme près, inclus dans ${\textstyle \alpha }$ donc a un plus petit élément qui est le plus petit élément de ${\textstyle 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 ${\textstyle (E,<)}$ est un bon ordre obtenu en ajoutant « au bout » de ${\textstyle E}$ un nouvel élément, soit ${\textstyle e}$, c’est-à-dire que tout élément de ${\textstyle E}$ est strictement inférieur à ${\textstyle e}$. Il est par définition strictement supérieur au bon ordre ${\textstyle (E,<)}$. Tous les bons ordres successeurs de ${\textstyle (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.

Solution dans la théorie des ensembles de Zermelo-Fraenkel

Tout comme pour le paradoxe de Russell, dont il a d'ailleurs d'une certaine façon la structure logique (il s'agit d'un raisonnement diagonal), le paradoxe de Burali-Forti se résout en restreignant le schéma d'axiomes de compréhension. Si l'on suit la définition naturelle d'ordinal, on le définirait comme une classe d'isomorphie de bons ordres pour l'isomorphisme d'ordre décrit au paragraphe précédent. Mais, à cause de la restriction du schéma de compréhension, une classe d'isomorphie n'est pas un ensemble. La classe d'isomorphie de l'ordre à un élément regroupe déjà tous les singletons (muni de la relation vide comme ordre strict). Par axiome de la réunion, on aurait l'ensemble de tous les ensembles, donc le paradoxe de Russell par le schéma de compréhension.

Cependant, il est possible de construire de façon uniforme un représentant par classe d'isomorphie : ce sont les ordinaux de von Neumann. On peut alors définir dans le langage de la théorie des ensembles la propriété « être un ordinal » (un ordinal de von Neumann est un ensemble transitif bien ordonné par l'appartenance). On peut donc parler de la classe des ordinaux. Il n'y a plus de contradiction, le paradoxe de Burali-Forti se traduit en :

la classe des ordinaux est une classe propre.

Aspects historiques

Le paradoxe de Burali-Forti a été publié pour la première fois dans un article de cet auteur de 1897, mais sous une forme différente de celle décrite ci-dessus. Tout laisse penser cependant que Cantor connaissait ce paradoxe à une date antérieure. La date de 1895 ou une lettre à David Hilbert de 1896 sont souvent citées en référence. Il semble que ce soit Philip Jourdain qui les ait le premier avancées. On cite souvent un article paru en 1905 de Felix Bernstein, qui était étudiant de Cantor, mais celui-ci se réfère à Jourdain. Par exemple Jean Cavaillès cite Bernstein. Même si ces dates sont vraisemblables, aucune lettre de 1896 n'a été retrouvée. Dans une lettre à Hilbert de 1897, Cantor donne son explication du paradoxe du plus grand cardinal, mais en faisant référence à la série des aleph, indexés par les ordinaux. On peut donc penser qu'il connait aussi le paradoxe de Burali-Forti, d'autant que la lettre témoigne de l'état avancé de sa réflexion à ce sujet. Quoi qu'il en soit, à la fin des années 1890, à Göttingen, le paradoxe de Burali-Forti, et l'analyse qu'en fait Cantor sont connus de Hilbert et son entourage, dont Zermelo.

Burali-Forti

Burali-Forti déclare, dès la première phrase de sa note de 1897, que l'objet principal de celle-ci est de montrer qu'il existe des nombres transfinis qui ne sont pas comparables, c’est-à-dire la négation de la propriété de trichotomie (voir ci-dessus) démontrée par Cantor et publiée la même année, quelques mois après la note de Burali-Forti. Pour prouver ce résultat, Burali-Forti introduit la notion d’ensemble parfaitement ordonné, qu'il pense, à tort, être plus forte que celle d'ensemble bien ordonné (introduite par Cantor en 1883). Il définit ensuite les ordinaux, en tant que types d'ordre d'ensembles parfaitement ordonnés. Il ordonne ainsi la classe de ses « ordinaux » : un ensemble ordonné ${\textstyle (A,<_{A})}$ est strictement plus petit qu'un ensemble ordonné $(B,<_{B})$, s'il existe une injection croissante de ${\textstyle (A,<_{A})}$ dans $(B,<_{B})$, mais pas de bijection croissante, ce qui pour les « vrais » ordinaux, équivaut à l'ordre par section commençante décrit ci-dessus. Puis il montre que, si l'on suppose que cet ordre est total (propriété de trichotomie), alors la classe des « ordinaux » (en son sens) est parfaitement ordonnée. On ne peut faire de raisonnement par induction sur un ordre parfait, cependant cette notion suffit pour que Burali-Forti puisse montrer que les ordinaux tels qu'il les a définis, ne sont pas isomorphes à une de leurs sections commençantes propres, alors que cela est faux pour les ordres totaux en général, et, comme il le remarque lui-même, pour ce qu'il croit être les bons ordres (sous une forme un peu différente). Cependant, comme Burali-Forti pense que les ordres parfaits sont de bons ordres, il peut tout de même en déduire que la propriété de trichotomie est fausse a fortiori pour ceux-ci.

Le raisonnement de Burali-Forti est donc bien celui décrit ci-dessus, même si celui-ci ne l'applique pas à la bonne notion, et en tire donc une conclusion fausse pour les « vrais » bons ordres, mais juste pour les ordres parfaits, ou ce qu'il croit être les bons ordres. Les ordinaux de Burali-Forti, qui sont associés aux ordres parfaits, ne sont effectivement pas totalement ordonnés. Simplement sa preuve ne peut être considérée comme acceptable, elle ne peut se formaliser dans une théorie des ensembles raisonnable, puisqu'elle se transposerait telle quelle aux vrais ordinaux, pour lesquels le résultat est faux.

Dans une note de quelques lignes parue la même année dans la même revue (voir références), Burali-Forti fait lui-même remarquer qu'il s'est trompé dans sa définition de bon ordre, et que la notion d'ordre parfait est en fait plus faible que celle de bon ordre au sens de Cantor. Curieusement, il n'en tire aucune conclusion, si ce n'est que « le lecteur pourra vérifier quelles propositions dans ma note [...] sont également vérifiées par les classes bien ordonnées ». Cependant son raisonnement, comme déjà dit, s'applique sans aucun problème aux bons ordres, et donc aux ordinaux au sens de Cantor, et il semble que cela fut clair assez rapidement pour les mathématiciens qui s'intéressaient à ces problèmes, ce qui fait bien du paradoxe de Burali-Forti le premier paradoxe connu de théorie des ensembles, nonobstant le fait qu'il pourrait être connu de Cantor avant 1897.

Les définitions utilisées par Burali-Forti

Les ordres parfaits ne semblent guère avoir survécu à la note de Burali-Forti. Cette notion est de toute façon clairement moins utile que celle de bon ordre, et de principe d'induction qui lui est associée. Les définitions qui suivent n'ont donc essentiellement qu'un intérêt historique. On ne suit pas exactement la terminologie de Burali-Forti, même si elle resterait assez compréhensible pour un lecteur moderne.

Appelons successeur d'un élément dans un ensemble totalement ordonné le plus petit des majorants stricts de cet élément : il n'existe pas forcément, mais s'il existe il est bien unique. De façon analogue, appelons prédécesseur d'un élément le plus grand des minorants stricts (s'il existe) de cet élément.

Burali-Forti pense erronément qu'un ensemble bien ordonné ${\textstyle (E,<)}$ est un ensemble totalement ordonné qui satisfait les deux propriétés suivantes :

• ${\textstyle (E,<)}$ a un plus petit élément ;
• Tout élément de ${\textstyle (E,<)}$ qui possède un majorant strict possède un plus petit majorant strict, c’est-à-dire un successeur.

Pour définir les ensembles parfaitement ordonnés, il ajoute une troisième propriété :

• Tout élément de ${\textstyle E}$ est le successeur itéré un nombre fini de fois, éventuellement nul, d'un élément qui n'a pas de prédécesseur.

Pourquoi introduire cette troisième propriété ? Burali-Forti donne un exemple d'ordre qui satisfait les deux premières mais pas la suivante : il suffit de mettre bout à bout une copie des entiers, suivie d'une copie dans l'ordre inverse, ${\textstyle \{0\}\times \mathbb {N} \cup \{1\}\times \mathbb {Z} _{-}}$ ordonné lexicographiquement pour être formel. Si l'on prend le successeur de cet ordre, celui obtenu en ajoutant un élément « au bout », ${\textstyle \{0\}\times \mathbb {N} \cup \{1\}\times (\mathbb {Z} _{-}\cup \{1\})}$ pour être formel, on obtient un ordre isomorphe. On ne peut donc espérer montrer l'irreflexivité de l'ordre de comparaison entre ensembles ordonnés défini par section commençante, et même si ce n'est pas celui-ci que Burali-Forti utilise, il a tout de même besoin de pouvoir construire un majorant strict.

Par contre l'exemple ci-dessus ne satisfait pas la troisième propriété. Dès que la troisième propriété est vérifiée, un ordre ne peut être isomorphe à son successeur. En effet soit l'ordre initial n'avait pas de plus grand élément, mais alors l'ordre successeur en a forcément un, soit il avait un plus grand élément et on a le résultat par récurrence ordinaire (sur les entiers) sur le nombre d'itérations nécessaire pour se ramener à un élément sans prédécesseur (il faut une itération de plus pour l'ordre successeur). Cela montre donc que le successeur d'un ensemble parfaitement ordonné est un majorant strict, propriété qui suffit pour l'argument de Burali-Forti (qui rappelons-le raisonne par l'absurde, en supposant la propriété de trichotomie).

Un bon ordre est un ordre parfait : s'il ne l'était pas la suite des prédécesseurs itérés d'un élément donnerait un ensemble sans plus petit élément. Un ordre est parfait quand chaque élément vit, en quelque sorte, dans une copie des entiers naturels, et quand il y un plus petit élément. Ce n'est pas suffisant pour assurer la propriété de bon ordre, car rien n'indique que ces copies des entiers soient elles-mêmes bien ordonnées. Par exemple, en ajoutant un plus petit élément à ${\textstyle \mathbb {Z} \times \mathbb {N} }$ (ordonné lexicographiquement), on obtient un ordre parfait qui n'est pas un bon ordre.

Cantor

On trouve le paradoxe de Burali-Forti (le nom de ce dernier n'est pas cité) expliqué de façon particulièrement lumineuse dans deux lettres de Georg Cantor à Dedekind datées de 1899. Cantor en donne une solution qui, si elle n'est pas vraiment satisfaisante d'un point de vue axiomatique, est compatible avec l'axiomatisation ultérieure de la théorie des ensembles.

Cantor distingue deux sortes de multiplicités définies [(de)bestimmte Vielheit] que nous appellerions aujourd'hui classes.

• Les multiplicités dont l'existence aboutit à une contradiction, qu'il appelle multiplicités inconsistantes [(de)inconsistente Vielheit] ou absolument infinies [(de)absolut unendliche Vielheit], et que nous appellerions aujourd'hui classes propres, avec une définition précise et formelle cependant, ce qui n'est pas le cas de la définition de Cantor.
• Les multiplicités dont « la totalité des éléments […] peut être pensée sans contradiction comme étant réunies […] en « une seule chose » » qu'il appelle multiplicités consistantes ou ensembles [(de) Menge], qui correspondent à ce que nous appelons toujours ensembles aujourd'hui.

Cantor appelle ${\textstyle \Omega }$ le système de tous les ordinaux. Il rappelle la propriété de trichotomie, et le fait que toute partie non vide de ${\textstyle \Omega }$ a un plus petit élément. Comme un ordinal a même type d'ordre (est isomorphe) à l'ensemble des ordinaux qui lui sont strictement inférieurs, il en déduit que si ${\textstyle \Omega }$ était un ensemble, donc un ordinal, il serait strictement supérieur à lui-même, d'où une contradiction. Pour Cantor, la classe de tous les ordinaux, ${\textstyle \Omega }$, est donc une multiplicité inconsistante, ou absolument infinie, c’est-à-dire peu ou prou l'interprétation du paradoxe de Burali-Forti dans la théorie des ensembles de Zermelo-Fraenkel.

La distinction entre multiplicités consistantes et inconsistantes, si elle n'est pas très formelle, n'est pas une notion amorphe et entièrement ad hoc : Cantor énonce une propriété dont Van Heijenoort remarque qu'elle est une version du schéma d'axiomes de remplacement, à savoir que deux multiplicités équivalentes, c’est-à-dire en bijection, sont soit toutes deux des ensembles, soit toutes deux inconsistantes. Cantor l'utilise pour montrer que la classe des alephs, la série des cardinaux indexés par les ordinaux, est également inconsistante, ce qui est connu sous le nom de paradoxe du plus grand cardinal, ou paradoxe de Cantor. Cependant, se pose le problème de savoir comment déterminer si une multiplicité bien définie est consistante. Cantor pose lui-même la question dans une lettre à Dedekind d'août 1899 : « […] on doit se demander d'où je sais que les multiplicités bien ordonnées ou suites auxquelles j'assigne les nombres cardinaux […] sont réellement des « ensembles » ». Cantor propose d'introduire de nouveaux axiomes dans le cas des cardinaux. Mais en l'absence par ailleurs d'une axiomatisation de la théorie des ensembles, cela semble difficile d'aller très loin dans cette voie.

Articles connexes

• Paradoxe de Russell
• Paradoxe de Cantor
• Paradoxe de Richard
• Paradoxe de Berry

Sources

• (it) Cesare Burali-Forti, « Una questione sui numeri transfiniti », Rendiconti del Circolo mathematico di Palermo, vol. 11,‎ 1897, p. 154-164 et « Sulle classi ben ordinate », ibid., p. 260. Traductions en anglais de l'article de Burali-Forti de 1897 et de son addendum dans A Source Book in Mathematical Logic 1879-1931, p. 104-112, avec une préface de Jean van Heijenoort.
• (de) Georg Cantor (1899), Aus dem Briefwechsel zwischen Cantor und Dedekind (extraits de la correspondance entre Cantor et Dedekind) dans le volume édité par Zermelo en 1932, traduction anglaise partielle dans A Source Book in Mathematical Logic, p. 113-117.
• (de) Georg Cantor, Gesammelte Abhandlungen mathematischen und philosophischen Inhalts. édité par Ernst Zermelo. Berlin: Springer, 1932. (Reprint: Springer, 1980.) – [1]. -88mb!.
• (de) Georg Cantor Briefe, Herbert Meschkowski et Winfried Nilson (ed.), Springer, 1991 (ISBN 3-540-50621-7).
• (en) Bertrand Russell (1903), The Principles of Mathematics, vol. 1, Cambridge Univ. Press, version en ligne disponible, en fac simile sur le site de l'université du Michigan.
• (en) A Source Book in Mathematical Logic 1879-1931, J. van Heijenoort (ed.), Harvard Univ. Press, Cambridge, 1967 (ISBN 0-674-32450-1) (ISBN 0-674-32449-8).
• Jean Cavaillès, Philosophie mathématique, Hermann, 1962, 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.
• (en) Ivor Grattan-Guinness, « The rediscovery of the Cantor-Dedekind Correspondence », Jber. Deutsch. Math.-Verein., vol. 76,‎ 1974 (lire en ligne).
• Paul Halmos, Introduction à la théorie des ensembles [détail des éditions].
• (en) Justin T Miller, « An historical account of set-theoretic antinomies caused by the axiom of abstraction »