В математике бинарное отношение R на множестве X является транзитивным , если для всех элементов a , b , c в X всякий раз, когда R связывает a с b и b с c , тогда R также связывает a с c .
Нематематический пример: отношение «является предком» является транзитивным. Например, если Эми — предок Бекки, а Бекки — предок Кэрри, то Эми тоже является предком Кэрри.
С другой стороны, «является биологическим родителем» не является транзитивным отношением, поскольку если Алиса является биологическим родителем Бренды, а Бренда является биологическим родителем Клэр, то это не означает, что Алиса является биологическим родителем Клэр. . Более того, оно антитранзитивно : Алиса никогда не сможет быть биологическим родителем Клэр.
Нетранзитивные, неантитранзитивные отношения включают спортивные матчи (расписание плей-офф), «знает» и «разговаривает с».
«Больше», «по меньшей мере так же велик, как» и «равно» ( равенство ) — это транзитивные отношения на различных множествах, например, на множестве действительных чисел или множестве натуральных чисел:
всякий раз, когда x > y и y > z , тогда также x > z
всякий раз, когда x ≥ y и y ≥ z , тогда также x ≥ z
всякий раз, когда x = y и y = z , тогда также x = z .
Еще примеры транзитивных отношений:
«является подмножеством » (включение множества, отношение к множествам)
«делит» ( делимость , отношение натуральных чисел)
Пустое отношение на любом множестве является транзитивным [3] [4] , поскольку не существует таких элементов, что и , и, следовательно, условие транзитивности бессмысленно истинно . Отношение R , содержащее только одну упорядоченную пару, также транзитивно: если упорядоченная пара имеет форму для некоторых , то единственными такими элементами являются , и действительно в этом случае , а если упорядоченная пара не имеет формы, то таких элементов не существует и, следовательно, является бессмысленно транзитивным.
Характеристики
Свойства замыкания
Обратное (инверсное) транзитивное отношение всегда транзитивно . Например, зная, что «является подмножеством » является транзитивным, а «является надмножеством » является его обратным, можно заключить, что последнее также транзитивно.
Пересечение двух транзитивных отношений всегда транзитивно. [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 , обозначаемое R1 , представляет собой наименьшее бинарное отношение на X такое, что R1 содержит R , и если ( a , b ) ∈ R и ( b , c ) ∈ R , то ( a , c ) ∈ R1 . [8] Например, предположим, что 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 , R1 , R2 , ... . [9]
Транзитивное замыкание отношения является транзитивным отношением. [9]
Отношение «является биологическим родителем» для множества людей не является транзитивным отношением. Однако в биологии часто возникает необходимость рассматривать родословие на протяжении произвольного числа поколений: отношение «является биологическим предком» является транзитивным отношением и является транзитивным замыканием отношения «является биологическим родителем».
В приведенном выше примере городов и дорог ( A , C ) ∈ R * при условии, что вы можете путешествовать между городами A и C , используя любое количество дорог.
Строгий слабый порядок - строгий частичный порядок, в котором несравнимость является отношением эквивалентности.
Тотальный порядок - связное (тотальное), антисимметричное и транзитивное отношение.
Подсчет транзитивных отношений
Неизвестна общая формула, подсчитывающая количество транзитивных отношений на конечном множестве (последовательность A006905 в OEIS ). [10] Однако существует формула для нахождения количества отношений, которые одновременно являются рефлексивными, симметричными и транзитивными – другими словами, отношения эквивалентности – (последовательность A000110 в OEIS ), тех, которые симметричны и транзитивны, тех, которые являются симметричные, транзитивные и антисимметричные, а также тотальные, транзитивные и антисимметричные. Пфайффер [11] добился некоторого прогресса в этом направлении, выражая отношения с комбинациями этих свойств через друг друга, но вычислить какое-либо одно все же затруднительно. См. также Бринкманн и Маккей (2005). [12]
Поскольку рефлексивизация любого транзитивного отношения является предпорядком , количество транзитивных отношений в наборе из n элементов не более чем в 2 n раз больше, чем количество предпорядков, что асимптотически соответствует результатам Клейтмана и Ротшильда. [13]
Отношение 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]
Квазитранзитивное отношение — еще одно обобщение; [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 транзитивно .
Следствие : Если R однолистно, то R;RT T является отношением эквивалентности в области определения R.
Доказательство: R;RT T симметричен и рефлексивен в своей области определения. При однолистности R выполняется транзитивное требование эквивалентности.
^ Бьянки, Мариаграция; Маури, Анна Гиллио Берта; Херцог, Марсель; Верарди, Либеро (12 января 2000 г.). «О конечных разрешимых группах, в которых нормальность является транзитивным отношением». Журнал теории групп . 3 (2). дои : 10.1515/jgth.2000.012. ISSN 1433-5883. Архивировано из оригинала 4 февраля 2023 г. Проверено 29 декабря 2022 г.
^ Аб Робинсон, Дерек Дж. С. (январь 1964 г.). «Группы, в которых нормальность является транзитивным отношением». Математические труды Кембриджского философского общества . 60 (1): 21–38. Бибкод : 1964PCPS...60...21R. дои : 10.1017/S0305004100037403. ISSN 0305-0041. S2CID 119707269. Архивировано из оригинала 4 февраля 2023 г. Проверено 29 декабря 2022 г.
^ Флашка, В.; Ежек, Дж.; Кепка, Т.; Кортелайнен, Дж. (2007). Транзитивные замыкания бинарных отношений I (PDF) . Прага: Школа математики – Физика Карлова университета. п. 1. Архивировано из оригинала (PDF) 2 ноября 2013 г.Лемма 1.1 (iv). Обратите внимание, что в этом источнике асимметричные отношения называются «строго антисимметричными».
^ Лю 1985, с. 111
^ Аб Лю 1985, с. 112
^ Стивен Р. Финч, «Транзитивные отношения, топологии и частичные порядки». Архивировано 4 марта 2016 г. в Wayback Machine , 2003 г.
^ Гетц Пфайффер, «Подсчет транзитивных отношений, архивировано 4 февраля 2023 г. в Wayback Machine », Journal of Integer Sequences , Vol. 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 г.). «Предпочтения не транзитивны». Мать Джонс . Архивировано из оригинала 29 ноября 2018 г. Проверено 29 ноября 2018 г.
^ Оливейра, IFD; Зехави, С.; Давыдов, О. (август 2018 г.). «Стохастическая транзитивность: аксиомы и модели». Журнал математической психологии . 85 : 25–35. дои : 10.1016/j.jmp.2018.06.002. ISSN 0022-2496.
^ Сен, А. (1969). «Квазитранзитивность, рациональный выбор и коллективные решения». Преподобный экон. Стад . 36 (3): 381–393. дои : 10.2307/2296434. JSTOR 2296434. Збл 0181.47302.