Английская Википедия:Asymmetric relation
Шаблон:Short description Шаблон:Distinguish Шаблон:Binary relations In mathematics, an asymmetric relation is a binary relation <math>R</math> on a 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>[1]
Formal definition
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>" The binary relation <math>R</math> is called Шаблон:Em 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 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,
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>
An example of an asymmetric relation is the "less than" relation <math>\,<\,</math> between real numbers: if <math>x < y</math> then necessarily <math>y</math> is not less than <math>x.</math> The "less than or equal" relation <math>\,\leq,</math> on the other hand, is not asymmetric, because reversing for example, <math>x \leq x</math> produces <math>x \leq x</math> and both are true. Asymmetry is not the same thing as "not symmetric": the less-than-or-equal relation is an example of a relation that is neither symmetric nor asymmetric. The empty relation is the only relation that is (vacuously) both symmetric and asymmetric.
Properties
- A relation is asymmetric if and only if it is both antisymmetric and irreflexive.[2]
- Restrictions and 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 inverse <math>\,>\,</math> of <math>\,<\,</math> is also asymmetric.
- A transitive relation is asymmetric if and only if it is irreflexive:[3] if <math>aRb</math> and <math>bRa,</math> transitivity gives <math>aRa,</math> contradicting irreflexivity.
- As a consequence, a relation is transitive and asymmetric if and only if it is a strict partial order.
- Not all asymmetric relations are strict partial orders. An example of an asymmetric non-transitive, even antitransitive relation is the Шаблон:Em 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>
- An asymmetric relation need not have the 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.
See also
- Tarski's axiomatization of the reals – part of this is the requirement that <math>\,<\,</math> over the real numbers be asymmetric.
References
- ↑ Шаблон:Citation.
- ↑ Шаблон:Citation.
- ↑ Шаблон:Cite book Lemma 1.1 (iv). Note that this source refers to asymmetric relations as "strictly antisymmetric".
