Bien fondé (ordre)

Imaginez un compte à rebours qui ne peut descendre qu’en passant par des entiers naturels. À partir de 11, on peut aller à 8, puis 5, puis 2. On finit nécessairement par atteindre une valeur où la règle de descente s’arrête : il n’existe pas de suite infinie d’entiers naturels qui diminue à chaque étape.

Un ordre est dit bien fondé lorsque tout groupe non vide d’éléments possède au moins un point de départ minimal. Cette garantie autorise les raisonnements par récurrence et les preuves de terminaison fondées sur une quantité qui décroît.

Soit un ensemble noté E, muni d’une relation d’ordre stricte notée ≺. La relation est bien fondée si toute partie non vide A de E contient un élément minimal m. Cela signifie qu’aucun élément de A ne précède strictement m.

Avec une relation réflexive notée ≤, la même condition s’écrit : il n’existe dans A aucun élément a tel que a ≤ m et a ≠ m. Dans un ordre partiel, plusieurs éléments minimaux peuvent coexister et aucun ne doit nécessairement être inférieur à tous les autres. Pour l’ordre usuel sur les entiers naturels, toute partie non vide possède même un plus petit élément ; l’ordre est donc bien fondé.

La récurrence bien fondée en découle. Pour une propriété P définie sur E, il suffit de prouver P(x) en supposant P(y) vraie pour chaque prédécesseur y de x. La propriété est alors vraie pour tout élément de E.

On étudie une procédure qui soustrait 3 à un entier naturel tant que celui-ci vaut au moins 3.
Données : valeur initiale 11 ; décrément 3 ; arrêt dès que la valeur est strictement inférieure à 3 ; ordre usuel des entiers naturels.

1. La procédure part de 11 et produit 8.
2. Elle produit ensuite 5, puis 2.
3. À chaque opération, la valeur reste un entier naturel et diminue strictement.
4. À 2, la condition de poursuite n’est plus satisfaite : la procédure s’arrête après trois soustractions. La trajectoire complète est 11 → 8 → 5 → 2.

La valeur courante sert ici de mesure de terminaison. Une exécution infinie créerait une suite infinie strictement décroissante d’entiers naturels, ce que le bon fondement interdit.

Le contrôle se refait directement : 11 − 3 = 8, 8 − 3 = 5 et 5 − 3 = 2. Les trois valeurs avant soustraction sont au moins égales à 3, tandis que la valeur finale 2 est inférieure à 3.

Pour prouver qu’un algorithme s’arrête, on associe à chaque état une valeur dans un ensemble bien fondé. On vérifie ensuite que chaque étape fait strictement décroître cette valeur. Si une simple valeur entière ne décroît pas toujours, on choisit une mesure plus adaptée plutôt que de conclure trop vite.

Pour définir un objet par récurrence, on construit sa valeur à partir de celles déjà définies sur tous ses prédécesseurs. La récurrence ordinaire sur les entiers naturels suffit lorsque chaque rang ne dépend que de rangs plus petits ; une relation bien fondée plus générale convient à une dépendance ramifiée.

Pour tester un ordre proposé, on cherche une partie non vide dépourvue d’élément minimal. En trouver une réfute immédiatement le bon fondement. À défaut, il reste à démontrer que toute partie non vide possède un minimal, et pas seulement les quelques parties examinées.

Élément minimal et plus petit élément. Un minimal n’a aucun élément strictement plus petit dans la partie. Un plus petit élément appartient à la partie et est inférieur ou égal à tous les éléments de cette partie. Dans un ordre partiel, deux éléments incomparables peuvent être tous deux minimaux, sans qu’aucun soit le plus petit.

Ordre bien fondé et ordre total. Le bon fondement garantit des minimaux dans toutes les parties non vides ; la totalité garantit que deux éléments sont toujours comparables. L’ordre usuel des entiers relatifs est total, mais il n’est pas bien fondé, car l’ensemble entier n’a pas de minimal.

Élément minimal et borne inférieure. Une borne inférieure peut se trouver hors de la partie, tandis qu’un élément minimal lui appartient nécessairement. Dans les réels usuels, 0 est la borne inférieure de l’intervalle ouvert des nombres strictement compris entre 0 et 1, mais cet intervalle n’a pas d’élément minimal.

La partie vide ne sert pas de test. Elle ne contient aucun élément minimal, mais la définition porte uniquement sur les parties non vides. Inclure la partie vide rendrait la condition impossible à satisfaire.

Un minimal n’est pas forcément unique. Dans un ordre partiel, une partie peut avoir plusieurs minimaux incomparables. Il faut établir l’unicité séparément avant de parler du minimal ou d’un plus petit élément.

La convention d’écriture compte. Avec l’ordre strict, un minimal n’a aucun prédécesseur dans la partie. Avec l’ordre réflexif, il peut être relié à lui-même ; on doit alors exclure explicitement l’égalité dans le test.

Une décroissance doit être stricte à chaque étape pertinente. Une mesure qui reste parfois constante ne prouve pas seule la terminaison. Il faut montrer qu’une autre mesure bien fondée décroît, ou regrouper des étapes de façon à obtenir une baisse stricte.

La relation d’ordre précise les propriétés du cadre dans lequel le bon fondement est étudié.

La notion d’élément minimal aide à distinguer minimalité, unicité et plus petit élément dans un ordre partiel.

Les entiers naturels fournissent le modèle fondamental d’un ordre bien fondé et le support habituel de la récurrence ordinaire.