Транзитивность

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

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

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

Примеры

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

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

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

См. также

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