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

Антисимметрия — одно из важнейших свойств бинарных отношений на множестве.

Основные определения

Определение:

Бинарное отношение [math]R[/math] на множестве [math]X[/math] называется антисимметричным, если для любых элементов [math]a[/math] и [math]b[/math] множества [math]X[/math] из выполнения отношений [math](aRb)[/math] и [math](bRa)[/math] следует равенство [math]a[/math] и [math]b[/math].

[math]\forall a, b \in X,\ R(a,b) \wedge R(b,a) \; \Rightarrow \; a = b[/math]

Или эквивалентное

Определение:

Бинарное отношение [math]R[/math] на множестве [math]X[/math] называется антисимметричным, если для любых неравных элементов [math]a[/math] и [math]b[/math] множества [math]X[/math] из выполнения отношения [math](aRb)[/math] следует невыполнение отношения [math](bRa)[/math].

[math]\forall a, b \in X,\ R(a,b) \wedge a \ne b \Rightarrow \lnot R(b,a)[/math]

Определение антисимметричного отношения как [math] (aRb) \Rightarrow \neg(bRa) [/math] является избыточным (и потому неверным), поскольку из такого определения также следует антирефлексивность R.

Антисимметричность отношения не исключает симметричности. Существуют бинарные отношения:

• одновременно симметричные и антисимметричные (отношение равенства);
• ни симметричные, ни антисимметричные;
• симметричные, но не антисимметричные;
• антисимметричные, но не симметричные ("меньше или равно", "больше или равно");

Следует различать антисимметричное и асимметричное бинарные отношения.

Определение:

Бинарное отношение [math]R[/math] на множестве [math]X[/math] называется асимметричным, если для любых элементов [math]a[/math] и [math]b[/math] множества [math]X[/math] одновременное выполнение отношений [math]a R b[/math] и [math]b R a[/math] невозможно.

Некоторые виды бинарных отношений на диаграмме Эйлера-Венна. Здесь AnS — антисимметричное отношение; As — асимметричное отношение; Ar — антирефлексивное отношение; S — симметричное отношение

Заметим, что асимметричное отношение — частный случай антисимметричного. Этот факт объясняют следующие рассуждения:

• Главная диагональ матрицы смежности асимметричного отношения заполнена нулями; в остальном свойства матрицы повторяют свойства матрицы смежности антисимметричного отношения.
• Граф асимметричного отношения не содержит петель; в остальном свойства графа повторяют свойства графа антисимметричного отношения.

(см. Свойства антисимметричного отношения)

Асимметричность, в отличии от антисимметричности, исключает симметричность (см. рисунок). Заметим также, что множество асимметричных отношений есть пересечение множества антисимметричных отношений с множеством антирефлексивных отношений.

Примеры антисимметричных отношений

Примерами антисимметричных отношений являются, по определению, все отношения полного и частичного порядка([math] \lt , \gt , \le, \ge [/math] и другие).

Антисимметрично отношение делимости на натуральных числах (если [math]a \mid b[/math] и [math]b \mid a[/math], то [math]a=b[/math])

Отношение включения на [math]2^U[/math], где [math]U[/math] - универсум, антисимметрично ([math] A \subseteq B \wedge B \subseteq A \Rightarrow A = B[/math]).

Свойства антисимметричного отношения

Граф антисимметричного отношения (не имеет кратных ребер)

Граф отношения, не являющегося антисимметричным

Матрица смежности антисимметричного отношения может содержать единицы на главной диагонали, притом если элемент [math]a_{ij}[/math] матрицы равен единице, то элемент [math]a_{ji}[/math] равен нулю. Отсюда следует, что матрица [math]M+M^T[/math], где [math]M[/math] - матрица смежности некоторого антисимметричного отношения, может содержать 2 только на главной диагонали.

Например, если [math]A[/math] — матрица смежности отношения "[math]\le[/math]" на [math]X \subset N, X = \{1, 2, 3 ,4 , 5\}[/math]; [math]B[/math] — матрица смежности отношения делимости на том же множестве [math]X[/math], то

[math] 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 } [/math]

[math] 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 } [/math]

Ориентированный граф, изображающий антисимметричное отношение не имеет двух дуг с противоположной ориентацией между двумя различными вершинами, однако в нём могут быть петли.

Если [math]a[/math] и [math]b[/math] - некоторые антисимметричные отношения, то антисимметричными также являются отношения:

1. [math]a\cap b[/math]
2. [math]a^{-1}[/math]
3. [math]b^{-1}[/math]

Однако объединение и композиция [math]a[/math] и [math]b[/math] может не сохранять антирефлексивности.

См. также

• Бинарное отношение
• Симметричное отношение

Источники

• Антисимметричное отношение — Википедия
• Антисимметричное отношение — статья на английской Википедии
• Статья на сайте МАДИ