Asymmetric relation

A binary relation on $X$ is any subset $R$ of $X\; \backslash times\; X.$ Given $a,\; b\; \backslash in\; X,$ write $a\; R\; b$ if and only if $(a,\; b)\; \backslash in\; R,$ which means that $a\; R\; b$ is shorthand for $(a,\; b)\; \backslash in\; R.$ The expression $a\; R\; b$ is read as "$a$ is related to $b$ by $R.$"

The binary relation $R$ is called {{em|asymmetric}} if for all $a,\; b\; \backslash in\; X,$ if $a\; R\; b$ is true then $b\; R\; a$ is false; that is, if $(a,\; b)\; \backslash in\; R$ then $(b,\; a)\; \backslash not\backslash in\; R.$

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

$$\backslash forall\; a,\; b\; \backslash in\; X:\; a\; R\; b\; \backslash implies\; \backslash lnot(b\; R\; a).$$

A logically equivalent definition is:

:for all $a,\; b\; \backslash in\; X,$ at least one of $a\; R\; b$ and $b\; R\; a$ is {{em|false}},

which in first-order logic can be written as:

$$\backslash forall\; a,\; b\; \backslash in\; X:\; \backslash lnot(a\; R\; b\; \backslash wedge\; b\; R\; a).$$

A relation is asymmetric if and only if it is both antisymmetric and irreflexive,{{citation|first1=Yves|last1=Nievergelt|title=Foundations of Logic and Mathematics: Applications to Computer Science and Cryptography|publisher=Springer-Verlag|year=2002|page=[https://books.google.com/books?id=_H_nJdagqL8C&pg=PA158 158]}}. so this may also be taken as a definition.

An example of an asymmetric relation is the "less than" relation between real numbers: if 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 {{em|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.$

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 $\backslash ,>\backslash ,$ of is also asymmetric.

An asymmetric relation need not have the connex property. For example, the strict subset relation $\backslash ,\backslash subsetneq\backslash ,$ is asymmetric, and neither of the sets $\backslash \{1,\; 2\backslash \}$ and $\backslash \{3,\; 4\backslash \}$ 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 $\backslash leq$. This is not asymmetric, because reversing for example, $x\; \backslash leq\; x$ produces $x\; \backslash leq\; 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.

The following conditions are sufficient for a relation $R$ to be asymmetric:{{cite arXiv |last1=Burghardt |first1=Jochen |title=Simple Laws about Nonprominent Properties of Binary Relations |date=2018 |class=math.LO |eprint=1806.05036}}

• $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:{{cite book|last1=Flaška|first1=V.|last2=Ježek|first2=J.|last3=Kepka|first3=T.|last4=Kortelainen|first4=J.|title=Transitive Closures of Binary Relations I|year=2007|publisher=School of Mathematics - Physics Charles University|location=Prague|page=1|url=http://www.karlin.mff.cuni.cz/~jezek/120/transitive1.pdf|access-date=2013-08-20|archive-url=https://web.archive.org/web/20131102214049/http://www.karlin.mff.cuni.cz/~jezek/120/transitive1.pdf|archive-date=2013-11-02|url-status=dead}} Lemma 1.1 (iv). Note that this source refers to asymmetric relations as "strictly antisymmetric". 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

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

{{reflist}}

{{DEFAULTSORT:Asymmetric Relation}}

Category:Properties of binary relations

Category:Asymmetry