Antisymmetric relation

In mathematics, a binary relation on a set is antisymmetric if there is no pair of distinct elements of each of which is related by to the other. More formally, is antisymmetric precisely if for all

or equivalently,
The definition of antisymmetry says nothing about whether actually holds or not for any . An antisymmetric relation on a set may be reflexive (that is, for all ), irreflexive (that is, for no ), or neither reflexive nor irreflexive. A relation is asymmetric if and only if it is both antisymmetric and irreflexive.

Examples edit

The divisibility relation on the natural numbers is an important example of an antisymmetric relation. In this context, antisymmetry 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   and   are distinct and   is a factor of   then   cannot be a factor of   For example, 12 is divisible by 4, but 4 is not divisible by 12.

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

A real-life example of a relation that is typically antisymmetric is "paid the restaurant bill of" (understood as restricted to a given occasion). Typically, some people pay their own bills, while others pay for their spouses or friends. As long as no two people pay each other's bills, the relation is antisymmetric.

Properties edit

Symmetric and antisymmetric relations

Partial and total orders are antisymmetric by definition. A relation can be both symmetric and antisymmetric (in this case, it must be coreflexive), and there are relations which are neither symmetric nor antisymmetric (for example, the "preys on" relation on biological species).

Antisymmetry is different from asymmetry: a relation is asymmetric if and only if it is antisymmetric and irreflexive.

See also edit

References edit

  • 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.
  • nLab antisymmetric relation