# Antisymmetric relation

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.