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

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

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

[math]\displaystyle{ \forall a, b, c \in X,\ a R b \land b R c \Rightarrow a R c. }[/math]

Примеры

Равенство: [math]\displaystyle{ a=b }[/math] и [math]\displaystyle{ b=c }[/math], значит [math]\displaystyle{ a=c }[/math] (на самом деле, отношение равенства вместе с отношением эквивалентности и параллельности прямых обладает более сильным свойством также ещё и «равенства третьему» по причине своей симметричности).
Отношение порядка: [math]\displaystyle{ a\gt b }[/math] и [math]\displaystyle{ b\gt c }[/math], значит [math]\displaystyle{ a\gt c }[/math] или нестрогого порядка: [math]\displaystyle{ a \geqslant b }[/math] и [math]\displaystyle{ b \geqslant c }[/math], значит [math]\displaystyle{ a \geqslant c }[/math].
Параллельность прямых: [math]\displaystyle{ a||b }[/math] и [math]\displaystyle{ b||c }[/math], значит [math]\displaystyle{ a||c }[/math] (см. примечание к «равенству чисел»).
Импликация: [math]\displaystyle{ a \Rightarrow b }[/math] и [math]\displaystyle{ b \Rightarrow c }[/math], значит [math]\displaystyle{ a \Rightarrow c }[/math].
Эквивалентность: [math]\displaystyle{ a \Leftrightarrow b }[/math] и [math]\displaystyle{ b \Leftrightarrow c }[/math], значит [math]\displaystyle{ a \Leftrightarrow c }[/math] (см. примечание к «равенству чисел»).
Включение подмножества: если [math]\displaystyle{ b }[/math] является подмножеством [math]\displaystyle{ a }[/math], и в свою очередь [math]\displaystyle{ c }[/math] является подмножеством [math]\displaystyle{ b }[/math], тогда [math]\displaystyle{ c }[/math] является подмножеством [math]\displaystyle{ a }[/math].
Делимость: если [math]\displaystyle{ a }[/math] делится на [math]\displaystyle{ b }[/math], и [math]\displaystyle{ b }[/math] делится на [math]\displaystyle{ c }[/math], тогда [math]\displaystyle{ a }[/math] делится на [math]\displaystyle{ c }[/math].
Отношение следования вершин ориентированного графа: если вершина [math]\displaystyle{ a }[/math] достижима из вершины [math]\displaystyle{ b }[/math], а вершина [math]\displaystyle{ b }[/math], в свою очередь, — из [math]\displaystyle{ c }[/math], то [math]\displaystyle{ a }[/math] достижима из [math]\displaystyle{ c }[/math].

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

Игра «Камень, ножницы, бумага»: Камень сильнее Ножниц; Ножницы сильнее Бумаги; однако Камень не сильнее Бумаги ([math]\displaystyle{ t R s \land s R p \nRightarrow t R p }[/math]). Здесь "сильнее" не имеет буквального значения, поскольку "сила" Бумаги в том, что она просто обёртывает Камень.
В круговом турнире часто бывает ситуация, когда команда [math]\displaystyle{ A }[/math] победила команду [math]\displaystyle{ B }[/math], команда [math]\displaystyle{ B }[/math] — команду [math]\displaystyle{ C }[/math], а команда [math]\displaystyle{ C }[/math] победила команду [math]\displaystyle{ A }[/math]. Следовательно, в таком турнире отношение «победа» является нетранзитивным и не имеет эквивалента арифметической операции или арифметического отношения.
Отношение связи вершин граф-схемы алгоритма: например, если в граф-схеме алгоритма имеет место альтернативное ветвление, начинающееся условной вершиной [math]\displaystyle{ a^{\psi} }[/math], и две вершины [math]\displaystyle{ a_1 }[/math] и [math]\displaystyle{ a_2 }[/math], входящие в состав различных альтернативных ветвей ветвления, то вершина [math]\displaystyle{ a_1 }[/math] связана с [math]\displaystyle{ a^{\psi} }[/math], [math]\displaystyle{ a^{\psi} }[/math] связана с [math]\displaystyle{ a_2 }[/math], однако вершины [math]\displaystyle{ a_1 }[/math] и [math]\displaystyle{ a_2 }[/math] не связаны (они либо параллельны, либо альтернативны).
Отношение параллельности вершин параллельной граф-схемы алгоритма: например, если в составе параллельного фрагмента алгоритма в одной из ветвей находится вершина [math]\displaystyle{ a_1 }[/math], а другая представлена альтернативным ветвлением с двумя ветвями, одна из которых содержит вершину [math]\displaystyle{ a_2 }[/math], а другая — [math]\displaystyle{ a_3 }[/math], то вершины [math]\displaystyle{ a_2 }[/math] и [math]\displaystyle{ a_1 }[/math] находятся в отношении параллельности, также как и вершины [math]\displaystyle{ a_1 }[/math] и [math]\displaystyle{ a_3 }[/math], однако вершины [math]\displaystyle{ a_2 }[/math] и [math]\displaystyle{ a_3 }[/math] не параллельны (они находятся в отношении альтернативы).
Отношение альтернативы вершин граф-схемы алгоритма: например, если в составе альтернативного фрагмента алгоритма одна из ветвей представлена вершиной [math]\displaystyle{ a_1 }[/math], а другая включает последовательно выполняемые вершины [math]\displaystyle{ a_2 }[/math] и [math]\displaystyle{ a_3 }[/math], то вершины [math]\displaystyle{ a_2 }[/math] и [math]\displaystyle{ a_1 }[/math] находятся в отношении альтернативы, что справедливо и для вершин [math]\displaystyle{ a_1 }[/math] и [math]\displaystyle{ a_3 }[/math], однако вершины [math]\displaystyle{ a_2 }[/math] и [math]\displaystyle{ a_3 }[/math] не состоят в отношении альтернативы (они состоят в отношениях следования и связи).

См. также