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.

Web links

Wiktionary: antisymmetric  - explanations of meanings, word origins, synonyms, translations

Individual evidence

1. ↑ Ingmar Lehmann , Wolfgang Schulz: Sets - Relations - Functions. A clear introduction. 3rd, revised and expanded edition. Teubner, Wiesbaden 2007, ISBN 978-3-8351-0162-3 .