Эта статья требует дополнительных ссылок для проверки . ( октябрь 2013 г. ) ( Узнайте, как и когда удалить этот шаблон сообщения ) |
В математике , А однородное отношение R над множеством X является транзитивным , если для всех элементов , Ь , гр в X , всякий раз , когда R имеет отношение к Ь и Ь к с , то R также относится к с . Каждый частичный порядок, а также каждое отношение эквивалентности должны быть транзитивными.
Определение [ править ]
Бинарные отношения | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
« ✓ » указывает, что свойство столбца требуется в определении строки. Например, определение отношения эквивалентности требует, чтобы оно было симметричным. Все определения молчаливо требуют транзитивности и рефлексивности . |
Однородное отношение R на множестве X является транзитивным отношением, если [1]
- для всех a , b , c ∈ X , если a R b и b R c , то a R c .
Или с точки зрения логики первого порядка :
где A R B представляет собой инфиксным обозначения для ( в , б ) ∈ R .
Примеры [ править ]
В качестве нематематического примера отношение «является предком» транзитивно. Например, если Эми - предок Бекки, а Бекки - предок Кэрри, то Эми тоже является предком Кэрри.
С другой стороны, «является биологическим родителем» не является транзитивным отношением, потому что, если Алиса является биологическим родителем Бренды, а Бренда является биологическим родителем Клэр, тогда Алиса не является биологическим родителем Клэр. Более того, это антитранзитивно : Алиса никогда не может быть биологическим родителем Клэр.
«Больше, чем», «не меньше, чем» и «равно» ( равенство ) - это транзитивные отношения на различных наборах, например, на множестве действительных чисел или множестве натуральных чисел:
- всякий раз, когда x > y и y > z , то также x > z
- если x ≥ y и y ≥ z , то также x ≥ z
- если x = y и y = z , то также x = z .
Еще примеры транзитивных отношений:
- "является подмножеством " (включение множества, отношение на множествах)
- «делит» ( делимость , отношение на натуральные числа)
- "подразумевает" ( импликация , символизируемая "⇒", отношение к предложениям )
Примеры нетранзитивных отношений:
- "является преемником " (отношение натуральных чисел)
- «является членом множества» (обозначается как «∈») [2]
- " перпендикулярно " (отношение линий в евклидовой геометрии )
Пустое отношение на любом множестве транзитивно [3] [4] , потому что нет никаких элементов таким образом, что и , и , следовательно , условие транзитивности бессодержательно истинно . Отношение R, содержащее только одну упорядоченную пару , также транзитивно: если упорядоченная пара имеет форму для некоторых, только такие элементы являются , и действительно в этом случае , в то время как если упорядоченная пара не имеет формы, то таких элементов нет и, следовательно, является вакуумно транзитивным.
Свойства [ править ]
Свойства закрытия [ править ]
- Обратное (обратное) транзитивного отношения всегда транзитивно. Например, зная, что «является подмножеством » является транзитивным, а «является надмножеством » является обратным, можно сделать вывод, что последнее также транзитивно.
- Пересечение двух транзитивных отношений всегда транзитивно. Например, зная, что "родился раньше" и "имеет то же имя, что и" являются переходными, можно сделать вывод, что "родился раньше и также имеет то же имя, что и" также транзитивны.
- Объединение двух транзитивных отношений не обязательно должно быть транзитивным. Например, «родился раньше или имеет то же имя, что и» не является переходным отношением, поскольку, например, Герберт Гувер связан с Франклином Д. Рузвельтом , который, в свою очередь, связан с Франклином Пирсом , в то время как Гувер не связан с Франклином Пирсом. .
- Дополнение транзитивного отношения не обязательно должно быть транзитивным. Например, в то время как «равно» транзитивно, «не равно» транзитивно только на множествах, содержащих не более одного элемента.
Другие свойства [ править ]
Транзитивное отношение асимметрично тогда и только тогда, когда оно иррефлексивно . [5]
Транзитивное отношение не обязательно должно быть рефлексивным . Когда это так, это называется предварительным заказом . Например, для набора 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 , и , если ( , б ) ∈ R и ( Ь , с ) ∈ R , то ( , с ) ∈ R 1 . [6] Например, предположим, что Xпредставляет собой набор городов, некоторые из которых соединены дорогами. Пусть R будет отношение в городах , где ( A , B ) ∈ R , если есть дорога , непосредственно связывающий город A и город B . Это отношение не обязательно должно быть транзитивным. Транзитивное расширение этого отношения может быть определено как ( A , C ) ∈ R 1, если вы можете перемещаться между городами A и C , используя не более двух дорог.
Если это отношение транзитивно , то его транзитивное расширение себя, то есть, если Р представляет собой транзитивное отношение , то R 1 = R .
Транзитивное расширение R 1 будет обозначаться R 2 , и, продолжая таким образом, в общем случае транзитивное расширение R i будет R i + 1 . Транзитивное замыкание в R , обозначим через R * или R ∞ является множественным объединением R , R 1 , R 2 , .... [7]
Транзитивное закрытие отношения - это транзитивное отношение. [7]
Отношение «является биологическим родителем» для группы людей не является транзитивным отношением. Однако в биологии часто возникает необходимость рассматривать вопрос о рождении отцовства на протяжении произвольного числа поколений: отношение «является родоначальником» является транзитивным отношением, и это транзитивное завершение отношения «является родителем».
В приведенном выше примере городов и дорог ( A , C ) ∈ R * при условии, что вы можете перемещаться между городами A и C по любому количеству дорог.
Свойства отношения, требующие транзитивности [ править ]
- Предварительный заказ - рефлексивное переходное отношение
- Частичный заказ - антисимметричный предзаказ
- Total preorder - общий предварительный заказ
- Отношение эквивалентности - симметричный предпорядок
- Строгий слабый порядок - строгий частичный порядок, в котором несравнимость является отношением эквивалентности
- Общий порядок - это общее , антисимметричны транзитивное отношение
Подсчет транзитивных отношений [ править ]
Нет общей формулы, которая подсчитывает количество транзитивных отношений на конечном множестве (последовательность A006905 в OEIS ). [8] Однако существует формула для определения количества отношений, которые одновременно являются рефлексивными, симметричными и транзитивными - другими словами, отношения эквивалентности - (последовательность A000110 в OEIS ), симметричных и транзитивных, тех, которые являются симметричные, транзитивные и антисимметричные, а также полные, транзитивные и антисимметричные. Пфайффер [9]добился некоторого прогресса в этом направлении, выражая отношения с комбинациями этих свойств друг через друга, но все же вычислить какое-либо одно из них сложно. Смотрите также. [10]
Элементы | Любой | Переходный | Рефлексивный | Предварительный заказ | Частичный заказ | Всего предзаказ | Общий заказ | Отношение эквивалентности |
---|---|---|---|---|---|---|---|---|
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 | 4096 | 355 | 219 | 75 | 24 | 15 |
п | 2 п 2 | 2 п 2 - п | ∑п к = 0 к ! S ( п , к ) | п ! | ∑п к = 0 S ( п , к ) | |||
OEIS | A002416 | A006905 | A053763 | A000798 | A001035 | A000670 | A000142 | A000110 |
Связанные свойства [ править ]
Отношение R называется интранзитивным, если оно не транзитивно, то есть если xRy и yRz , но не xRz , для некоторых x , y , z . Напротив, отношение R называется антитранзитивным, если xRy и yRz всегда подразумевают, что xRz не выполняется. Например, отношение, определяемое xRy, если xy - четное число, является непереходным [11], но не антитранзитивным. [12] Отношение, определяемое xRyесли х даже и у является нечетным одновременно транзитивно и antitransitive. [13] Отношение, определяемое xRy, если x является последующим номером y, является как непереходным [14], так и антитранзитивным. [15] Неожиданные примеры неприкосновенности возникают в таких ситуациях, как политические вопросы или групповые предпочтения. [16]
Обобщенное на стохастические версии ( стохастическая транзитивность ), исследование транзитивности находит применения в теории принятия решений , психометрии и полезных моделях . [17]
Quasitransitive соотношение является еще одним обобщением; требуется, чтобы он был транзитивным только на своей несимметричной части. Такие отношения используются в теории социального выбора или микроэкономике . [18]
См. Также [ править ]
- Переходное сокращение
- Нетранзитивные кости
- Теория рационального выбора
- Гипотетический силлогизм - транзитивность материального условного
Заметки [ править ]
- Перейти ↑ Smith, Eggen & St. Andre 2006 , p. 145
- ^ Однако класс ординалов фон Неймана построен таким образом, что ∈ является транзитивным при ограничении этим классом.
- Перейти ↑ Smith, Eggen & St. Andre 2006 , p. 146
- ^ https://courses.engr.illinois.edu/cs173/sp2011/Lectures/relations.pdf
- ^ Flaška, V .; Ježek, J .; Кепка, Т .; Кортелайнен, Дж. (2007). Транзитивные замыкания двоичных отношений I (PDF) . Прага: Школа математики - Карлов университет физики. п. 1. Архивировано из оригинального (PDF) 02.11.2013.Лемма 1.1 (iv). Обратите внимание, что в этом источнике асимметричные отношения называются «строго антисимметричными».
- ↑ Лю 1985 , стр. 111
- ^ а б Лю 1985 , стр. 112
- ^ Стивен Р. Финч, "Транзитивные отношения, топологии и частичные порядки" , 2003.
- ^ Гётц Пфайффер, " Подсчет переходных отношений ", Журнал целочисленных последовательностей , Vol. 7 (2004 г.), статья 04.3.2.
- ^ Гуннар Бринкманн и Брендан Д. Маккей, " Подсчет немаркированных топологий и транзитивных отношений "
- ^ так как, например, 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 .
- ^ Oliveira, IFD; Zehavi, S .; Давыдов, О. (август 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-е изд.), Аддисон-Уэсли, ISBN 0-201-19912-2
- Лю, CL (1985), Элементы дискретной математики , McGraw-Hill, ISBN 0-07-038133-X
- Гюнтер Шмидт , 2010. Реляционная математика . Издательство Кембриджского университета, ISBN 978-0-521-76268-7 .
- Смит, Дуглас; Эгген, Морис; Сент-Андр, Ричард (2006), Переход к высшей математике (6-е изд.), Брукс / Коул, ISBN 978-0-534-39900-9
Внешние ссылки [ править ]
- «Транзитивность» , Математическая энциклопедия , EMS Press , 2001 [1994]
- Транзитивность в действии на пороге