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

Определение

В математике бинарное отношение [math]R[/math] на множестве [math]X[/math] называется транзитивным, если для любых трёх элементов a, b, c из выполнения отношений [math] aRb [/math] и [math] bRc [/math] следует выполнение отношения [math] aRc [/math]. Свойство транзитивности на отношениях в графе означает, что существоние пути из вершины a в b и из b в с влечёт существование пути из a в с. Формально записывается [math] (a \mapsto b) \land (b \mapsto c) \Rightarrow (a \mapsto c) [/math]. Также это можно понимать, что вершины графа a, b, c находятся в одной компоненте связности.

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

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

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

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

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

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

• Быть сыном(отцом, бабушкой). Но! Можно быть братом(сестрой) — тогда отношение транзитивное.
• Игра "Камень, ножницы, бумага". Камень побеждает ножницы, ножницы выигрывают у бумаги, но камень проигрывает бумаге и т. д.
• Отношение бойцовской силы между биологическими видами(1-й вид организмов вытесняет 2-й вид, 2-й вытесняет 3-й, а тот, в свою очередь, вытесняет 1-й). Это относится и к группам людей, использующих разные экономические стратегии.

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

• Wikipedia | Transitive relation
• Wkipedia | Intransivity
• Парадокс Кондорсе
• Отношения на графах
• Развитие понимания транзитивности и нетранзитивности