Транзитивное отношение

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

Бинарное отношение [math]R[/math], заданное на множестве [math]X[/math] называется транзитивным, если для [math]\forall a, b, c \in X[/math] выполняется [math]aRb, bRc \Rightarrow aRc[/math]

Свойства

  • Если отношение [math]R[/math] транзитивно, то обратное отношение [math]R^{-1}[/math] также транзитивно. Пусть [math]aR^{-1}b, bR^{-1}c[/math], но по определению обратного отношения [math]cRb, bRa[/math]. Так как [math]R[/math] транзитивно, то [math]cRa[/math] и [math]aR^{-1}c[/math], что и требовалось доказать.
  • Если отношения [math]R, S[/math] транзитивны, то отношение [math]T = R \cap S[/math] тразнитивно. Пусть [math]aTb, bTc \Rightarrow aRb, aSb, bRc, bSc[/math]. Из транзитивности [math]R, S[/math] следует [math]aRc, aSc[/math], но из определения пересечения отношений получаем [math]aTc[/math], что и требовалось доказать.
  • Из последнего свойства следует, что пересечение любого количества транзитивных отношений транзитивно.

Примеры

Следующие отношения являются транзитивными:

  • отношение [math]\le[/math] на множестве вещественных чисел
  • отношение [math]\subset[/math] на множестве наборов
  • отношение параллельности на множестве прямых