Asymmetric relation
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]
In mathematical notation, this is:
An example 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 x ≤ x produces x ≤ x and both are true. In general, any relation in which x R x holds for some x (that is, which is not irreflexive) is also not asymmetric.
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 inverses 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 a R b and b R a, transitivity gives a R a, contradicting irreflexivity.
- An asymmetric relation need not be total. For example, strict subset or ⊊ is asymmetric, and neither of the sets {1,2} and {3,4} is a strict subset of the other. In general, every strict partial order is asymmetric, and conversely, every transitive asymmetric relation is a strict partial order. Not all asymmetric relations are strict partial orders. An example of an asymmetric intransitive relation is the rock-paper-scissors relation: if X beats Y, then Y does not beat X; but if X beats Y and Y beats Z, then X does not beat Z.
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. Lemma 1.1 (iv). Note that this source refers to asymmetric relations as "strictly antisymmetric".
This article is issued from
Wikipedia.
The text is licensed under Creative Commons - Attribution - Sharealike.
Additional terms may apply for the media files.