Editing Antisymmetric relation

{{short description|Binary relation such that if A is related to B and is different from it then B is not related to A}}
{{Refimprove|date=January 2010}}
{{distinguish|Asymmetric relation}}
{{stack|{{Binary relations}}}}

In [[mathematics]], a [[binary relation]] <math>R</math> on a [[Set (mathematics)|set]] <math>X</math> is '''antisymmetric''' if there is no pair of ''distinct'' elements of <math>X</math> each of which is related by <math>R</math> to the other. More formally, <math>R</math> is antisymmetric precisely if for all <math>a, b \in X,</math>
<math display=block>\text{if } \,aRb\, \text{ with } \,a \neq b\, \text{ then } \,bRa\, \text{ must not hold},</math>
or equivalently,
<math display=block>\text{if } \,aRb\, \text{ and } \,bRa\, \text{ then } \,a = b.</math>
The definition of antisymmetry says nothing about whether <math>aRa</math> actually holds or not for any <math>a</math>. An antisymmetric relation <math>R</math> on a set <math>X</math> may be [[Reflexive relation|reflexive]] (that is, <math>aRa</math> for all <math>a \in X</math>), [[Irreflexive relation|irreflexive]] (that is, <math>aRa</math> for no <math>a \in X</math>), or neither reflexive nor irreflexive. A relation is [[Asymmetric relation|asymmetric]] if and only if it is both antisymmetric and irreflexive.

== Examples ==

The [[divisibility]] relation on the [[natural number]]s is an important example of an antisymmetric relation. In this context, antisymmetry means that the only way each of two numbers can be divisible by the other is if the two are, in fact, the same number; equivalently, if <math>n</math> and <math>m</math> are distinct and <math>n</math> is a factor of <math>m,</math> then <math>m</math> cannot be a factor of <math>n.</math>  For example, 12 is divisible by 4, but 4 is not divisible by 12.

The usual [[order relation]] <math>\,\leq\,</math> on the [[real number]]s is antisymmetric: if for two real numbers <math>x</math> and <math>y</math> both [[Inequality (mathematics)|inequalities]] <math>x \leq y</math> and <math>y \leq x</math> hold, then <math>x</math> and <math>y</math> must be equal. Similarly, the [[subset order]] <math>\,\subseteq\,</math> on the subsets of any given set is antisymmetric: given two sets <math>A</math> and <math>B,</math> if every [[Element (mathematics)|element]] in <math>A</math> also is in <math>B</math> and every element in <math>B</math> is also in <math>A,</math> then <math>A</math> and <math>B</math> must contain all the same elements and therefore be equal:
<math display=block>A \subseteq B \text{ and } B \subseteq A \text{ implies } A = B</math>
A real-life example of a relation that is typically antisymmetric is "paid the restaurant bill of" (understood as restricted to a given occasion). Typically, some people pay their own bills, while others pay for their spouses or friends. As long as no two people pay each other's bills, the relation is antisymmetric.

== Properties ==

[[File:Symmetric-and-or-antisymmetric.svg|thumb|Symmetric and antisymmetric relations|340x340px]]

[[Partial order|Partial]] and [[total order]]s are antisymmetric by definition. A relation can be both [[Symmetric relation|symmetric]] and antisymmetric (in this case, it must be [[Coreflexive relation|coreflexive]]), and there are relations which are neither symmetric nor antisymmetric (for example, the "preys on" relation on biological [[species]]).

Antisymmetry is different from [[Asymmetric relation|asymmetry]]: a relation is asymmetric if and only if it is antisymmetric and [[Irreflexive relation|irreflexive]].

== See also ==

* {{annotated link|Reflexive relation}}
* [[Symmetry in mathematics]]

== References ==

{{notelist}}
{{reflist}}

* {{MathWorld|urlname=AntisymmetricRelation|title=Antisymmetric Relation}}
* {{cite book|title=Theory and Problems of Discrete Mathematics|url=https://archive.org/details/schaumsoutlinedi00lips_585|url-access=limited|first=Seymour|last=Lipschutz|author-link=Seymour Lipschutz|author2=Marc Lars Lipson|year=1997|publisher=McGraw-Hill|isbn=0-07-038045-7|page=[https://archive.org/details/schaumsoutlinedi00lips_585/page/n39 33]}}
* [https://ncatlab.org/nlab/show/antisymmetric+relation nLab antisymmetric relation]

{{DEFAULTSORT:Antisymmetric Relation}}
[[Category:Properties of binary relations]]