Asymmetric relation

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 $a R b$ if and only if $(a, b) \in R,$ which means that $a R b$ is shorthand for $(a, b) \in R.$ The expression $a R b$ is read as "$a$ is related to $b$ by $R.$"

Definition

The binary relation $R$ is called if for all $a, b \in X,$ if $a R b$ is true then $b R a$ 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: a R b \implies \lnot(b R a).$
A logically equivalent definition is:
:for all $a, b \in X,$ at least one of $a R b$ and $b R a$ is ,
which in first-order logic can be written as:
$\forall a, b \in X: \lnot(a R b \wedge b R a).$
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 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 $\,\subsetneq\,$ is asymmetric, and neither of the sets $\$ and $\$ 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 $\leq$. This is not asymmetric, because reversing for example, $x \leq x$ produces $x \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.

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: 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

See also

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

References

{{DEFAULTSORT:Asymmetric Relation
Properties of binary relations
Asymmetry