Asymmetric relation

Template:Large Template:Navbar
Template:Aligned table
Template:Aye indicates that the column's property is always true for the row's term (at the very left), while Template:N& 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 Template:Aye in the "Symmetric" column and Template:N& 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

Preliminaries

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.$"

Definition

The binary relation $R$ is called Template:Em 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)\in ̸R.$ This can be written in the notation of first-order logic as $$\mathrm{\forall }a,b\in X:aRb⟹\mathrm{\neg }(bRa).$$ A logically equivalent definition is:

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

which in first-order logic can be written as: $$\mathrm{\forall }a,b\in X:\mathrm{\neg }(aRb\wedge bRa).$$ A relation is asymmetric if and only if it is both antisymmetric and irreflexive, so this may also be taken as a definition.

Examples

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.$ More generally, any strict partial order is an asymmetric relation. Not all asymmetric relations are strict partial orders. An example of an asymmetric non-transitive, even antitransitive relation is the Template:Em 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.$

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 converse or dual $>$ of $<$ is also asymmetric.

An asymmetric relation need not have the connex property. For example, the strict subset relation $⊊$ 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.

A non-example is the "less than or equal" relation $\le$. This is not asymmetric, because reversing for example, $x\le x$ produces $x\le x$ and both are true. The less-than-or-equal relation is an example of a relation that is neither symmetric nor asymmetric, showing that asymmetry is not the same thing as "not symmetric".

The empty relation is the only relation that is (vacuously) both symmetric and asymmetric.

Properties

The following conditions are sufficient for a relation $R$ to be asymmetric:

• $R$ is irreflexive and anti-symmetric (this is also necessary)
• $R$ is irreflexive and transitive. A transitive relation is asymmetric if and only if it is irreflexive: if $aRb$ and $bRa,$ transitivity gives $aRa,$ contradicting irreflexivity. Such a relation is a strict partial order.
• $R$ is irreflexive and satisfies semiorder property 1 (there do not exist two mutually incomparable two-point linear orders)
• $R$ is anti-transitive and anti-symmetric
• $R$ is anti-transitive and transitive
• $R$ is anti-transitive and satisfies semi-order property 1

See also

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