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

En théorie des ordres, le théorème de Cantor, énoncé par lui 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

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 a$_0$, a$_1$, a$_2$, … , a$_n$, … : ayant aussi numéroté les rationnels, b$_0$, b$_1$, b$_2$, … , on pose, pour tout n, f(a$_n$) = b$_p$, où p est le plus petit indice pour lequel b$_p$ est placé, par rapport aux f(a$_k$) pour k < n, de la même façon que a$_n$ par rapport aux a$_k$ 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(a$_k$) tels que k < n et a$_k$ < a$_n$, et J l'ensemble des f(a$_k$) tels que k < n et a$_k$ > a$_n$, p est le plus petit indice tel que I < b$_p$ < J. Lorsque l'ordre sur E est dense et sans premier ni dernier élément, Cantor démontre que tous les b$_p$ appartiennent à l'image de l'injection f, qui est donc alors une bijection, par récurrence forte sur p : si b$_0$, … , b$_p$ appartiennent à l'image de {a$_0$, … , a$_n$} et si b$_{p+1}$ n'appartient pas à cette image, soit q (> n) le plus petit indice pour lequel a$_q$ est placé, par rapport à a$_0$, … , a$_n$, de la même façon que b$_{p+1}$ par rapport à f(a$_0$), … , f(a$_n$). Alors, b$_{p+1}$ est encore placé, par rapport à f(a$_0$), … , f(a$_{q–1}$) (dont font partie b$_0$, … , b$_p$), de la même façon que a$_q$ par rapport à a$_0$, … , a$_{q–1}$, donc f(a$_q$) = b$_{p+1}$.

## Généralisations

Wacław Sierpiński, tentant de généraliser ce théorème à 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 », 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é qu'il est consistant avec ZFC que 2$^{ℵ0}$ = ℵ$_2$ et qu'il n'existe pas d'ordre universel sur ω$_1$, ou d'ailleurs qu'il en existe un.