Переходное отношение - Transitive relation

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

Определение

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

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

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

Однородное отношение $р$ на съемочной площадке $Икс$ это переходное отношение если,^[1]

для всех

а, б, c \in Икс

, если

а R б

и

б R в

, тогда

а R c

.

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

{ displaystyle forall a, b, c in X: (aRb wedge bRc) Rightarrow aRc,}

куда $а R б$ это инфиксная запись за $(а, б) \in р$ .

Примеры

В качестве нематематического примера отношение «является предком» транзитивно. Например, если Эми - предок Бекки, а Бекки - предок Кэрри, то Эми тоже является предком Кэрри.

С другой стороны, «является биологическим родителем» не является транзитивным отношением, потому что если Алиса является биологическим родителем Бренды, а Бренда является биологическим родителем Клэр, то Алиса не является биологическим родителем Клэр. Более того, это антитранзитивный: Алиса может никогда быть биологическим родителем Клэр.

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

всякий раз, когда Икс > у и у > z, то также Икс > z

всякий раз, когда Икс ≥ у и у ≥ z, то также Икс ≥ z

всякий раз, когда Икс = у и у = z, то также Икс = z.

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

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

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

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

В пустое отношение на любом наборе ${ displaystyle X}$ транзитивен^[3]^[4] потому что нет элементов ${ 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}$ вакуумно транзитивен.

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

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

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

Другие свойства

Транзитивное отношение асимметричный если и только если это иррефлексивный.^[5]

Транзитивное отношение не обязательно рефлексивный. Когда это так, это называется предзаказ. Например, на съемочной площадке Икс = {1,2,3}:

р = {(1,1), (2,2), (3,3), (1,3), (3,2)} рефлексивно, но не транзитивно, так как пара (1,2) отсутствует,
р = {(1,1), (2,2), (3,3), (1,3)} рефлексивно так же, как и транзитивно, поэтому это предпорядок,
р = {(1,1), (2,2), (3,3)} рефлексивно, а также транзитивно, еще один предпорядок.

Транзитивные расширения и транзитивное замыкание

Позволять $р$ быть бинарным отношением на множестве $Икс$ . В транзитивное расширение из $р$ , обозначенный $р 1$ , является наименьшим бинарным отношением на $Икс$ такой, что $р 1$ содержит $р$ , и если $(а, б) \in р$ и $(б, c) \in р$ тогда $(а, c) \in р 1$ .^[6] Например, предположим $Икс$ представляет собой набор городов, некоторые из которых связаны дорогами. Позволять $р$ быть отношением к городам, где $(А, B) \in р$ если есть дорога, соединяющая город $А$ и город $B$ . Это отношение не обязательно должно быть транзитивным. Транзитивное расширение этого отношения можно определить как $(А, C) \in р 1$ если вы можете путешествовать между городами $А$ и $C$ используя не более двух дорог.

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

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

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

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

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

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

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

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

Нет общей формулы, которая подсчитывала бы количество транзитивных отношений на конечном множестве (последовательность A006905 в OEIS ) известен.^[8] Однако существует формула для определения количества отношений, которые одновременно являются рефлексивными, симметричными и транзитивными, другими словами, отношения эквивалентности - (последовательность A000110 в OEIS ), симметричные и транзитивные, симметричные, транзитивные и антисимметричные, а также полные, транзитивные и антисимметричные. Pfeiffer^[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	4,096	355	219	75	24	15
п	2^п²		2^п²−п			$\sum п k =0 k! S (п, k)$	п!	$\sum п k =0 S (п, k)$
OEIS	A002416	A006905	A053763	A000798	A001035	A000670	A000142	A000110

Связанные свойства

В Камень ножницы Бумага игра основана на непереходном и антитранзитивном отношениях "Икс удары у".

Отношение р называется непереходный если он не транзитивен, то есть если xRy и yRz, но нет xRz, для некоторых Икс, у, zНапротив, отношение р называется антитранзитивный если xRy и yRz всегда подразумевает, что xRz не выполняется. Например, отношение, определяемое формулой xRy если ху является четное число непереходный,^[11] но не антитранзитивный.^[12] Отношение, определяемое xRy если Икс даже и у является странный одновременно транзитивен и антитранзитивен.^[13] Отношение, определяемое xRy если Икс это преемник количество у оба непереходные^[14] и антитранзитивный.^[15] Неожиданные примеры неприемлемости возникают в таких ситуациях, как политические вопросы или групповые предпочтения.^[16]

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

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

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

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

Примечания

^ Смит, Эгген и Сент-Андре 2006, п. 145
^ Однако класс ординалы фон Неймана построен таким образом, что ∈ является транзитивный, когда ограничен этим классом.
^ Смит, Эгген и Сент-Андре 2006, п. 146
^ https://courses.engr.illinois.edu/cs173/sp2011/Lectures/relations.pdf
^ Флашка, В .; Ježek, J .; Кепка, Т .; Кортелайнен, Дж. (2007). Транзитивные замыкания бинарных отношений I (PDF). Прага: Школа математики - Карлов университет физики. п. 1. Архивировано из оригинал (PDF) на 2013-11-02. Лемма 1.1 (iv). Обратите внимание, что этот источник называет асимметричные отношения «строго антисимметричными».
^ Лю 1985, п. 111
^ ^а ^б Лю 1985, п. 112
^ Стивен Р. Финч, «Транзитивные отношения, топологии и частичные порядки», 2003.
^ Гётц Пфайффер "Подсчет переходных отношений ", Журнал целочисленных последовательностей, Vol. 7 (2004 г.), статья 04.3.2.
^ Гуннар Бринкманн и Брендан Д. Маккей "Подсчет немаркированных топологий и транзитивных отношений "
^ поскольку, например, 3р4 и 4р5, а не 3р5
^ поскольку, например, 2р3 и 3р4 и 2р4
^ поскольку xRy и yRz никогда не может случиться
^ поскольку, например, 3р2 и 2р1, а не 3р1
^ поскольку в более общем плане xRy и yRz подразумевает Икс=у+1=z+2≠z+1, т.е. не xRz, для всех Икс, у, z
^ Барабан, Кевин (ноябрь 2018). «Предпочтения непостоянны». Мать Джонс. Получено 2018-11-29.
^ Oliveira, I.F.D .; Zehavi, S .; Давыдов, О. (август 2018). «Стохастическая транзитивность: аксиомы и модели». Журнал математической психологии. 85: 25–35. Дои:10.1016 / j.jmp.2018.06.002. ISSN 0022-2496.
^ Сен, А. (1969). «Квазитранзитивность, рациональный выбор и коллективные решения». Rev. Econ. Шпилька. 36 (3): 381–393. Дои:10.2307/2296434. JSTOR 2296434. Zbl 0181.47302.CS1 maint: ref = harv (ссылка на сайт)

внешняя ссылка

[1] Смит, Эгген и Сент-Андре 2006, п. 145

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

[3] Смит, Эгген и Сент-Андре 2006, п. 146

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

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

[6] Лю 1985, п. 111

[Liu112-7] а ^б Лю 1985, п. 112

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

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

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

[11] поскольку, например, 3р4 и 4р5, а не 3р5

[12] поскольку, например, 2р3 и 3р4 и 2р4

[13] поскольку xRy и yRz никогда не может случиться

[14] поскольку, например, 3р2 и 2р1, а не 3р1

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

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

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

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

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]