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

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

В математике бинарное отношение 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 ∈ X , если a R b и b R c , то a R c .

Или с точки зрения логики первого порядка :

${\displaystyle \forall a,b,c\in X:(aRb\wedge bRc)\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 .

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

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

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

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

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

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

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

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

Другие объекты недвижимости

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

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

Если отношение транзитивно, то его транзитивным расширением является оно само, т. е. если R — транзитивное отношение, то R ₁ = R .

Транзитивное расширение R ₁ будет обозначаться как R ₂ , и, продолжая в том же духе, в общем случае транзитивное расширение R _i будет равно R _{i + 1} . Транзитивное замыкание R _, обозначаемое R * или R∞ ^, представляет собой объединение множеств R , R1 , R2 _, ... . ^[9]

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

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

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

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

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

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

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

Поскольку рефлексивизация любого транзитивного отношения является предпорядком , количество транзитивных отношений в наборе из n элементов не более чем в 2 ⁿ раз больше, чем количество предпорядков, что асимптотически соответствует результатам Клейтмана и Ротшильда. ^[13] ${\displaystyle 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 — четное число, является нетранзитивным ^[14] , но не антитранзитивным. ^[15] Отношение, определяемое xRy, если x четное, а y нечетное, является одновременно транзитивным и антитранзитивным. ^[16] Отношение, определяемое xRy , если x является порядковым номером y , является одновременно нетранзитивным ^[17] и антитранзитивным. ^[18] Неожиданные примеры нетранзитивности возникают в таких ситуациях, как политические вопросы или групповые предпочтения. ^[19]

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

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

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

Доказательство: предположим, что существуют a и b такие, что Поскольку R однолистный, из yRb и aRT ^T y следует a = b . Следовательно, ^{x R a RT} z , следовательно , x R ; RT ^z и R;RT ^{транзитивно} . ${\displaystyle xR;R^{T}yR;R^{T}z.}$ ${\displaystyle xRaR^{T}yRbR^{T}z.}$

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

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

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

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

Примечания

1. Смит, Эгген и Сент-Андре 2006, с. 145
2. Однако класс ординалов фон Неймана построен таким образом, что ∈ является транзитивным при ограничении этим классом.
3. Смит, Эгген и Сент-Андре 2006, с. 146
4. https://courses.engr.illinois.edu/cs173/sp2011/Lectures/relations.pdf. Архивировано 4 февраля 2023 г. в Wayback Machine ^{[ пустой URL-адрес в формате PDF ]}
5. Бьянки, Мариаграция; Маури, Анна Гиллио Берта; Херцог, Марсель; Верарди, Либеро (12 января 2000 г.). «О конечных разрешимых группах, в которых нормальность является транзитивным отношением». Журнал теории групп . 3 (2). дои : 10.1515/jgth.2000.012. ISSN  1433-5883. Архивировано из оригинала 4 февраля 2023 г. Проверено 29 декабря 2022 г.
6. Робинсон, Дерек Дж. С. (январь 1964 г.). «Группы, в которых нормальность является транзитивным отношением». Математические труды Кембриджского философского общества . 60 (1): 21–38. Бибкод : 1964PCPS...60...21R. дои : 10.1017/S0305004100037403. ISSN  0305-0041. S2CID  119707269. Архивировано из оригинала 4 февраля 2023 г. Проверено 29 декабря 2022 г.
7. Флашка, В.; Ежек, Дж.; Кепка, Т.; Кортелайнен, Дж. (2007). Транзитивные замыкания бинарных отношений I (PDF) . Прага: Школа математики – Физика Карлова университета. п. 1. Архивировано из оригинала (PDF) 2 ноября 2013 г.Лемма 1.1 (iv). Обратите внимание, что в этом источнике асимметричные отношения называются «строго антисимметричными».
8. Лю 1985, с. 111
9. Лю 1985, с. 112
10. Стивен Р. Финч, «Транзитивные отношения, топологии и частичные порядки». Архивировано 4 марта 2016 г. в Wayback Machine , 2003 г.
11. Гетц Пфайффер, «Подсчет транзитивных отношений, архивировано 4 февраля 2023 г. в Wayback Machine », Journal of Integer Sequences , Vol. 7 (2004 г.), статья 04.3.2.
12. Гуннар Бринкманн и Брендан Д. Маккей, «Подсчет немаркированных топологий и транзитивных отношений. Архивировано 20 июля 2005 г. в Wayback Machine »
13. Клейтман, Д.; Ротшильд, Б. (1970), «Число конечных топологий», Труды Американского математического общества , 25 (2): 276–282, JSTOR  2037205
14. поскольку, например, 3 R 4 и 4 R 5, но не 3 R 5
15. поскольку, например, 2 R 3 и 3 R 4 и 2 R 4
16. поскольку xRy и yRz никогда не могут случиться
17. поскольку, например, 3 R 2 и 2 R 1, но не 3 R 1
18. поскольку, в более общем смысле, xRy и yRz подразумевают x = y +1= z +2≠ z +1, т.е. не xRz , для всех x , y , z
19. Драм, Кевин (ноябрь 2018 г.). «Предпочтения не транзитивны». Мать Джонс . Архивировано из оригинала 29 ноября 2018 г. Проверено 29 ноября 2018 г.
20. Оливейра, IFD; Зехави, С.; Давыдов, О. (август 2018 г.). «Стохастическая транзитивность: аксиомы и модели». Журнал математической психологии . 85 : 25–35. дои : 10.1016/j.jmp.2018.06.002. ISSN  0022-2496.
21. Сен, А. (1969). «Квазитранзитивность, рациональный выбор и коллективные решения». Преподобный экон. Стад . 36 (3): 381–393. дои : 10.2307/2296434. JSTOR  2296434. Збл  0181.47302.

Рекомендации

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

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

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