Transitive binary relations | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
![]() ![]() All definitions tacitly require the homogeneous relation be transitive: for all if and then |
In mathematics, an asymmetric relation is a binary relation on a set where for all if is related to then is not related to [1]
Formal definition
editPreliminaries
editA binary relation on is any subset of Given write if and only if which means that is shorthand for The expression is read as " is related to by "
Definition
editThe binary relation is called asymmetric if for all if is true then is false; that is, if then This can be written in the notation of first-order logic as A logically equivalent definition is:
- for all at least one of and is false,
which in first-order logic can be written as: A relation is asymmetric if and only if it is both antisymmetric and irreflexive,[2] so this may also be taken as a definition.
Examples
editAn example of an asymmetric relation is the "less than" relation between real numbers: if then necessarily is not less than 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 rock paper scissors relation: if beats then does not beat and if beats and beats then does not beat
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 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 . This is not asymmetric, because reversing for example, produces 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
editThe following conditions are sufficient for a relation to be asymmetric:[3]
- is irreflexive and anti-symmetric (this is also necessary)
- is irreflexive and transitive. A transitive relation is asymmetric if and only if it is irreflexive:[4] if and transitivity gives contradicting irreflexivity. Such a relation is a strict partial order.
- is irreflexive and satisfies semiorder property 1 (there do not exist two mutually incomparable two-point linear orders)
- is anti-transitive and anti-symmetric
- is anti-transitive and transitive
- is anti-transitive and satisfies semi-order property 1
See also
edit- Tarski's axiomatization of the reals – part of this is the requirement that over the real numbers be asymmetric.
References
edit- ^ 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.
- ^ Burghardt, Jochen (2018). "Simple Laws about Nonprominent Properties of Binary Relations". arXiv:1806.05036.
- ^ 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".