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

В математике бинарное отношение $R$ на множестве $X$ называется транзитивным, если для любых трёх элементов множества $a, b, c$ выполнение отношений $a R b$ и $b R c$ влечёт выполнение отношения $a R c$.

Формально, отношение $R$ транзитивно, если $\forall a, b, c \in X,\ a R b \land b R c \Rightarrow a R c$.

Примеры

• Равенство: $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$.

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

• Игра «Камень, ножницы, бумага»: Камень сильнее Ножниц; Ножницы сильнее Бумаги; однако Камень не сильнее Бумаги ($t R s \land s R p \nRightarrow t R p$). Здесь "сильнее" не имеет буквального значения, поскольку "сила" Бумаги в том, что она просто обертывает Камень.
• В круговом турнире часто бывает ситуация, когда команда 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$ не состоят в отношении альтернативы (они состоят в отношениях следования и связи).

См. также

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