Aller au contenu

Relation asymétrique

Un article de Wikipédia, l'encyclopédie libre.

En mathématiques, une relation (binaire, interne) R est dite asymétrique[1],[2],[3],[4],[5],[6] si elle vérifie :

ou encore, si son graphe est disjoint de celui de sa relation réciproque.

L'asymétrie est parfois appelée « antisymétrie forte[7] », par opposition à l'antisymétrie (usuelle, ou « faible »)[8]. En effet, une relation est asymétrique si et seulement si elle est à la fois antisymétrique et antiréflexive[9].

  • les relations d'ordre strict, qui sont les relations transitives et asymétriques ;
  • dans les entiers, la relation "est le successeur de" ;
  • dans un ensemble de personnes, la relation « est enfant de »  : personne n'est enfant d'un de ses enfants.

Une relation ne peut pas être à la fois symétrique et asymétrique, sauf si son graphe est vide.

Dénombrements

[modifier | modifier le code]
  • Dans un ensemble à n éléments, il existe relations asymétriques.
  • Les relations d'ordre strict, qui sont en bijection avec les relations d'ordre, ne possèdent pas de formule de dénombrement "fermée" ; voir la suite A001035 de l'OEIS.
  • Les relations d'ordre strict total sont en nombre .

Notes et références

[modifier | modifier le code]
  1. Louis Couturat, Les principes des mathématiques, avec un appendice sur la philosophie des mathématiques de Kant, Georg Olms Verlag (de), (lire en ligne), p. 31.
  2. Michel Marchand, Mathématique discrète : outil pour l'informaticien, De Boeck, (lire en ligne), p. 271.
  3. Louis Frécon, Éléments de mathématiques discrètes, PPUR, (lire en ligne), p. 69.
  4. Nathalie Caspard, Bruno Leclerc et Bernard Monjardet, Ensembles ordonnés finis : concepts, résultats et usages, Springer, (lire en ligne), p. 3.
  5. Robert Faure, Bernard Lemaire et Christophe Picouleau, Précis de recherche opérationnelle, Dunod, , 7e éd. (lire en ligne), p. 2, 3 et 5.
  6. En anglais : asymmetric(en) David Gries et Fred B. Schneider, A Logical Approach to Discrete Math, Springer, (lire en ligne), p. 273 ; (en) Yves Nievergelt, Foundations of Logic and Mathematics : Applications to Computer Science and Cryptography, Springer, (lire en ligne), p. 158. En allemand : asymmetrisch(de) Ingmar Lehmann et Wolfgang Schulz, Mengen - Relationen : Funktionen, Springer, (lire en ligne), p. 56.
  7. Ou « stricte » : « Strictly (or sharply) antisymmetric » dans (en) V. Flaška, J. Ježek, T. Kepka et J. Kortelainen, « Transitive Closures of Binary Relations I », Acta Univ. Carolin. Math. Phys., vol. 48, no 1,‎ , p. 55-69 (lire en ligne).
  8. Jiří Matoušek et Jaroslav Nešetřil, Introduction aux mathématiques discrètes, Springer, (lire en ligne), p. 44.
  9. (en) Václav Flaška et al., Transitive closures of binary relations. I., coll. « Acta Universitatis Carolinae. Mathematica et Physica » (no 48), (lire en ligne), p. 56, 1.1 Lemma. (ii).