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.
Flaška et al. 2007, lemme 1.1 (ii).

Cet article est issu de wikipedia. Text licence: CC BY-SA 4.0, Des conditions supplémentaires peuvent s’appliquer aux fichiers multimédias.