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

Материал из Викиконспекты
Перейти к: навигация, поиск

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

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

Определение:
Бинарное отношение [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, b[/math] одновременное выполнение отношений [math]a R b[/math] и [math]b R a[/math] невозможно.

Заметим, что антисимметричное отношение частный случай асимметричного.

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

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

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

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

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

См. также

Источники