Antisymmetric relation

From Wikipedia, the free encyclopedia

Jump to: navigation, search

In mathematics, a binary relation R on a set X is antisymmetric if, for all a and b in X

if aRb and bRa, then a = b,

or, equivalently,

if aRb with a ≠ b, then bRa must not hold.

In mathematical notation, this is:

$\forall a, b \in X,\ a R b \and b R a \; \Rightarrow \; a = b$

or equally,

$\forall a, b \in X,\ a R b \and a \ne b \Rightarrow \lnot ( b R a ) .$

Partial and total orders are antisymmetric by definition. Therefore the usual order relation ≤ on the real numbers, the subset order ⊆ on the subsets of any given set and the divisibility order of the integers are antisymmetric. For example, if for two real numbers x and y both inequalities x ≤ y and y ≤ x hold then x and y must be equal.

A relation can be both symmetric and antisymmetric (e.g., the equality relation), and there are relations which are neither symmetric nor antisymmetric (e.g., the preys-on relation on biological species).

Antisymmetry is different from asymmetry. According to one definition of asymmetric, anything that fails to be symmetric is asymmetric. Another definition of asymmetric makes asymmetry equivalent to antisymmetry plus irreflexivity.