Relation bien fondée
Source: Wikipédia sous licence CC-BY-SA 3.0.
La liste des auteurs de cet article est disponible ici.

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 et seulement si elle vérifie l'une des deux conditions suivantes, équivalentes d'après l'axiome (Un axiome (du grec ancien αξιωμα/axioma, « considéré comme digne, convenable, évident en...) du choix dépendant (une version très faible de l'axiome du choix) :

  • Pour toute partie 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) ;
  • Il n'existe pas de suite infinie (xn) d'éléments de E telle qu'on ait xn+1Rxn pour tout (Le tout compris comme ensemble de ce qui existe est souvent interprété comme le monde ou l'univers.) n.

Exemples

  • Sur l'ensemble (En théorie des ensembles, un ensemble désigne intuitivement une collection d’objets (les éléments de l'ensemble), « une multitude qui peut être comprise...) des arbres binaires finis, construits à partir de l'arbre (Un arbre est une plante terrestre capable de se développer par elle-même en hauteur, en général au delà de sept mètres. Les arbres...) vide (Le vide est ordinairement défini comme l'absence de matière dans une zone spatiale.) \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 " et bien fondé.
  • Sur l'ensemble des chaînes de caractères, l'ordre du dictionnaire n'est pas bien fondé.
  • L'ordre strict associé à un bon ordre.
  • De manière générale une relation d'ordre total ( Total est la qualité de ce qui est complet, sans exception. D'un point de vue comptable, un total est le résultat d'une addition, c'est-à-dire une somme. Exemple : "Le total des dettes". En physique...) est un bon ordre si et seulement si la relation stricte associée est bien fondée.
  • L'axiome de fondation (L'axiome de fondation, encore appelé axiome de régularité, est l'un des axiomes de la théorie axiomatique des ensembles. Introduit en 1925 par John von Neumann, il joue un grand rôle dans cette théorie, alors que les...) exprime que la relation d'appartenance est bien fondée.
  • 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

On notera que dans le dernier ordre, l'arbre (\Box ¤ \Box) ¤ \Box a une infinité d'arbres plus petit que lui.

Usage (L’usage est l'action de se servir de quelque chose.) en algorithmique (L'algorithmique est l’ensemble des règles et des techniques qui sont impliquées dans la définition et la conception d'algorithmes, c'est à dire de processus systématiques de résolution, par le...)

Sans entrer dans les détails, une conséquence directe et quasi-triviale de la définition (Une définition est un discours qui dit ce qu'est une chose ou ce que signifie un nom. D'où la division entre les définitions réelles et les définitions nominales.) 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 (Un programme informatique est une liste d'ordres indiquant à un ordinateur ce qu'il doit faire. Il se présente sous la forme d'une ou plusieurs séquences d'instructions, comportant souvent des données de base,...).

Relation bien fondée (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...) et récurrence

À une relation bien fondée est associée une fonction de rang ( Mathématiques En algèbre linéaire, le rang d'une famille de vecteurs est la dimension du sous-espace vectoriel engendré par cette famille. Le théorème du...) construite par récurrence transfinie, ce qui permet des démonstrations par récurrence transfinie. Voyons cela de plus près.

Soient R une relation bien fondée sur un ensemble E et J un ensemble bien ordonné, de cardinal supérieur à celui de E, nous servant de " réservoir d'ordinaux " (ses premiers éléments sont 0,1,...). La fonction de rang ρ de R est l'application de E dans J définie par récurrence transfinie comme suit : pour xE

  • ρ(x) = 0 si x n'a pas d'antécédent pour R ;
  • ρ(x) = sup { ρ(y)+1, y antécédent de x pour R } dans le cas général.

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 (Dans les sciences du vivant, l’espèce (du latin species, « type » ou « apparence ») est le taxon de base de la...). La longueur (La longueur d’un objet est la distance entre ses deux extrémités les plus éloignées. Lorsque l’objet est filiforme ou en forme de lacet, sa longueur est celle de l’objet complètement...) 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 axiomatique des ensembles (Il existe plusieurs versions formelles de la théorie des ensembles, mais quand on parle de « la » théorie axiomatique des ensembles, on désigne habituellement sous ce nom la théorie ZFC. Au XXIe siècle, c'est...) 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 (Un théorème est une proposition qui peut être mathématiquement démontrée, c'est-à-dire une assertion qui peut être établie comme vraie au travers d'un raisonnement logique construit à partir d'axiomes. Un théorème est à...) 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 (En mathématiques, l'ensemble vide est l'ensemble ne contenant aucun élément.), 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.

Page générée en 0.066 seconde(s) - site hébergé chez Amen
Ce site fait l'objet d'une déclaration à la CNIL sous le numéro de dossier 1037632
Ce site est édité par Techno-Science.net - A propos - Informations légales
Partenaire: HD-Numérique