Введение

Тип бинарного отношения

В математике бинарное отношение R на множестве X называется транзитивным, если для любых элементов a, b, c из X, всякий раз, когда R связывает a с b и b с c, то R связывает и a с c.

Любое частичное упорядочение и любое отношение эквивалентности являются транзитивными. Например, неравенство и равенство между действительными числами являются транзитивными: если a < b и b < c, то a < c; и если a = b и b = c, то a = c.

Свойства закрытия

Обратное (инверсное) транзитивное отношение всегда транзитивно. Например, зная, что отношение "является подмножеством" транзитивно, а "является надмножеством" – его обратное, можно заключить, что последнее также транзитивно. Пересечение двух транзитивных отношений всегда транзитивно. Например, зная, что отношения "родился раньше" и "имеет то же имя, что и" транзитивны, можно заключить, что отношение "родился раньше и имеет то же имя, что и" также транзитивно. Объединение двух транзитивных отношений не обязательно должно быть транзитивным. Например, отношение "родился раньше или имеет то же имя" не является транзитивным, поскольку, например, Герберт Гувер связан с Франклином Д. Рузвельтом, который, в свою очередь, связан с Франклином Пирсом, в то время как Гувер не связан с Франклином Пирсом. Дополнение транзитивного отношения не обязательно должно быть транзитивным. Например, хотя отношение "равно" транзитивно, отношение "не равно" транзитивно только на множествах, содержащих не более одного элемента.

Переходные расширения и переходные закрытия

Пусть R будет бинарным отношением на множестве X. Транзитивное расширение R, обозначаемое R1, является наименьшим бинарным отношением на X, таким, что R1 содержит R, и если (a, b) ∈ R и (b, c) ∈ R, то (a, c) ∈ R1. Например, предположим, что X – это множество городов, некоторые из которых соединены дорогами. Пусть R – отношение на городах, где (A, B) ∈ R, если существует дорога, непосредственно связывающая город A и город B. Это отношение не обязательно должно быть транзитивным. Транзитивное расширение этого отношения может быть определено как (A, C) ∈ R1, если можно добраться из города A в город C, используя не более двух дорог. Если отношение является транзитивным, то его транзитивным расширением является оно само, то есть, если R является транзитивным отношением, то R1 = R. Транзитивное расширение R1 будет обозначаться R2, и продолжая таким образом, в общем случае, транзитивное расширение Ri будет Ri + 1. Транзитивное замыкание R, обозначаемое R* или R^(∞), – это объединение множеств R, R1, R2. Транзитивное замыкание отношения является транзитивным отношением. Однако существует формула для нахождения числа отношений, которые одновременно являются рефлексивными, симметричными и транзитивными – другими словами, отношений эквивалентности –, которые являются симметричными и транзитивными, симметричными, транзитивными и антисимметричными, а также полными, транзитивными и антисимметричными. Пфайффер добился некоторого прогресса в этом направлении, выражая отношения с различными комбинациями этих свойств друг через друга, но вычисление любого из них все еще является сложной задачей. См. также Brinkmann и McKay (2005). Поскольку рефлексивизация любого транзитивного отношения является предпорядком, число транзитивных отношений на множестве из n элементов не более чем в 2n раз превышает число предпорядков, таким образом, оно асимптотически… по результатам Клейтмана и Ротшильда.