Меню Главная Случайная статья Настройки Транзитивность Материал из https://ru.wikipedia.org Транзитивность — свойство бинарного отношения: бинарное отношение ${\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 с., ил. — 148 900 экз.