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

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

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

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

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

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

Литература

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