Antisymmetric relation

Binary relation such that if A is related to B and is different from it then B is not related to A
Transitive binary relations
  • v
  • t
  • e
Symmetric Antisymmetric Connected Well-founded Has joins Has meets Reflexive Irreflexive Asymmetric
Total, Semiconnex Anti-
reflexive
Equivalence relation Green tickY ✗ ✗ ✗ ✗ ✗ Green tickY ✗ ✗
Preorder (Quasiorder) ✗ ✗ ✗ ✗ ✗ ✗ Green tickY ✗ ✗
Partial order ✗ Green tickY ✗ ✗ ✗ ✗ Green tickY ✗ ✗
Total preorder ✗ ✗ Green tickY ✗ ✗ ✗ Green tickY ✗ ✗
Total order ✗ Green tickY Green tickY ✗ ✗ ✗ Green tickY ✗ ✗
Prewellordering ✗ ✗ Green tickY Green tickY ✗ ✗ Green tickY ✗ ✗
Well-quasi-ordering ✗ ✗ ✗ Green tickY ✗ ✗ Green tickY ✗ ✗
Well-ordering ✗ Green tickY Green tickY Green tickY ✗ ✗ Green tickY ✗ ✗
Lattice ✗ Green tickY ✗ ✗ Green tickY Green tickY Green tickY ✗ ✗
Join-semilattice ✗ Green tickY ✗ ✗ Green tickY ✗ Green tickY ✗ ✗
Meet-semilattice ✗ Green tickY ✗ ✗ ✗ Green tickY Green tickY ✗ ✗
Strict partial order ✗ Green tickY ✗ ✗ ✗ ✗ ✗ Green tickY Green tickY
Strict weak order ✗ Green tickY ✗ ✗ ✗ ✗ ✗ Green tickY Green tickY
Strict total order ✗ Green tickY Green tickY ✗ ✗ ✗ ✗ Green tickY Green tickY
Symmetric Antisymmetric Connected Well-founded Has joins Has meets Reflexive Irreflexive Asymmetric
Definitions, for all a , b {\displaystyle a,b} and S ≠ ∅ : {\displaystyle S\neq \varnothing :} a R b ⇒ b R a {\displaystyle {\begin{aligned}&aRb\\\Rightarrow {}&bRa\end{aligned}}} a R b  and  b R a ⇒ a = b {\displaystyle {\begin{aligned}aRb{\text{ and }}&bRa\\\Rightarrow a={}&b\end{aligned}}} a ≠ b ⇒ a R b  or  b R a {\displaystyle {\begin{aligned}a\neq {}&b\Rightarrow \\aRb{\text{ or }}&bRa\end{aligned}}} min S exists {\displaystyle {\begin{aligned}\min S\\{\text{exists}}\end{aligned}}} a ∨ b exists {\displaystyle {\begin{aligned}a\vee b\\{\text{exists}}\end{aligned}}} a ∧ b exists {\displaystyle {\begin{aligned}a\wedge b\\{\text{exists}}\end{aligned}}} a R a {\displaystyle aRa} not  a R a {\displaystyle {\text{not }}aRa} a R b ⇒ not  b R a {\displaystyle {\begin{aligned}aRb\Rightarrow \\{\text{not }}bRa\end{aligned}}}
Green tickY indicates that the column's property is always true the row's term (at the very left), while ✗ indicates that the property is not guaranteed in general (it might, or might not, hold). For example, that every equivalence relation is symmetric, but not necessarily antisymmetric, is indicated by Green tickY in the "Symmetric" column and ✗ in the "Antisymmetric" column, respectively.

All definitions tacitly require the homogeneous relation R {\displaystyle R} be transitive: for all a , b , c , {\displaystyle a,b,c,} if a R b {\displaystyle aRb} and b R c {\displaystyle bRc} then a R c . {\displaystyle aRc.}
A term's definition may require additional properties that are not listed in this table.

In mathematics, a binary relation R {\displaystyle R} on a set X {\displaystyle X} is antisymmetric if there is no pair of distinct elements of X {\displaystyle X} each of which is related by R {\displaystyle R} to the other. More formally, R {\displaystyle R} is antisymmetric precisely if for all a , b ∈ X , {\displaystyle a,b\in X,}

if  a R b  with  a ≠ b  then  b R a  must not hold , {\displaystyle {\text{if }}\,aRb\,{\text{ with }}\,a\neq b\,{\text{ then }}\,bRa\,{\text{ must not hold}},}
or equivalently,
if  a R b  and  b R a  then  a = b . {\displaystyle {\text{if }}\,aRb\,{\text{ and }}\,bRa\,{\text{ then }}\,a=b.}
The definition of antisymmetry says nothing about whether a R a {\displaystyle aRa} actually holds or not for any a {\displaystyle a} . An antisymmetric relation R {\displaystyle R} on a set X {\displaystyle X} may be reflexive (that is, a R a {\displaystyle aRa} for all a ∈ X {\displaystyle a\in X} ), irreflexive (that is, a R a {\displaystyle aRa} for no a ∈ X {\displaystyle a\in X} ), or neither reflexive nor irreflexive. A relation is asymmetric if and only if it is both antisymmetric and irreflexive.

Examples

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 n {\displaystyle n} and m {\displaystyle m} are distinct and n {\displaystyle n} is a factor of m , {\displaystyle m,} then m {\displaystyle m} cannot be a factor of n . {\displaystyle n.} For example, 12 is divisible by 4, but 4 is not divisible by 12.

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

A ⊆ B  and  B ⊆ A  implies  A = B {\displaystyle A\subseteq B{\text{ and }}B\subseteq A{\text{ implies }}A=B}
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

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

References