Переходное отношение

Эта статья требует дополнительных ссылок для проверки . Пожалуйста, помогите улучшить эту статью , добавив цитаты из надежных источников . Материал, не полученный от источника, может быть оспорен и удален.
Найти источники: «Transitive Relations» - новости · газеты · книги · ученый · JSTOR ( октябрь 2013 г. ) ( Узнайте, как и когда удалить этот шаблон сообщения )

В математике , А однородное отношение $R$ над множеством $X$ является транзитивным , если для всех элементов , $Ь$ , $гр$ в $X$ , всякий раз , когда $R$ имеет отношение к $Ь$ и $Ь$ к $с$ , то $R$ также относится к $с$ . Каждый частичный порядок, а также каждое отношение эквивалентности должны быть транзитивными.

Определение [ править ]

Бинарные отношения

	Симметричный	Антисимметричный	Connex	Обоснованный	Присоединяется	Встречается
Отношение эквивалентности	✓	✗	✗	✗	✗	✗
Предзаказ (Квазипорядок)	✗	✗	✗	✗	✗	✗
Частичный заказ	✗	✓	✗	✗	✗	✗
Всего предзаказ	✗	✗	✓	✗	✗	✗
Общий заказ	✗	✓	✓	✗	✗	✗
Предварительный заказ	✗	✗	✓	✓	✗	✗
Хорошо-квазиупорядоченный	✗	✗	✗	✓	✗	✗
Хороший порядок	✗	✓	✓	✓	✗	✗
Решетка	✗	✓	✗	✗	✓	✓
Соединение-полурешетка	✗	✓	✗	✗	✓	✗
Встреча-полурешетка	✗	✓	✗	✗	✗	✓

« ✓ » указывает, что свойство столбца требуется в определении строки.
Например, определение отношения эквивалентности требует, чтобы оно было симметричным.
Все определения молчаливо требуют транзитивности и рефлексивности .

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

для всех

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

Если это отношение транзитивно , то его транзитивное расширение себя, то есть, если $Р$ представляет собой транзитивное отношение , то $R 1 = R$ .

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

Транзитивное закрытие отношения - это транзитивное отношение. ^[7]

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

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

Свойства отношения, требующие транзитивности [ править ]

Предварительный заказ - рефлексивное переходное отношение
Частичный заказ - антисимметричный предзаказ
Total preorder - общий предварительный заказ
Отношение эквивалентности - симметричный предпорядок
Строгий слабый порядок - строгий частичный порядок, в котором несравнимость является отношением эквивалентности
Общий порядок - это общее , антисимметричны транзитивное отношение

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

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

Количество n -элементных бинарных отношений разных типов
Элементы	Любой	Переходный	Рефлексивный	Предварительный заказ	Частичный заказ	Всего предзаказ	Общий заказ	Отношение эквивалентности
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 ^{п ² - п}			$\sum п к = 0 к! S (п, к)$	п !	$\sum п к = 0 S (п, к)$
OEIS	A002416	A006905	A053763	A000798	A001035	A000670	A000142	A000110

Связанные свойства [ править ]

Игра камень-ножницы-бумага основана на непереходном и антитранзитивном отношении « x бьет y ».

Отношение 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]
Транзитивность в действии на пороге

[1] Перейти ↑ Smith, Eggen & St. Andre 2006 , p. 145

[2] Однако класс ординалов фон Неймана построен таким образом, что ∈ является транзитивным при ограничении этим классом.

[3] Перейти ↑ Smith, Eggen & St. Andre 2006 , p. 146

[4] ttps://courses.engr.illinois.edu/cs173/sp2011/Lectures/relations.pdf

[5] Flaška, V .; Ježek, J .; Кепка, Т .; Кортелайнен, Дж. (2007). Транзитивные замыкания двоичных отношений I (PDF) . Прага: Школа математики - Карлов университет физики. п. 1. Архивировано из оригинального (PDF) 02.11.2013.Лемма 1.1 (iv). Обратите внимание, что в этом источнике асимметричные отношения называются «строго антисимметричными».

[6] Лю 1985 , стр. 111

[Liu112-7] а б Лю 1985 , стр. 112

[8] Стивен Р. Финч, "Транзитивные отношения, топологии и частичные порядки" , 2003.

[9] Гётц Пфайффер, " Подсчет переходных отношений ", Журнал целочисленных последовательностей , Vol. 7 (2004 г.), статья 04.3.2.

[10] Гуннар Бринкманн и Брендан Д. Маккей, " Подсчет немаркированных топологий и транзитивных отношений "

[11] так как, например, 3 R 4 и 4 R 5, но не 3 R 5

[12] так как, например, 2 R 3 и 3 R 4 и 2 R 4

[13] так как xRy и yRz никогда не могут произойти

[14] так как, например, 3 R 2 и 2 R 1, но не 3 R 1

[15] поскольку, в более общем смысле, xRy и yRz влечет x = y + 1 = z + 2 ≠ z +1, т.е. не xRz , для всех x , y , z

[16] Барабан, Кевин (ноябрь 2018 г.). «Предпочтения непереходны» . Мать Джонс . Проверено 29 ноября 2018 .

[17] Oliveira, IFD; Zehavi, S .; Давыдов, О. (август 2018). «Стохастическая транзитивность: аксиомы и модели». Журнал математической психологии . 85 : 25–35. DOI : 10.1016 / j.jmp.2018.06.002 . ISSN 0022-2496 .

[18] Сен, А. (1969). «Квазитранзитивность, рациональный выбор и коллективные решения». Rev. Econ. Stud . 36 (3): 381–393. DOI : 10.2307 / 2296434 . JSTOR 2296434 . Zbl 0181.47302 .