Транзитивность — свойство бинарного отношения . Бинарное отношение ${\displaystyle R}$ на множестве ${\displaystyle X}$ называется транзитивным , если для любых трёх элементов множества ${\displaystyle a,b,c}$ выполнение отношений ${\displaystyle aRb}$ и ${\displaystyle bRc}$ влечёт выполнение отношения ${\displaystyle aRc}$ (запись ${\displaystyle aRb}$ означает отношение ${\displaystyle a}$ к ${\displaystyle b}$ , ${\displaystyle bRc}$ — ${\displaystyle b}$ к ${\displaystyle c}$ , ${\displaystyle aRc}$ — ${\displaystyle a}$ к ${\displaystyle c}$ ).

Формально, отношение ${\displaystyle R}$ транзитивно, если

${\displaystyle \forall a,b,c\in X,\ aRb\land bRc\Rightarrow aRc.}$

Примеры

• Равенство : ${\displaystyle a=b}$ и ${\displaystyle b=c}$ , значит ${\displaystyle a=c}$ .
• Отношение порядка : ${\displaystyle a>b}$ и ${\displaystyle b>c}$ , значит ${\displaystyle a>c}$ или нестрогого порядка : ${\displaystyle a\geqslant b}$ и ${\displaystyle b\geqslant c}$ , значит ${\displaystyle a\geqslant c}$ .
• Параллельность прямых : ${\displaystyle a||b}$ и ${\displaystyle b||c}$ , значит ${\displaystyle a||c}$ .
• Импликация : ${\displaystyle a\Rightarrow b}$ и ${\displaystyle b\Rightarrow c}$ , значит ${\displaystyle a\Rightarrow c}$ .
• Эквивалентность : ${\displaystyle a\Leftrightarrow b}$ и ${\displaystyle b\Leftrightarrow c}$ , значит ${\displaystyle a\Leftrightarrow c}$ .
• Включение подмножества : если ${\displaystyle b}$ является подмножеством ${\displaystyle a}$ , и в свою очередь ${\displaystyle c}$ является подмножеством ${\displaystyle b}$ , тогда ${\displaystyle c}$ является подмножеством ${\displaystyle a}$ .
• Делимость : если ${\displaystyle a}$ делится на ${\displaystyle b}$ , и ${\displaystyle b}$ делится на ${\displaystyle c}$ , тогда ${\displaystyle a}$ делится на ${\displaystyle c}$ .
• Сравнение чисел по модулю : два числа, сравнимые с третьим числом по одному и тому же модулю, сравнимы между собой.
• вершин ориентированного графа : если вершина ${\displaystyle a}$ достижима из вершины ${\displaystyle b}$ , а вершина ${\displaystyle b}$ , в свою очередь, — из ${\displaystyle c}$ , то ${\displaystyle a}$ достижима из ${\displaystyle c}$ .

Примеры отсутствия транзитивности (встречаются, когда логические высказывания связаны не арифметическими отношениями или их эквивалентами в языке, а другими смысловыми отношениями):

• Игра « Камень, ножницы, бумага » : Камень сильнее Ножниц; Ножницы «сильнее» Бумаги; однако Камень не «сильнее» Бумаги ( ${\displaystyle tRs\land sRp\nRightarrow tRp}$ ). Здесь «сильнее» не имеет буквального значения, поскольку сила Бумаги в том, что она просто обёртывает Камень.
• В круговом турнире часто бывает ситуация, когда команда ${\displaystyle A}$ победила команду ${\displaystyle B}$ , команда ${\displaystyle B}$ — команду ${\displaystyle C}$ , а команда ${\displaystyle C}$ победила команду ${\displaystyle A}$ . Следовательно, в таком турнире отношение «победа» является нетранзитивным и не имеет эквивалента арифметической операции или арифметического отношения.
• вершин граф-схемы алгоритма : например, если в граф-схеме алгоритма имеет место альтернативное ветвление, начинающееся условной вершиной ${\displaystyle a^{\psi }}$ , и две вершины ${\displaystyle a_{1}}$ и ${\displaystyle a_{2}}$ , входящие в состав различных альтернативных ветвей ветвления, то вершина ${\displaystyle a_{1}}$ связана с ${\displaystyle a^{\psi }}$ , ${\displaystyle a^{\psi }}$ связана с ${\displaystyle a_{2}}$ , однако вершины ${\displaystyle a_{1}}$ и ${\displaystyle a_{2}}$ не связаны (они либо параллельны, либо альтернативны).
• вершин параллельной граф-схемы алгоритма: например, если в составе параллельного фрагмента алгоритма в одной из ветвей находится вершина ${\displaystyle a_{1}}$ , а другая представлена альтернативным ветвлением с двумя ветвями, одна из которых содержит вершину ${\displaystyle a_{2}}$ , а другая — ${\displaystyle a_{3}}$ , то вершины ${\displaystyle a_{2}}$ и ${\displaystyle a_{1}}$ находятся в отношении параллельности, также как и вершины ${\displaystyle a_{1}}$ и ${\displaystyle a_{3}}$ , однако вершины ${\displaystyle a_{2}}$ и ${\displaystyle a_{3}}$ не параллельны (они находятся в отношении альтернативы).
• вершин граф-схемы алгоритма: например, если в составе альтернативного фрагмента алгоритма одна из ветвей представлена вершиной ${\displaystyle a_{1}}$ , а другая включает последовательно выполняемые вершины ${\displaystyle a_{2}}$ и ${\displaystyle a_{3}}$ , то вершины ${\displaystyle a_{2}}$ и ${\displaystyle a_{1}}$ находятся в отношении альтернативы, что справедливо и для вершин ${\displaystyle a_{1}}$ и ${\displaystyle a_{3}}$ , однако вершины ${\displaystyle a_{2}}$ и ${\displaystyle a_{3}}$ не состоят в отношении альтернативы (они состоят в отношениях следования и связи).

См. также

• Нетранзитивность
• Закон обратного отношения между содержанием и объёмом понятия