A binary relation which never occurs in both directions
Transitive binary relations |
| Symmetric | Antisymmetric | Connected | Well-founded | Has joins | Has meets | Reflexive | Irreflexive | Asymmetric | | | | Total, Semiconnex | | | | | Anti- reflexive | | Equivalence relation | Y | ✗ | ✗ | ✗ | ✗ | ✗ | Y | ✗ | ✗ | Preorder (Quasiorder) | ✗ | ✗ | ✗ | ✗ | ✗ | ✗ | Y | ✗ | ✗ | Partial order | ✗ | Y | ✗ | ✗ | ✗ | ✗ | Y | ✗ | ✗ | Total preorder | ✗ | ✗ | Y | ✗ | ✗ | ✗ | Y | ✗ | ✗ | Total order | ✗ | Y | Y | ✗ | ✗ | ✗ | Y | ✗ | ✗ | Prewellordering | ✗ | ✗ | Y | Y | ✗ | ✗ | Y | ✗ | ✗ | Well-quasi-ordering | ✗ | ✗ | ✗ | Y | ✗ | ✗ | Y | ✗ | ✗ | Well-ordering | ✗ | Y | Y | Y | ✗ | ✗ | Y | ✗ | ✗ | Lattice | ✗ | Y | ✗ | ✗ | Y | Y | Y | ✗ | ✗ | Join-semilattice | ✗ | Y | ✗ | ✗ | Y | ✗ | Y | ✗ | ✗ | Meet-semilattice | ✗ | Y | ✗ | ✗ | ✗ | Y | Y | ✗ | ✗ | Strict partial order | ✗ | Y | ✗ | ✗ | ✗ | ✗ | ✗ | Y | Y | Strict weak order | ✗ | Y | ✗ | ✗ | ✗ | ✗ | ✗ | Y | Y | Strict total order | ✗ | Y | Y | ✗ | ✗ | ✗ | ✗ | Y | Y | | Symmetric | Antisymmetric | Connected | Well-founded | Has joins | Has meets | Reflexive | Irreflexive | Asymmetric | Definitions, for all and ![{\displaystyle S\neq \varnothing :}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a538fab804c9428c4f7d4ca3ed214a97483c4260) | ![{\displaystyle {\begin{aligned}&aRb\\\Rightarrow {}&bRa\end{aligned}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a18cac1ed3115c87d45b4d751de57124233a6e00) | ![{\displaystyle {\begin{aligned}aRb{\text{ and }}&bRa\\\Rightarrow a={}&b\end{aligned}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e9cc3f46e9f0b647ce6771396a975ef8d364674d) | ![{\displaystyle {\begin{aligned}a\neq {}&b\Rightarrow \\aRb{\text{ or }}&bRa\end{aligned}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/8c73cadd7ab7bf3b5257f5c505c756ec098902f3) | ![{\displaystyle {\begin{aligned}\min S\\{\text{exists}}\end{aligned}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b7ec5a418cceeb68b9945ca75d31604719db4660) | ![{\displaystyle {\begin{aligned}a\vee b\\{\text{exists}}\end{aligned}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b3386379a9406067b50b99e12241e9d7fab3369b) | ![{\displaystyle {\begin{aligned}a\wedge b\\{\text{exists}}\end{aligned}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/abff244e064dd72fd16781277ad3440b35bd767d) | ![{\displaystyle aRa}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ba7fc1d9d50c65105d5edcb3478b5ca4172c54d6) | ![{\displaystyle {\text{not }}aRa}](https://wikimedia.org/api/rest_v1/media/math/render/svg/8263f0c706367e5306eae1b9353034024639da23) | ![{\displaystyle {\begin{aligned}aRb\Rightarrow \\{\text{not }}bRa\end{aligned}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a1aec245f8776556d3ad3fcdc18d4ba61929eccb) | |
Y indicates that the column's property is always true the row's term (at the very left), while ✗ indicates that the property is not guaranteed in general (it might, or might not, hold). For example, that every equivalence relation is symmetric, but not necessarily antisymmetric, is indicated by Y in the "Symmetric" column and ✗ in the "Antisymmetric" column, respectively. All definitions tacitly require the homogeneous relation be transitive: for all if and then A term's definition may require additional properties that are not listed in this table. |
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
Preliminaries
A 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
The 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
![{\displaystyle \forall a,b\in X:aRb\implies \lnot (bRa).}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ff6ebaa25628e00c76a2d685c3b9a75b161c2dee)
A
logically equivalent definition is:
- for all
at least one of
and
is false,
which in first-order logic can be written as:
![{\displaystyle \forall a,b\in X:\lnot (aRb\wedge bRa).}](https://wikimedia.org/api/rest_v1/media/math/render/svg/185d931209ab187236ad8c1f9e8b8b49619e8e46)
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
An 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
The 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
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.
- ^ 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".