Editing Asymmetric relation

{{Short description|A binary relation which never occurs in both directions}}
{{distinguish|Antisymmetric relation}}
{{Binary relations}}
In [[mathematics]], an '''asymmetric relation''' is a [[binary relation]] <math>R</math> on a [[Set (mathematics)|set]] <math>X</math> where for all <math>a, b \in X,</math> if <math>a</math> is related to <math>b</math> then <math>b</math> is ''not'' related to <math>a.</math><ref>{{citation|first1=David|last1=Gries|author1-link=David Gries|first2=Fred B.|last2=Schneider|author2-link=Fred B. Schneider|title=A Logical Approach to Discrete Math|publisher=Springer-Verlag|year=1993|page=[https://books.google.com/books?id=ZWTDQ6H6gsUC&pg=PA273 273]}}.</ref>

== Formal definition ==

=== Preliminaries ===
A binary relation on <math>X</math> is any subset <math>R</math> of <math>X \times X.</math> Given <math>a, b \in X,</math> write <math>a R b</math> if and only if <math>(a, b) \in R,</math> which means that <math>a R b</math> is shorthand for <math>(a, b) \in R.</math> The expression <math>a R b</math> is read as "<math>a</math> is related to <math>b</math> by <math>R.</math>"

=== Definition ===

The binary relation <math>R</math> is called '''{{em|asymmetric}}''' if for all <math>a, b \in X,</math> if <math>a R b</math> is true then <math>b R a</math> is false; that is, if <math>(a, b) \in R</math> then <math>(b, a) \not\in R.</math> 
This can be written in the notation of [[first-order logic]] as
<math display=block>\forall a, b \in X: a R b \implies \lnot(b R a).</math>
A [[Logical equivalence|logically equivalent]] definition is:
:for all <math>a, b \in X,</math> at least one of <math>a R b</math> and <math>b R a</math> is {{em|false}},
which in first-order logic can be written as:
<math display=block>\forall a, b \in X: \lnot(a R b \wedge b R a).</math>
A relation is asymmetric if and only if it is both [[Antisymmetric relation|antisymmetric]] and [[Reflexive relation|irreflexive]],<ref>{{citation|first1=Yves|last1=Nievergelt|title=Foundations of Logic and Mathematics: Applications to Computer Science and Cryptography|publisher=Springer-Verlag|year=2002|page=[https://books.google.com/books?id=_H_nJdagqL8C&pg=PA158 158]}}.</ref> so this may also be taken as a definition.

== Examples ==

An example of an asymmetric relation is the "[[less than]]" relation <math>\,<\,</math> between [[real number]]s: if <math>x < y</math> then necessarily <math>y</math> is not less than <math>x.</math> 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 {{em|[[rock paper scissors]]}} relation: if <math>X</math> beats <math>Y,</math> then <math>Y</math> does not beat <math>X;</math> and if <math>X</math> beats <math>Y</math> and <math>Y</math> beats <math>Z,</math> then <math>X</math> does not beat <math>Z.</math>

[[Binary relation#Restriction|Restrictions]] and [[Converse relation|converses]] of asymmetric relations are also asymmetric. For example, the restriction of <math>\,<\,</math> from the reals to the integers is still asymmetric, and the converse or dual <math>\,>\,</math> of <math>\,<\,</math> is also asymmetric.

An asymmetric relation need not have the [[Connex relation|connex property]]. For example, the [[strict subset]] relation <math>\,\subsetneq\,</math> is asymmetric, and neither of the sets <math>\{1, 2\}</math> and <math>\{3, 4\}</math> 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 <math>\leq</math>. This is not asymmetric, because reversing for example, <math>x \leq x</math> produces <math>x \leq x</math> 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 relation|symmetric]]".

The [[empty relation]] is the only relation that is ([[Vacuous truth|vacuously]]) both symmetric and asymmetric.

== Properties ==

The following conditions are sufficient for a relation <math>R</math> to be asymmetric:<ref>{{cite arXiv |last1=Burghardt |first1=Jochen |title=Simple Laws about Nonprominent Properties of Binary Relations |date=2018 |class=math.LO |eprint=1806.05036}}</ref>
* <math>R</math> is irreflexive and anti-symmetric (this is also necessary)
* <math>R</math> is irreflexive and transitive. A [[transitive relation]] is asymmetric if and only if it is irreflexive:<ref>{{cite book|last1=Flaška|first1=V.|last2=Ježek|first2=J.|last3=Kepka|first3=T.|last4=Kortelainen|first4=J.|title=Transitive Closures of Binary Relations I|year=2007|publisher=School of Mathematics - Physics Charles University|location=Prague|page=1|url=http://www.karlin.mff.cuni.cz/~jezek/120/transitive1.pdf|access-date=2013-08-20|archive-url=https://web.archive.org/web/20131102214049/http://www.karlin.mff.cuni.cz/~jezek/120/transitive1.pdf|archive-date=2013-11-02|url-status=dead}} Lemma 1.1 (iv). Note that this source refers to asymmetric relations as "strictly antisymmetric".</ref> if <math>aRb</math> and <math>bRa,</math> transitivity gives <math>aRa,</math> contradicting irreflexivity. Such a relation is a [[strict partial order]].
* <math>R</math> is irreflexive and satisfies [[semiorder]] property 1 (there do not exist two mutually incomparable two-point linear orders)
* <math>R</math> is anti-transitive and anti-symmetric
* <math>R</math> is anti-transitive and transitive
* <math>R</math> is anti-transitive and satisfies semi-order property 1

== See also ==

* [[Tarski's axiomatization of the reals]] – part of this is the requirement that <math>\,<\,</math> over the real numbers be asymmetric.

== References ==

{{reflist}}

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