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 .
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:
Special case asymmetrical relation
Every asymmetrical relation is also an antisymmetrical relation. Since for an asymmetrical relation to
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.
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 .
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 .
Asymmetric relations are the smaller relation on the real numbers and the subset relation between sets. Compared to or lacking in these relationships, reflexivity .
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.
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.
properties
- With the help of the converse relation , the antisymmetry can also be characterized by the following condition:
- Here the identical relation on the basic set denotes the set of all pairs .
- 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.
- Every subset of an antisymmetric relation is again antisymmetric.
Web links
Individual evidence
- ↑ Ingmar Lehmann , Wolfgang Schulz: Sets - Relations - Functions. A clear introduction. 3rd, revised and expanded edition. Teubner, Wiesbaden 2007, ISBN 978-3-8351-0162-3 .