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

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

Тип	Бинарное отношение
Поле	Элементарная алгебра
Заявление	Отношение $R$ на съемочной площадке $X$ транзитивно, если для всех элементов $a$, $b$, $c$ в $X$, в любое время $R$ относится $a$ к $b$ и $b$ к $c$, затем $R$ также относится $a$ к $c$.
Символическое заявление	$\forall a,b,c\in X:(aRb\wedge bRc)\Rightarrow aRc$

В математике бинарное отношение 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}}$
Y 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 Y 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 является транзитивным отношением , если:

для всех a , b , c ∈ 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 ∈ R. )

Примеры

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

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

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

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

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

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

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

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

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

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

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

Пустое отношение на любом множестве $X$ транзитивен потому что нет элементов $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$ является вакуумно транзитивным.

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

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

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

Другие объекты недвижимости

Транзитивное отношение асимметрично тогда и только тогда, когда оно иррефлексивно .

Транзитивное отношение не обязательно должно быть рефлексивным . В этом случае это называется предзаказом . Например, для набора 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 _, наименьшим бинарным отношением на X такое, что содержит _, R , и если ( a , b ) ∈ R ∈ ( b , c ) ∈ R то ( a , является c ) R1 _R1 . Например, предположим, что X — это набор городов, некоторые из которых соединены дорогами. Пусть R — отношение к городам, где ( A , B ) ∈ R если существует дорога, напрямую соединяющая города A и B. , Это отношение не обязательно должно быть транзитивным. Транзитивное расширение этого отношения можно определить как ( A , C ) ∈ R1 _, если вы можете путешествовать между городами A и C, используя не более двух дорог.

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

Транзитивное расширение R ₁ будет обозначаться как R ₂ , и, продолжая в том же духе, в общем случае транзитивное расширение R _i будет равно R _{i + 1} . Транзитивное замыкание R обозначаемое , R * или R ^∞ представляет собой объединение множеств R , R ₁ , R ₂ , ... .

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

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

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

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

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

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

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

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

Количество n -элементных бинарных отношений разных типов

Elem­ents	Любой	Переходный	Рефлексивный	Симметричный	Предварительный заказ	Частичный заказ	Общий предзаказ	Общий заказ	Отношение эквивалентности
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		2 п ( п -1)	2 п ( п +1)/2			∑ н к = 0 к ! С ( п , к )	н !	∑ н k =0 S ( n , 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 — четное число, является нетранзитивным, но не антитранзитивен. Отношение, определяемое xRy , если x четное, а y нечетное , является одновременно транзитивным и антитранзитивным. Отношение, определяемое xRy , если x является порядковым номером y, является нетранзитивным. и антитранзитивен. Неожиданные примеры нетранзитивности возникают в таких ситуациях, как политические вопросы или групповые предпочтения.

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

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

Предложение: Если 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 выполняется транзитивное требование эквивалентности.

См. также

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

Ссылки

• Гримальди, Ральф П. (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]
• Транзитивность действии в