Relation bien fondée
En mathématiques, une relation bien fondée (encore appelée relation noethérienne ou relation artinienne) est une relation binaire vérifiant l'une des deux conditions suivantes, équivalentes d'après l'axiome du choix dépendant (une version faible de l'axiome du choix) :
- pour toute partie non vide X de E, il existe un élément x de X n'ayant aucun R-antécédent dans X (un R-antécédent de x dans X est un élément y de X vérifiant yRx) ;
- condition de chaîne descendante : il n'existe pas de suite infinie (xn) d'éléments de E telle qu'on ait xn+1Rxn pour tout n.
Un ordre bien fondé (encore appelé ordre noethérien ou ordre artinien<ref>Modèle:Ouvrage.</ref>) est une relation d'ordre dont l'ordre strict associé est une relation bien fondée.
Toute relation bien fondée est strictement acyclique, c'est-à-dire que sa clôture transitive est un ordre strict. Une relation R est bien fondée si sa clôture transitive l'est, ou encore si R est antiréflexive et si sa clôture réflexive transitive est un ordre bien fondé.
Exemples
Nombres
- Sur l'ensemble N des entiers naturels, la relation R définie par x R y ⇔ y = x + 1 est bien fondée. Sa clôture transitive est l'ordre strict usuel <, et l'ordre usuel ≤ est un ordre total bien fondé, c'est-à-dire un bon ordre.
- Sur N×N, l'ordre produit est bien fondé (mais non total).
- Sur l'ensemble Z des entiers relatifs, la relation R définie par x R y ⇔ y = x + 1 n'est pas bien fondée comme l'atteste cette suite de nombres relatifs qui ne respectent pas la condition de chaîne descendante : ... < −6 < −5 < −4 < −3 < −2 < −1 < 0. Sa clôture transitive qui est l'ordre strict usuel < ne l'est pas non plus.
Chaînes de caractères
- Sur l'ensemble des chaînes de caractères, l'ordre strict « est préfixe strict de » est bien fondé.
- Sur l'ensemble des chaînes de caractères, l'ordre lexicographique n'est pas bien fondé. Par exemple, voici un exemple d'une suite de chaînes de caractères qui ne respectent pas la condition de chaîne descendante : ... < aaaaab < aaaab < aaab < aab < ab
Arbres binaires finis
- Sur l'ensemble des arbres binaires finis, construits à partir de l'arbre vide <math>\Box</math> et de l'enracinement ¤ (c'est-à-dire qu'à partir de deux arbres A et B on forme l'arbre A ¤ B), l'ordre strict « est un sous-arbre strict de » est un ordre bien fondé. Il se signifie ainsi : A ¤ B > <math>\Box</math> ou A ¤ B > C si A <math>\ge</math> C ou B <math>\ge</math> C.
- Sur l'ensemble des arbres binaires, on peut définir l'ordre bien fondé > suivant :
- A ¤ B > <math>\Box</math>,
- ou A ¤ B > C ¤ D parce que
- A > C et A ¤ B > D,
- ou A = C et B > D
- Dans le dernier ordre, l'arbre (<math>\Box</math> ¤ <math>\Box</math>) ¤ <math>\Box</math> a une infinité d'arbres plus petits que lui.
Théorie des ensembles
L'axiome de fondation affirme que la relation d'appartenance est bien fondée ; mais on peut avoir une théorie des ensembles équicohérente avec l'axiome d'anti-fondation.
Propriétés
La bonne fondation est préservée par Modèle:Lang, c'est-à-dire que pour toute application ρ : E → F et toute relation bien fondée S sur F, la relation T sur E définie par xTy ⇔ ρ(x)Sρ(y) est bien fondée.
Récurrence noethérienne ou bien fondée
On notera RModèle:-1[x] l'ensemble des R-antécédents de x.
Le théorème suivant (dans la théorie des ensembles de Zermelo) offre à la fois une troisième définition équivalente de la bonne fondation et une généralisation du principe de démonstration par induction transfinie (sur un bon ordre ou sur un ordinal), qui elle-même étend l'axiome de Peano Modèle:N° ou le principe de récurrence (correspondant à l'ordre usuel sur les entiers naturels) : Modèle:Théorème
Modèle:Démonstration/début Par passage au complémentaire, la condition de l'énoncé équivaut à l'implication
- pour toute partie X de E, si ∀ x ∈ E (RModèle:-1[x]∩X = ∅ ⇒ x ∉ X) alors X = ∅
ou encore, à sa contraposée :
- pour toute partie non vide X de E, ∃ x ∈ X (RModèle:-1[x]∩X = ∅),
qui exprime bien que pour toute partie non vide X de E, il existe un élément x de X n'ayant aucun R-antécédent dans X. Modèle:Démonstration/fin
De même, un second théorème (dans la théorie des ensembles de Zermelo-Fraenkel, donc avec remplacement) généralise le principe de définition par récurrence d'une suite et plus généralement, de définition d'une fonction par récursion transfinie :
Modèle:Démonstration/début Définissons le prédicat rec(h) par : h est une fonction, de domaine Dh ⊂ E, telle que pour tout z ∈ Dh, RModèle:-1[z] ⊂ Dh et h(z) = G(z, h|RModèle:-1[z]), puis le prédicat F(x, y) par : ∃h (rec(h) et h(x) = y).
Par induction bien fondée, la classe F est fonctionnelle (ce qui prouve déjà, par extensionnalité, que l'éventuelle fonction f annoncée dans le théorème est unique), or son domaine est inclus dans l'ensemble E donc (d'après le schéma d'axiomes de remplacement) il existe une fonction f telle que F(x, y) ⇔ f(x) = y. De plus, par construction, rec(f) est satisfait.
Enfin, Df = E, à nouveau par induction bien fondée : pour tout x ∈ E tel que RModèle:-1[x] ⊂ Df, l'ensemble de couples h := f∪{(x, G(x, f|RModèle:-1[x]))} satisfait rec(h) donc x ∈ Df. Modèle:Démonstration/fin
Ces deux théorèmes s'étendent aux classes<ref>Modèle:Ouvrage.</ref>,<ref>Modèle:Ouvrage.</ref>, comme leurs homologues dans le cas particulier de la récurrence transfinie. Plus précisément : on peut remplacer, dans ces deux énoncés, les ensembles E, R et f par des classes (relationnelle pour R et fonctionnelle pour f), sous réserve que pour tout ensemble x, la classe RModèle:-1[x] soit un ensemble (dans le cas de la récurrence transfinie, il est inutile d'ajouter cette hypothèse car ∈Modèle:-1[x] = x).
Fonction rang
Dans un ensemble E muni d'une relation bien fondée R, chaque élément x admet un rang ρ(x), qui est un nombre ordinal. La fonction rang est définie sur E par récursion bien fondée par :
- ρ(x) = ∪ { α + 1 | α ∈ [[Image d'une application|im(ρ|RModèle:-1[x])]] } = ∪ { ρ(y) + 1 | y R x }
(l'union d'un ensemble d'ordinaux est un ordinal). Ainsi, le rang de x est le plus petit ordinal strictement supérieur aux rangs des antécédents de x.
La longueur de la relation R, souvent notée |R|, est le plus petit ordinal contenant tous les ρ(x).
L'induction et la récursion bien fondées Modèle:Supra s'appliquent à R, mais il est parfois plus commode de les appliquer au [[#Exemples|Modèle:Lang]] par ρ de l'ordre strict sur l'ordinal |R|, c'est-à-dire à la relation T définie par : xTy ⇔ ρ(x) < ρ(y).
La fonction rang permet d'organiser de manière évidente E en une hiérarchie, très utilisée en théorie des ensembles avec pour R la relation d'appartenance (cf. « Rang d'un ensemble »).
Usage en algorithmique
Un cas particulier de la récurrence bien fondée est la récurrence structurelle. Un algorithme, lorsqu'il construit une suite d'éléments en assurant qu'un élément construit est strictement inférieur à son prédécesseur, assure aussi sa terminaison, dès que l'ordre strict est bien fondé.
Les structures utilisées en algorithmique (types construits) étant souvent des ordres stricts bien fondés, on dispose ainsi d'une méthode très générale pour prouver la terminaison d'un programme informatique.
