Транзитивное отношение

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

Каждое частичное упорядочение и каждое отношение эквивалентности транзитивны. Например, меньше и равенство среди действительных чисел транзитивны: если $a < b$ и $b < c,$ то $a < c$ ; и если $x = y$ и $y = z,$ то $x = z$ .

Определение

Однородное отношение $R$ на множестве $X$ является транзитивным отношением , если ^[1]

для всех

a, b, c \in X

, если

a R b

b R c

, то

a R c

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

\forall a,b,c\in X:(aRb\wedge bRc)\Rightarrow aRc

где $a R b$ — инфиксная запись для $(a, b) \in R$ .

Примеры

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

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

Нетранзитивные, неантитранзитивные отношения включают спортивные мероприятия (расписания плей-офф), «знает» и «общается с».

Примеры «больше», «меньше», «равен» ( равенство ) являются транзитивными отношениями на различных множествах. Как и множество действительных чисел или множество натуральных чисел:

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

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

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

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

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

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

«является преемником » (отношение натуральных чисел)
«является членом множества» (обозначается как «∈») ^[2]
« перпендикулярно » (отношение на прямых в евклидовой геометрии )

Пустое отношение на любом множестве транзитивно ^[3], поскольку не существует элементов, таких что и , и, следовательно, условие транзитивности является пустопорожне истинным . Отношение $R,$ содержащее только одну упорядоченную пару , также транзитивно: если упорядоченная пара имеет вид для некоторых , то единственными такими элементами являются , и действительно в этом случае , тогда как если упорядоченная пара не имеет вида , то таких элементов нет и, следовательно, является пустопорожне транзитивным. $X$ $a,b,c\in X$ $aRb$ $bRc$ $(x,x)$ $x\in X$ $a,b,c\in X$ $a=b=c=x$ $aRc$ $(x,x)$ $a,b,c\in X$ $R$

Характеристики

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

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

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

Транзитивное отношение асимметрично тогда и только тогда, когда оно иррефлексивно . ^[6]

Транзитивное отношение не обязательно должно быть рефлексивным . Когда это так, оно называется предпорядком . Например, на множестве 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$ $)$ $\in$ $R$ и $($ $b$ $,$ $c$ $) \in$ $R ,$ то $($ $a$ $,$ $c$ $) \in$ $R$ $1$ . ^[7] Например, предположим, что $X$ — это множество городов, некоторые из которых соединены дорогами. Пусть $R$ — отношение на городах, где $($ $A$ $,$ $B$ $) \in$ $R$ , если есть дорога, напрямую соединяющая город $A$ и город $B$ . Это отношение не обязательно должно быть транзитивным. Транзитивное расширение этого отношения можно определить как $($ $A$ $,$ $C$ $) \in$ $R$ $1$ , если вы можете путешествовать между городами $A$ и $C,$ используя не более двух дорог.

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

Транзитивное расширение $R 1$ будет обозначаться как $R 2$ $, и$ продолжая таким образом, в общем случае транзитивное расширение $R i$ будет обозначаться как $R i + 1$ . Транзитивное замыкание R , обозначаемое как $R$ $*$ или $R$ $\infty ,$ является объединением множеств $R$ , $R$ $1$ , $R$ $2$ , ... . ^[8]

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

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

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

Типы отношений, требующие транзитивности

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

Подсчет транзитивных отношений

Неизвестна общая формула, которая подсчитывает количество транзитивных отношений на конечном множестве (последовательность A006905 в OEIS ). ^[9] Однако существует формула для нахождения количества отношений, которые одновременно являются рефлексивными, симметричными и транзитивными — другими словами, отношений эквивалентности — (последовательность A000110 в OEIS ), тех, которые являются симметричными и транзитивными, тех, которые являются симметричными, транзитивными и антисимметричными, и тех, которые являются тотальными, транзитивными и антисимметричными. Пфайффер ^[10] добился некоторого прогресса в этом направлении, выразив отношения с комбинациями этих свойств в терминах друг друга, но все еще сложно вычислить любое из них. См. также Бринкманн и Маккей (2005). ^[11]

Поскольку рефлексивизация любого транзитивного отношения является предпорядком , число транзитивных отношений на множестве из n элементов не превышает в 2 ⁿ раз числа предпорядков, поэтому оно асимптотически соответствует результатам Клейтмана и Ротшильда. ^[12] $2^{(1/4+o(1))n^{2}}$

Обратите внимание, что S ( n , k ) относится к числам Стирлинга второго рода .

Связанные свойства

Диаграмма цикла — Игра « Камень-ножницы-бумага » основана на нетранзитивном и антитранзитивном отношении « x бьет y ».

Отношение R называется нетранзитивным , если оно не транзитивно, то есть если xRy и yRz , но не xRz , для некоторых x , y , z . Напротив, отношение R называется антитранзитивным , если xRy и yRz всегда подразумевают, что xRz не выполняется. Например, отношение, определяемое xRy , если xy — четное число, является нетранзитивным, ^[13] но не антитранзитивным. ^[14] Отношение, определяемое xRy , если x — четное, а y — нечетное, является как транзитивным, так и антитранзитивным. ^[15] Отношение, определяемое xRy , если x — последующее число y, является как нетранзитивным ^[16], так и антитранзитивным. ^[17] Неожиданные примеры нетранзитивности возникают в таких ситуациях, как политические вопросы или групповые предпочтения. ^[18]

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

Квазитранзитивное отношение — это еще одно обобщение; ^[5] оно должно быть транзитивным только на своей несимметричной части. Такие отношения используются в теории общественного выбора или микроэкономике . ^[20]

Предложение: Если R — унивалент , то R;R ^T транзитивен.

доказательство: Предположим Тогда существуют a и b такие, что Поскольку R одновалентен, yRb и aR ^Ty влекут a = b . Следовательно, x R a R ^Tz , следовательно, x R;R ^Tz и R;R ^T транзитивны.

xR;R^{T}yR;R^{T}z.

xRaR^{T}yRbR^{T}z.

Следствие : Если R одновалентен, то R;RT ^{является} отношением эквивалентности на области определения R.

доказательство: R;R ^T симметричен и рефлексивен на своей области определения. При однолистности R транзитивное требование эквивалентности выполняется.

Смотрите также

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

Примечания

^ Смит, Эгген и Сент-Андре 2006, с. 145
^ Однако класс ординалов фон Неймана построен таким образом, что ∈ является транзитивным при ограничении этим классом.
^ Смит, Эгген и Сент-Андре 2006, с. 146
^ Бьянки, Марияграция; Маури, Анна Джиллио Берта; Херцог, Марсель; Верарди, Либеро (2000-01-12). «О конечных разрешимых группах, в которых нормальность является транзитивным отношением». Журнал теории групп . 3 (2). doi :10.1515/jgth.2000.012. ISSN 1433-5883. Архивировано из оригинала 2023-02-04 . Получено 2022-12-29 .
^ ab Robinson, Derek JS (январь 1964). «Группы, в которых нормальность является транзитивным отношением». Математические труды Кембриджского философского общества . 60 (1): 21–38. Bibcode :1964PCPS...60...21R. doi :10.1017/S0305004100037403. ISSN 0305-0041. S2CID 119707269. Архивировано из оригинала 2023-02-04 . Получено 2022-12-29 .
^ Flaška, V.; Ježek, J.; Kepka, T.; Kortelainen, J. (2007). Транзитивные замыкания бинарных отношений I (PDF) . Прага: Школа математики - Физика Карлова университета. стр. 1. Архивировано из оригинала (PDF) 2013-11-02.Лемма 1.1 (iv). Обратите внимание, что этот источник называет асимметричные отношения «строго антисимметричными».
^ Лю 1985, стр. 111
^ Аб Лю 1985, стр. 112
↑ Стивен Р. Финч, «Транзитивные отношения, топологии и частичные порядки». Архивировано 4 марта 2016 г. на Wayback Machine , 2003 г.
^ Гётц Пфайффер, «Подсчет транзитивных отношений. Архивировано 4 февраля 2023 г. в Wayback Machine », Журнал целочисленных последовательностей , том 7 (2004), статья 04.3.2.
^ Гуннар Бринкманн и Брендан Д. Маккей, «Подсчет немаркированных топологий и транзитивных отношений » . Архивировано 20 июля 2005 г. на Wayback Machine.
^ Клейтман, Д.; Ротшильд, Б. (1970), «Число конечных топологий», Труды Американского математического общества , 25 (2): 276–282, JSTOR 2037205
^ так как например 3 R 4 и 4 R 5, но не 3 R 5
^ так как например 2 R 3 и 3 R 4 и 2 R 4
^ поскольку xRy и yRz никогда не могут произойти
^ так как например 3 R 2 и 2 R 1, но не 3 R 1
^ поскольку, в более общем случае, xRy и yRz подразумевают x = y +1= z +2≠ z +1, т.е. не xRz , для всех x , y , z
^ Драм, Кевин (ноябрь 2018 г.). «Предпочтения не транзитивны». Mother Jones . Архивировано из оригинала 29.11.2018 . Получено 29.11.2018 .
^ Оливейра, ИФД; Зехави, С.; Давидов, О. (август 2018 г.). «Стохастическая транзитивность: аксиомы и модели». Журнал математической психологии . 85 : 25–35. doi :10.1016/j.jmp.2018.06.002. ISSN 0022-2496.
^ Сен, А. (1969). «Квазитранзитивность, рациональный выбор и коллективные решения». Rev. Econ. Stud . 36 (3): 381–393. doi :10.2307/2296434. JSTOR 2296434. Zbl 0181.47302.

Ссылки

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

Внешние ссылки

«Транзитивность», Энциклопедия математики , EMS Press , 2001 [1994]
Транзитивность в действии при разрезании узла