Asymmetric relation

Summary

Transitive binary relations
Symmetric Antisymmetric Connected Well-founded Has joins Has meets Reflexive Irreflexive Asymmetric
Total, Semiconnex Anti-
reflexive
Equivalence relation Green tickY Green tickY
Preorder (Quasiorder) Green tickY
Partial order Green tickY Green tickY
Total preorder Green tickY Green tickY
Total order Green tickY Green tickY Green tickY
Prewellordering Green tickY Green tickY Green tickY
Well-quasi-ordering Green tickY Green tickY
Well-ordering Green tickY Green tickY Green tickY Green tickY
Lattice Green tickY Green tickY Green tickY Green tickY
Join-semilattice Green tickY Green tickY Green tickY
Meet-semilattice Green tickY Green tickY Green tickY
Strict partial order Green tickY Green tickY Green tickY
Strict weak order Green tickY Green tickY Green tickY
Strict total order Green tickY Green tickY Green tickY Green tickY
Symmetric Antisymmetric Connected Well-founded Has joins Has meets Reflexive Irreflexive Asymmetric
Definitions, for all and
Green tickY 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 Green tickY 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

edit

Preliminaries

edit

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

edit

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   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

edit

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

edit

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

edit

References

edit
  1. ^ Gries, David; Schneider, Fred B. (1993), A Logical Approach to Discrete Math, Springer-Verlag, p. 273.
  2. ^ Nievergelt, Yves (2002), Foundations of Logic and Mathematics: Applications to Computer Science and Cryptography, Springer-Verlag, p. 158.
  3. ^ Burghardt, Jochen (2018). "Simple Laws about Nonprominent Properties of Binary Relations". arXiv:1806.05036 [math.LO].
  4. ^ 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".