Asymmetric relation

From HandWiki
Short description: A binary relation which never occurs in both directions

In mathematics, an asymmetric relation is a binary relation [math]\displaystyle{ R }[/math] on a set [math]\displaystyle{ X }[/math] where for all [math]\displaystyle{ a, b \in X, }[/math] if [math]\displaystyle{ a }[/math] is related to [math]\displaystyle{ b }[/math] then [math]\displaystyle{ b }[/math] is not related to [math]\displaystyle{ a. }[/math][1]

Formal definition

A binary relation on [math]\displaystyle{ X }[/math] is any subset [math]\displaystyle{ R }[/math] of [math]\displaystyle{ X \times X. }[/math] Given [math]\displaystyle{ a, b \in X, }[/math] write [math]\displaystyle{ a R b }[/math] if and only if [math]\displaystyle{ (a, b) \in R, }[/math] which means that [math]\displaystyle{ a R b }[/math] is shorthand for [math]\displaystyle{ (a, b) \in R. }[/math] The expression [math]\displaystyle{ a R b }[/math] is read as "[math]\displaystyle{ a }[/math] is related to [math]\displaystyle{ b }[/math] by [math]\displaystyle{ R. }[/math]" The binary relation [math]\displaystyle{ R }[/math] is called asymmetric if for all [math]\displaystyle{ a, b \in X, }[/math] if [math]\displaystyle{ a R b }[/math] is true then [math]\displaystyle{ b R a }[/math] is false; that is, if [math]\displaystyle{ (a, b) \in R }[/math] then [math]\displaystyle{ (b, a) \not\in R. }[/math] This can be written in the notation of first-order logic as [math]\displaystyle{ \forall a, b \in X: a R b \implies \lnot(b R a). }[/math]

A logically equivalent definition is:

for all [math]\displaystyle{ a, b \in X, }[/math] at least one of [math]\displaystyle{ a R b }[/math] and [math]\displaystyle{ b R a }[/math] is false,

which in first-order logic can be written as: [math]\displaystyle{ \forall a, b \in X: \lnot(a R b \wedge b R a). }[/math]

An example of an asymmetric relation is the "less than" relation [math]\displaystyle{ \,\lt \, }[/math] between real numbers: if [math]\displaystyle{ x \lt y }[/math] then necessarily [math]\displaystyle{ y }[/math] is not less than [math]\displaystyle{ x. }[/math] The "less than or equal" relation [math]\displaystyle{ \,\leq, }[/math] on the other hand, is not asymmetric, because reversing for example, [math]\displaystyle{ x \leq x }[/math] produces [math]\displaystyle{ x \leq x }[/math] 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 [math]\displaystyle{ \,\lt \, }[/math] from the reals to the integers is still asymmetric, and the inverse [math]\displaystyle{ \,\gt \, }[/math] of [math]\displaystyle{ \,\lt \, }[/math] is also asymmetric.
  • A transitive relation is asymmetric if and only if it is irreflexive:[3] if [math]\displaystyle{ aRb }[/math] and [math]\displaystyle{ bRa, }[/math] transitivity gives [math]\displaystyle{ aRa, }[/math] 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 [math]\displaystyle{ X }[/math] beats [math]\displaystyle{ Y, }[/math] then [math]\displaystyle{ Y }[/math] does not beat [math]\displaystyle{ X; }[/math] and if [math]\displaystyle{ X }[/math] beats [math]\displaystyle{ Y }[/math] and [math]\displaystyle{ Y }[/math] beats [math]\displaystyle{ Z, }[/math] then [math]\displaystyle{ X }[/math] does not beat [math]\displaystyle{ Z. }[/math]
  • An asymmetric relation need not have the connex property. For example, the strict subset relation [math]\displaystyle{ \,\subsetneq\, }[/math] is asymmetric, and neither of the sets [math]\displaystyle{ \{1, 2\} }[/math] and [math]\displaystyle{ \{3, 4\} }[/math] is a strict subset of the other. A relation is connex if and only if its complement is asymmetric.

See also

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. Prague: School of Mathematics - Physics Charles University. p. 1. http://www.karlin.mff.cuni.cz/~jezek/120/transitive1.pdf. Retrieved 2013-08-20.  Lemma 1.1 (iv). Note that this source refers to asymmetric relations as "strictly antisymmetric".