Théorème de Cantor (théorie des ordres)

Un article de Wikipédia, l'encyclopédie libre.

En théorie des ordres, le théorème de Cantor, énoncé par lui[1] en 1895 dans le cadre de son étude sur les types d'ordre, affirme que tout ensemble totalement ordonné dénombrable est isomorphe à un sous-ensemble de l'ensemble des rationnels, muni de l'ordre usuel.

Énoncé et démonstration[modifier | modifier le code]

La forme la plus générale donnée par Cantor est la suivante : soit E un ensemble infini dénombrable, muni d'un ordre total noté <. Il existe alors une injection croissante de E vers l'ensemble Q des nombres rationnels et qui, si de plus l'ordre < est dense et sans premier ni dernier élément, est même un isomorphisme.

La construction de cette injection f se fait par récurrence sur l'indice n des éléments de E, numérotés arbitrairement a0, a1, a2, … , an, … : ayant aussi numéroté les rationnels, b0, b1, b2, … , on pose, pour tout n, f(an) = bp, où p est le plus petit indice pour lequel bp est placé, par rapport aux f(ak) pour k < n, de la même façon que an par rapport aux ak pour k < n, ce qui est toujours possible parce que l'ordre des rationnels est dense et sans minimum ni maximum : entre deux ensembles finis de rationnels (éventuellement vides), il existe toujours un rationnel, et même une infinité. Plus explicitement : si I est l'ensemble des f(ak) tels que k < n et ak < an, et J l'ensemble des f(ak) tels que k < n et ak > an, p est le plus petit indice tel que I < bp < J. Lorsque l'ordre sur E est dense et sans premier ni dernier élément, Cantor démontre que tous les bp appartiennent à l'image de l'injection f, qui est donc alors une bijection[2], par récurrence forte sur p : si b0, … , bp appartiennent à l'image de {a0, … , an} et si bp+1 n'appartient pas à cette image, soit q (> n) le plus petit indice pour lequel aq est placé, par rapport à a0, … , an, de la même façon que bp+1 par rapport à f(a0), … , f(an). Alors, bp+1 est encore placé, par rapport à f(a0), … , f(aq–1) (dont font partie b0, … , bp), de la même façon que aq par rapport à a0, … , aq–1, donc f(aq) = bp+1.

Généralisations[modifier | modifier le code]

Wacław Sierpiński, tentant de généraliser ce théorème[3] à des ensembles ordonnés non dénombrables, démontre, en admettant l'hypothèse du continu, qu'il est possible de munir le plus petit ordinal non dénombrable, ω1, d'un ordre « universel »[4], c'est-à-dire tel que tout ensemble totalement ordonné de cardinal 1 soit isomorphe (pour l'ordre) à un sous-ensemble de ω1. Il suffit, pour pouvoir calquer la démonstration de Cantor, que l'ordre construit sur ω1 soit tel que pour deux sous-ensembles dénombrables quelconques de ω1, A et B, tels que tout élément de A soit plus petit que tout élément de B, il existe un élément supérieur à tous ceux de A et inférieur à tous ceux de B. Sierpinski montre qu'une telle construction est possible si l'ensemble des suites dénombrables d'ordinaux a pour cardinal ℵ1, résultat qui est équivalent à l'hypothèse du continu (en admettant l'axiome du choix). La construction des nombres surréels a permis de beaucoup simplifier ce résultat : il est en effet facile de démontrer que l'ensemble ordonné des surréels construits avant l'étape ω1 possède la propriété précédente.

Plus généralement, une construction analogue est possible pour tout cardinal en admettant l'hypothèse du continu généralisée, c'est-à-dire que 2α = ℵα+1 ; si on ne suppose pas cette hypothèse, Kojman et Shelah ont démontré[5] qu'il est consistant avec ZFC que 20 = ℵ2 et qu'il n'existe pas d'ordre universel sur ω1, ou d'ailleurs qu'il en existe un.

Notes et références[modifier | modifier le code]

  1. (de) Georg Cantor, « Beiträge zur Begründung der transfiniten Mengenlehre », Math. Ann., vol. 46, no 4,‎ , p. 481-512 (lire en ligne), p. 504-507
  2. La construction directe d'une bijection (dans ce cas particulier), connue en anglais sous le nom de back-and-forth method, en français méthode du va-et-vient, que l'on trouvera par exemple dans (en) Thomas Jech, Set Theory, Academic Press, (lire en ligne), p. 30, dispense de cette récurrence, tout en étant essentiellement équivalente à celle donnée par Cantor. Elle est d'ailleurs proche dans son principe de celle donnée par Cantor du théorème de Cantor-Bernstein.
  3. W. Sierpinski, « Généralisation d'un théorème de Cantor concernant les ensembles ordonnés dénombrables », Fund. Math., vol. 18,‎ , p. 280-284 (lire en ligne) ; dans cet article, Sierpinski fait référence à « un théorème bien connu de Cantor », et remarque qu'une construction analogue à la sienne (mais moins facile à généraliser) a déjà été publiée par Hausdorff.
  4. Cette notion d'universalité est plus faible que celle de la théorie des catégories, car l'injection croissante n'est nullement unique, et l'ordre universel (même à isomorphisme près) n'est pas unique non plus.
  5. (en) Menachem Kojman et Saharon Shelah, « Non-existence of Universal Orders in Many Cardinals », J. Symb. Logic, vol. 57, no 3,‎ , p. 875-891 (lire en ligne)