Antisymmetric relation

Transitive binary relations

	Symmetric	Antisymmetric	Connected	Well-founded	Has joins	Has meets	Reflexive	Irreflexive	Asymmetric
			Total, Semiconnex					Anti- reflexive
Equivalence relation	Y	✗	✗	✗	✗	✗	Y	✗	✗
Preorder (Quasiorder)	✗	✗	✗	✗	✗	✗	Y	✗	✗
Partial order	✗	Y	✗	✗	✗	✗	Y	✗	✗
Total preorder	✗	✗	Y	✗	✗	✗	Y	✗	✗
Total order	✗	Y	Y	✗	✗	✗	Y	✗	✗
Prewellordering	✗	✗	Y	Y	✗	✗	Y	✗	✗
Well-quasi-ordering	✗	✗	✗	Y	✗	✗	Y	✗	✗
Well-ordering	✗	Y	Y	Y	✗	✗	Y	✗	✗
Lattice	✗	Y	✗	✗	Y	Y	Y	✗	✗
Join-semilattice	✗	Y	✗	✗	Y	✗	Y	✗	✗
Meet-semilattice	✗	Y	✗	✗	✗	Y	Y	✗	✗
Strict partial order	✗	✗	✗	✗	✗	✗	✗	Y	Y
Strict weak order	✗	✗	✗	✗	✗	✗	✗	Y	Y
Strict total order	✗	✗	Y	✗	✗	✗	✗	Y	Y
	Symmetric	Antisymmetric	Connected	Well-founded	Has joins	Has meets	Reflexive	Irreflexive	Asymmetric
Definitions, for all $a,b$ and $S\neq \varnothing$ :	${\begin{aligned}&aRb\\\Rightarrow {}&bRa\end{aligned}}$	${\begin{aligned}aRb{\text{ and }}&bRa\\\Rightarrow a={}&b\end{aligned}}$	${\begin{aligned}a\neq {}&b\Rightarrow \\aRb{\text{ or }}&bRa\end{aligned}}$	${\begin{aligned}\min S\\{\text{exists}}\end{aligned}}$	${\begin{aligned}a\vee b\\{\text{exists}}\end{aligned}}$	${\begin{aligned}a\wedge b\\{\text{exists}}\end{aligned}}$	$aRa$	${\text{not }}aRa$	${\begin{aligned}aRb\Rightarrow \\{\text{not }}bRa\end{aligned}}$

indicates that the column's property is required by the definition of the row's term (at the very left). For example, the definition of an equivalence relation requires it to be symmetric. All definitions tacitly require the homogeneous relation

R

be transitive: for all

a,b,c,

if

aRb

and

bRc

then

aRc,

and there are additional properties that a homogeneous relation may satisfy.

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

{\text{if }}\,aRb\,{\text{ with }}\,a\neq b\,{\text{ then }}\,bRa\,{\text{ must not hold}},

or equivalently,

{\text{if }}\,aRb\,{\text{ and }}\,bRa\,{\text{ then }}\,a=b.

The definition of antisymmetry says nothing about whether

aRa

actually holds or not for any

a

. This is known as reflexivity.

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$ 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 $\,\leq \,$ on the real numbers is antisymmetric: if for two real numbers $x$ and $y$ both inequalities $x\leq y$ and $y\leq x$ hold then $x$ and $y$ must be equal. Similarly, the subset order $\,\subseteq \,$ on the subsets of any given set is antisymmetric: 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{\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[]

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.

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

Antisymmetric relation

Contents

Examples[]

Properties[]

See also[]

References[]