Antisymmetric relation

Anti- symmetric ie, a binary relation on a set, if for arbitrary elements and the amount at the same time with the reversal may not apply, unless, and are the same. Formulated thus equivalent for arbitrary elements and this set that out and always follows.

The anti-symmetry is one of the prerequisites for a partial order.

Formal definition

Is a set and a binary relation on, then called antisymmetric if and only if (using infix notation ):

Special case Asymmetric relation

Each asymmetric relation is also an antisymmetric relation. Since on for an asymmetric relation

Is the premise of the definition of the antisymmetric relation always wrong and after the logical principle ex falso quodlibet thus the statement met.

The asymmetry is one of the prerequisites for a ( irreflexive ) Strict order.

Examples

Anti Symmetrically, the relations and to the real numbers. It follows from and. The same is true for and.

The divisibility of natural numbers is antisymmetric, because then follows. The divisibility on the integers, however, is not anti- symmetric, because for example, and applies, though.

Asymmetric relations are the less-than relation on the real numbers and the subset relationship between sets. Compared to these relationships or lack the reflexivity.

Representation as a directed graph

Any relation on a set can be regarded as a directed graph (see example above). The nodes of the graph are the elements of. From node to node is a directed edge if and only pulled (an arrow ) if the following applies.

The anti-symmetry of the graph can now be characterized as follows: Whenever there is an arrow between different nodes and the graph, then it can not simultaneously give an arrow.

Loops do not need to be examined for this criterion.

Properties

• Using the converse relation can the anti-symmetry by the following condition characterize:

• Are the relations and anti-symmetric, then this also applies to their intersection. This statement can be generalized from two relations on the intersection of any ( non-empty ) family of antisymmetric relations.
• Every subset of an antisymmetric relation is antisymmetric again.