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

Определение

В математике бинарное отношение [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\colon (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\colon (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\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](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-й). Это относится и к группам людей, использующих разные экономические стратегии.

Отношение эквивалентности. Класс эквивалентности

Бинарное отношение [math] R [/math] на множестве [math] X [/math] называется отношением эквивалентности, если оно рефлексивно, симметрично и транзитивно. На письме обозначается, как [math]\thicksim{,} \thickapprox{,} ={,} \equiv{,} \Leftrightarrow{.} [/math] Примером отношения эквивалентности может быть отношение иметь одинаковый рост на множестве людей.

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

Бинарное отношение [math]\thicksim[/math], заданное на множестве [math]X[/math] называется отношение эквивалентности, если [math] \forall a \in X\colon (a\thicksim a) [/math] [math] \forall a, b \in X\colon (a\thicksim b) \Rightarrow (b\thicksim a)[/math] [math] \forall a, b, c \in X\colon (a\thicksim b) \land (b\thicksim c) \Rightarrow (a\thicksim c)[/math]

С отношением эквивалентности тесно связано разбиение множества на классы.

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

Система непустых подмножеств [math] \{ M_1, M_2,...,M_n\} [/math] множества [math] M [/math] называется разбиением этого множества, если [math] M = M_1 \cup M_2 \cup ... \cup M_n [/math] и при [math] i \ne j\colon ~M_i \cap M_j = \varnothing{.} [/math] Сами множества [math]M_1, M_2,...,M_n[/math] называются классами данного разбиения.

Классом эквивалентности [math] C(a) [/math] элемента a называется подмножество элементов эквивалентных a. Из определения следует, что, если [math] b \in C(a) [/math], то [math] С(a) = C(b) [/math]. Класс эквивалентности элемента a обозначают: [math] [a],~ a/^{\sim} , ~\overline{a} [/math].

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

Подмножество элементов множества [math] X [/math] эквивалентных данному элементу [math] a [/math] называется его классом эквивалентности, т. е. [math] [a] = \{ b ~ \in ~ X \mid a \thicksim b \}.[/math]

Пусть [math] a, b \in X [/math], тогда либо [math] [a] \cap [b] = \emptyset [/math], либо [math] [a] = [b] [/math]. Таким образом отношение эквивалентности порождает разбиение множества на классы эквивалентности. Семейство всех классов эквивалентности образует множество, называемое фактор-множеством, и обозначается [math] X/^{\thicksim} [/math].

Примеры отношений эквивалентности

• Равенство [math] ("=") [/math] - классический пример отношения эквивалентности на любом множестве, в т. ч. вещественных чисел
• Равенство по модулю: [math] a \equiv b(mod ~ m) [/math]
• В Евклидовой геометрии:
  • отношение подобия[math] ("\thicksim ") [/math]
  • отношение параллельности[math] ("\parallel ") [/math]
  • отношение конгруэнтности[math] ("\cong ") [/math]
• Разбиение многоугольников по количеству вершин
• Оношение равносильности на множестве уравнений
• Отношение равномощности множеств
• Отношение принадлежать к одному виду на множестве животных
• Отношение жить в одном городе на множестве людей

Неэквивалентные отношения

• Отношения частичного порядка не являются симметричными
• Отношение иметь наибольший общий делитель больше 1 - нетранзитивное. Например, [math] \gcd (2,6) = 2, \gcd (3,6) = 3, \gcd(2,3) = 1 [/math]
• Отношение быть родственниками на множестве людей - нерефлексивное. Человек не может быть родственником самому себе
• Разбиение треугольников по свойствам сторон(разносторонние, равнобедренные, равносторонние) не образует классы эквивалентности, так как множество равносторонних треугольников является подмножеством равнобедренных треугольников

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

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