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

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

$\mathrm{\forall }(a,b,c\in X)a\star b\wedge 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$, то отношение называется антитранзитивным.

Литература

• Шаблон:БСЭ3
• Транзити́вность // Математический энциклопедический словарь / Гл. ред. Ю. В. Прохоров; Ред. Кол.: С. И. Адян, Н. С. Бахвалов, В. И. Битюцков, А. П. Ершов, Л. Д. Кудрявцев, А. Л. Онищик, А. Л. Юшкевич. — М.: «Советская энциклопедия», 1988. — С. 585. — 847 с. — 150 000 экз.
• Транзити́вность // Толковый словарь математических терминов : (Около 1800 терминов) : [Пособие для учителей] / О. В. Мантуров, Ю. К. Солнцев, Ю. И. Соркин, Н. Г. Федин; под ред. проф. В. А. Диткина. — Москва : Просвещение, 1965. — 539 с. : ил.; 22 см.
• Шаблон:Книга:БелЭн