Théorie des ordinaux

En linguistique, les mots premier, deuxième, troisième, quatrième, etc. s'appellent des adjectifs numéraux ordinaux qui servent à préciser le rang d'un objet dans une collection ou l'ordre d'un événement dans une succession. Cette notion se généralise en mathématiques pour qualifier le type d'ordre d'un ensemble bien ordonné quelconque, plutôt que son « étendue » laquelle est mesurée par sa cardinalité : tous les cardinaux sont aussi des ordinaux mais la réciproque n'est pas vraie. Un ordinal peut être fini ou bien infini. Ce concept a été inventé par Georg Cantor.

Sommaire 1 Introduction 2 Définition 3 Propriétés 4 Opérations arithmétiques sur les ordinaux 4.1 Addition 4.2 Multiplication 4.3 Exponentiation 4.4 Forme normale de Cantor 5 Utilisation des ordinaux 5.1 En arithmétique 5.2 En analyse 5.3 En topologie 6 Voir aussi

Introduction

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 (un, deux, trois,...) et ordinaux (premier, deuxième, troisième, ...) et sont très semblables. Cependant, dans le cas infini, on est amené à distinguer soigneusement 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 particulièrement 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 est noté 0, le suivant 1, le suivant 2, mais dès que l'ensemble est infini une notation adaptée est nécessaire pour désigner dans l'ordre tous les éléments de l'ensemble.

Considérons par exemple l'ensemble des entiers strictement positifs ordonné selon une variante de l'ordre de Sarkovski (ce dernier n'est pas un bon ordre). Disposons d'abord les entiers impairs, puis les impairs multipliés par 2, puis par 4, etc.

1, 3, 5, 7, etc. occupent respectivement les positions 0, 1, 2, 3, etc.

2 est le plus petit élément se trouvant après une infinité d'éléments. Du point de vue ordinal, il occupe une position notée ω.

2 × 3 est l'élément qui suit ω et occupe la place notée ω + 1, etc.

4 est le plus petit élément se trouvant après une double infinité d'éléments. Il occupe la place ω2. Plus généralement 2ⁿ occupe la place ω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, donc occuperaient les positions ω²,ω² + 1, et ainsi de suite.

Définition

On définit un nombre ordinal par l'une des deux manières qui suivent. La deuxième traduit le fait qu'un ordinal est défini par l'ensemble des ordinaux qui le précèdent :

• 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. Un ordinal α est un ensemble vérifiant les deux propriétés suivantes :

(i) La relation d'appartenance ∈ est un bon ordre strict sur lui.

(ii) Il est transitif, ce qui signifie que : .

C'est cette dernière définition 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 U {n}

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

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 est noté ω. Il correspond à l'ensemble des nombres entiers naturels .

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), mais 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

On montre que :

• Si deux ordinaux α et β sont donnés, alors ou bien , ce qu'on note également α < β, ou bien α = β, ou bien . On a l'équivalence entre et ( ou α = β), ce qu'on note .
• Tous les éléments d'un ordinal sont des ordinaux.
• Si est un ensemble bien ordonné, il existe un unique ordinal α et un unique isomorphisme d'ordre entre E et α ; en particulier si α et β sont deux ordinaux isomorphes alors α = β 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 α est un ordinal, aussi. Ce dernier ordinal est noté α + 1. Si α < β, alors . Il n'existe donc aucun ordinal entre α et α + 1, qu'on peut donc qualifier d'ordinal successeur de α.
• Si A est un ensemble dont les éléments sont des ordinaux, alors est un ordinal, borne supérieure de A pour la relation d'appartenance. (On note la réunion des ordinaux éléments de A).
• Si α est un ordinal non vide, alors :

ou bien α possède un élément maximal β. Alors , mais (puisque β est maximal), donc β + 1 = α.

ou bien α ne possède pas d'élément maximal. Alors et on montre alors que . Dans ce dernier cas, on dit que α est un ordinal limite. Un exemple d'un tel ordinal est donné par ω, plus petit ordinal infini.

• On dit que l'ordinal α est fini si α n'est pas un ordinal limite et ne contient aucun ordinal limite ; autrement dit α est infini s'il existe un ordinal limite .
• Récurrence transfinie. Cette récurrence généralise le principe de récurrence qu'on applique sur les entiers à tous les ordinaux. Si est une propriété portant sur les ordinaux, telle que, pour tout ordinal α, l'implication suivante soit vraie :

alors est vraie pour tous les ordinaux. Dans le cas contraire, il suffirait de considérer le plus petit ordinal α tel que soit fausse pour obtenir une contradiction.

On utilise souvent une variante de ce principe pour définir une fonction sur les tous ordinaux par récurrence. Il suffit de donner trois cas  ;

• Cas de base : f(0) = α₀ où α₀ est un ordinal donné ;
• Cas successeur : f(α + 1) = g(α,f(α)) où g est une fonction donnée ;
• Cas limite : .

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

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

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

Plus précisément on considère l'union disjointe de α et β, c'est à dire l'ensemble que l'on ordonne lexicographiquement : (i,γ) < (j,γ') ssi i < j ou i = j et γ < γ'.

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

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

• α + 0 = α
• α + (β + 1) = (α + β) + 1
• si β est un ordinal limite, alors , ordinal limite (ou borne supérieure) des α + γ pour γ < β.

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

Donnons quelques exemples.

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

ω est le premier ordinal infini, correspondant à l'ensemble des entiers naturels. Essayons de visualiser ω + ω. Deux copies de ω 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 ω + ω ressemble à ceci :

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

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

Considérons maintenant 3 + ω et ω + 3

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

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

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

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

On a par exemple : (ω + 4) + ω = ω + (4 + ω) = ω + ω

On peut également montrer que :

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

3 + ω = 0 + ω = ω et

De même, on a :

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

Pour tout ordinal α inférieur ou égal à β, on montre qu'il existe un ordinal unique γ tel que α + γ = β. γ s'appelle la différence de β par α. Si α est strictement supérieur à β, on convient que cette différence est nulle.

Multiplication

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

Plus précisément on considère le produit cartésien que l'on ordonne lexicographiquement par la droite : (γ₁,γ₂) < (γ'₁,γ'₂) ssi γ₂ < γ'₂ ou γ₂ = γ'₂ et γ₁ < γ'₁.

On obtient un ensemble bien ordonné qui est isomorphe à un unique ordinal, noté αβ.

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

• α0 = 0
• α(β + 1) = αβ + α
• si β est un ordinal limite, , ordinal limite (ou borne supérieure) des αγ pour γ < β.

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

Voici ω2 :

0₀ < 1₀ < 2₀ < 3₀ < ... < 0₁ < 1₁ < 2₁ < 3₁ < ...

Et on voit que ω2 = ω + ω.

Par contre, 2ω ressemble à ceci :

0₀ < 1₀ < 0₁ < 1₁ < 0₂ < 1₂ < 0₃ < 1₃ < ...

et après renommage, on reconnaît ω, de sorte que 2ω = ω. 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 :

α0 = 0α = 0

α1 = 1α = α

α < β et , mais si on change γ de côté, l'inégalité stricte peut être mise en défaut.

Par exemple, 1 < 2 mais 1ω = 2ω = ω. Par contre, on a :

γα = γβ et (simplification à gauche). L'exemple ci-dessus montre qu'il n'y a pas de simplification à droite.

ou β = 0

α(β + γ) = αβ + αγ (distributivité à gauche). Par contre, il n'y a pas de distributivité à droite.

En effet, (ω + 1)2 = ω + 1 + ω + 1 = ω + ω + 1 = ω2 + 1 et non ω2 + 2

soit α un ordinal et β > 0. Alors il existe un unique ordinal γ et un unique ordinal δ < β tels que α = βγ + δ. (C'est une sorte de division euclidienne.)

Exponentiation

Passons maintenant à l'exponentiation des ordinaux.

Pour un exposant fini, on peut se ramener au produit. Par exemple, ω² = ωω. 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, ωⁿ peut-être vu comme l'ensemble des n-uplets d'entiers.

Si on tente d'étendre ce procédé à ω^ω, 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. On obtient un tel bon ordre en se limitant aux suites d'entiers n'ayant qu'un nombre fini d'éléments non nuls.

Plus généralement étant donné deux ordinaux α et β, on considère l'ensemble α^(β) des fonctions de β dans α dont le support est fini (le support de est l'ensemble des tels que ). Soient f et g deux telles fonctions et notons S_f et S_g leurs supports. Comme ces deux ensembles sont finis leur union est finie aussi ; on pose f < g ssi et f(γ₀) < g(γ₀) où γ₀ est le plus grand tel que .

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

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

• α⁰ = 1
• α^{β + 1} = α^βα
• si β est un ordinal limite et α > 0, alors . Si α = 0 et alors α^β = 0.

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

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

1^α = 1

si γ > 1 alors

. On prendra garde que :

2 < 3 mais 2^ω = 3^ω = ω

α > 1 et il existe un unique ordinal δ tel que

α^βα^γ = α^{β + γ}

(α^β)^γ = α^βγ

si β > 0 et α > 1, alors il existe une décomposition unique avec, pour tout i, 0 < γ_i < α et les exposants β_i strictement croissants, ce qui donne une sorte de décomposition de β en base α

Remarque : on prendra garde que l'exponentiation des ordinaux n'a que peu de rapport avec l'exponentiation des cardinaux. Par exemple 2^ω = ω est un ordinal dénombrable, alors que, dans les cardinaux, désigne le cardinal de , ensemble des parties de , 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 pour les cardinaux.

La suite des ordinaux transfinis commence comme suit:

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 ω. Le plus petit d'entre eux est appelé ε₀ et vaut

. C'est le plus petit ordinal solution de l'équation x = ω^x. On peut ensuite définir , , etc. jusqu'à ε₁ deuxième solution de x = ω^x.

On peut de même définir ε₂, ε₃, ..., ε_ω, ..., , ...

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 plus petit ordinal non dénombrable. Il contient tous les ordinaux dénombrables. Toute suite définie dans Ω admet un majorant dans Ω.

Forme normale de Cantor

Pour manipuler les ordinaux, il est plus simple de recourir à une écriture unique. Pour les petits ordinaux, c'est possible : soit ε₀ le plus petit ordinal tel que . Tout α<ε₀ peut être écrit de façon unique où sont des entiers et sont des ordinaux (on autorise β_k = 0).

Les β_i sont eux aussi exprimés sous forme normale, ce qui donne des ordinaux du type :

.

L'ensemble des ordinaux définissables sous l'une ou l'autre de ces formes est donc ε₀.

Les opérations sur les ordinaux deviennent simples :

• l'addition ω^βc + ω^β'c'=
  • ω^β'c si β<β'
  • irréductible si β>β'
  • ω^β(c+c') si β=β'
• la multiplication reste ω^βc.ω^β'c = ω^β+β'c.

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

en forçant avec cette fois-ci des répétitions possibles :

.

Utilisation des ordinaux

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

En arithmétique

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

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 est nulle sur , 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¹ comme l'ensemble des points d'accumulation de P. Pour tout entier n, il définit P^{n + 1} comme étant le dérivé de l'ensemble Pⁿ. Il montre que, si la série trigonométrique est nulle sur [0,2π] en dehors d'un ensemble P pour lequel l'un des Pⁿ est vide, alors les coefficients sont nuls.

Cherchant à prolonger ce résultat si les Pⁿ sont tous non vides. Il définit alors , puis P^{ω + 1} comme étant le dérivé de P^ω. D'une manière générale, on définit, pour tout ordinal α l'ensemble P^{α + 1} comme étant l'ensemble dérivé de P^α, et si α est un ordinal limite, P^α comme étant .

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 α tel que P^α 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 à l'ensemble P^Ω, où Ω désigne le premier ordinal non dénombrable. On montre que P^Ω est un ensemble parfait.

En topologie

Soit Γ un ordinal. Notons [0,Γ] l'ensemble des ordinaux inférieurs ou égaux à Γ. Cet ensemble peut être muni d'une structure topologique, en prenant comme prébase d'ouverts les parties et pour tout ordinal α et β inférieurs ou égaux à Γ. Ces topologies sont sources de nombreux exemples et contre-exemples.

Ainsi, si on prend Γ = ω, alors [0,ω[ est l'ensemble muni de sa topologie discrète usuelle. [0,ω] est un compactifié de .

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

Dans tout espace [0,Γ], les points de la forme α + 1 sont isolés. [0,Γ] est un espace compact. [0,Γ] et [0,Γ[ sont des espaces topologiques normaux. est normal mais pas complètement normal. est complètement régulier mais n'est pas normal. [0,Ω] est complètement normal, mais pas parfaitement normal. est faiblement normal mais pas normal.

Voir aussi

• Ensemble bien ordonné
• Nombre cardinal
• Nombre transfini
• Nombre surréel et pseudo-réel

Notion de nombre
Ensembles usuels	Entier naturel • Entier relatif • Nombre décimal • Nombre rationnel • Nombre réel • Nombre complexe
Extensions	Quaternion • Octonion • Sédénion • Nombre complexe fendu • Tessarine • Nombre bicomplexe • Nombre multicomplexe • Biquaternion • Coquaternion • Octonion fendu • Nombre hypercomplexe • Nombre p-adique • Nombre hyperréel • Nombre superréel • Nombre dual • Droite réelle achevée • Nombre cardinal • Nombre ordinal • Nombre surréel et pseudo-réel
Propriétés particulières	Parité • Nombre premier • Nombre composé • Carré parfait • Nombre parfait • Nombre positif • Nombre négatif • Fraction dyadique • Nombre irrationnel • Nombre algébrique • Nombre transcendant • Nombre imaginaire pur • Nombre de Liouville • Nombre normal • Nombre univers • Nombre constructible • Nombre réel calculable • Nombre transfini • Infiniment petit • Infiniment grand
Exemples d’importance historique	π Pi • √2 Racine carrée de deux • φ Nombre d’or • 0 Zéro • i Unité imaginaire • e Constante de Neper • ℵ0 Aleph-zéro • Table de constantes mathématiques
Notions connexes	Chiffre • Numération • Fraction • Opération • Calcul • Algèbre • Arithmétique • Suite d’entiers • ∞ Infini • Chiffre significatif

• Portail des mathématiques