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

Материал из Викиконспекты
Версия от 18:31, 3 октября 2010; Андрей Шулаев (обсуждение | вклад) (определение и свойства)
(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск

Бинарное отношение [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], что и требовалось доказать.

Из последнего свойства следует, что пересечение любого количества транзитивных отношений транзитивно.