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

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

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

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

Предварительные

Бинарное отношение на является любым подмножеством заданной записи тогда и только тогда, когда , что означает, что является сокращением для Выражение читается как « связано с помощью ». ${\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}$

что в логике первого порядка можно записать так: Отношение асимметрично тогда и только тогда, когда оно одновременно антисимметрично и иррефлексивно ^[2] , поэтому это также можно принять в качестве определения. $${\displaystyle \forall a,b\in X:\lnot (aRb\wedge bRa).}$$

Примеры

Примером асимметричного отношения является отношение " меньше чем " между действительными числами : если то обязательно не меньше чем В более общем смысле, любой строгий частичный порядок является асимметричным отношением. Не все асимметричные отношения являются строгими частичными порядками. Примером асимметричного нетранзитивного, даже антитранзитивного отношения является отношение "камень-ножницы-бумага" : если бьет , то не бьет и если бьет и бьет , то не бьет ${\displaystyle \,<\,}$ ${\displaystyle x<y}$ ${\displaystyle y}$ ${\displaystyle x.}$ ${\displaystyle X}$ ${\displaystyle Y,}$ ${\displaystyle Y}$ ${\displaystyle X;}$ ${\displaystyle X}$ ${\displaystyle Y}$ ${\displaystyle Y}$ ${\displaystyle Z,}$ ${\displaystyle X}$ ${\displaystyle Z.}$

Ограничения и обратные отношения асимметричных отношений также асимметричны. Например, ограничение с вещественных чисел на целые числа все еще асимметрично, а обратное или двойственное отношение также асимметрично. ${\displaystyle \,<\,}$ ${\displaystyle \,>\,}$ ${\displaystyle \,<\,}$

Асимметричное отношение не обязательно должно иметь свойство connex . Например, отношение strict subset является асимметричным, и ни одно из множеств и не является строгим подмножеством другого. Отношение connex тогда и только тогда, когда его дополнение асимметрично. ${\displaystyle \,\subsetneq \,}$ ${\displaystyle \{1,2\}}$ ${\displaystyle \{3,4\}}$

Непримером является отношение "меньше или равно" . Оно не асимметрично, потому что, например, при обратном порядке получается и оба являются истинными. Отношение "меньше или равно" является примером отношения, которое не является ни симметричным, ни асимметричным, показывая, что асимметрия - это не то же самое, что "не симметрично ". ${\displaystyle \leq }$ ${\displaystyle x\leq x}$ ${\displaystyle x\leq x}$

Пустое отношение — единственное отношение, которое ( пусто ) одновременно симметрично и асимметрично.

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

Для того чтобы отношение было асимметричным, достаточно следующих условий: ^[3] ${\displaystyle R}$

• ${\displaystyle R}$является нерефлексивным и антисимметричным (это также необходимо)
• ${\displaystyle R}$является иррефлексивным и транзитивным. Транзитивное отношение асимметрично тогда и только тогда, когда оно иррефлексивно: ^[4] если и транзитивность даёт противоречивую иррефлексивность. Такое отношение является строгим частичным порядком . ${\displaystyle aRb}$ ${\displaystyle bRa,}$ ${\displaystyle aRa,}$
• ${\displaystyle R}$является иррефлексивным и удовлетворяет свойству полупорядка 1 (не существует двух взаимно несравнимых двухточечных линейных порядков)
• ${\displaystyle R}$является антитранзитивным и антисимметричным
• ${\displaystyle R}$является антитранзитивным и транзитивным
• ${\displaystyle R}$является антитранзитивным и удовлетворяет свойству полупорядка 1

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

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

Ссылки

1. Грайс, Дэвид ; Шнайдер, Фред Б. (1993), Логический подход к дискретной математике , Springer-Verlag, стр. 273.
2. Нивергельт, Ив (2002), Основы логики и математики: приложения к информатике и криптографии , Springer-Verlag, стр. 158.
3. Бургхардт, Йохен (2018). «Простые законы о незначительных свойствах бинарных отношений». arXiv : 1806.05036 [math.LO].
4. Flaška, V.; Ježek, J.; Kepka, T.; Kortelainen, J. (2007). Transitive Closures of Binary Relations I (PDF) . Прага: School of Mathematics - Physics Karlov University. стр. 1. Архивировано из оригинала (PDF) 2013-11-02 . Получено 2013-08-20 .Лемма 1.1 (iv). Обратите внимание, что этот источник называет асимметричные отношения «строго антисимметричными».