Proposition 5Structures d'ordre

Bons ordres

Un bon ordre sur $E$ est une relation d'ordre pour laquelle toute partie non vide de $E$ a un plus petit élément. Pour $x \in E$ , on note $E_x = \{y \in E : y < x\}$ .

Énoncé

Soit $(E, \leqslant)$ bien ordonné.

(i) L'ordre est total.

(ii) Principe d'induction. Soit $P \subset E$ telle que, pour tout $x \in E$ , l'inclusion $E_x \subset P$ entraîne $x \in P$ . Alors $P = E$ .

(iii) Toute application strictement croissante $f : E \to E$ vérifie $x \leqslant f(x)$ pour tout $x$ .

(iv) Tout segment initial $C \neq E$ est de la forme $E_x$ , avec $x = \min(E \setminus C)$ . Aucun $E_x$ n'est isomorphe à $E$ .

(v) Entre deux ensembles bien ordonnés, il existe au plus un isomorphisme d'ordres.

Démonstration

(i) Pour $x, y \in E$ , la partie $\{x, y\}$ a un plus petit élément, qui est inférieur à l'autre.

(ii) Sinon, $E \setminus P$ a un plus petit élément $x$ . Tout $y < x$ appartient à $P$ , donc $E_x \subset P$ , et l'hypothèse donne $x \in P$ : contradiction.

(iii) Sinon, $\{x : f(x) < x\}$ a un plus petit élément $x_0$ . Comme $f(x_0) < x_0$ et que $f$ est strictement croissante, $f(f(x_0)) < f(x_0)$ : l'élément $f(x_0)$ appartient à cet ensemble et précède $x_0$ , contradiction.

(iv) Soit $x$ le plus petit élément de $E \setminus C$ . Si $y < x$ , alors $y \in C$ par minimalité. Si $y \in C$ , on ne peut avoir $x \leqslant y$ , sinon $x \in C$ ; donc $y < x$ par totalité. Ainsi $C = E_x$ .

Un isomorphisme $f$ de $E$ sur $E_x$ serait strictement croissant de $E$ dans $E$ avec $f(x) < x$ , contrairement à (iii).

(v) Si $f$ et $g$ sont deux isomorphismes de $E$ sur $F$ , alors $g^{-1} \circ f$ et $f^{-1} \circ g$ sont strictement croissantes de $E$ dans $E$ . Par (iii), $x \leqslant g^{-1}(f(x))$ , soit $g(x) \leqslant f(x)$ , et de même $f(x) \leqslant g(x)$ . Donc $f = g$ .

□

Remarque

Le principe (ii) est la forme ensembliste de l'induction transfinie. Sur les ordinaux, qui ne forment pas un ensemble, il deviendra un schéma, au nœud Induction transfinie.

Remarque

Sur un ensemble bien ordonné, aucune suite ne peut décroître strictement indéfiniment, puisque ses termes formeraient une partie non vide sans plus petit élément. Cette formulation demande les suites, donc $\mathbb N$ . Elle caractérise les bons ordres parmi les ordres totaux, mais la réciproque emploie l'axiome du choix dépendant (⋆), défini au nœud $\mathbb N$ : si une partie non vide $A$ d'un ensemble totalement ordonné n'a pas de plus petit élément, tout $x \in A$ admet un $y \in A$ tel que $y < x$ , et le choix dépendant, appliqué à cette relation sur $A$ , fournit une suite strictement décroissante d'éléments de $A$ .

Repose sur

Majorants, plus grand élément, borne supérieure Applications croissantes, isomorphismes d'ordres Intervalles et segments

Sert à

Aucune fiche de ce graphe ne l'utilise encore.