Открыть главное меню

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

Асимметри́чное отноше́ние в математикебинарное отношение на некотором множестве обладающее для любых из следующим свойством «невзаимности»[1]: если связано данным отношением с то не связано с . Формальная запись:

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

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

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

Не следует путать асимметричное и антисимметричное отношение — последнее не исключает возможности и одновременно, если Упомянутое выше отношение «меньше или равно» антисимметрично, но не асимметрично. Общее правило[2]:

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

СвойстваПравить

  • Если отношение   асимметрично, то его обращение[en] и сужение также асимметричны. Например, ограничение вещественного отношения «меньше» на целые числа асимметрично, таково же и его обращение — отношение «больше».
  • Транзитивное отношение асимметрично тогда и только тогда, когда оно антирефлексивно[3]. В самом деле,   и   в силу транзитивности влечёт   откуда видно, что «взаимные отношения» невозможны.
  • Не все асимметричные отношения представляют строгий частичный порядок. Пример: отношение типа «камень, ножницы, бумага» является асимметричным, но не транзитивным (даже «антитранзитивным»):
    • если   одолевает  , то   не одолевает  
    • если   одолевает   и   одолевает   то   не одолевает   .
  • Асимметричное отношение не обязано быть полным[en], то есть нет гарантии, что для любой пары элементов   имеет место   или   Например, отношение «быть собственным подмножеством» асимметрично, однако не все подмножества   связаны им в ту или иную сторону.

ПрименениеПравить

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

ПримечанияПравить

  1. Gries, David & Schneider, Fred B. (1993), A Logical Approach to Discrete Math, Springer-Verlag, с. 273 .
  2. Nievergelt, Yves (2002), Foundations of Logic and Mathematics: Applications to Computer Science and Cryptography, Springer-Verlag, с. 158 .
  3. Flaška, V. Transitive Closures of Binary Relations I / V. Flaška, J. Ježek, T. Kepka … [и др.]. — Prague : School of Mathematics - Physics Charles University, 2007. — P. 1. Архивная копия от 2 ноября 2013 на Wayback Machine Lemma 1.1 (iv). Note that this source refers to asymmetric relations as "strictly antisymmetric".

ЛитератураПравить

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

СсылкиПравить