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)

$\forall x,y\in E\,(\,xRy\land yRx)\Rightarrow x=y\,\,(1)$

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 :

$R\cap R^{-1}\subset \Delta _{X}$.

La condition (1) peut aussi s'écrire $\forall x\not =y\in E\,\,(xRy)\Rightarrow y\not Rx\,\,(2)$

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

• 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 $y=x+1$ 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

Le nombre de relations antisymétriques dans un ensemble à $n$ éléments est égal à $2^{n}3^{\frac {n(n-1)}{2}}$, voir la suite A083667 de l'OEIS.

Démonstration

Il y a deux possibilités pour n les couples $(x,x)$ : soit appartenir au graphe soit ne pas y appartenir.

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

Le nombre de relations antisymétriques et réflexives est $3^{\frac {n(n-1)}{2}}$, voir la suite A047656 de l'OEIS.

Propriété

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

Démonstration :

On doit montrer  : $(P)\Rightarrow (Q)$, où $(P):{\begin{cases}\forall (x,y)\in E^{2},((xRy)\land (yRx))\Rightarrow x=y\\\forall (x,y)\in E^{2},((xSy)\land (ySx))\Rightarrow x=y\end{cases}}$ et $(Q):(x(R\cap S)y\land y(R\cap S)x)\Rightarrow x=y$.

Preuve directe :

Considérons un couple $(x,y)$ de E x E tel que : $x(R\cap S)y\land y(R\cap S)x$. Il vient de $x(R\cap S)y$ que $xRy$ et de $y(R\cap S)x$ que $yRx$ . Par antisymétrie de R, on obtient : $x=y$.