WikiSort.ru - Не сортированное

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

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

${\displaystyle \forall a,b,c\in X,\ aRb\land bRc\Rightarrow aRc}$ .

Примеры

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

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

• Игра «Камень, ножницы, бумага»: Камень сильнее Ножниц; Ножницы сильнее Бумаги; однако Камень не сильнее Бумаги (${\displaystyle tRs\land sRp\nRightarrow tRp}$ ). Здесь "сильнее" не имеет буквального значения, поскольку "сила" Бумаги в том, что она просто обертывает Камень.
• В круговом турнире часто бывает ситуация, когда команда ${\displaystyle A}$ победила команду ${\displaystyle B}$ , команда ${\displaystyle B}$  — команду ${\displaystyle C}$ , а команда ${\displaystyle C}$ победила команду ${\displaystyle A}$ . Следовательно, в таком турнире отношение «победа» является нетранзитивным и не имеет эквивалента арифметической операции или арифметического отношения.
• Отношение связи вершин граф-схемы алгоритма: например, если в граф-схеме алгоритма имеет место альтернативное ветвление, начинающееся условной вершиной ${\displaystyle a^{\psi }}$ , и две вершины ${\displaystyle a_{1}}$ и ${\displaystyle a_{2}}$ , входящие в состав различных альтернативных ветвей ветвления, то вершина ${\displaystyle a_{1}}$ связана с ${\displaystyle a^{\psi }}$ , ${\displaystyle a^{\psi }}$ связана с ${\displaystyle a_{2}}$ , однако вершины ${\displaystyle a_{1}}$ и ${\displaystyle a_{2}}$ не связаны (они либо параллельны, либо альтернативны).
• Отношение параллельности вершин параллельной граф-схемы алгоритма: например, если в составе параллельного фрагмента алгоритма в одной из ветвей находится вершина ${\displaystyle a_{1}}$ , а другая представлена альтернативным ветвлением с двумя ветвями, одна из которых содержит вершину ${\displaystyle a_{2}}$ , а другая — ${\displaystyle a_{3}}$ , то вершины ${\displaystyle a_{2}}$ и ${\displaystyle a_{1}}$ находятся в отношении параллельности, также как и вершины ${\displaystyle a_{1}}$ и ${\displaystyle a_{3}}$ , однако вершины ${\displaystyle a_{2}}$ и ${\displaystyle a_{3}}$ не параллельны (они находятся в отношении альтернативы).
• Отношение альтернативы вершин граф-схемы алгоритма: например, если в составе альтернативного фрагмента алгоритма одна из ветвей представлена вершиной ${\displaystyle a_{1}}$ , а другая включает последовательно выполняемые вершины ${\displaystyle a_{2}}$ и ${\displaystyle a_{3}}$ , то вершины ${\displaystyle a_{2}}$ и ${\displaystyle a_{1}}$ находятся в отношении альтернативы, что справедливо и для вершин ${\displaystyle a_{1}}$ и ${\displaystyle a_{3}}$ , однако вершины ${\displaystyle a_{2}}$ и ${\displaystyle a_{3}}$ не состоят в отношении альтернативы (они состоят в отношениях следования и связи).

См. также

• Нетранзитивность
• Равенство третьему
• Закон обратного отношения между содержанием и объёмом понятия

Это заготовка статьи по математике. Вы можете помочь проекту, дополнив её.