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

Асимметри́чное отноше́ние в математике — бинарное отношение ${\displaystyle R}$ на некотором множестве ${\displaystyle X,}$ обладающее для любых ${\displaystyle a,b}$ из ${\displaystyle X}$ следующим свойством «невзаимности»^[1]: если ${\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.}$ Упомянутое выше отношение «меньше или равно» антисимметрично, но не асимметрично. Общее правило^[2]:

• Если отношение ${\displaystyle R}$ асимметрично, то его обращение и сужение также асимметричны. Например, ограничение вещественного отношения «меньше» на целые числа асимметрично, таково же и его обращение — отношение «больше».
• Транзитивное отношение асимметрично тогда и только тогда, когда оно антирефлексивно^[3]. В самом деле, ${\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}$ связаны им в ту или иную сторону.

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

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

• Difference Between Asymmetric & Antisymmetric Relation