Антисимметричное отношение — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 5: Строка 5:
 
{{Определение
 
{{Определение
 
|definition =
 
|definition =
[[Бинарное отношение]] <tex dpi=180>R</tex> на множестве <tex dpi=180>X</tex> называется '''антисимметричным''', если для любых элементов <tex dpi=180 dpi=180>a</tex> и <tex dpi=180>b</tex> множества <tex dpi=180>X</tex> из выполнения отношений <tex dpi=180>(aRb)</tex> и <tex dpi=180>(bRa)</tex> следует равенство <tex dpi=180>a</tex> и <tex dpi=180>b</tex>.
+
[[Бинарное отношение]] <tex>R</tex> на множестве <tex>X</tex> называется '''антисимметричным''', если для любых элементов <tex>a</tex> и <tex>b</tex> множества <tex>X</tex> из выполнения отношений <tex>(aRb)</tex> и <tex>(bRa)</tex> следует равенство <tex dpi=180>a</tex> и <tex>b</tex>.
 
}}
 
}}
:<tex dpi=180>\forall a, b \in X,\ R(a,b) \wedge R(b,a) \; \Rightarrow \; a = b</tex>
+
:<tex>\forall a, b \in X,\ R(a,b) \wedge R(b,a) \; \Rightarrow \; a = b</tex>
 
Или эквивалентное
 
Или эквивалентное
 
{{Определение
 
{{Определение
 
|definition =
 
|definition =
Бинарное отношение <tex dpi=180>R</tex> на множестве <tex dpi=180>X</tex> называется '''антисимметричным''', если для любых неравных элементов <tex dpi=180>a</tex> и <tex dpi=180>b</tex> множества <tex dpi=180>X</tex> из выполнения отношения <tex dpi=180>(aRb)</tex> следует невыполнение отношения <tex dpi=180>(bRa)</tex>.
+
Бинарное отношение <tex>R</tex> на множестве <tex>X</tex> называется '''антисимметричным''', если для любых неравных элементов <tex>a</tex> и <tex>b</tex> множества <tex>X</tex> из выполнения отношения <tex>(aRb)</tex> следует невыполнение отношения <tex>(bRa)</tex>.
 
}}
 
}}
:<tex dpi=180>\forall a, b \in X,\ R(a,b) \wedge a \ne b \Rightarrow \lnot  R(b,a)</tex>
+
:<tex>\forall a, b \in X,\ R(a,b) \wedge a \ne b \Rightarrow \lnot  R(b,a)</tex>
  
Определение антисимметричного отношения как <tex dpi=180> (aRb) \Rightarrow \neg(bRa) </tex> является избыточным (и потому неверным), поскольку из такого определения также следует [[Рефлексивное_отношение| антирефлексивность]] R.
+
Определение антисимметричного отношения как <tex> (aRb) \Rightarrow \neg(bRa) </tex> является избыточным (и потому неверным), поскольку из такого определения также следует [[Рефлексивное_отношение| антирефлексивность]] R.
  
 
Антисимметричность отношения не исключает симметричности. Существуют бинарные отношения:
 
Антисимметричность отношения не исключает симметричности. Существуют бинарные отношения:
Строка 26: Строка 26:
 
{{Определение
 
{{Определение
 
|definition =
 
|definition =
[[Бинарное отношение]] <tex dpi=180>R</tex> на множестве <tex dpi=180>X</tex> называется '''асимметричным''', если для любых элементов <tex dpi=180 dpi=180>a</tex> и <tex dpi=180>b</tex> множества <tex dpi=180>X</tex> одновременное выполнение отношений <tex dpi=180>a R b</tex> и <tex dpi=180>b R a</tex> невозможно.
+
[[Бинарное отношение]] <tex>R</tex> на множестве <tex>X</tex> называется '''асимметричным''', если для любых элементов <tex>a</tex> и <tex>b</tex> множества <tex>X</tex> одновременное выполнение отношений <tex>a R b</tex> и <tex>b R a</tex> невозможно.
 
}}
 
}}
 
Заметим, что антисимметричное отношение {{---}} частный случай асимметричного. Это наглядно показывают следующие рассуждения:
 
Заметим, что антисимметричное отношение {{---}} частный случай асимметричного. Это наглядно показывают следующие рассуждения:
Строка 37: Строка 37:
 
Примерами антисимметричных отношений являются, по определению, все отношения [http://ru.wikipedia.org/wiki/Вполне_упорядоченное_множество полного] и [http://ru.wikipedia.org/wiki/Частично_упорядоченное_множество частичного порядка](<tex> <, >, \le, \ge </tex> и другие).
 
Примерами антисимметричных отношений являются, по определению, все отношения [http://ru.wikipedia.org/wiki/Вполне_упорядоченное_множество полного] и [http://ru.wikipedia.org/wiki/Частично_упорядоченное_множество частичного порядка](<tex> <, >, \le, \ge </tex> и другие).
  
Антисимметрично отношение делимости на натуральных числах (если <tex dpi=150>a \mid b</tex> и <tex dpi=150>b \mid a</tex>, то <tex dpi=150>a=b</tex>)
+
Антисимметрично отношение делимости на натуральных числах (если <tex>a \mid b</tex> и <tex>b \mid a</tex>, то <tex>a=b</tex>)
  
Отношение включения на <tex dpi=180>2^U</tex>, где <tex dpi=180>U</tex> - универсум, антисимметрично (<tex dpi=180> A \subseteq B \wedge B \subseteq A \Rightarrow A = B</tex>).
+
Отношение включения на <tex>2^U</tex>, где <tex>U</tex> - универсум, антисимметрично (<tex> A \subseteq B \wedge B \subseteq A \Rightarrow A = B</tex>).
  
 
== Свойства антисимметричного отношения ==
 
== Свойства антисимметричного отношения ==
  
Матрица смежности антисимметричного отношения может содержать единицы на главной диагонали, притом если элемент <tex dpi=180>a_{ij}</tex> матрицы равен единице, то элемент <tex dpi=180>a_{ji}</tex> равен нулю. Отсюда следует, что матрица <tex dpi=180>M+M^T</tex>, где <tex dpi=180>M</tex> - матрица смежности некоторого антисимметричного отношения, может содержать 2 только на главной диагонали.
+
Матрица смежности антисимметричного отношения может содержать единицы на главной диагонали, притом если элемент <tex>a_{ij}</tex> матрицы равен единице, то элемент <tex>a_{ji}</tex> равен нулю. Отсюда следует, что матрица <tex>M+M^T</tex>, где <tex>M</tex> - матрица смежности некоторого антисимметричного отношения, может содержать 2 только на главной диагонали.
  
 
Ориентированный граф, изображающий антисимметричное отношение не имеет двух дуг с противоположной ориентацией между двумя различными вершинами, однако в нём могут быть петли.  
 
Ориентированный граф, изображающий антисимметричное отношение не имеет двух дуг с противоположной ориентацией между двумя различными вершинами, однако в нём могут быть петли.  
  
Если <tex dpi=180>a</tex> и <tex dpi=180>b</tex> - некоторые антисимметричные отношения, то антисимметричными также являются отношения:
+
Если <tex>a</tex> и <tex>b</tex> - некоторые антисимметричные отношения, то антисимметричными также являются отношения:
#<tex dpi=180>a\cap b</tex>
+
#<tex>a\cap b</tex>
#<tex dpi=180>a^{-1}</tex>
+
#<tex>a^{-1}</tex>
#<tex dpi=180>b^{-1}</tex>
+
#<tex>b^{-1}</tex>
  
 
==См. также==
 
==См. также==

Версия 16:57, 18 октября 2011

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

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

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

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

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

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

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

Примерами антисимметричных отношений являются, по определению, все отношения полного и частичного порядка([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]b[/math] - некоторые антисимметричные отношения, то антисимметричными также являются отношения:

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

См. также

Источники