Изменения

[[Бинарное отношение]] <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>

Бинарное отношение <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.

Антирефлексивное антисимметричное отношение иногда называют асимметричным. Следует различать антисимметричное и асимметричное бинарные отношенияэти два понятия.Формальное определение:

[[Бинарное отношение]] <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> невозможно.

== Примеры Примерами антисимметричных отношений являются, по определению, все отношения [[Отношение порядка|полного и частичного порядка]] (<tex> <, >, \leqslant, \geqslant </tex> и другие). Антисимметрично отношение делимости на натуральных числах (если <tex>a \mid b</tex> и <tex>b \mid a</tex>, то <tex>a==b</tex>)

Примерами антисимметричных отношений являются, по определениюОтношение включения на <tex>2^U</tex>, все отношения [http://ru.wikipedia.org/wiki/Вполне_упорядоченное_множество полного] и [http://ru.wikipedia.org/wiki/Частично_упорядоченное_множество частичного порядка](где <tex> U</tex> {{---}} универсум, антисимметрично (<tex>, A \subseteq B \wedge B \le, subseteq A \ge Rightarrow A = B</tex> и другие).

[[Файл:antisym.png|400px|thumb|right|Граф антисимметричного отношения (не имеет кратных ребер)]][[Файл:nonantisym.png|400px|thumb|right|Граф отношения, не являющегося антисимметричным]]Матрица смежности антисимметричного отношения может содержать единицы на главной диагонали, притом если элемент <tex>a_{ij}</tex> матрицы равен единице, то элемент <tex>a_{ji}</tex> равен нулю.  Например, если <tex>A</tex> {{---}} матрица смежности отношения "<tex>\leqslant</tex>" на <tex>X \subset N, X = \{1, 2, 3 ,4 , 5\}</tex>; <tex>B</tex> {{---}} матрица смежности отношения делимости на том же множестве <tex>X</tex>, то <tex> A=\bordermatrix{ & 1 & 2 & 3 & 4 & 5 \cr 1 & 1 & 1 & 1 & 1 & 1 \cr 2 & 0 & 1 & 1 & 1 & 1 \cr 3 & 0 & 0 & 1 & 1 & 1 \cr 4 & 0 & 0 & 0 & 1 & 1 \cr 5 & 0 & 0 & 0 & 0 & 1 \cr } </tex> <tex> B=\bordermatrix{ & 1 & 2 & 3 & 4 & 5 \cr 1 & 1 & 1 & 1 & 1 & 1 \cr 2 & 0 & 1 & 0 & 1 & 0 \cr 3 & 0 & 0 & 1 & 0 & 0 \cr 4 & 0 & 0 & 0 & 1 & 0 \cr 5 & 0 & 0 & 0 & 0 & 1 \cr } </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] [[Категория: Дискретная математика и алгоритмы]][[Категория: Отношения]]