Ordres bien fondés et induction structurelle

Une relation $⪯$ sur un ensemble $E$ est une relation d'ordre si elle est réflexive, antisymétrique et transitive. L'ordre est total si deux éléments quelconques sont toujours comparables, partiel sinon. On note $x\prec y$ pour « $x⪯y$ et $x\ne y$ ».

Soit $x,y\in E$.

• $x$ est un prédécesseur de $y$ si $x\prec y$ ; $y$ est alors un successeur de $x$.
• $x$ est un prédécesseur immédiat de $y$ si $x\prec y$ et qu'aucun $z$ ne vérifie $x\prec z\prec y$ : rien ne s'intercale.

$m\in E$ est minimal s'il n'admet aucun prédécesseur : aucun $x$ ne vérifie $x\prec m$.

Sur $E\times F$ munis de ${⪯}_E$ et ${⪯}_F$ :

$$(x_1,y_1)⪯(x_2,y_2)⟺x_1{⪯}_E{x}_2\text{ et }{y}_1{⪯}_F{y}_2.$$

Il faut que les deux composantes soient plus petites. C'est un ordre partiel même si ${⪯}_E$ et ${⪯}_F$ sont totaux : $(1,5)$ et $(3,2)$ ne sont pas comparables.

Sur ce même produit :

$$(x_1,y_1){⪯}_{\text{lex}}(x_2,y_2)⟺x_1{\prec }_E{x}_2\text{ ou }(x_1=x_2\text{ et }{y}_1{⪯}_F{y}_2).$$

C'est l'ordre du dictionnaire : on départage sur la première composante, et l'on ne regarde la seconde qu'en cas d'égalité. Il est total dès que ${⪯}_E$ et ${⪯}_F$ le sont — c'est là toute sa différence avec l'ordre produit.

Un ordre $⪯$ sur $E$ est bien fondé s'il n'existe aucune suite infinie strictement décroissante

$$x_0\succ x_1\succ x_2\succ \cdots$$

De façon équivalente : toute partie non vide de $E$ admet au moins un élément minimal.