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

Определение

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

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

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

Если это условие соблюдается не для всех троек a, b, c, то такое отношение называется нетранзитивным. Например, не для всех троек [math] a, b, c \in \mathbb{N} [/math] верно, что [math]~(a \nmid b)~ \land ~(b \nmid c)~ \Rightarrow ~(a \nmid c) [/math].

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

Бинарное отношение [math]R[/math], заданное на множестве [math]X,[/math] называется нетранзитивным, если [math]\exists ~a, b, c \in X\colon ~(aRb)~ \land ~(bRc)~ \land ~\neg(aRc)[/math].

Существует более "сильное" свойство — антитранзитивность. Под этим термином понимается, что для любых троек a, b, c отсутствует транзитивность. Антитранзитивное отношение, например — отношение победить в турнирах «на вылет»: если A победил игрока B, а B победил игрока C, то A не играл с C, следовательно, не мог его победить.

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

Бинарное отношение [math]R[/math], заданное на множестве [math]X,[/math] называется антитранзитивным, если для [math]\forall ~a, b, c \in X\colon ~(aRb)~ \land ~(bRc)~ \Rightarrow ~\neg(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]\colon ~(a \lt b), ~(b \lt c)~ \Rightarrow ~(~a \lt c)\;[/math]
  • нестрогое неравенство [math]\colon ~("\le ")\;[/math]
  • включение подмножества:
    • строгое подмножество [math]\colon ~ ("\subset ")\;[/math]
    • нестрогое подмножество [math]\colon ~ ("\subseteq ")\;[/math]
  • делимость:
    • [math](a \mid b), ~(b \mid c)~ \Rightarrow ~(a \mid c)\;[/math]
    • [math](a \,\vdots\, b), ~(b \,\vdots\, c)~ \Rightarrow ~(a \,\vdots\, c)\;[/math]
• Равенство [math]\colon ~(a = b), ~(b = c) \Rightarrow ~(a = c)\;[/math]
• Эквивалентность [math]\colon ~(a \Leftrightarrow b), ~(b \Leftrightarrow c)~ \Rightarrow ~(a \Leftrightarrow c)\;[/math]
• Импликация [math]\colon ~(a \Rightarrow b), ~(b \Rightarrow c)~ \Longrightarrow ~(a \Rightarrow c)\;[/math]
• Параллельность [math]\colon ~(a \parallel b), ~(b \parallel c)~ \Rightarrow ~(a \parallel c)\;[/math]
• Отношение подобия геометрических фигур
• Являться предком

Примеры нетранзитивных отношений

• Пищевая цепочка: это отношение не всегда является транзитивным (пример — волки едят оленей, олени едят траву, но волки не едят траву)
• Быть предпочтительнее чем. Если мы хотим яблоко вместо апельсина, а вместо яблока мы бы хотели арбуз, то это не значит, что мы предпочтём арбуз апельсину.
• Быть другом
• Являться коллегой по работе
• Быть подчиненным. Например, во времена феодального строя в Западной Европе была в ходу поговорка: Вассал моего вассала — не мой вассал.
• Быть похожим на другого человека

Примеры антитранзитивных отношений

• Быть сыном (отцом, бабушкой).
• Игра "Камень, ножницы, бумага". Камень побеждает ножницы, ножницы выигрывают у бумаги, но камень проигрывает бумаге и т. д.

Источники информации

• Wikipedia — Transitive relation
• Wikipedia — Intransivity
• Wikipedia — Отношение эквивалентности
• Парадокс Кондорсе
• Отношения на графах
• Развитие понимания транзитивности и нетранзитивности
• Бинарные отношения. Отношения эквивалентности (очень хорошая статья про отношения, в ней суть раскрыта более полно)