Math gifts

- Art Gallery -

In mathematics, an asymmetric relation is a binary relation on a set X where

For all a and b in X, if a is related to b, then b is not related to a.[1]

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

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

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 < between real numbers: if x < y, then necessarily y is not less than x. The "less than or equal" relation ≤, on the other hand, is not asymmetric, because reversing e.g. x ≤ x produces x ≤ 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 < 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 aRb and bRa, transitivity gives 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 X beats Y, then Y does not beat X; and if X beats Y and Y beats Z, then X does not beat Z.
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.

See also

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

References

Gries, David; Schneider, Fred B. (1993), A Logical Approach to Discrete Math, Springer-Verlag, p. 273.
Nievergelt, Yves (2002), Foundations of Logic and Mathematics: Applications to Computer Science and Cryptography, Springer-Verlag, p. 158.
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".

Undergraduate Texts in Mathematics

Graduate Texts in Mathematics

Graduate Studies in Mathematics

Mathematics Encyclopedia

World

Index

Hellenica World - Scientific Library

Retrieved from "http://en.wikipedia.org/"
All text is available under the terms of the GNU Free Documentation License