Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
Antisymmetric relation
open-in-new
<table><tbody><tr><th><a href="/facts/Transitive_relation/9r90y50r">Transitive</a> <a href="/facts/Binary_relation/r9BwGgaK">binary relations</a> <ul><li>v</li><li>t</li><li>e</li></ul></th></tr><tr><td><table><tbody><tr><td></td><td> <a href="/facts/Symmetric_relation/ekCWDIAH">Symmetric</a></td><td> Antisymmetric</td><td> <a href="/facts/Connected_relation/UpwopAts">Connected</a></td><td> <a href="/facts/Well-founded_relation/zyRRyJ4M">Well-founded</a></td><td> <a href="/facts/Join_and_meet/cYcLhRIR">Has joins</a></td><td> <a href="/facts/Join_and_meet/cYcLhRIR">Has meets</a></td><td> <a href="/facts/Reflexive_relation/NzTytEg9">Reflexive</a></td><td> <a href="/facts/Reflexive_relation/NzTytEg9">Irreflexive</a></td><td> <a href="/facts/Asymmetric_relation/rUdVRwuI">Asymmetric</a></td></tr><tr><td></td><td></td><td></td><td> Total, Semiconnex</td><td></td><td></td><td></td><td></td><td> Anti-reflexive</td><td></td></tr><tr><td> <a href="/facts/Equivalence_relation/1MQ5rtkW">Equivalence relation</a></td><td> Y</td><td> ✗</td><td> ✗</td><td> ✗</td><td> ✗</td><td> ✗</td><td> Y</td><td> ✗</td><td> ✗</td></tr><tr><td> <a href="/facts/Preorder/uubzHSWm">Preorder (Quasiorder)</a></td><td> ✗</td><td> ✗</td><td> ✗</td><td> ✗</td><td> ✗</td><td> ✗</td><td> Y</td><td> ✗</td><td> ✗</td></tr><tr><td> <a href="/facts/Partial_order/qb4a3FAX">Partial order</a></td><td> ✗</td><td> Y</td><td> ✗</td><td> ✗</td><td> ✗</td><td> ✗</td><td> Y</td><td> ✗</td><td> ✗</td></tr><tr><td> <a href="/facts/Total_preorder/LmaM9lSs">Total preorder</a></td><td> ✗</td><td> ✗</td><td> Y</td><td> ✗</td><td> ✗</td><td> ✗</td><td> Y</td><td> ✗</td><td> ✗</td></tr><tr><td> <a href="/facts/Total_order/xnTtmuYJ">Total order</a></td><td> ✗</td><td> Y</td><td> Y</td><td> ✗</td><td> ✗</td><td> ✗</td><td> Y</td><td> ✗</td><td> ✗</td></tr><tr><td> <a href="/facts/Prewellordering/EMhoWkMU">Prewellordering</a></td><td> ✗</td><td> ✗</td><td> Y</td><td> Y</td><td> ✗</td><td> ✗</td><td> Y</td><td> ✗</td><td> ✗</td></tr><tr><td> <a href="/facts/Well-quasi-ordering/suQavGN9">Well-quasi-ordering</a></td><td> ✗</td><td> ✗</td><td> ✗</td><td> Y</td><td> ✗</td><td> ✗</td><td> Y</td><td> ✗</td><td> ✗</td></tr><tr><td> <a href="/facts/Well-order/GrWEBWlW">Well-ordering</a></td><td> ✗</td><td> Y</td><td> Y</td><td> Y</td><td> ✗</td><td> ✗</td><td> Y</td><td> ✗</td><td> ✗</td></tr><tr><td> <a href="/facts/Lattice_(order)/5ak6ufky">Lattice</a></td><td> ✗</td><td> Y</td><td> ✗</td><td> ✗</td><td> Y</td><td> Y</td><td> Y</td><td> ✗</td><td> ✗</td></tr><tr><td> <a href="/facts/Join-semilattice/kW5po0rp">Join-semilattice</a></td><td> ✗</td><td> Y</td><td> ✗</td><td> ✗</td><td> Y</td><td> ✗</td><td> Y</td><td> ✗</td><td> ✗</td></tr><tr><td> <a href="/facts/Meet-semilattice/kW5po0rp">Meet-semilattice</a></td><td> ✗</td><td> Y</td><td> ✗</td><td> ✗</td><td> ✗</td><td> Y</td><td> Y</td><td> ✗</td><td> ✗</td></tr><tr><td> <a href="/facts/Strict_partial_order/qb4a3FAX">Strict partial order</a></td><td> ✗</td><td> Y</td><td> ✗</td><td> ✗</td><td> ✗</td><td> ✗</td><td> ✗</td><td> Y</td><td> Y</td></tr><tr><td> <a href="/facts/Weak_ordering/LmaM9lSs">Strict weak order</a></td><td> ✗</td><td> Y</td><td> ✗</td><td> ✗</td><td> ✗</td><td> ✗</td><td> ✗</td><td> Y</td><td> Y</td></tr><tr><td> <a href="/facts/Strict_total_order/xnTtmuYJ">Strict total order</a></td><td> ✗</td><td> Y</td><td> Y</td><td> ✗</td><td> ✗</td><td> ✗</td><td> ✗</td><td> Y</td><td> Y</td></tr><tr><td></td><td> <a href="/facts/Symmetric_relation/ekCWDIAH">Symmetric</a></td><td> Antisymmetric</td><td> <a href="/facts/Connected_relation/UpwopAts">Connected</a></td><td> <a href="/facts/Well-founded_relation/zyRRyJ4M">Well-founded</a></td><td> <a href="/facts/Join_and_meet/cYcLhRIR">Has joins</a></td><td> <a href="/facts/Join_and_meet/cYcLhRIR">Has meets</a></td><td> <a href="/facts/Reflexive_relation/NzTytEg9">Reflexive</a></td><td> <a href="/facts/Reflexive_relation/NzTytEg9">Irreflexive</a></td><td> <a href="/facts/Asymmetric_relation/rUdVRwuI">Asymmetric</a></td></tr><tr><td> Definitions, for all a , b {\displaystyle a,b} and S ≠ ∅ : {\displaystyle S\neq \varnothing :} </td><td> a R b ⇒ b R a {\displaystyle {\begin{aligned}&aRb\\\Rightarrow {}&bRa\end{aligned}}} </td><td> a R b and b R a ⇒ a = b {\displaystyle {\begin{aligned}aRb{\text{ and }}&bRa\\\Rightarrow a={}&b\end{aligned}}} </td><td> a ≠ b ⇒ a R b or b R a {\displaystyle {\begin{aligned}a\neq {}&b\Rightarrow \\aRb{\text{ or }}&bRa\end{aligned}}} </td><td> min S exists {\displaystyle {\begin{aligned}\min S\\{\text{exists}}\end{aligned}}} </td><td> a ∨ b exists {\displaystyle {\begin{aligned}a\vee b\\{\text{exists}}\end{aligned}}} </td><td> a ∧ b exists {\displaystyle {\begin{aligned}a\wedge b\\{\text{exists}}\end{aligned}}} </td><td> a R a {\displaystyle aRa} </td><td> not a R a {\displaystyle {\text{not }}aRa} </td><td> a R b ⇒ not b R a {\displaystyle {\begin{aligned}aRb\Rightarrow \\{\text{not }}bRa\end{aligned}}} </td></tr></tbody></table></td></tr><tr><td>Y indicates that the column's property is always true for 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. <p>All definitions tacitly require the <a href="/facts/Homogeneous_relation/wh0QoWzS">homogeneous relation</a> R {\displaystyle R} be <a href="/facts/Transitive_relation/9r90y50r">transitive</a>: for all a , b , c , {\displaystyle a,b,c,} if a R b {\displaystyle aRb} and b R c {\displaystyle bRc} then a R c . {\displaystyle aRc.} A term's definition may require additional properties that are not listed in this table.</p></td></tr></tbody></table> <p>In <a href="/facts/Mathematics/pxTouaz4">mathematics</a>, a <a href="/facts/Binary_relation/r9BwGgaK">binary relation</a> R {\displaystyle R} on a <a href="/facts/Set_(mathematics)/BfucfHMq">set</a> X {\displaystyle X} is antisymmetric if there is no pair of <i>distinct</i> elements of X {\displaystyle X} each of which is related by R {\displaystyle R} to the other. More formally, R {\displaystyle R} is antisymmetric precisely if for all a , b ∈ X , {\displaystyle a,b\in X,} if a R b with a ≠ b then b R a must not hold , {\displaystyle {\text{if }}\,aRb\,{\text{ with }}\,a\neq b\,{\text{ then }}\,bRa\,{\text{ must not hold}},} or equivalently, if a R b and b R a then a = b . {\displaystyle {\text{if }}\,aRb\,{\text{ and }}\,bRa\,{\text{ then }}\,a=b.} The definition of antisymmetry says nothing about whether a R a {\displaystyle aRa} actually holds or not for any a {\displaystyle a} . An antisymmetric relation R {\displaystyle R} on a set X {\displaystyle X} may be <a href="/facts/Reflexive_relation/NzTytEg9">reflexive</a> (that is, a R a {\displaystyle aRa} for all a ∈ X {\displaystyle a\in X} ), <a href="/facts/Irreflexive_relation/NzTytEg9">irreflexive</a> (that is, a R a {\displaystyle aRa} for no a ∈ X {\displaystyle a\in X} ), or neither reflexive nor irreflexive. A relation is <a href="/facts/Asymmetric_relation/rUdVRwuI">asymmetric</a> if and only if it is both antisymmetric and irreflexive. </p>