Relation asymétrique

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

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^{\frac {n(n-1)}{2}}$ relations asymétriques.

Démonstration

Aucun des n couples $(x,x)$ n'appartient au graphe.

Pour les ${\frac {n(n-1)}{2}}$ paires $\{x,y\}$ , il y a trois possibilités : soit seul $(x,y)$ appartient au graphe, soit seul $(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!$ .

Notes et références

↑ Louis Couturat, Les principes des mathématiques, avec un appendice sur la philosophie des mathématiques de Kant, Georg Olms Verlag (de), 1965 (lire en ligne), p. 31.
↑ Michel Marchand, Mathématique discrète : outil pour l'informaticien, De Boeck, 1989 (lire en ligne), p. 271.
↑ Louis Frécon, Éléments de mathématiques discrètes, PPUR, 2002 (lire en ligne), p. 69.
↑ Nathalie Caspard, Bruno Leclerc et Bernard Monjardet, Ensembles ordonnés finis : concepts, résultats et usages, Springer, 2007 (lire en ligne), p. 3.
↑ Robert Faure, Bernard Lemaire et Christophe Picouleau, Précis de recherche opérationnelle, Dunod, 2014, 7^e éd. (lire en ligne), p. 2, 3 et 5.
↑ En anglais : asymmetric — (en) David Gries et Fred B. Schneider, A Logical Approach to Discrete Math, Springer, 1993 (lire en ligne), p. 273 ; (en) Yves Nievergelt, Foundations of Logic and Mathematics : Applications to Computer Science and Cryptography, Springer, 2002 (lire en ligne), p. 158. En allemand : asymmetrisch — (de) Ingmar Lehmann et Wolfgang Schulz, Mengen - Relationen : Funktionen, Springer, 2013 (lire en ligne), p. 56.
↑ 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, n^o 1,‎ 2007, p. 55-69 (lire en ligne).
↑ Jiří Matoušek et Jaroslav Nešetřil, Introduction aux mathématiques discrètes, Springer, 2004 (lire en ligne), p. 44.
↑ (en) Václav Flaška et al., Transitive closures of binary relations. I., coll. « Acta Universitatis Carolinae. Mathematica et Physica » (n^o 48), 2007 (lire en ligne), p. 56, 1.1 Lemma. (ii).

Portail des mathématiques

[1] Louis Couturat, Les principes des mathématiques, avec un appendice sur la philosophie des mathématiques de Kant, Georg Olms Verlag (de), 1965 (lire en ligne), p. 31.

[2] Michel Marchand, Mathématique discrète : outil pour l'informaticien, De Boeck, 1989 (lire en ligne), p. 271.

[3] Louis Frécon, Éléments de mathématiques discrètes, PPUR, 2002 (lire en ligne), p. 69.

[4] Nathalie Caspard, Bruno Leclerc et Bernard Monjardet, Ensembles ordonnés finis : concepts, résultats et usages, Springer, 2007 (lire en ligne), p. 3.

[5] Robert Faure, Bernard Lemaire et Christophe Picouleau, Précis de recherche opérationnelle, Dunod, 2014, 7^e é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, 1993 (lire en ligne), p. 273 ; (en) Yves Nievergelt, Foundations of Logic and Mathematics : Applications to Computer Science and Cryptography, Springer, 2002 (lire en ligne), p. 158. En allemand : asymmetrisch — (de) Ingmar Lehmann et Wolfgang Schulz, Mengen - Relationen : Funktionen, Springer, 2013 (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, n^o 1,‎ 2007, p. 55-69 (lire en ligne).

[8] Jiří Matoušek et Jaroslav Nešetřil, Introduction aux mathématiques discrètes, Springer, 2004 (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 » (n^o 48), 2007 (lire en ligne), p. 56, 1.1 Lemma. (ii).

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]