Транзитивное отношение

Транзитивное отношение
Тип	Бинарное отношение
Поле	Элементарная алгебра
Заявление	Отношение на съемочной площадке транзитивно, если для всех элементов , , в , в любое время относится к и к , затем также относится к .
Символическое заявление

В математике бинарное отношение $R$ на множестве $X$ является транзитивным , если для всех элементов $a$ , $b$ , $c$ в $X$ всякий раз, когда $R$ связывает $a$ с $b$ и $b$ с $c$ , тогда $R$ также связывает $a$ с $c$ .

Любой частичный порядок и каждое отношение эквивалентности транзитивны. Например, неравенство и равенство действительных чисел транзитивны: если $a < b$ и $b < c$ , то $a < c$ ; и если $x = y$ и $y = z,$ то $x = z$ .

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

Транзитивные бинарные отношения

	Symmetric	Antisymmetric	Connected	Well-founded	Has joins	Has meets	Reflexive	Irreflexive	Asymmetric
			Total, Semiconnex					Anti- reflexive
Equivalence relation	Y	✗	✗	✗	✗	✗	Y	✗	✗
Preorder (Quasiorder)	✗	✗	✗	✗	✗	✗	Y	✗	✗
Partial order	✗	Y	✗	✗	✗	✗	Y	✗	✗
Total preorder	✗	✗	Y	✗	✗	✗	Y	✗	✗
Total order	✗	Y	Y	✗	✗	✗	Y	✗	✗
Prewellordering	✗	✗	Y	Y	✗	✗	Y	✗	✗
Well-quasi-ordering	✗	✗	✗	Y	✗	✗	Y	✗	✗
Well-ordering	✗	Y	Y	Y	✗	✗	Y	✗	✗
Lattice	✗	Y	✗	✗	Y	Y	Y	✗	✗
Join-semilattice	✗	Y	✗	✗	Y	✗	Y	✗	✗
Meet-semilattice	✗	Y	✗	✗	✗	Y	Y	✗	✗
Strict partial order	✗	Y	✗	✗	✗	✗	✗	Y	Y
Strict weak order	✗	Y	✗	✗	✗	✗	✗	Y	Y
Strict total order	✗	Y	Y	✗	✗	✗	✗	Y	Y
	Symmetric	Antisymmetric	Connected	Well-founded	Has joins	Has meets	Reflexive	Irreflexive	Asymmetric
Definitions, for all $a,b$ and $S\neq \varnothing :$	${\begin{aligned}&aRb\\\Rightarrow {}&bRa\end{aligned}}$	${\begin{aligned}aRb{\text{ and }}&bRa\\\Rightarrow a={}&b\end{aligned}}$	${\begin{aligned}a\neq {}&b\Rightarrow \\aRb{\text{ or }}&bRa\end{aligned}}$	${\begin{aligned}\min S\\{\text{exists}}\end{aligned}}$	${\begin{aligned}a\vee b\\{\text{exists}}\end{aligned}}$	${\begin{aligned}a\wedge b\\{\text{exists}}\end{aligned}}$	$aRa$	${\text{not }}aRa$	${\begin{aligned}aRb\Rightarrow \\{\text{not }}bRa\end{aligned}}$

indicates that the column's property is always true the row's term (at the very left), while ✗ indicates that the property is not guaranteed in general (it might, or might not, hold). For example, that every equivalence relation is symmetric, but not necessarily antisymmetric, is indicated by

in the "Symmetric" column and ✗ in the "Antisymmetric" column, respectively.

All definitions tacitly require the homogeneous relation $R$ be transitive: for all $a,b,c,$ if $aRb$ and $bRc$ then $aRc.$
A term's definition may require additional properties that are not listed in this table.

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

для всех

a, b, c \in X

, если

a R b

и

b R c

, то

a R c

.

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

\forall a,b,c\in X:(aRb\wedge bRc)\Rightarrow aRc

,

где $a R b$ — инфиксная запись для $(a, b \in R.$ )

Примеры [ править ]

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

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

Нетранзитивные, неантитранзитивные отношения включают спортивные матчи (расписание плей-офф), «знает» и «разговаривает с».

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

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

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

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

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

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

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

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

Пустое отношение на любом множестве $X$ транзитивен ^[3] потому что нет элементов $a,b,c\in X$ такой, что $aRb$ и $bRc$ , и, следовательно, условие транзитивности бессмысленно верно . Отношение $R$ , содержащее только одну упорядоченную пару , также транзитивно: если упорядоченная пара имеет вид $(x,x)$ для некоторых $x\in X$ единственные такие элементы $a,b,c\in X$ являются $a=b=c=x$ , и действительно в этом случае $aRc$ , а если упорядоченная пара не имеет вида $(x,x)$ тогда таких элементов нет $a,b,c\in X$ и поэтому $R$ является вакуумно транзитивным.

Свойства [ править ]

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

Обратное ( инверсное) транзитивное отношение всегда транзитивно. Например, зная, что «является подмножеством » является транзитивным, а «является надмножеством » является его обратным, можно заключить, что последнее также транзитивно.
Пересечение двух транзитивных отношений всегда транзитивно. ^[4] Например, зная, что фразы «родился раньше» и «имеет то же имя, что» являются переходными, можно заключить, что слова «родился раньше и имеет то же имя, что» также являются переходными.
Объединение двух транзитивных отношений не обязательно должно быть транзитивным. Например, фраза «родился раньше или имеет то же имя, что и» не является переходным отношением, поскольку, например, Герберт Гувер связан с Франклином Д. Рузвельтом , который, в свою очередь, является родственником Франклина Пирса , тогда как Гувер не является родственником Франклина Пирса. .
Дополнение транзитивного отношения не обязательно должно быть транзитивным. ^[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$ , обозначаемое $R1 R$ , является наименьшим бинарным отношением на $X$ такое, что $содержит R$ R $,$ если $(a, b) \in,$ и $(b, c) \in то$ ( $a, c) \in R1 и$ . ^[7]Например, предположим, что $X$ — это набор городов, некоторые из которых соединены дорогами. Пусть $R$ — отношение к городам, где $(A, B) \in R$ если существует дорога, напрямую соединяющая города $A$ и $B.$ , Это отношение не обязательно должно быть транзитивным. Транзитивное расширение этого отношения можно определить как $(A, C) \in R 1$ , если вы можете путешествовать между городами $A$ и $C$ , используя не более двух дорог.

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

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

Транзитивное замыкание отношения является транзитивным отношением. ^[8]

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

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

, требующие транзитивности отношений Типы

Предпорядок – рефлексивное и транзитивное отношение.
Частичный порядок - антисимметричный предварительный порядок
Тотальный предзаказ – связанный (ранее называвшийся тотальным) предзаказ.
Отношение эквивалентности – симметричный предварительный порядок
Строгий слабый порядок - строгий частичный порядок, в котором несравнимость является отношением эквивалентности.
Тотальный порядок - связное (тотальное), антисимметричное и транзитивное отношение.

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

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

Поскольку рефлексивизация любого транзитивного отношения является предпорядком , число транзитивных отношений на n -элементном множестве не превосходит 2 ^н раз больше количества предзаказов, поэтому асимптотически $2^{(1/4+o(1))n^{2}}$ по результатам Клейтмана и Ротшильда. ^[12]

Количество n -элементных бинарных отношений разных типов
Elements	Любой	Переходный	Рефлексивный	Симметричный	Предварительный заказ	Частичный заказ	Общий предзаказ	Общий заказ	Отношение эквивалентности
0	1	1	1	1	1	1	1	1	1
1	2	2	1	2	1	1	1	1	1
2	16	13	4	8	4	3	3	2	2
3	512	171	64	64	29	19	13	6	5
4	65,536	3,994	4,096	1,024	355	219	75	24	15
н	2 ^{н ²}		2 ^{п ( п -1)}	2 ^{п ( п +1)/2}			∑ ^н _{k =0} k ! S ( n , k )	н !	∑ ^н _{k знак равно 0} S ( п , k )
ОЭИС	А002416	А006905	А053763	А006125	А000798	А001035	А000670	А000142	А000110

Обратите внимание, что S ( n , k ) относится к числам Стирлинга второго рода .

Связанные объекты [ изменить ]

Диаграмма цикла — Игра «Камень-ножницы-бумага» основана на интранзитивном и антитранзитивном отношении « x бьет y ».

Отношение R называется интранзитивным , если оно не транзитивно, т. е. если xRy и yRz , но не xRz , для некоторых x , y , z . Напротив, отношение R называется антитранзитивным , если xRy и yRz всегда подразумевают, что xRz не выполняется. Например, отношение, определяемое xRy , если xy — четное число , является нетранзитивным. ^[13] но не антитранзитивен. ^[14] Отношение, определяемое xRy , если x четное, а y нечетное , является одновременно транзитивным и антитранзитивным. ^[15] Отношение, определяемое xRy , если x является порядковым номером y, является нетранзитивным. ^[16] и антитранзитивен. ^[17] Неожиданные примеры нетранзитивности возникают в таких ситуациях, как политические вопросы или групповые предпочтения. ^[18]

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

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

Предложение: Если R — унивалент , то R;R ^Т является транзитивным.

доказательство: предположим

xR;R^{T}yR;R^{T}z.

Тогда найдутся a и b такие, что

xRaR^{T}yRbR^{T}z.

Поскольку R одновалентен, yRb и aR ^Тy подразумевает a = b . Следовательно, x R a R ^Тz , следовательно, x R;R ^Тг и Р;Р ^Т является транзитивным.

Следствие : если R однолистно, то R;R ^Т является отношением эквивалентности в области R .

доказательство: Р;Р ^Тсимметричен и рефлексивен в своей области определения. При однолистности R выполняется транзитивное требование эквивалентности.

См. также [ править ]

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

Примечания [ править ]

^ Смит, Эгген и Сент-Андре 2006 , стр. 145.
^ Однако класс ординалов фон Неймана построен таким образом, что ∈ является транзитивным при ограничении этим классом.
^ Смит, Эгген и Сент-Андре 2006 , стр. 146.
^ Бьянки, Мариаграция; Маури, Анна Гиллио Берта; Херцог, Марсель; Верарди, Либеро (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 .

Ссылки [ править ]

Гримальди, Ральф П. (1994), Дискретная и комбинаторная математика (3-е изд.), Аддисон-Уэсли, ISBN 0-201-19912-2
Лю, CL (1985), Элементы дискретной математики , McGraw-Hill, ISBN 0-07-038133-Х
Гюнтер Шмидт , 2010. Реляционная математика . Издательство Кембриджского университета, ISBN 978-0-521-76268-7 .
Смит, Дуглас; Эгген, Морис; Сент-Андре, Ричард (2006), Переход к высшей математике (6-е изд.), Брукс/Коул, ISBN 978-0-534-39900-9
Пфайффер, Г. (2004). Подсчет транзитивных отношений. Журнал целочисленных последовательностей , 7 (2), 3.

Внешние ссылки [ править ]

«Транзитивность» , Математическая энциклопедия , EMS Press , 2001 [1994]
в действии Транзитивность

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

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

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

[4] Бьянки, Мариаграция; Маури, Анна Гиллио Берта; Херцог, Марсель; Верарди, Либеро (12 января 2000 г.). «О конечных разрешимых группах, в которых нормальность является транзитивным отношением» . Журнал теории групп . 3 (2). дои : 10.1515/jgth.2000.012 . ISSN 1433-5883 . Архивировано из оригинала 4 февраля 2023 г. Проверено 29 декабря 2022 г.

[Derek.1964-5] Перейти обратно: ^а ^б Робинсон, Дерек Дж. С. (январь 1964 г.). «Группы, в которых нормальность является транзитивным отношением» . Математические труды Кембриджского философского общества . 60 (1): 21–38. Бибкод : 1964PCPS...60...21R . дои : 10.1017/S0305004100037403 . ISSN 0305-0041 . S2CID 119707269 . Архивировано из оригинала 4 февраля 2023 г. Проверено 29 декабря 2022 г.

[6] Флашка, В.; Ежек, Дж.; Кепка, Т.; Кортелайнен, Дж. (2007). Транзитивные замыкания бинарных отношений I (PDF) . Прага: Школа математики – Физика Карлова университета. п. 1. Архивировано из оригинала (PDF) 2 ноября 2013 г. Лемма 1.1 (iv). Обратите внимание, что в этом источнике асимметричные отношения называются «строго антисимметричными».

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

[Liu112-8] Перейти обратно: ^а ^б Лю 1985 , стр. 112.

[9] Стивен Р. Финч, «Транзитивные отношения, топологии и частичные порядки». Архивировано 4 марта 2016 г. в Wayback Machine , 2003 г.

[10] Гетц Пфайффер, « Подсчет транзитивных отношений, архивировано 4 февраля 2023 г. в Wayback Machine », Journal of Integer Sequences , Vol. 7 (2004 г.), статья 04.3.2.

[11] Гуннар Бринкманн и Брендан Д. Маккей, « Подсчет неразмеченных топологий и транзитивных отношений. Архивировано 20 июля 2005 г. в Wayback Machine ».

[12] Клейтман, Д.; Ротшильд, Б. (1970), «Число конечных топологий», Труды Американского математического общества , 25 (2): 276–282, JSTOR 2037205

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

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

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

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

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

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

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

[20] Сен, А. (1969). «Квазитранзитивность, рациональный выбор и коллективные решения». Преподобный экон. Стад . 36 (3): 381–393. дои : 10.2307/2296434 . JSTOR 2296434 . Збл 0181.47302 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]