Асимметричное отношение

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

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

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

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

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

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

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

Свойства

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

Применение

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

Литература

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

Ссылки

• Difference Between Asymmetric & Antisymmetric Relation