Nombre ordinal

Un article de Wikipédia, l'encyclopédie libre.
(Redirigé depuis Ordinal)
Aller à : navigation, rechercher
Page d'aide sur les redirections « Ordinal » redirige ici. Pour les autres significations, voir Ordinal (homonymie).

En mathématiques, on appelle nombre ordinal un objet permettant de caractériser le type d'ordre d'un ensemble bien ordonné quelconque. Comme, en linguistique, les mots premier, deuxième, troisième, quatrième, etc. s'appellent des adjectifs numéraux ordinaux, et servent à préciser le rang d'un objet dans une collection, ou l'ordre d'un événement dans une succession. Georg Cantor a été amené (lors de ses travaux sur les séries trigonométriques) à nommer de même le concept qu'il avait introduit à cette occasion pour caractériser le type d'ordre des ensembles qu'il rencontrait, de façon plus précise qu'en les mesurant par leur cardinalité (leur « nombre d'éléments »). Les ordinaux finis peuvent en fait être identifiés aux entiers naturels qui s'identifient eux-mêmes aux cardinaux finis, mais, dans le cas des ensembles infinis, ce n'est plus vrai : tous les cardinaux sont encore identifiables à des ordinaux, mais la réciproque est fausse.

Introduction[modifier | modifier le code]

Un entier naturel peut être utilisé dans deux buts : décrire la taille d'un ensemble, ou donner la position d'un élément dans une suite ordonnée. Dans le cas fini, ces notions correspondent respectivement aux adjectifs numéraux cardinaux (zéro, un, deux, trois…) et ordinaux (zéroième[1], premier, deuxième, troisième…) et sont très semblables. Cependant, dans le cas infini, on est amené à distinguer nombre cardinal et nombre ordinal.

Si la notion de cardinal est associée à un ensemble sans structure particulière, les ordinaux sont intimement liés à un ordre sur les éléments de cet ensemble, et plus précisément à un bon ordre. Brièvement, un ensemble bien ordonné est un ensemble dans lequel toute partie non vide admet un plus petit élément. Le plus petit élément de l'ensemble peut être numéroté 0, le suivant 1, le suivant 2, etc., mais dès que l'ensemble est infini une notation adaptée est nécessaire pour désigner judicieusement tous les éléments de l'ensemble.

Considérons par exemple l'ensemble des couples d'entiers positifs ou nuls ordonnés selon ce qu'on appelle l'ordre lexicographique :

(0,0) \;\triangleleft\; (0,1) \;\triangleleft\; (0,2) \;\triangleleft\; (0,3) \;\triangleleft\; \ldots \;\triangleleft\; (1,0) \;\triangleleft\; (1,1) \;\triangleleft\; (1,2) \;\triangleleft\; (1,3) \;\triangleleft\; \ldots \;\triangleleft\; (n,0) \;\triangleleft\; (n,1) \;\triangleleft\; (n,2) \;\triangleleft\; (n,3) \;\triangleleft\; \ldots
Représentation graphique de l'exemple. La série de barres de gauche correspond aux couples commençant par 0, la suivante aux couples commençant par 1, etc.

On peut imaginer une technique de « numérotation » des éléments de cet ensemble ordonné :

On dira que (0,0), (0,1), (0,2), (0,3) etc. occupent respectivement les positions 0, 1, 2, 3, etc.

(1,0) est le plus petit élément se trouvant après une infinité d'éléments. On convient de noter \omega sa position[2].

(1,1) est l'élément qui suit \omega ; sa place sera indexée \omega+1, etc.

(2,0) est le plus petit élément se trouvant après une double infinité d'éléments. Il occupe la position \omega+\omega, aussi notée \omega2. Plus généralement (n,0) occupe la place \omega n. Si on disposait des éléments supplémentaires à la suite des éléments précédents, ils se trouveraient après une infinité d'infinis, et on noterait \omega^2, \omega^2+1 et ainsi de suite les positions occupées.

Par exemple, si au lieu de couples on avait utilisé des triplets ou même des n-uplets (a1,a2,...,an-1 ,an) d'ordre quelconque, de façon générique on noterait \omega^{n-1}a_1+\omega^{n-2}a_2+ ... +\omega.a_{n-1}+a_n les positions occupées.

La théorie des ordinaux permet, entre autres, de donner un sens précis à cette numérotation heuristique des éléments d'un ensemble bien ordonné.

Définition[modifier | modifier le code]

On définit un nombre ordinal de l'une des deux manières suivantes :

  • la première définition est basée sur les classes d'équivalence d'ensembles ordonnés. Un ordinal est un ensemble bien ordonné, considéré à un isomorphisme d'ordre près (dans la catégorie des bons ordres où les morphismes sont les applications croissantes et les isomorphismes les bijections croissantes). Ainsi, si on change les noms des éléments d'un bon ordre, tant qu'on ne change pas la manière dont les éléments se comparent entre eux, on parle toujours du même ordinal ;
  • la seconde définition est due à John von Neumann, et traduit le fait qu'un ordinal est défini par l'ensemble des ordinaux qui le précèdent. Un ordinal α est un ensemble vérifiant les deux propriétés suivantes :
(i) La relation d'appartenance ∈ sur cet ensemble est un bon ordre strict, ce qui signifie
- ∀x∈α, x∉x
- ∀x,y,z∈α, (x∈y et y∈z) ⇒ x∈z
- ∀A∈P(α)\{∅}, ∃x∈A, ∀y∈A\{x}, x∈y
(ii) Cet ensemble est transitif, ce qui signifie : ∀x∈α, x⊂α.

La première définition ne se formalise pas commodément dans une théorie des ensembles telle que ZFC, les classes d'isomorphismes des bons ordres (non vides) n'étant pas des ensembles (ce sont des classes propres). La définition de von Neumann permet de désigner ces classes par un ensemble, en fournissant un représentant unique par classe d'isomorphisme, la relation d'ordre sur cet ensemble étant la relation d'appartenance (voir le paragraphe Propriétés).

C'est cette dernière que nous adopterons dans la suite de l'article. Usuellement, les ordinaux sont désignés par des lettres grecques, les ensembles en général par des lettres latines.

En appliquant la définition précédente, les entiers naturels peuvent être construits de la façon suivante :

0 = {} (ensemble vide)
n+1 = n ∪ {n}

Un entier positif est ainsi identifié à l'ensemble de ses prédécesseurs sur N. Exemples :

0 = {}
1 = {0} = { {} }
2 = {0,1} = { {}, { {} } }
3 = {0,1,2} = {{}, { {} }, { {}, { {} } }}
4 = {0,1,2,3} = { {} , { {} }, { {}, { {} } } , {{}, { {} }, { {}, { {} } }} }
etc.

De cette manière, tout entier naturel est un ensemble bien ordonné par la relation d'appartenance ∈, et l'inclusion des ensembles se traduit par un ordre sur les entiers naturels.

L'existence des ordinaux infinis est assuré par l'axiome de l'infini. Le premier nombre ordinal transfini (i.e. infini) est noté ω. Il correspond à l'ensemble des nombres entiers naturels \mathbb{N}=\{0,1,2,3,\ldots\}.

L'ordinal qui suit est ω ∪ {ω}, noté ω+1.

Pour définir une notation adaptée aux ordinaux suivants, nous aurons besoin de définir des opérations arithmétiques sur les ordinaux.

Les ordinaux sont totalement ordonnés au sens large par l'inclusion ou au sens strict par l'appartenance, mais ne forment pas un ensemble au sens des axiomes ZFC (la théorie des ensembles habituelle) ; ils forment une classe propre. Ceci peut être mis en évidence grâce au paradoxe de Burali-Forti : l'ensemble des ordinaux serait par définition un ordinal ... mais qui serait strictement plus grand (aussi par définition) que tous les ordinaux, et donc que lui-même, ce qui est contradictoire.

Propriétés[modifier | modifier le code]

On montre que :

  • Si deux ordinaux \alpha et \beta sont donnés, alors ou bien \alpha \in \beta, ce qu'on note également \alpha < \beta, ou bien \alpha = \beta, ou bien \beta \in \alpha. On a l'équivalence entre \alpha \subset \beta et (\alpha \in \beta ou \alpha = \beta), ce qu'on note \alpha \le \beta.
  • Tous les éléments d'un ordinal sont des ordinaux.
  • Si (E, \leq) est un ensemble bien ordonné, il existe un unique ordinal \alpha et un unique isomorphisme d'ordre entre E et \alpha ; en particulier si \alpha et \beta sont deux ordinaux isomorphes alors \alpha=\beta et l'isomorphisme est l'identité.
  • L'intersection de deux ordinaux est un ordinal, égal au plus petit des deux ordinaux.
  • La réunion de deux ordinaux est un ordinal, égal au plus grand des deux ordinaux.
  • Si \alpha est un ordinal, \alpha \cup \{\alpha\} aussi. Ce dernier ordinal est noté \alpha + 1. Si \alpha < \beta, alors \alpha +1\le \beta. Il n'existe donc aucun ordinal entre \alpha et \alpha +1, qu'on peut donc qualifier d'ordinal successeur de \alpha.
  • Si A est un ensemble dont les éléments sont des ordinaux, alors \cup(A) est un ordinal, borne supérieure de A pour la relation d'appartenance. (On note \cup(A) la réunion des ordinaux éléments de A).
  • Si \alpha est un ordinal non vide, alors :
ou bien \alpha possède un élément maximal \beta. Alors \cup(\alpha) = \beta \in \alpha, mais \beta + 1 \notin \alpha (puisque \beta est maximal), donc \beta+1 = \alpha.
ou bien \alpha ne possède pas d'élément maximal. Alors \cup(\alpha) \notin \alpha et on montre alors que \cup(\alpha) = \alpha. Dans ce dernier cas, on dit que \alpha est un ordinal limite. Un exemple d'un tel ordinal est donné par \omega, plus petit ordinal infini.
  • On dit que l'ordinal \alpha est fini si \alpha n'est pas un ordinal limite et ne contient aucun ordinal limite ; autrement dit \alpha est infini s'il existe un ordinal limite \beta\leq\alpha.
  • Récurrence transfinie. Cette récurrence généralise le principe de récurrence (qu'on applique sur les entiers) à tous les ordinaux. Si \varphi est une propriété portant sur les ordinaux, telle que, pour tout ordinal \alpha, l'implication suivante soit vraie :
(\forall \beta < \alpha, \varphi(\beta)) \Longrightarrow \varphi(\alpha)
alors \varphi est vérifiée pour tous les ordinaux. Dans le cas contraire, il suffirait de considérer le plus petit ordinal \alpha tel que \varphi(\alpha) soit fausse pour obtenir une contradiction[3].
On utilise souvent une variante de ce principe pour définir une fonction \alpha \to f(\alpha) sur les ordinaux par récurrence. Il suffit de donner trois cas  ;
  • Cas de base : f(0) = X_0X_0 est un ensemble donné ;
  • Cas successeur : f(\alpha + 1) = g(\alpha, f(\alpha))g est une fonction donnée ;
  • Cas limite : f(\lambda) = \bigcup_{\alpha<\lambda}f(\alpha).
Les deux premiers cas sont les deux usuels de la récurrence sur les entiers, le troisième est nécessaire pour étendre le schéma à tous les ordinaux.

Opérations arithmétiques sur les ordinaux[modifier | modifier le code]

On peut étendre les trois opérations arithmétiques de somme, produit et exponentiation à tous les ordinaux ; dans chaque cas il y a deux manières de définir l'opération.

Méthode intrinsèque 
On utilise les deux opérandes pour construire un ensemble ordonné dont on montre qu'il s'agit d'un bon ordre. Il y a donc un unique ordinal isomorphe à cet ordre, qui est par définition le résultat de l'opération. Cette méthode est plus constructive que la suivante mais moins aisée à utiliser en pratique.
Récurrence transfinie 
L'opération est définie par récurrence sur l'un des deux opérandes. Les deux premiers cas de la récurrence (cas de base et successeur) sont les mêmes que pour les entiers ce qui montre que l'opération est une extension de sa version arithmétique. Cette méthode permet de facilement démontrer les propriétés élémentaires de l'opération, par exemple l'associativité de la somme et du produit.

Addition[modifier | modifier le code]

Pour définir la somme de deux ordinaux \alpha et \beta, on procède comme suit. En premier lieu on renomme les éléments de \beta de façon à ce qu'ils soient distincts de ceux de \alpha, ensuite, les éléments de l'ordinal \alpha dans l'ordre sont écrits à gauche des éléments de \beta, de sorte qu'on définit un ordre sur \alpha \cup \beta dans lequel tout élément de \alpha est strictement plus petit que tout élément de \beta. Les ordinaux \alpha et \beta conservent leur ordre initial.

Plus précisément on considère l'union disjointe \alpha\uplus\beta de \alpha et \beta, c'est-à-dire l'ensemble (\{0\}\times\alpha)\cup(\{1\}\times\beta) que l'on ordonne lexicographiquement : (i,\gamma)<(j,\gamma') ssi i<j ou i=j et \gamma<\gamma'.

De cette façon, on définit un bon ordre sur \alpha \uplus \beta ; cet ensemble bien ordonné est isomorphe à un unique ordinal que l'on appelle \alpha + \beta.

On peut également définir la somme par récurrence transfinie de la façon suivante :

  • \alpha + 0 = \alpha
  • \alpha + (\beta + 1) = (\alpha + \beta) + 1
  • si \beta est un ordinal limite, alors \alpha + \beta = \cup_{\gamma < \beta} (\alpha + \gamma), ordinal limite (ou borne supérieure) des \alpha + \gamma pour \gamma < \beta.

On vérifie facilement (par induction transfinie) que les deux définitions coïncident.

Donnons quelques exemples.

Si \alpha et \beta sont des ordinaux finis, c'est-à-dire des entiers naturels, alors leur somme au sens ordinal est égale à leur somme au sens arithmétique.

\omega est le premier ordinal infini, correspondant à l'ensemble des entiers naturels. Essayons de visualiser \omega + \omega. Deux copies de \omega sont placées l'une à la suite de l'autre. Si nous notons {0<1<2<...} la première copie et {0'<1'<2',...} la deuxième copie, alors \omega + \omega ressemble à ceci :

0 < 1 < 2 < 3 < ... < 0' < 1' < 2' < ...

Cet ordinal est différent de \omega car, dans \omega, 0 est le seul élément à ne pas avoir de prédécesseur direct, alors que dans \omega + \omega, 0 et 0' n'ont pas de prédécesseurs directs.

Considérons maintenant 3+\omega et \omega+3

0 < 1 < 2 < 0' < 1' < 2' < ...
0 < 1 < 2 < ... < 0' < 1' < 2'

Après renommage, le premier est comparable à \omega lui-même, mais pas le deuxième. On a donc 3+\omega = \omega mais \omega < \omega+3. On peut voir également, en utilisant la définition formelle, que \omega + 3 est le successeur de \omega + 2 alors que 3+\omega est un ordinal limite, à savoir l'ordinal limite réunion de 3+0, 3+1, 3+2, ... qui n'est autre que \omega lui-même.

Ainsi, l'addition n'est pas commutative, par contre, on peut montrer qu'elle est associative.

On a par exemple : (\omega + 4) + \omega = \omega + (4 + \omega) = \omega + \omega

On peut également montrer que :

\gamma+\alpha = \gamma+\beta \Longrightarrow \alpha = \beta

Il y a donc une simplification à gauche. Par contre, il n'y a pas de simplification à droite, puisque :

3+\omega = 0+\omega = \omega et 3 \neq 0

De même, on a :

\alpha < \beta \Longrightarrow \gamma + \alpha < \gamma + \beta

mais la relation analogue avec \gamma à droite est fausse. On a seulement :

\alpha \le \beta \Longrightarrow \alpha+\gamma \le \beta+\gamma

Soit deux ordinaux α ≤ β, alors il existe un unique ordinal γ tel que

\beta = \alpha + \gamma

L'ordinal γ est l'unique ordinal isomorphe à l'ensemble bien ordonné {η | α ≤ η < β}. Cette propriété permet de définir une soustraction à gauche, et l'on note parfois γ = β - α (si α < β, on convient que α - β = 0).

Multiplication[modifier | modifier le code]

Pour multiplier deux ordinaux \alpha et \beta, on écrit dans l'ordre les éléments de \beta, et on remplace chacun d'eux par différentes copies de la liste ordonnée des éléments de \alpha.

Plus précisément on considère le produit cartésien \alpha\times\beta que l'on ordonne lexicographiquement par la droite : (\gamma_1,\gamma_2)<(\gamma'_1,\gamma'_2) ssi \gamma_2<\gamma'_2 ou \gamma_2=\gamma'_2 et \gamma_1<\gamma'_1.

On obtient un ensemble bien ordonné qui est isomorphe à un unique ordinal, noté \alpha\beta.

On peut également définir le produit par récurrence transfinie :

  • \alpha 0 = 0
  • \alpha(\beta+1) = \alpha\beta + \alpha
  • si \beta est un ordinal limite, \alpha\beta = \cup_{\gamma < \beta} (\alpha\gamma), ordinal limite (ou borne supérieure) des \alpha\gamma pour \gamma < \beta.

Comme pour la somme on montre facilement par induction transfinie que les deux définitions coïncident. Lorsqu'on les applique à des ordinaux finis on retrouve le produit usuel des entiers naturels.

Voici \omega 2 :

00 < 10 < 20 < 30 < ... < 01 < 11 < 21 < 31 < ...

Et on voit que \omega 2 = \omega + \omega.

Par contre, 2\omega ressemble à ceci :

00 < 10 < 01 < 11 < 02 < 12 < 03 < 13 < ...

et après renommage, on reconnaît \omega, de sorte que 2\omega = \omega. La multiplication des ordinaux n'est donc pas commutative, par contre, on peut montrer qu'elle est associative.

Les principales propriétés du produit sont :

  • \alpha 0 = 0\alpha = 0 et \alpha 1 = 1\alpha = \alpha,
  • \alpha\beta = 0 \Longrightarrow \alpha = 0 ou \beta=0,
  • \alpha < \beta et \gamma > 0 \Longrightarrow \gamma\alpha < \gamma\beta,

mais si on change \gamma de côté, l'inégalité stricte peut être mise en défaut. Par exemple, 1 < 2 mais 1\omega = 2\omega = \omega. Par contre, on a :

  • \alpha \le \beta \Longrightarrow \alpha\gamma \le \beta\gamma
  • \gamma\alpha = \gamma\beta et \gamma > 0 \Longrightarrow \alpha = \beta (simplification à gauche). L'exemple ci-dessus montre qu'il n'y a pas de simplification à droite.
  • \alpha(\beta + \gamma) = \alpha\beta + \alpha\gamma (distributivité à gauche).

Par contre, il n'y a pas de distributivité à droite. En effet,

(\omega+1)2 = \omega + 1 + \omega + 1 = \omega + \omega + 1= \omega 2 + 1 et non \omega 2 + 2
  • Soit α un ordinal et β > 0, il existe un unique γ et un unique δ < β tel que α = βγ + δ (propriété analogue à la division euclidienne sur les entiers).

Exponentiation[modifier | modifier le code]

Pour un exposant fini, on peut se ramener au produit. Par exemple, \omega^2 = \omega \omega. Mais on peut visualiser cet ordinal comme l'ensemble des couples d'entiers, ordonné selon l'ordre lexicographique suivant, où l'ordre sur les entiers de droite a plus de poids que l'ordre sur les entiers de gauche  :

(0,0) < (1,0) < (2,0) < (3,0) < ... < (0,1) < (1,1) < (2,1) < (3,1) < ... < (0,2) < (1,2) < (2,2) < ...

et de même, pour un n fini, \omega^n peut-être vu comme l'ensemble des n-uplets d'entiers.

Si on tente d'étendre ce procédé à \omega^\omega, on obtient :

(0,0,0,...) < (1,0,0,0,...) < (2,0,0,0,...) < ... <
(0,1,0,0,0,...) < (1,1,0,0,0,...) < (2,1,0,0,0,...) < ... <
(0,2,0,0,0,...) < (1,2,0,0,0,...) < (2,2,0,0,0,...)
< ... <
(0,0,1,0,0,0,...) < (1,0,1,0,0,0,...) < (2,0,1,0,0,0,...)
< ...

Chaque élément du tableau est une suite infinie d'entiers, mais si on prend des suites quelconques, l'ordre ainsi défini n'est pas un bon ordre. Par exemple, cette suite infinie est strictement décroissante :

(1,1,1,...) > (0,1,1,1,...) > (0,0,1,1,1,...) > ...

Pour obtenir un bon ordre, on se limite aux suites d'entiers n'ayant qu'un nombre fini d'éléments non nuls : étant donné deux ordinaux \alpha et \beta, on considère l'ensemble \alpha^{(\beta)} des fonctions de \beta dans \alpha dont le support est fini (le support de f:\beta\rightarrow\alpha est l'ensemble des \gamma\in\beta tels que f(\gamma) \neq 0). Soient f et g deux telles fonctions. On pose f<g s'il existe \gamma_0\in \beta tel que

f(\gamma_0)<g(\gamma_0)\quad\text{ et }\quad\forall \gamma>\gamma_0, \; f(\gamma)=g(\gamma)

On vérifie que \alpha^{(\beta)} est alors bien ordonné, donc isomorphe à un unique ordinal noté \alpha^\beta. Dans le cas où \alpha et \beta sont finis on voit immédiatement que cet ordinal est l'exponentielle des entiers naturels. Dans le cas où \alpha=\omega l'ordre que l'on a construit sur \omega^{(\beta)} est connu sous le nom d'ordre multi-ensemble.

Comme pour la somme et le produit on peut également définir \alpha^\beta par récurrence transfinie de la façon suivante :

  • \alpha^0 = 1
  • \alpha^{\beta+1} = \alpha^{\beta}\alpha
  • si \beta est un ordinal limite et \alpha>0, alors \alpha^\beta = \cup_{\gamma < \beta}(\alpha^\gamma). Si \alpha=0 et \beta \ge 1 alors \alpha^\beta = 0.

On trouve que 1^\omega = 1, 2^\omega = \omega, 2^{\omega+1} = \omega 2 = \omega + \omega.

Voici quelques propriétés de l'exponentiation :

1^\alpha=1
si \gamma > 1 alors \alpha < \beta \iff \gamma^{\alpha}<\gamma^{\beta}
\alpha \le \beta \Rightarrow \alpha^{\gamma} \le \beta^{\gamma}. On prendra garde que :
2<3 mais 2^{\omega}=3^{\omega} = \omega
\alpha>1 et \beta>0 \Rightarrow il existe un unique ordinal \delta tel que \alpha^{\delta} \le \beta <\alpha^{\delta+1}
\alpha^{\beta}\alpha^{\gamma}=\alpha^{\beta+\gamma}
(\alpha^{\beta})^{\gamma}=\alpha^{\beta\gamma}
si \beta>0 et \alpha>1, alors il existe une décomposition unique \beta = \alpha^{\beta_n}\gamma_n + \cdots + \alpha^{\beta_0}\gamma_0 avec, pour tout i, 0<\gamma_i < \alpha et les exposants \beta_i strictement croissants, ce qui donne une sorte de décomposition de \beta en base \alpha

Remarque : on prendra garde que l'exponentiation des ordinaux n'a que peu de rapport avec l'exponentiation des cardinaux. Par exemple 2^{\omega}=\omega est un ordinal dénombrable, alors que, dans les cardinaux, 2^{\aleph_0} désigne le cardinal de \mathcal P(\aleph_0), ensemble des parties de \aleph_0, et a la puissance du continu. L'ambiguïté est levée si on convient d'utiliser les lettres grecques en calcul ordinal et la lettre \aleph pour les cardinaux.

La suite des ordinaux transfinis commence comme suit :

\omega < \omega + 1< \omega + 2 < \dots < \omega+\omega = \omega 2 < \dots < \omega 3 < \dots < \omega\omega = \omega^2 < \dots < \omega^\omega < \dots < \omega^{\omega^\omega} < \dots

Il existe des nombres ordinaux transfinis qui ne peuvent pas être obtenus en effectuant un nombre fini d'opérations arithmétiques n'utilisant que les nombres ordinaux finis et \omega. Le plus petit d'entre eux est appelé ε₀ (en) et vaut

\omega^{\omega^{\omega^{\cdots}}}. C'est le plus petit ordinal solution de l'équation x=\omega^x. On peut ensuite définir ε₀ε₀, ε₀ε₀ε₀, etc. jusqu'à ε1, deuxième solution de x=\omega^x.

On peut de même définir ε2, ε3, … , εω, … , εε₀

Tous ces ordinaux, construits en utilisant les opérations successeur et limite d'ordinaux déjà construits, sont dénombrables. On désigne par Ω, le premier ordinal non dénombrable. Il contient tous les ordinaux dénombrables. Toute suite définie dans Ω, admet un majorant dans Ω.

Forme normale de Cantor[modifier | modifier le code]

On peut généraliser aux ordinaux la notation en base 10 usuelle des entiers naturels. En prenant comme base un ordinal λ ≥ 2, tout ordinal α ≥ 1 s'écrit de façon unique

\alpha=\lambda^{\beta_1} \delta_1 + \lambda^{\beta_2}\delta_2 + \cdots + \lambda^{\beta_k}\delta_k

avec k un entier naturel, α ≥ β1 > ... > βk et pour ik, 0 < δi < λ.

Malheureusement, cette écriture en base λ n'est utile que pour les ordinaux α strictement inférieurs à la limite de λ, λλ, λλ), ... En effet la limite μ de cette suite vérifie μ = λμ, qui est sa forme normale de Cantor en base λ, laquelle forme étant sans intérêt. En base 10, on ne peut donc atteindre que les ordinaux finis, ie les entiers naturels.

En base ω, on pose ε0 le plus petit ordinal tel que \omega^{\varepsilon_0}=\varepsilon_0 (la limite des puissances de ω). En mettant également les βi sous forme normale, un ordinal α < ε0 s'écrit en base ω par exemple

\alpha = \omega^{\omega^{\omega6+42}\cdot1729+\omega^9+88}+\omega^{\omega^\omega}+65537

Les opérations sur les ordinaux sont simples sous forme normale :

  • l'addition ωβc + ωβ'c'=
    • ωβ'c' si β<β'
    • est déjà sous forme normale si β>β'
    • ωβ(c+c') si β=β'
  • la multiplication reste ωβc.ωβ'c = ωβ+β'c.

On notera une variante de cette forme normale qui écrit :

\alpha = \omega^{\beta_1}  + \omega^{\beta_2} + \cdots + \omega^{\beta_k}

en forçant c_1, c_2, \ldots, c_k =1 avec cette fois-ci des répétitions possibles :

\beta_1 \geq \beta_2 \geq \ldots \geq \beta_k.

Utilisation des ordinaux[modifier | modifier le code]

En dehors d'utilisations spécifiques à la théorie des ensembles, les ordinaux se rencontrent dans les domaines suivants :

En arithmétique[modifier | modifier le code]

Le théorème de Goodstein est un théorème d'arithmétique dont la démonstration repose sur la théorie des ordinaux. Ce théorème pose la question de savoir si une certaine suite à valeurs entières finit par prendre la valeur 0. On associe à cette suite d'entiers une suite d'ordinaux strictement décroissante. Compte tenu du bon ordre des ordinaux, une telle suite est effectivement finie. La suite possède une définition relativement simple, pourtant on peut démontrer que le théorème de Goodstein n'est pas démontrable en utilisant uniquement les propriétés de l'arithmétique usuelle et donc que l'utilisation des ordinaux infinis permet de démontrer des résultats arithmétiques indécidables dans l'arithmétique.

En analyse[modifier | modifier le code]

Les ordinaux ont été définis par Cantor à la suite de ses études sur la convergence des séries trigonométriques. Si une telle série \sum a_n \cos(nx) + b_n \sin(nx) est nulle sur \mathbb R, alors tous les coefficients a_n et b_n sont nuls. Cantor va chercher à affaiblir les hypothèses en réduisant le domaine sur lequel la série s'annule. Il montre que le résultat reste vrai si la série est nulle sauf en un nombre fini de points. Puis il introduit la notion suivante. Si P est une partie d'un segment [a,b], il définit l'ensemble dérivé de P, noté P^1 comme l'ensemble des points d'accumulation de P ou, de manière équivalente, comme l'ensemble P duquel ont été retirés tous les points isolés. Pour tout entier n, il définit P^{n+1} comme étant le dérivé de l'ensemble P^n. Il montre que, si la série trigonométrique est nulle sur [0,2\pi] en dehors d'un ensemble P pour lequel l'un des P^n est vide, alors les coefficients sont nuls.

Cherchant à prolonger ce résultat si les P^n sont tous non vides. Il définit alors P^{\omega} = \cap_{n \in \mathbb N}P^n, puis P^{\omega+1} comme étant le dérivé de P^{\omega}. D'une manière générale, on définit, pour tout ordinal \alpha l'ensemble P^{\alpha+1} comme étant l'ensemble dérivé de P^{\alpha}, et si \alpha est un ordinal limite, P^{\alpha} comme étant \cap_{\beta < \alpha} P^{\beta}.

René Baire reprendra cette démarche pour la convergence simple des suites de fonctions continues vers une fonction discontinue. Il définit une partie réductible P comme une partie pour laquelle il existe un ordinal \alpha tel que P^{\alpha} soit vide. Baire montre ensuite que si f est une fonction telle que l'ensemble des points où elle est discontinue est un ensemble réductible, alors f est limite simple d'une suite de fonctions continues.

Dans le cas contraire, la suite des P α se stabilise avant l'ensemble P Ω, où Ω désigne, à nouveau, le premier ordinal non dénombrable. On montre que P Ω est un ensemble parfait.

En topologie[modifier | modifier le code]

Soit α un ordinal. Notons [0, α] l'ensemble des ordinaux inférieurs ou égaux à α. Cet ensemble peut être muni d'une structure topologique : la topologie de l'ordre, dont une prébase d'ouverts est constituée des parties {x | x > β} et {x | x < β} pour tout ordinal β inférieur ou égal à α. Ces topologies sont sources de nombreux exemples et contre-exemples.

Ainsi, si l'on prend α = ω, alors [0, ω[ est l'ensemble ℕ muni de sa topologie discrète usuelle. Son compactifié d'Alexandrov est [0, ω].

Si l'on prend α = ω₁, le premier ordinal non dénombrable (noté ci-dessus Ω), alors aucune suite strictement inférieure à ω1 ne peut converger vers ω1, bien que ω1 appartienne à l'adhérence de [0, ω1[. En particulier, ω1 n'admet pas de base dénombrable de voisinages et c'est le seul point de [0, ω1] qui soit dans ce cas.

Dans tout espace [0, α], les points de la forme β + 1 sont isolés. L'espace [0, α] est compact. Les espaces [0, α] et [0, α[ sont normaux. La planche de Tychonoff [0, ω1]×[0, ω] est normale mais pas complètement normale. La planche de Tychonoff épointée, [0, ω1]×[0, ω] \ {(ω1, ω)}, est complètement régulière mais n'est pas normale. L'espace [0, ω1] est complètement normal, mais pas parfaitement normal. L'espace [0, ω1]×[0, ω1] \ {(ω1, ω1)} est faiblement normal mais pas normal.

Une construction similaire donne naissance à la longue droite, un espace topologique analogue à la droite réelle, mais « beaucoup plus long ».

Notes[modifier | modifier le code]

  1. Hapax : zéroième sur le CNRTL
  2. Cette notation, due à Georg Cantor, a été largement adoptée et est désormais employée dans la plupart des branches des mathématiques
  3. Les utilisateurs habitués à la récurrence usuelle peuvent penser qu'il faut aussi ajouter le "cas de base" \varphi(0). Il n'en est rien, en raison de la définition rigoureuse de l'implication, et surtout des propriétés (parfois jugées paradoxales) de l'ensemble vide ; on trouvera plus de précisions dans l'article détaillé récurrence transfinie

Articles connexes[modifier | modifier le code]

Sur les autres projets Wikimedia :