Asymmetric relation

Not to be confused with Antisymmetric relation.

Transitive binary relations v t e
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 ${\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 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 Y in the "Symmetric" column and ✗ in the "Antisymmetric" column, respectively. 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.}$ A term's definition may require additional properties that are not listed in this table.

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

1. Gries, David; Schneider, Fred B. (1993), A Logical Approach to Discrete Math, Springer-Verlag, p. 273.
2. Nievergelt, Yves (2002), Foundations of Logic and Mathematics: Applications to Computer Science and Cryptography, Springer-Verlag, p. 158.
3. Flaška, V.; Ježek, J.; Kepka, T.; Kortelainen, J. (2007). (PDF). Prague: School of Mathematics - Physics Charles University. p. 1. Archived from the original (PDF) on 2013-11-02. Retrieved 2013-08-20. Lemma 1.1 (iv). Note that this source refers to asymmetric relations as "strictly antisymmetric".