Les ordinaux et la récurrence transfinie

Un ordre est bon exactement quand il n'existe pas de suite infinie strictement décroissante.

Dans ℕ, on ne peut pas descendre indéfiniment : en partant de 100, il faudra s'arrêter à 0 au bout d'au plus 100 pas. Dans ℤ ou dans ℚ, au contraire, on peut toujours descendre plus bas. La page joue ici à « descendre au hasard » dans six ensembles ordonnés : à chaque pas, elle choisit au hasard un élément strictement plus petit. Dans un bon ordre, la descente finit toujours, même quand le nombre de pas n'est borné par rien à l'avance. C'est ce qui se passe dans ℕ × ℕ rangé lexicographiquement : on peut descendre de (1, 0) vers (0, 1 000 000), puis encore un million de fois.

Tout ordinal non nul est soit un successeur, soit une limite.

Un ordinal α a un successeur α + 1 = α ∪ {α}. Un ordinal non nul qui n'est le successeur de personne est un ordinal limite : c'est la réunion de tous ceux qui le précèdent. On l'atteint par une suite qui grimpe vers lui sans l'atteindre, sa suite fondamentale : ω = sup(1, 2, 3, …), ω·2 = sup(ω + 1, ω + 2, …), ω² = sup(ω, ω·2, ω·3, …). Tout ordinal inférieur à ω³ s'écrit de façon unique ω²·a + ω·b + c. C'est un successeur si c ≠ 0, et une limite si c = 0 sans que l'ordinal soit nul. Choisissez α : ses prédécesseurs, c'est-à-dire ses éléments, s'allument en bleu.

Trois cas au lieu de deux : zéro, le successeur, et la limite.

Pour démontrer qu'une propriété P(α) est vraie pour tous les ordinaux, il suffit de prouver trois choses. D'abord P(0). Ensuite, si P(α) est vraie, P(α + 1) l'est aussi. Enfin, pour un ordinal limite λ, si P(β) est vraie pour tous les β < λ, alors P(λ) l'est aussi. En effet, s'il existait un contre-exemple, il y en aurait un plus petit, puisque les ordinaux sont bien ordonnés, et aucun des trois cas ne le permet. Le même schéma sert à définir une fonction. L'addition se définit ainsi : α + 0 = α, α + (β + 1) = (α + β) + 1, et α + λ = sup{α + β : β < λ}. Pour la multiplication : α·0 = 0, α·(β + 1) = α·β + α, et α·λ = sup{α·β : β < λ}. La page calcule chaque résultat de deux façons : en déroulant cette définition (le sup étant lu sur la suite fondamentale), et par les formules de Cantor sur la forme normale ω^k·c + …

Les ordinaux s'additionnent et se multiplient, mais l'ordre des facteurs compte.

Comme l'addition consiste à mettre deux files bout à bout, elle n'est pas commutative : 1 + ω = ω, mais ω + 1 > ω. Le produit α·β est la file β dans laquelle on remplace chaque élément par une copie de α. Ainsi 2·ω, ω copies de 2, donne ω, alors que ω·2, deux copies de ω, donne ω + ω. Certaines lois survivent : l'associativité, la distributivité à gauche α·(β + γ) = α·β + α·γ, la simplification à gauche. D'autres tombent : la commutativité, la distributivité à droite, la simplification à droite. La page met chaque loi à l'épreuve sur 8 000 triplets tirés au hasard parmi les ordinaux inférieurs à ω³. Elle compare enfin avec la somme naturelle de Hessenberg, qui additionne les formes normales terme à terme et redevient commutative.

Trois endroits où les ordinaux font un travail que les entiers ne peuvent pas faire.