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

Транзити́вность — свойство бинарного отношения: бинарное отношение ${\displaystyle \star }$ на множестве ${\displaystyle X}$ транзитивно, если для любых трёх элементов множества ${\displaystyle a}$, ${\displaystyle b}$, ${\displaystyle c}$ выполнение отношений ${\displaystyle a\star b}$ и ${\displaystyle b\star c}$ влечёт выполнение отношения ${\displaystyle a\star c}$:

${\displaystyle \forall (a,b,c\in X)\,a\star b\land b\star c\Rightarrow a\star c}$.

Одно из важнейших свойств бинарных отношений; по определению транзитивны отношения эквивалетнтности (в частности, равенство), отношения порядка (например, отношение включения множеств), импликация, отношение следования вершин ориентированного графа, отношение параллельности прямых (из ${\displaystyle a||b}$ и ${\displaystyle b||c}$ следует ${\displaystyle a||c}$). В теории чисел транзитивны делимость (если ${\displaystyle a}$ делится на ${\displaystyle b}$, и ${\displaystyle b}$ делится на ${\displaystyle c}$, то ${\displaystyle a}$ делится на ${\displaystyle c}$) и сравнение по модулю.

Транзитивное замыкание — пересечение всех транзитивных отношений, содержащих заданное — наименьшее транзитивное отношение, содержащееся в данном.

Нетранзитивность — отсутствие транзитивности, когда из выполнения ${\displaystyle a\star b}$ и ${\displaystyle b\star c}$ выполнение ${\displaystyle a\star c}$ не следует. Нетранзитивно, например, отношение смежности вершин в графе (смежная ко смежной вершина может быть смежной с исходной, а может и не быть). Отношение толерантности ­— рефлексивное и симметричное отношение, которые может быть нетранзитивным. Если же из выполнения ${\displaystyle a\star b}$ и ${\displaystyle b\star c}$ следует невыполнение ${\displaystyle a\star c}$, то отношение называется антитранзитивным.

• Транзитивность // Тихоходки — Ульяново. — М. : Советская энциклопедия, 1977. — С. 146. — (Большая советская энциклопедия : [в 30 т.] / гл. ред. А. М. Прохоров ; 1969—1978, т. 26).
• Транзитивность // Математический энциклопедический словарь / Гл. ред. Ю. В. Прохоров. Ред. кол. С. И. Адян, Н. С. Бахвалов и др. — М.: Советская энциклопедия, 1988. — С. 585. — 847 с. — 150 000 экз.
• Мантуров О. В., Солнцев Ю. К., Соркин Ю. И., Федин Н. Г. Транзити́вность // Толковый словарь математических терминов : (Около 1800 терминов) : [Пособие для учителей] (рус.) / под ред. проф. В. А. Диткина. — Москва: Просвещение, 1965. — 539 с.
• Транзітыўнасць // Беларуская энцыклапедыя: У 18 т. Т. 15: Следавікі — Трыо (бел.) / Рэдкал.: Г. П. Пашкоў і інш. — Мінск: БелЭн, 2002. — С. 505. — 10 000 экз. — ISBN 985-11-0251-2.