Relation asymétrique

Page d’aide sur l’homonymie

Pour les articles homonymes, voir Relation et Asymétrique.

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

x R y ⇒ ( y R x ) , {\displaystyle xRy\Rightarrow (y{\cancel {R}}x),}

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].

Exemples

  • 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

  • Dans un ensemble à n éléments, il existe 3 n ( n − 1 ) 2 {\displaystyle 3^{\frac {n(n-1)}{2}}} relations asymétriques.
Démonstration

Aucun des n couples ( x , x ) {\displaystyle (x,x)} n'appartient au graphe.

Pour les n ( n − 1 ) 2 {\displaystyle {\frac {n(n-1)}{2}}} paires { x , y } {\displaystyle \{x,y\}} , il y a trois possibilités : soit seul ( x , y ) {\displaystyle (x,y)} appartient au graphe, soit seul ( y , x ) {\displaystyle (y,x)} , soit aucun des deux (ils ne peuvent y appartenir tous les deux).

  • 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 n ! {\displaystyle n!} .

Notes et références

  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).
  • icône décorative Portail des mathématiques