Asymmetric relation

Not to be confused with 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 Y Strict weak order ✗ Y ✗ ✗ ✗ ✗ ✗ Y Y Strict total order ✗ Y 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}}$
Y indicates that the column's property is always true for 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 Y in the "Symmetric" column and ✗ in the "Antisymmetric" column, respectively. All definitions tacitly require the homogeneous relation $R$ be transitive: for all $a,b,c,$ if $aRb$ and $bRc$ then $aRc.$ A term's definition may require additional properties that are not listed in this table.

In mathematics, an asymmetric relation is a binary relation $R$ on a set $X$ where for all $a,b\in X,$ if $a$ is related to $b$ then $b$ is not related to $a.$

Formal definition

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

A logically equivalent definition is:

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

which in first-order logic can be written as: $$\forall a,b\in X:\lnot (aRb\wedge bRa).$$

An example of an asymmetric relation is the "less than" relation $\,<\,$ between real numbers: if $x<y$ then necessarily $y$ is not less than $x.$ The "less than or equal" relation $\,\leq ,$ on the other hand, is not asymmetric, because reversing for example, $x\leq x$ produces $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.
• Restrictions and converses of asymmetric relations are also asymmetric. For example, the restriction of $\,<\,$ from the reals to the integers is still asymmetric, and the inverse $\,>\,$ of $\,<\,$ is also asymmetric.
• A transitive relation is asymmetric if and only if it is irreflexive: if $aRb$ and $bRa,$ transitivity gives $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 $X$ beats $Y,$ then $Y$ does not beat $X;$ and if $X$ beats $Y$ and $Y$ beats $Z,$ then $X$ does not beat $Z.$
• An asymmetric relation need not have the connex property. For example, the strict subset relation $\,\subsetneq \,$ is asymmetric, and neither of the sets $\{1,2\}$ and $\{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 $\,<\,$ over the real numbers be asymmetric.