Asymmetric 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 ${\displaystyle a,b}$ and ${\displaystyle S\neq \varnothing :}$ ${\displaystyle {\begin{aligned}&aRb\\\Rightarrow {}&bRa\end{aligned}}}$ ${\displaystyle {\begin{aligned}aRb{\text{ and }}&bRa\\\Rightarrow a={}&b\end{aligned}}}$ ${\displaystyle {\begin{aligned}a\neq {}&b\Rightarrow \\aRb{\text{ or }}&bRa\end{aligned}}}$ ${\displaystyle {\begin{aligned}\min S\\{\text{exists}}\end{aligned}}}$ ${\displaystyle {\begin{aligned}a\vee b\\{\text{exists}}\end{aligned}}}$ ${\displaystyle {\begin{aligned}a\wedge b\\{\text{exists}}\end{aligned}}}$ ${\displaystyle aRa}$ ${\displaystyle {\text{not }}aRa}$ ${\displaystyle {\begin{aligned}aRb\Rightarrow \\{\text{not }}bRa\end{aligned}}}$
Y 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. ✗ indicates that the property may, or may not hold. All definitions tacitly require the homogeneous relation ${\displaystyle R}$ be transitive: for all ${\displaystyle a,b,c,}$ if ${\displaystyle aRb}$ and ${\displaystyle bRc}$ then ${\displaystyle aRc,}$ and there are additional properties that a homogeneous relation may satisfy.

In mathematics, an asymmetric relation is a binary relation ${\displaystyle R}$ on a set ${\displaystyle X}$ where for all ${\displaystyle a,b\in X,}$ if ${\displaystyle a}$ is related to ${\displaystyle b}$ then ${\displaystyle b}$ is not related to ${\displaystyle a.}$^[1]

Formal definition[]

A binary relation on ${\displaystyle X}$ is any subset ${\displaystyle R}$ of ${\displaystyle X\times X.}$ Given ${\displaystyle a,b\in X,}$ write ${\displaystyle aRb}$ if and only if ${\displaystyle (a,b)\in R,}$ which means that ${\displaystyle aRb}$ is shorthand for ${\displaystyle (a,b)\in R.}$ The expression ${\displaystyle aRb}$ is read as "${\displaystyle a}$ is related to ${\displaystyle b}$ by ${\displaystyle R.}$" The binary relation ${\displaystyle R}$ is called asymmetric if for all ${\displaystyle a,b\in X,}$ if ${\displaystyle aRb}$ is true then ${\displaystyle bRa}$ is false; that is, if ${\displaystyle (a,b)\in R}$ then ${\displaystyle (b,a)\not \in R.}$ This can be written in the notation of first-order logic as

$${\displaystyle \forall a,b\in X:aRb\implies \lnot (bRa).}$$

A logically equivalent definition is:

for all ${\displaystyle a,b\in X,}$ at least one of ${\displaystyle aRb}$ and ${\displaystyle bRa}$ is false,

which in first-order logic can be written as:

$${\displaystyle \forall a,b\in X:\lnot (aRb\wedge bRa).}$$

An example of an asymmetric relation is the "less than" relation ${\displaystyle \,<\,}$ between real numbers: if ${\displaystyle x<y}$ then necessarily ${\displaystyle y}$ is not less than ${\displaystyle x.}$ The "less than or equal" relation ${\displaystyle \,\leq ,}$ on the other hand, is not asymmetric, because reversing for example, ${\displaystyle x\leq x}$ produces ${\displaystyle x\leq x}$ and both are true. Asymmetry is not the same thing as "not symmetric": the less-than-or-equal relation is an example of a relation that is neither symmetric nor asymmetric. The empty relation is the only relation that is (vacuously) both symmetric and asymmetric.

Properties[]

• A relation is asymmetric if and only if it is both antisymmetric and irreflexive.^[2]
• Restrictions and converses of asymmetric relations are also asymmetric. For example, the restriction of ${\displaystyle \,<\,}$ from the reals to the integers is still asymmetric, and the inverse ${\displaystyle \,>\,}$ of ${\displaystyle \,<\,}$ is also asymmetric.
• A transitive relation is asymmetric if and only if it is irreflexive:^[3] if ${\displaystyle aRb}$ and ${\displaystyle bRa,}$ transitivity gives ${\displaystyle aRa,}$ contradicting irreflexivity.
• As a consequence, a relation is transitive and asymmetric if and only if it is a strict partial order.
• Not all asymmetric relations are strict partial orders. An example of an asymmetric non-transitive, even antitransitive relation is the rock paper scissors relation: if ${\displaystyle X}$ beats ${\displaystyle Y,}$ then ${\displaystyle Y}$ does not beat ${\displaystyle X;}$ and if ${\displaystyle X}$ beats ${\displaystyle Y}$ and ${\displaystyle Y}$ beats ${\displaystyle Z,}$ then ${\displaystyle X}$ does not beat ${\displaystyle Z.}$
• An asymmetric relation need not have the connex property. For example, the strict subset relation ${\displaystyle \,\subsetneq \,}$ is asymmetric, and neither of the sets ${\displaystyle \{1,2\}}$ and ${\displaystyle \{3,4\}}$ is a strict subset of the other. A relation is connex if and only if its complement is asymmetric.

See also[]

• Tarski's axiomatization of the reals – part of this is the requirement that ${\displaystyle \,<\,}$ over the real numbers be asymmetric.

References[]