Relation antisymétrique

En mathématiques, une relation (binaire, interne) R sur un ensemble E est dite antisymétrique si elle vérifie :

Diagramme sagittal d'une relation antisymétrique (mais ni réflexive, ni transitive)

ce qui signifie que l'intersection de son graphe avec celui de sa relation réciproque est incluse dans la diagonale de E, autrement dit :

.

La condition (1) peut aussi s'écrire

On remarque l'antisymétrie d'une relation sur son diagramme sagittal par le fait qu'il n'y a pas de double flèche (donc que des sens uniques).

L'antisymétrie est parfois appelée « antisymétrie faible », par opposition à l'« antisymétrie forte » qu'est l'asymétrie (une relation asymétrique est une relation antisymétrique et antiréflexive).

Exemples

modifier
  • Les relations d'ordre, qui sont les préordres antisymétriques.
  • Sont antisymétriques sans être des relations d'ordre :
    • La relation vide
    • La relation définie par   dans les entiers (lien verbal : "être le successeur de")
    • la relation de lien verbal "être l'enfant de ".
    • La relation sur les entiers naturels " être un diviseur premier de".
  • Une relation est à la fois symétrique et antisymétrique si et seulement si son graphe est inclus dans la diagonale (le graphe de l'égalité).

Dénombrements

modifier

Le nombre de relations antisymétriques dans un ensemble à   éléments est égal à  , voir la suite A083667 de l'OEIS.

Le nombre de relations antisymétriques et réflexives est  , voir la suite A047656 de l'OEIS.

Propriété

modifier

L'intersection   de deux relations antisymétriques R et S dans un ensemble E est également antisymétrique.

Démonstration :

On doit montrer  :  , où   et  .

Preuve directe :

Considérons un couple   de E x E tel que :  . Il vient de   que   et de   que   . Par antisymétrie de R, on obtient :  .