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

Бинарное отношение, которое никогда не возникает в обоих направлениях.

В математике асимметричное отношение — это бинарное отношение на множестве , где для всех если связано с то не связано с ^[1 ] ${\displaystyle R}$ ${\displaystyle X}$ ${\displaystyle a,b\in X,}$ ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle b}$ ${\displaystyle a.}$

Формальное определение

Бинарное отношение on — это любое подмножество заданного write тогда и только тогда, когда это означает, что это сокращение для Выражение читается как « связано с » Бинарное отношение называется асимметричным, если для всех если истинно, то ложно; то есть если то Это можно записать в обозначениях логики первого порядка как ${\displaystyle X}$ ${\displaystyle R}$ ${\displaystyle X\times X.}$ ${\displaystyle a,b\in X,}$ ${\displaystyle aRb}$ ${\displaystyle (a,b)\in R,}$ ${\displaystyle aRb}$ ${\displaystyle (a,b)\in R.}$ ${\displaystyle aRb}$ ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle R.}$ ${\displaystyle R}$ ${\displaystyle a,b\in X,}$ ${\displaystyle aRb}$ ${\displaystyle bRa}$ ${\displaystyle (a,b)\in R}$ ${\displaystyle (b,a)\not \in R.}$

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

Логически эквивалентное определение:

для всех хотя бы один из и является ложным , ${\displaystyle a,b\in X,}$ ${\displaystyle aRb}$ ${\displaystyle bRa}$

что в логике первого порядка можно записать как:

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

Примером асимметричного отношения является отношение « меньше чем » между действительными числами : if then обязательно не меньше. С другой стороны, отношение «меньше или равно» не является асимметричным, потому что, например, реверсирование дает и оба являются истинный. Асимметрия — это не то же самое, что «несимметрично » : отношение «меньше или равно» — это пример отношения, которое не является ни симметричным, ни асимметричным. Пустое отношение — единственное отношение, которое ( пусто ) одновременно симметрично и асимметрично. ${\displaystyle \,<\,}$ ${\displaystyle x<y}$ ${\displaystyle y}$ ${\displaystyle x.}$ ${\displaystyle \,\leq ,}$ ${\displaystyle x\leq x}$ ${\displaystyle x\leq x}$

Характеристики

• Отношение асимметрично тогда и только тогда, когда оно одновременно антисимметрично и иррефлексивно . ^[2]
• Ограничения и обращения асимметричных отношений также асимметричны. Например, ограничение от действительных чисел к целым числам по-прежнему асимметрично, и обратное значение также асимметрично. ${\displaystyle \,<\,}$ ${\displaystyle \,>\,}$ ${\displaystyle \,<\,}$
• Транзитивное отношение асимметрично тогда и только тогда, когда оно иррефлексивно: ^[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.}$
• Асимметричное отношение не обязательно должно иметь свойство connex . Например, отношение строгого подмножества асимметрично, и ни одно из множеств и не является строгим подмножеством другого. Отношение является связным тогда и только тогда, когда его дополнение асимметрично. ${\displaystyle \,\subsetneq \,}$ ${\displaystyle \{1,2\}}$ ${\displaystyle \{3,4\}}$

Смотрите также

• Аксиоматизация действительных чисел Тарским - отчасти это требование, чтобы действительные числа были асимметричными. ${\displaystyle \,<\,}$

Рекомендации

1. Грис, Дэвид ; Шнайдер, Фред Б. (1993), Логический подход к дискретной математике , Springer-Verlag, стр. 273.
2. Нивергельт, Ив (2002), Основы логики и математики: приложения к информатике и криптографии , Springer-Verlag, p. 158.
3. Флашка, В.; Ежек, Дж.; Кепка, Т.; Кортелайнен, Дж. (2007). Транзитивные замыкания бинарных отношений I (PDF) . Прага: Школа математики – Физика Карлова университета. п. 1. Архивировано из оригинала (PDF) 2 ноября 2013 г. Проверено 20 августа 2013 г.Лемма 1.1 (iv). Обратите внимание, что в этом источнике асимметричные отношения называются «строго антисимметричными».