# Antisymmetric relation

An anti-symmetric relation, as directed graph shown
A non- anti-symmetric relation, as directed graph shown

A two-digit relation on a set is called antisymmetric if the inversion can not hold for any elements and the set with , unless and are equal. In an equivalent form, it applies to any elements and this set that it follows from and always . ${\ displaystyle R}$ ${\ displaystyle x}$${\ displaystyle y}$${\ displaystyle xRy}$${\ displaystyle yRx}$${\ displaystyle x}$${\ displaystyle y}$${\ displaystyle x}$${\ displaystyle y}$${\ displaystyle xRy}$${\ displaystyle yRx}$${\ displaystyle x = y}$

Antisymmetry is one of the prerequisites for a partial order .

## definition

If there is a set and a two-digit relation , then it is called antisymmetric if (using the infix notation ) applies: ${\ displaystyle M}$${\ displaystyle R \ subseteq M \ times M}$${\ displaystyle M}$${\ displaystyle R}$

${\ displaystyle \ forall x, y \ in M: xRy \ land yRx \ Rightarrow x = y}$

## Special case asymmetrical relation

Every asymmetrical relation is also an antisymmetrical relation. Since for an asymmetrical relation to${\ displaystyle R}$${\ displaystyle M}$

${\ displaystyle \ forall x, y \ in M: xRy \ Rightarrow \ neg (yRx)}$holds, i.e. the inverse does not hold for any of the ordered pairs ,${\ displaystyle (x, y)}$

the premise of the definition of the antisymmetric relation is always wrong and according to the logical principle Ex falso quodlibet the statement is fulfilled. ${\ displaystyle xRy \ land yRx}$${\ displaystyle \ forall x, y \ in M: xRy \ land yRx \ Rightarrow x = y}$

Asymmetry is one of the prerequisites for an (irreflexive) strict order .

## Examples

The relations and on the real numbers are antisymmetric . Out and follows . The same goes for and . ${\ displaystyle \ leq}$${\ displaystyle \ geq}$${\ displaystyle x \ leq y}$${\ displaystyle y \ leq x}$${\ displaystyle x = y}$${\ displaystyle x \ geq y}$${\ displaystyle y \ geq x}$

The divisibility relation for natural numbers is also antisymmetric, because from and follows . The divisibility on the whole numbers , however, is not antisymmetric because, for example, and is true although . ${\ displaystyle \ mid}$${\ displaystyle a \ mid b}$${\ displaystyle b \ mid a}$${\ displaystyle a = b}$${\ displaystyle 3 \ mid -3}$${\ displaystyle -3 \ mid 3}$${\ displaystyle -3 \ neq 3}$

Asymmetric relations are the smaller relation on the real numbers and the subset relation between sets. Compared to or lacking in these relationships, reflexivity . ${\ displaystyle <}$ ${\ displaystyle \ subset}$${\ displaystyle \ leq}$${\ displaystyle \ subseteq}$

## Representation as a directed graph

Any relation on a set can be interpreted as a directed graph (see example above). The nodes of the graph are the elements of . A directed edge (an arrow ) is drawn from node to node if and only if applies. ${\ displaystyle R}$${\ displaystyle M}$${\ displaystyle M}$${\ displaystyle a}$${\ displaystyle b}$${\ displaystyle a \ longrightarrow b}$${\ displaystyle a \, R \, b}$

The antisymmetry of can now be characterized in the graph as follows: Whenever there is an arrow between different nodes and the graph, then there cannot be an arrow at the same time . Loops therefore do not need to be examined for this criterion. ${\ displaystyle R}$${\ displaystyle a \ longrightarrow b}$${\ displaystyle a}$${\ displaystyle b}$${\ displaystyle b \ longrightarrow a}$ ${\ displaystyle {\ stackrel {a} {\ circlearrowright}}}$

## properties

• With the help of the converse relation , the antisymmetry can also be characterized by the following condition: ${\ displaystyle R ^ {- 1}}$
${\ displaystyle R \ cap R ^ {- 1} \ subseteq \ mathrm {Id} _ {M}}$
Here the identical relation on the basic set denotes the set of all pairs .${\ displaystyle \ mathrm {Id} _ {M}}$${\ displaystyle M}$${\ displaystyle (x, x)}$
• If the relations and are antisymmetric, then this also applies to their intersection . This statement can be generalized from two relations to the intersection of any (non-empty) family of antisymmetric relations.${\ displaystyle R}$${\ displaystyle S}$ ${\ displaystyle R \ cap S}$${\ displaystyle \ cap _ {i \ in I} R_ {i}}$
• Every subset of an antisymmetric relation is again antisymmetric.