Antisymmetric relation

In mathematics, a binary relation R on a set X is anti-symmetric if there is no pair of distinct elements of X each of which is related by R to the other. More formally, R is anti-symmetric precisely if for all a and b in X

if R(a, b) with a ≠ b, then R(b, a) must not hold,

or, equivalently,

if R(a, b) and R(b, a), then a = b.

(The definition of anti-symmetry says nothing about whether R(a, a) actually holds or not for any a.)

The divisibility relation on the natural numbers is an important example of an anti-symmetric relation. In this context, anti-symmetry means that the only way each of two numbers can be divisible by the other is if the two are, in fact, the same number; equivalently, if n and m are distinct and n is a factor of m, then m cannot be a factor of n. For example, 12 is divisible by 4, but 4 is not divisible by 12.

The usual order relation ≤ on the real numbers is anti-symmetric: if for two real numbers x and y both inequalities x ≤ y and y ≤ x hold then x and y must be equal. Similarly, the subset order ⊆ on the subsets of any given set is anti-symmetric: given two sets A and B, if every element in A also is in B and every element in B is also in A, then A and B must contain all the same elements and therefore be equal:

$A\subseteq B\land B\subseteq A\Rightarrow A=B$

Partial and total orders are anti-symmetric by definition. A relation can be both symmetric and anti-symmetric (e.g., the equality relation), and there are relations which are neither symmetric nor anti-symmetric (e.g., the "preys on" relation on biological species).

Anti-symmetry is different from asymmetry, which requires both anti-symmetry and irreflexivity. Thus, every asymmetric relation is anti-symmetric, but the reverse is false.

See also

• Symmetric relation
• Asymmetric relation
• Symmetry in mathematics

References

• Weisstein, Eric W. "Antisymmetric Relation". MathWorld.
• Lipschutz, Seymour; Marc Lars Lipson (1997). Theory and Problems of Discrete Mathematics. McGraw-Hill. p. 33. ISBN 0-07-038045-7.