Nombre ordinal - Définition

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 :

.