Asymmetric relation

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]

This can be written in the notation of first-order logic as

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

where ${\displaystyle aRb}$ is shorthand for ${\displaystyle (a,b)\in R}$ (because by definition, a binary relation on ${\displaystyle X}$ is just a subset of ${\displaystyle X\times X}$). The expression ${\displaystyle aRb}$ is read as "${\displaystyle a}$ is related to ${\displaystyle b}$ by ${\displaystyle R.}$" A logically equivalent definition is ${\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 e.g. ${\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 > of < 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 X.}$
• An asymmetric relation need not have the connex property. For example, the strict subset relation ⊊ 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 iff, and only if, its complement is asymmetric.

See also

• Binary relation
• Tarski's axiomatization of the reals – part of this is the requirement that < 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). Transitive Closures of Binary Relations I (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".