Relation bien fondée

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

En mathématiques, une relation bien fondée est une relation binaire vérifiant la propriété supplémentaire suivante.

Soit E un ensemble non vide. On dit qu'une relation R sur E est bien fondée ou plus rarement noethérienne (alors que l'on devrait dire en toute rigueur artinienne ce qui se dit plus rarement encore) si elle vérifie l'une des deux conditions suivantes, équivalentes d'après l'axiome du choix dépendant (en) (une version très faible de l'axiome du choix) :

  • pour toute partie X de E non vide, 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) ;
  • il n'existe pas de suite infinie (xn) d'éléments de E telle qu'on ait xn+1Rxn pour tout n ;
  • pour qu'une partie non vide de E soit égale à E tout entier, il suffit qu'elle contienne chaque élément dont elle contient tous les R-antécédents (récurrence bien fondée).

Toute relation bien fondée est antiréflexive et antisymétrique. Une relation est bien fondée si et seulement si sa clôture transitive l'est.

Un ordre bien fondé est une relation d'ordre dont l'ordre strict associé est une relation bien fondée.

Exemples[modifier | modifier le code]

  • Sur l'ensemble des arbres binaires finis, construits à partir de l'arbre vide \Box 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 > \Box ou A ¤ B > C si A \ge C ou B \ge C.
  • 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é.
  • L'ordre strict associé à un bon ordre.
  • De manière générale une relation d'ordre total est un bon ordre si et seulement si la relation stricte associée est bien fondée.
  • 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'antifondation.
  • Sur l'ensemble des arbres binaires, on peut définir l'ordre bien fondé > suivant :
    • A ¤ B > \Box,
    • 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 (\Box ¤ \Box) ¤ \Box a une infinité d'arbres plus petits que lui.

Usage en algorithmique[modifier | modifier le code]

Une conséquence directe de la définition d'ordre strict bien fondé est qu'un algorithme, qui 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.

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.

Relation bien fondée et récurrence[modifier | modifier le code]

Dans un ensemble muni d'une relation bien fondée, chaque élément admet un rang construit par induction transfinie ; ce rang permet des démonstrations par récurrence transfinie. Voyons cela de plus près.

Soit R une relation bien fondée sur un ensemble E. Le rang ρ(x) d'un élément xE est le nombre ordinal défini comme suit :

  • ρ(x) = 0 si x n'a pas d'antécédent pour R ;
  • ρ(x) = ∪ { ρ(y)+1, y antécédent de x pour R } dans le cas général (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 ; il peut être de première ou deuxième espèce. La longueur de la relation R, souvent notée |R|, est le plus petit ordinal strictement plus grand que tous les ρ(x). La fonction de rang permet d'organiser E en une hiérarchie de manière évidente, très utilisée en théorie des ensembles avec pour R la relation d'appartenance.

La fonction de rang permet de faire des démonstrations par récurrence transfinie à l'aide du théorème suivant qui généralise l'axiome de Peano n°5 ou le principe de récurrence :

Soit P une partie de E contenant, pour tout j, tous les x∈E de rang j dès qu'il contient tous les x de rang < j. Alors P est l'ensemble E tout entier.

Grâce à l'ensemble vide, ensemble des x de rang <0, on n'a pas eu besoin de démarrer la récurrence explicitement. Attention ! Il ne suffit pas ici de passer du rang j au rang j+1 à cause de l'existence d'ordinaux de deuxième espèce.

Voir aussi[modifier | modifier le code]