Relation antisymétrique

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

\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$ .

Portail des mathématiques