Переходное отношение - Transitive relation
В математике , A отношение R на множестве X является транзитивным , если для всех элементов , Ь , гр в X , всякий раз , когда R имеет отношение к Ь и Ь к с , то R также относится к с . Каждый частичный порядок, а также каждое отношение эквивалентности должны быть транзитивными.
Определение
Транзитивные бинарные отношения | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Все определения неявно требуют, чтобы однородное отношение было транзитивным : « ✓ » указывает, что свойство столбца требуется в определении строки. Например, определение отношения эквивалентности требует, чтобы оно было симметричным. Упомянутые здесь дополнительные свойства , что однородное отношение может удовлетворять.
|
Однородное отношение R на множестве X представляет собой транзитивное отношение , если,
- для всех 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 .
Еще примеры транзитивных отношений:
- "является подмножеством " (включение множества, отношение на множествах)
- «делит» ( делимость , отношение на натуральные числа)
- "подразумевает" ( импликация , символизируемая "⇒", отношение к предложениям )
Примеры нетранзитивных отношений:
- "является преемником " (отношение натуральных чисел)
- «является членом множества» (обозначается как «∈»)
- " перпендикулярно " (отношение линий в евклидовой геометрии )
Пустое отношение на любом множестве транзитивно , потому что нет никаких элементов , таких , что и , следовательно , условие транзитивности бессодержательно верно . Отношение 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 , и , если ( , б ) ∈ R и ( Ь , с ) ∈ R , то ( , с ) ∈ R 1 . Например, предположим, что 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 , ....
Транзитивное закрытие отношения - это транзитивное отношение.
Отношение «является биологическим родителем» для группы людей не является транзитивным отношением. Однако в биологии часто возникает необходимость рассматривать вопрос о рождении отцовства на протяжении произвольного числа поколений: отношение «является биологическим предком» является транзитивным отношением, и это транзитивное завершение отношения «является биологическим родителем».
В приведенном выше примере городов и дорог ( A , C ) ∈ R * при условии, что вы можете перемещаться между городами A и C по любому количеству дорог.
Свойства отношения, требующие транзитивности
- Предварительный заказ - рефлексивно- переходное отношение
- Частичный заказ - антисимметричный предзаказ
- Тотальный предварительный заказ - связанный (ранее называвшийся тотальным) предварительный заказ
- Отношение эквивалентности - симметричный предпорядок
- Строгий слабый порядок - строгий частичный порядок, в котором несравнимость является отношением эквивалентности
- Тотальный порядок - связное (тотальное), антисимметричное и транзитивное отношение
Подсчет переходных отношений
Нет общей формулы, которая подсчитывает количество транзитивных отношений на конечном множестве (последовательность A006905 в OEIS ). Однако существует формула для определения количества отношений, которые одновременно являются рефлексивными, симметричными и транзитивными - другими словами, отношения эквивалентности - (последовательность A000110 в OEIS ), симметричных и транзитивных, симметричных, транзитивных. , и антисимметричные, и те, которые являются полными, транзитивными и антисимметричными. Пфайффер добился некоторого прогресса в этом направлении, выразив отношения с комбинациями этих свойств в терминах друг друга, но все же вычислить какое-либо одно из них сложно. Смотрите также.
Элементы | Любой | Переходный | Рефлексивный | Предзаказ | Частичный заказ | Всего предзаказ | Общий заказ | Отношение эквивалентности |
---|---|---|---|---|---|---|---|---|
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 - п | S ( п , к ) | п ! | S ( п , к ) | |||
OEIS | A002416 | A006905 | A053763 | A000798 | A001035 | A000670 | A000142 | A000110 |
Связанные свойства
Отношение R называется интранзитивным, если оно не транзитивно, то есть если xRy и yRz , но не xRz , для некоторых x , y , z . Напротив, отношение R называется антитранзитивным, если xRy и yRz всегда подразумевают, что xRz не выполняется. Например, отношение, определяемое xRy, если xy - четное число, является непереходным, но не антитранзитивным. Отношение , определенное с помощью хКи , если х даже и у является нечетным одновременно транзитивно и antitransitive. Отношение, определяемое xRy, если x является последующим номером y, является как непереходным, так и антитранзитивным. Неожиданные примеры неприемлемости возникают в таких ситуациях, как политические вопросы или групповые предпочтения.
Обобщенное на стохастические версии ( стохастическая транзитивность ), исследование транзитивности находит применения в теории принятия решений , психометрии и полезных моделях .
Quasitransitive соотношение является еще одним обобщением; требуется, чтобы он был транзитивным только на своей несимметричной части. Такие отношения используются в теории социального выбора или микроэкономике .
Смотрите также
- Переходное сокращение
- Непереходные кости
- Теория рационального выбора
- Гипотетический силлогизм - транзитивность материального условного
Примечания
использованная литература
- Гримальди, Ральф П. (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-е изд.), Brooks / Cole, ISBN 978-0-534-39900-9
внешние ссылки
- «Транзитивность» , Математическая энциклопедия , EMS Press , 2001 [1994]
- Транзитивность в действии на пороге