Транзитивность — свойство бинарного отношения. Бинарное отношение на множестве называется транзитивным, если для любых трёх элементов множества выполнение отношений и влечёт выполнение отношения (запись означает отношение к ,  — к ,  — к ).

Формально, отношение транзитивно, если

Примеры править

  • Равенство:   и  , значит  .
  • Отношение порядка:   и  , значит   или нестрогого порядка:   и  , значит  .
  • Параллельность прямых:   и  , значит  .
  • Импликация:   и  , значит  .
  • Эквивалентность:   и  , значит  .
  • Включение подмножества: если   является подмножеством  , и в свою очередь   является подмножеством  , тогда   является подмножеством  .
  • Делимость: если   делится на  , и   делится на  , тогда   делится на  .
  • Сравнение чисел по модулю: два числа, сравнимые с третьим числом по одному и тому же модулю, сравнимы между собой.
  • Отношение следования вершин ориентированного графа: если вершина   достижима из вершины  , а вершина  , в свою очередь, — из  , то   достижима из  .

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

  • Игра «Камень, ножницы, бумага»: Камень сильнее Ножниц; Ножницы «сильнее» Бумаги; однако Камень не «сильнее» Бумаги ( ). Здесь «сильнее» не имеет буквального значения, поскольку сила Бумаги в том, что она просто обёртывает Камень.
  • В круговом турнире часто бывает ситуация, когда команда   победила команду  , команда   — команду  , а команда   победила команду  . Следовательно, в таком турнире отношение «победа» является нетранзитивным и не имеет эквивалента арифметической операции или арифметического отношения.
  • Отношение связи вершин граф-схемы алгоритма: например, если в граф-схеме алгоритма имеет место альтернативное ветвление, начинающееся условной вершиной  , и две вершины   и  , входящие в состав различных альтернативных ветвей ветвления, то вершина   связана с  ,   связана с  , однако вершины   и   не связаны (они либо параллельны, либо альтернативны).
  • Отношение параллельности вершин параллельной граф-схемы алгоритма: например, если в составе параллельного фрагмента алгоритма в одной из ветвей находится вершина  , а другая представлена альтернативным ветвлением с двумя ветвями, одна из которых содержит вершину  , а другая —  , то вершины   и   находятся в отношении параллельности, также как и вершины   и  , однако вершины   и   не параллельны (они находятся в отношении альтернативы).
  • Отношение альтернативы вершин граф-схемы алгоритма: например, если в составе альтернативного фрагмента алгоритма одна из ветвей представлена вершиной  , а другая включает последовательно выполняемые вершины   и  , то вершины   и   находятся в отношении альтернативы, что справедливо и для вершин   и  , однако вершины   и   не состоят в отношении альтернативы (они состоят в отношениях следования и связи).

См. также править