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

Определение

Бинарное отношение [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)~ \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]\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]
• Отношение подобия геометрических фигур
• Являться предком

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

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

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

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

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

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

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

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

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

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