Relation asymétrique
![Page d’aide sur l’homonymie](http://upload.wikimedia.org/wikipedia/commons/thumb/a/a9/Logo_disambig.svg/20px-Logo_disambig.svg.png)
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 :
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 relations asymétriques.
Aucun des n couples n'appartient au graphe.
Pour les paires , il y a trois possibilités : soit seul appartient au graphe, soit seul , 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 .
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), (lire en ligne), p. 31.
- ↑ Michel Marchand, Mathématique discrète : outil pour l'informaticien, De Boeck, (lire en ligne), p. 271.
- ↑ Louis Frécon, Éléments de mathématiques discrètes, PPUR, (lire en ligne), p. 69.
- ↑ Nathalie Caspard, Bruno Leclerc et Bernard Monjardet, Ensembles ordonnés finis : concepts, résultats et usages, Springer, (lire en ligne), p. 3.
- ↑ Robert Faure, Bernard Lemaire et Christophe Picouleau, Précis de recherche opérationnelle, Dunod, , 7e é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, (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.
- ↑ 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).
- ↑ Jiří Matoušek et Jaroslav Nešetřil, Introduction aux mathématiques discrètes, Springer, (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 » (no 48), (lire en ligne), p. 56, 1.1 Lemma. (ii).
Portail des mathématiques