Relation bien fondée

Relation bien fondée

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 nœthé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 (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.

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.

Sommaire

Exemples

  • 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

Sans entrer dans les détails, une conséquence directe et quasi-triviale de la définition d'un ordre strict bien fondé est qu'un algorithme, qui construit une suite d'éléments d'un tel ordre tout en assurant qu'un élément construit est strictement inférieur à son prédécesseur, assure aussi sa terminaison (prouvé par l'absurde : en effet, dans le cas contraire on construirait une suite infinie strictement décroissante).

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

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


Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Relation bien fondée de Wikipédia en français (auteurs)

Игры ⚽ Поможем написать реферат

Regardez d'autres dictionnaires:

  • Relation bien fondee — Relation bien fondée En mathématiques, une relation bien fondée exprime un type de relation entre les éléments de deux ensembles. Soit E un ensemble non vide. On dit qu une relation R sur E est bien fondée ou plus rarement nœthérienne (alors que… …   Wikipédia en Français

  • Relation nœthérienne — Relation bien fondée En mathématiques, une relation bien fondée exprime un type de relation entre les éléments de deux ensembles. Soit E un ensemble non vide. On dit qu une relation R sur E est bien fondée ou plus rarement nœthérienne (alors que… …   Wikipédia en Français

  • Relation antisymétrique — Relation binaire Une relation binaire est un concept mathématique qui systématise des notions comme « ... est supérieur ou égal à ... » en arithmétique, ou « ... est élément de l’ensemble ... » en théorie des ensembles. C’est… …   Wikipédia en Français

  • Relation binaire — En mathématiques, une relation binaire entre deux ensembles E et F (ou simplement relation entre E et F) est caractérisée par un sous ensemble du produit cartésien E × F, soit une collection de couples dont la première composante est dans E et la …   Wikipédia en Français

  • RELATION — Le concept de relation apparaît comme l’un des concepts fondamentaux du discours rationnel. Il semble lié à la pratique de l’analyse, qui constitue elle même l’un des aspects essentiels de la démarche discursive. L’analyse décompose les unités… …   Encyclopédie Universelle

  • Ensemble bien ordonné — Un ensemble ordonné ( E, ≤ ) est bien ordonné et la relation ≤ est un bon ordre si la condition suivante est satisfaite : Toute partie non vide de E possède un plus petit élément. Si ( E, ≤ ) est bien ordonné alors ≤ est nécessairement un… …   Wikipédia en Français

  • Relation de Slutsky — La relation de Slutsky est un élément de la théorie du consommateur permettant de relier formellement la demande Marshallienne à la demande Hicksienne. Conceptuellement, elle permet de séparer la réponse de la demande à une variation du prix d un …   Wikipédia en Français

  • Relation d'amitié — Amitié Pour les articles homonymes, voir Ami (homonymie) …   Wikipédia en Français

  • Relation personnelle avec Dieu — Spiritualité La nébuleuse Hélix, parfois appelée Oeil de Dieu La spiritualité définit une aspiration personnelle ou collective, ou l ensemble des croyances, pratiques et études qui ont trait à la nature essentielle de l être vivant, à l âme, à ce …   Wikipédia en Français

  • Relation entre la Corée du Nord et la France — Relations entre la Corée du Nord et la France Cet article traite des relations franco nord coréennes. Au sein de l Union européenne, la France est le seul pays, avec l Estonie, à ne pas reconnaître la République populaire démocratique de Corée ou …   Wikipédia en Français

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”