Асимметричное отношение - NiNa.Az

Асимметри́чное отноше́ние в математике — бинарное отношение ${\displaystyle R}$ на некотором множестве ${\displaystyle X,}$ обладающее для любых ${\displaystyle a,b}$ из ${\displaystyle X}$ следующим свойством «невзаимности»: если ${\displaystyle a}$ связано данным отношением с ${\displaystyle b,}$ то ${\displaystyle b}$ не связано с ${\displaystyle a}$. Формальная запись:

${\displaystyle \forall a,b\in X(aRb\Rightarrow \lnot (bRa))}$

Примером может служить отношение «меньше» между вещественными числами: если ${\displaystyle x<y}$, то невозможно, чтобы одновременно ${\displaystyle y<x}$. Напротив, отношение «меньше или равно» не является асимметричным, так как в случае ${\displaystyle x=y}$ верны оба неравенства: ${\displaystyle x\leqslant y;\ y\leqslant x.}$ Другой пример: отношение «быть родителем».

Из определения вытекает, что для непустого асимметричного отношения ${\displaystyle R}$ ситуация ${\displaystyle aRa}$ невозможна ни для какого элемента ${\displaystyle a.}$ Такие отношения называют антирефлексивными (в другой терминологии, иррефлексивными).

Антиподом асимметричного является симметричное отношение, для которого отношение всегда взаимно: если ${\displaystyle aRb,}$ то ${\displaystyle bRa.}$ Единственное бинарное отношение, одновременно симметричное и асимметричное — это пустое отношение.

Не следует путать асимметричное и антисимметричное отношение — последнее не исключает возможности ${\displaystyle aRb}$ и ${\displaystyle bRa}$ одновременно, если ${\displaystyle a=b.}$ Упомянутое выше отношение «меньше или равно» антисимметрично, но не асимметрично. Общее правило:

Бинарное отношение асимметрично тогда и только тогда, когда оно антисимметрично и при этом антирефлексивно.

Свойства

• Если отношение ${\displaystyle R}$ асимметрично, то его обращение и сужение также асимметричны. Например, ограничение вещественного отношения «меньше» на целые числа асимметрично, таково же и его обращение — отношение «больше».
• Транзитивное отношение асимметрично тогда и только тогда, когда оно антирефлексивно. В самом деле, ${\displaystyle aRb}$ и ${\displaystyle bRa}$ в силу транзитивности влечёт ${\displaystyle aRa,}$ откуда видно, что «взаимные отношения» невозможны.
  • Следствие: отношение является транзитивным и асимметричным тогда и только тогда, когда это строгий частичный порядок.
• Не все асимметричные отношения представляют строгий частичный порядок. Пример: отношение типа «камень, ножницы, бумага» является асимметричным, но не транзитивным (даже «антитранзитивным»):
  • если ${\displaystyle x}$ одолевает ${\displaystyle y}$, то ${\displaystyle y}$ не одолевает ${\displaystyle x;}$
  • если ${\displaystyle x}$ одолевает ${\displaystyle y}$ и ${\displaystyle y}$ одолевает ${\displaystyle z,}$ то ${\displaystyle x}$ не одолевает ${\displaystyle z}$ .
• Асимметричное отношение не обязано быть ^[англ.], то есть нет гарантии, что для любой пары элементов ${\displaystyle x,y}$ имеет место ${\displaystyle xRy}$ или ${\displaystyle yRx.}$ Например, отношение «быть собственным подмножеством» асимметрично, однако не все подмножества ${\displaystyle X}$ связаны им в ту или иную сторону.

Применение

См., например, аксиоматику Тарского для вещественных чисел – в ней одна из аксиом требует асимметричности отношения «меньше».

Примечания

1. Gries, David; Schneider, Fred B. (1993), A Logical Approach to Discrete Math, Springer-Verlag, p. 273 {{citation}}: Указан более чем один параметр |first1= and |first= (справка); Указан более чем один параметр |last1= and |last= (справка).
2. Nievergelt, Yves (2002), Foundations of Logic and Mathematics: Applications to Computer Science and Cryptography, Springer-Verlag, p. 158 {{citation}}: Указан более чем один параметр |first1= and |first= (справка); Указан более чем один параметр |last1= and |last= (справка).
3. Flaška, V.; Flaška, V.; Ježek, J.; Kepka, T.; Kortelainen, J. Transitive Closures of Binary Relations I (англ.). — Prague: School of Mathematics - Physics Charles University, 2007. — P. 1. Архивировано 2 ноября 2013 года. Архивированная копия  (неопр.). Дата обращения: 2 сентября 2018. Архивировано из оригинала 2 ноября 2013 года. Lemma 1.1 (iv). Note that this source refers to asymmetric relations as "strictly antisymmetric".

Литература

• Алескеров Ф. Т., Хабина Э. Л., Шварц Д. А. Бинарные отношения, графы и коллективные решения. — М.: Учебники Высшей школы экономики, 2006. — 300 с.

Ссылки

• Difference Between Asymmetric & Antisymmetric Relation