Relation antisymétrique

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

En mathématiques, une relation (binaire, interne) Modèle:Math sur un ensemble Modèle:Math est dite antisymétrique si elle vérifie :

$\mathrm{\forall }x,y\in E(xRy\wedge 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 Modèle:Math, autrement dit :

$R\cap R^{-1}\subset {\mathrm{\Delta }}_X$.

La condition (1) peut aussi s'écrire $\mathrm{\forall }x=y\in E(xRy)\Rightarrow yRx(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 Modèle:OEIS. Modèle:Démonstration/début 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). Modèle:Démonstration/finLe nombre de relations antisymétriques et réflexives est $3^{\frac{n(n-1)}{2}}$, voir la Modèle:OEIS.

Propriété

L'intersection $R\cap S$ de deux relations antisymétriques Modèle:Math et Modèle:Math dans un ensemble Modèle:Math est également antisymétrique.

Démonstration :

On doit montrer  : $(P)\Rightarrow (Q)$, où $(P):\{\begin{array}{c}\mathrm{\forall }(x,y)\in E^2,((xRy)\wedge (yRx))\Rightarrow x=y\\ \mathrm{\forall }(x,y)\in E^2,((xSy)\wedge (ySx))\Rightarrow x=y\end{array}$ et $(Q):(x(R\cap S)y\wedge 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\wedge 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 Modèle:Math, on obtient : $x=y$.Modèle:Portail