Relation antisymétrique

Page d’aide sur l’homonymie

Pour les articles homonymes, voir Relation et Antisymétrie.

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

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

∀ x , y ∈ E ( x R y ∧ y R x ) ⇒ x = y ( 1 ) {\displaystyle \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 ∩ R − 1 ⊂ Δ X {\displaystyle R\cap R^{-1}\subset \Delta _{X}} .

La condition (1) peut aussi s'écrire ∀ x ≠ y ∈ E ( x R y ) ⇒ y R̸ x ( 2 ) {\displaystyle \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 {\displaystyle 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 {\displaystyle n} éléments est égal à 2 n 3 n ( n − 1 ) 2 {\displaystyle 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 ) {\displaystyle (x,x)}  : soit appartenir au graphe soit ne pas y appartenir.

Pour les n ( n − 1 ) 2 {\displaystyle {\frac {n(n-1)}{2}}} paires { x , y } {\displaystyle \{x,y\}} , il y a trois possibilités : soit seul ( x , y ) {\displaystyle (x,y)} appartient au graphe, soit seul ( y , x ) {\displaystyle (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 n ( n − 1 ) 2 {\displaystyle 3^{\frac {n(n-1)}{2}}} , voir la suite A047656 de l'OEIS.

Propriété

L'intersection R ∩ S {\displaystyle 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 ) ⇒ ( Q ) {\displaystyle (P)\Rightarrow (Q)} , où ( P ) : { ∀ ( x , y ) ∈ E 2 , ( ( x R y ) ∧ ( y R x ) ) ⇒ x = y ∀ ( x , y ) ∈ E 2 , ( ( x S y ) ∧ ( y S x ) ) ⇒ x = y {\displaystyle (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 ∩ S ) y ∧ y ( R ∩ S ) x ) ⇒ x = y {\displaystyle (Q):(x(R\cap S)y\land y(R\cap S)x)\Rightarrow x=y} .

Preuve directe :

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

  • icône décorative Portail des mathématiques