Переходное отношение

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

• 1 Определение
• 2 Примеры
• 3 Свойства
  • 3.1 Свойства замыкания
  • 3.2 Другие свойства
• 4 Транзитивные расширения и транзитивное замыкание
• 5 Свойства отношения, требующие транзитивности
• 6 Подсчет транзитивных отношений
• 7 Связанные свойства
• 8 См. Также
• 9 Примечания
• 10 Ссылки
• 11 Внешние ссылки

Бинарные отношения
Симметричные Антисимметричный Connex Хорошо обоснованный Имеет соединения Соответствует Отношение эквивалентности ✓ ✗ ✗ ✗ ✗ ✗ Предварительный заказ (Квазипорядок) ✗ ✗ ✗ ✗ ✗ ✗ Частичный заказ ✗ ✓ ✗ ✗ ✗ ✗ Общий предварительный заказ ✗ ✗ ✓ ✗ ✗ ✗ Общий заказ ✗ ✓ ✓ ✗ ✗ ✗ Предварительное упорядочение ✗ ✗ ✓ ✓ ✗ ✗ Правильное квазиупорядочение ✗ ✗ ✗ ✓ ✗ ✗ Правильное упорядочение ✗ ✓ ✓ ✓ ✗ ✗ Решетка ✗ ✓ ✗ ✗ ✓ ✓ Соединение-полурешетка ✗ ✓ ✗ ✗ ✓ ✗ Встреча-полурешетка ✗ ✓ ✗ ✗ ✗ ✓
Знак «✓» указывает, что свойство столбца требуется в определении строки.. Например, определение отношения эквивалентности требует, чтобы оно было симметричным.. Все определения неявно требуют транзитивности и рефлексивности.

Однородное отношение R на множестве X является переходное отношение ion if,

для всех a, b, c ∈ X, если a R b и b R c, то a R c.

Или в терминах логики первого порядка :

$\forall \; a,\; b,\; c\; \in \; X:\; (a\; R\; b\; \wedge \; b\; R\; c)\; \Rightarrow \; a\; R\; c,\; \{\backslash \; displaystyle\; \backslash \; forall\; a,\; b,\; c\; \backslash \; in\; X:\; (aRb\; \backslash \; wedge\; bRc)\; \backslash \; Rightarrow\; aRc,\}$

где a R b - это инфиксная нотация для (a, b) ∈ R.

В качестве нематематического примера отношение «является предком» является транзитивным. Например, если Эми - предок Бекки, а Бекки - предок Кэрри, то Эми тоже является предком Кэрри.

С другой стороны, «является биологическим родителем» не является транзитивным отношением, потому что если Алиса является биологическим родителем Бренды, а Бренда является биологическим родителем Клэр, тогда Алиса не является биологическим родителем. Клэр. Более того, это антитранзитивный : Алиса никогда не может быть биологическим родителем Клэр.

«Больше, чем», «не меньше, чем», и «равно» (равенство ) - это транзитивные отношения на различных наборах, например, на множестве реальных числа или набор натуральных чисел:

всякий раз, когда x>y и y>z, затем также x>z

всякий раз, когда x ≥ y и y ≥ z, тогда также x ≥ z

всякий раз, когда x = y и y = z, то также x = z.

Еще примеры транзитивных отношений:

• «является подмножеством из» (включение множества, отношение на множествах)
• «делит» (делимость, отношение к натуральным числам)
• «подразумевает» (импликация, обозначаемая «⇒», отношение на предложения )

Примеры нетранзитивных отношений:

• "является преемником " (отношения на натуральных числах)
• "является членом множества" (обозначается как "∈")
• "является перпендикулярно к" (отношение на линиях в евклидовой геометрии )

пустое отношение на любом множестве $X\; \{\backslash \; displaystyle\; X\}$является транзитивным, потому что нет элементов $a,\; b,\; c\; \in \; X\; \{\backslash \; displaystyle\; a,\; b,\; c\; \backslash \; in\; X\}$так, что $a\; R\; b\; \{\backslash \; displaystyle\; aRb\}$и $b\; R\; c\; \{\backslash \; displaystyle\; bRc\}$, и, следовательно, условие транзитивности истинно пусто. Отношение R, содержащее только одну упорядоченную пару, также является транзитивным: если упорядоченная пара имеет вид $(x,\; x)\; \{\backslash \; displaystyle\; (x,\; x)\}$для некоторый $x\; \in \; X\; \{\backslash \; displaystyle\; x\; \backslash \; in\; X\}$только такие элементы $a,\; b,\; c\; \in \; X\; \{\backslash \; displaystyle\; a,\; b,\; c\; \backslash \; in\; X\}$равны $a\; =\; b\; =\; c\; =\; x\; \{\backslash \; displaystyle\; a\; =\; b\; =\; c\; =\; x\}$, и действительно, в этом случае $a\; R\; c\; \{\backslash \; displaystyle\; aRc\}$, а если упорядоченная пара не имеет формы $(x,\; x)\; \{\backslash \; displaystyle\; (x,\; x)\}$, то таких элементов $a,\; b\; нет,\; c\; \in \; X\; \{\backslash \; displaystyle\; a,\; b,\; c\; \backslash \; in\; X\}$и, следовательно, $R\; \{\backslash \; displaystyle\; R\}$является вакуумно транзитивным.

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

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

Другие свойства

Транзитивное отношение является асимметричным, если и только если оно иррефлексивное.

. Транзитивное отношение не обязательно должно быть рефлексивным. Когда это так, это называется предварительным заказом. Например, на множестве X = {1,2,3}:

• R = {(1,1), (2,2), (3,3), (1,3), (3,2) } рефлексивен, но не транзитивен, так как пара (1,2) отсутствует,
• R = {(1,1), (2,2), (3,3), (1,3)} рефлексивен так же, как и транзитивен, поэтому это предпорядок,
• R = {(1,1), (2,2), (3,3)} рефлексивен так же, как и транзитивен, другой предварительный порядок.

Пусть R будет двоичным отношением на множестве X. Транзитивное расширение R, обозначенное R 1, является наименьшим двоичным отношением на X, таким что R 1 содержит R, и если (a, b) ∈ R и (b, c) ∈ R, то (a, c) ∈ R 1. Например, предположим, что X - это набор городов, некоторые из которых связаны дорогами. Пусть R будет отношением в городах, где (A, B) ∈ R, если существует дорога, напрямую связывающая город A и город B. Это отношение не обязательно должно быть транзитивным. Транзитивное расширение этого отношения может быть определено как (A, C) ∈ R 1, если вы можете перемещаться между городами A и C, используя не более двух дорог.

Если отношение транзитивно, то его транзитивное расширение есть само, то есть, если R - транзитивное отношение, то R 1 = R.

Транзитивное расширение R 1 будет обозначаться как R 2, и, продолжая таким образом, в целом, транзитивное расширение R i будет R i + 1. Транзитивное замыкание R, обозначенное R * или R, является объединением множеств R, R 1, R 2,....

Транзитивное замыкание отношения является транзитивным отношением.

Отношение «является биологическим родителем» для группы людей не является транзитивным отношением. Однако в биологии часто возникает необходимость рассматривать вопрос о рождении отцовства на протяжении произвольного числа поколений: отношение «является родоначальником» является транзитивным отношением, и это транзитивное завершение отношения «является родителем».

В приведенном выше примере городов и дорог (A, C) ∈ R * при условии, что вы можете перемещаться между городами A и C по любому количеству дорог.

• Предварительный порядок - рефлексивное транзитивное отношение
• Частичный порядок - антисимметричный предварительный порядок
• Общий предварительный заказ - общий предварительный заказ
• Отношение эквивалентности - симметричный предварительный заказ
• Строгий слабый порядок - строгий частичный порядок, в котором несопоставимость является отношением эквивалентности
• Общий порядок - общее, антисимметричное транзитивное отношение

Нет общей формулы для подсчета числа транзитивных отношений на конечном множестве (последовательность A006905 в OEIS ) известна. Однако существует формула для определения количества отношений, которые одновременно являются рефлексивными, симметричными и транзитивными - другими словами, отношения эквивалентности - (последовательность A000110 в OEIS ), симметричные и транзитивные, симметричные, транзитивные и антисимметричные, а также полные, транзитивные и антисимметричные. Пфайффер добился некоторого прогресса в этом направлении, выразив отношения с комбинациями этих свойств в терминах друг друга, но все же вычислить какое-либо одно из них сложно. См. Также.

Количество n-элементных бинарных отношений разных типов

Элементы	Любые	Переходные	Рефлексивные	Предварительный заказ	Частичный порядок	Общий предварительный заказ	Всего порядок	Отношение эквивалентности
0	1	1	1	1	1	1	1	1
1	2	2	1	1	1	1	1	1
2	16	13	4	4	3	3	2	2
3	512	171	64	29	19	13	6	5
4	65,536	3,994	4,096	355	219	75	24	15
n	2		2			∑n. к = 0 к! S (n, k)	n!	∑n. k = 0 S (n, k)
OEIS	A002416	A006905	A053763	A000798	A001035	A000670	A000142	A000110

Игра камень-ножницы-бумага основана на непереходном и антитранзитивном соотношении «x бьет y».

Отношение R называется непереходный, если он не транзитивен, то есть если xRy и yRz, но не xRz, для некоторых x, y, z. Напротив, отношение R называется антитранзитивным, если xRy и yRz всегда подразумевают, что xRz не выполняется. Например, отношение, определяемое xRy, если xy является четным числом, является непереходным, но не антитранзитивным. Отношение, определяемое xRy, если x четно, а y нечетное, одновременно транзитивно и антитранзитивно. Отношение, определяемое xRy, если x является порядковым номером для y, является как непереходным, так и антитранзитивным. Неожиданные примеры нетранзитивности возникают в таких ситуациях, как политические вопросы или групповые предпочтения.

Обобщенное на стохастические версии (стохастическая транзитивность ), исследование транзитивности находит применения в теории принятия решений, психометрия и полезные модели.

A квазитранзитивное отношение - еще одно обобщение; требуется, чтобы он был транзитивным только на своей несимметричной части. Такие отношения используются в теории социального выбора или микроэкономике.

• Переходная редукция
• Нетранзитивная игра в кости
• Теория рационального выбора
• Гипотетический силлогизм - транзитивность материального условного

• Гримальди, Ральф П. (1994), Дискретная и комбинаторная математика (3-е изд.), Аддисон-Уэсли, ISBN 0-201-19912-2
• Лю, CL (1985), Элементы дискретной математики, МакГроу-Хилл, ISBN 0-07-038133-X
• Гюнтер Шмидт, 2010. Реляционная математика. Cambridge University Press, ISBN 978-0-521-76268-7.
• Смит, Дуглас; Эгген, Морис; Сент-Андр, Ричард (2006), Переход к высшей математике (6-е изд.), Брукс / Коул, ISBN 978-0-534-39900-9

• , Энциклопедия математики, EMS Press, 2001 [1994]
• Транзитивность в действии at cut-the-knot