1632
правки
Изменения
м
Антисимметрия {{---}} одно из важнейших свойств бинарных отношений на множестве.
[[Файл:eulervenn1.png|350px|thumb|right|Некоторые виды бинарных отношений на диаграмме Эйлера-Венна. Здесь <span style="color:red">AnS {{---}} антисимметричное отношение; <span style="color:orange">As {{---}} асимметричное отношение; <span style="color:blue">Ar {{---}} антирефлексивное отношение; <span style="color:green">S {{---}} симметричное отношение]]
Заметим, что асимметричное отношение {{---}} частный случай антисимметричного. Этот факт объясняют следующие рассуждения:
*Главная диагональ матрицы смежности асимметричного отношения заполнена нулями; в остальном свойства матрицы повторяют свойства матрицы смежности антисимметричного отношения.
*Граф асимметричного отношения не содержит петель; в остальном свойства графа повторяют свойства графа антисимметричного отношения.
(см. [[Антисимметричное_отношение#Свойства_антисимметричного_отношения| Свойства антисимметричного отношения]])
Асимметричность, в отличии от антисимметричности, исключает симметричность (см. рисунок). Заметим также, что множество асимметричных отношений есть пересечение множества антисимметричных отношений с множеством антирефлексивных отношений.
rollbackEdits.php mass rollback
== Основные определения ==
{{Определение
|definition =
[[Бинарное отношение]] <tex>R</tex> на множестве <tex>X</tex> называется '''антисимметричным'''(англ. ''antisymmetric binary relation''), если для любых элементов <tex>a</tex> и <tex>b</tex> множества <tex>X</tex> из выполнения отношений <tex>(aRb)</tex> и <tex>(bRa)</tex> следует равенство <tex>a</tex> и <tex>b</tex>.
}}
:<tex>\forall a, b \in X,\ R(a,b) aRb \wedge R(b,a) bRa \; \Rightarrow \; a = b</tex>
Или эквивалентное
{{Определение
|definition =
Бинарное отношение <tex>R</tex> на множестве <tex>X</tex> называется '''антисимметричным''', если для любых неравных элементов <tex>a</tex> и <tex>b</tex> множества <tex>X</tex> из выполнения отношения <tex>(aRb)</tex> следует невыполнение отношения <tex>(bRa)</tex>.
}}
:<tex>\forall a, b \in X,\ R(a,b) aRb \wedge a \ne b \Rightarrow \lnot R(b,a)bRa</tex>
Определение антисимметричного отношения как <tex> (aRb) \Rightarrow \neg(bRa) </tex> является избыточным (и потому неверным), поскольку из такого определения также следует [[Рефлексивное_отношение| антирефлексивность]] R.
Антисимметричность отношения не исключает симметричности. Существуют бинарные отношения:
*антисимметричные, но не симметричные ("меньше или равно", "больше или равно");
Антирефлексивное антисимметричное отношение иногда называют асимметричным. Следует различать антисимметричное и асимметричное бинарные отношенияэти два понятия.Формальное определение:
{{Определение
|definition =
[[Бинарное отношение]] <tex>R</tex> на множестве <tex>X</tex> называется '''асимметричным'''(англ. ''asymmetric binary relation''), если для любых элементов <tex>a</tex> и <tex>b</tex> множества <tex>X</tex> одновременное выполнение отношений <tex>a R b</tex> и <tex>b R a</tex> невозможно.
}}
== Примеры антисимметричных отношений ==
Примерами антисимметричных отношений являются, по определению, все отношения [http://ru.wikipedia.org/wiki/Вполне_упорядоченное_множество [Отношение порядка|полного] и [http://ru.wikipedia.org/wiki/Частично_упорядоченное_множество частичного порядка]](<tex> <, >, \leleqslant, \ge geqslant </tex> и другие).
Антисимметрично отношение делимости на натуральных числах (если <tex>a \mid b</tex> и <tex>b \mid a</tex>, то <tex>a=b</tex>)
Отношение включения на <tex>2^U</tex>, где <tex>U</tex> {{- --}} универсум, антисимметрично (<tex> A \subseteq B \wedge B \subseteq A \Rightarrow A = B</tex>).
== Свойства антисимметричного отношения ==
[[Файл:antisym.png|200px400px|thumb|right|Граф антисимметричного отношения (не имеет кратных ребер)]][[Файл:nonantisym.png|200px400px|thumb|right|Граф отношения, не являющегося антисимметричным]]Матрица смежности антисимметричного отношения может содержать единицы на главной диагонали, притом если элемент <tex>a_{ij}</tex> матрицы равен единице, то элемент <tex>a_{ji}</tex> равен нулю. Отсюда следует, что матрица <tex>M+M^T</tex>, где <tex>M</tex> - матрица смежности некоторого антисимметричного отношения, может содержать 2 только на главной диагонали.
Например, если <tex>A</tex> {{---}} матрица смежности отношения "<tex>\leleqslant</tex>" на <tex>X \subset N, X = \{1, 2, 3 ,4 , 5\}</tex>; <tex>B</tex> {{---}} матрица смежности отношения делимости на том же множестве <tex>X</tex>, то
<tex> A=\bordermatrix{
5 & 0 & 0 & 0 & 0 & 1 \cr } </tex>
Ориентированный граф, изображающий антисимметричное отношение , не имеет двух дуг с противоположной ориентацией между двумя различными вершинами, однако в нём могут быть петли.
Если <tex>a</tex> и <tex>b</tex> {{- --}} некоторые антисимметричные отношения, то антисимметричными также являются отношения:
#<tex>a\cap b</tex>
#<tex>a^{-1}</tex>
#<tex>b^{-1}</tex>
Однако объединение и композиция <tex>a</tex> и <tex>b</tex> может могут не сохранять антирефлексивностиантисимметричности.
==См. также==
* [[Симметричное отношение]]
== Источники информации ==
* [http://ru.wikipedia.org/wiki/Антисимметричное_отношение Антисимметричное отношение {{---}} Википедия]
* [http://en.wikipedia.org/wiki/Antisymmetric_relation Антисимметричное отношение {{---}} статья на английской Википедии]
* [http://www.madi.ru/study/kafedra/asu_new/metod_new/mil/tpr09_13.shtml#1 Статья на сайте МАДИ]
* [http://en.wikipedia.org/wiki/Asymmetric_relation Wikipedia | Asymmetric relation]
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Отношения]]
