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

Лекция

Привет, Вы узнаете о том , что такое транзитивное отношение, Разберем основные их виды и особенности использования. Еще будет много подробных примеров и описаний. Для того чтобы лучше понимать что такое транзитивное отношение , настоятельно рекомендую прочитать все из категории Дискретная математика. Теория множеств . Теория графов . Комбинаторика..

В математике бинарное отношение 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 .

Определение

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

для всех a , b , c ∈ X , если a ∈ b и b ∈ c , то a ∈ c .

Или, говоря логикой первого порядка :

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

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

где $a R b$ — инфиксное обозначение для $(a, b)$ ∈ $R.$

Примеры

В качестве нематематического примера, отношение «является предком» является транзитивным. Об этом говорит сайт https://intellect.icu . Например, если Эми является предком Бекки, а Бекки является предком Кэрри, то Эми также является предком Кэрри.

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

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

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

Если 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$ таким образом, что $а Р б$ и $б Р с$ Следовательно, условие транзитивности является пустым . Отношение $R,$ содержащее только одну упорядоченную пару , также транзитивно: если упорядоченная пара имеет вид $(x,x)$ для некоторых $x\in X$ единственные такие элементы $a,b,c\in X$ являются $a=b=c=x$ и действительно в этом случае $а Р с$ , тогда как если упорядоченная пара не имеет вида $(x,x)$ тогда таких элементов не существует. $a,b,c\in X$ и, следовательно $Р$ является пустым транзитивным.

Пустая транзитивность — это транзитивность, когда в отношении отсутствуют упорядоченные пары вида ( a , b ) и ( b , c ).

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

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

Обратное (инверсное) отношение транзитивности всегда транзитивно. Например, зная, что «является подмножеством » транзитивно, а «является надмножеством » — его обратное, можно заключить , что последнее также транзитивно.
Пересечение двух транзитивных отношений всегда транзитивно. ^{[ 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 = { (1,2), (2,3), (1,3) } является транзитивным, но не рефлексивным.

В качестве контрпримера рассмотрим отношение $<$ Фраза «на действительных числах» транзитивна, но не рефлексивна.

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

Пусть R — бинарное отношение на множестве X. Транзитивное расширение R , обозначаемое R 1 , — это наименьшее бинарное отношение на X такое, что R 1 содержит R , и если ( a , b ) ∈ R и ( b , c ) ∈ R , то ( a , c ) ∈ R 1. [ 7 ] Например, предположим, что X — множество городов, некоторые из которых соединены дорогами. Пусть R — отношение на городах, где ( A , B ) ∈ R, если существует дорога, непосредственно соединяющая город A и город B. Это отношение не обязательно должно быть транзитивным. Транзитивное расширение этого отношения можно определить как ( A , C ) ∈ R 1 , если можно перемещаться между городами A и C , используя не более двух дорог.

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

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

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

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

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

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

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

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

Неизвестна общая формула, которая подсчитывает количество транзитивных отношений на конечном множестве (последовательность A006905 в OEIS ). [ 9 ] Однако существует формула для нахождения количества отношений, которые одновременно являются рефлексивными, симметричными и транзитивными — другими словами, отношениями эквивалентности — (последовательность A000110 в OEIS ), симметричными и транзитивными, симметричными, транзитивными и антисимметричными, а также полными, транзитивными и антисимметричными. Пфайффер [ 10 ] добился некоторого прогресса в этом направлении, выражая отношения с комбинациями этих свойств через друг друга, но вычислить хотя бы одно из них по-прежнему сложно. Вау!! 😲 Ты еще не читал? Это зря! Бринкманн и Маккей (2005) ^{[ 11 ]} и Мала (2022). ^{[ 12 ]}

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

Количество n -элементных бинарных отношений различных типов
Элементы	Любой	Транзитивный	Рефлексивный	Симметричный	Предварительный заказ	Частичный порядок	Общий объем предзаказов	Полный заказ	Отношение эквивалентности
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	4096	1024	355	219	75	24	15
н	2 ^{н ²}		2 ^{n ( n −1)}	2 ^{n ( n +1)/2}			∑n k =0 k ! S ( n , k )	н !	∑n k =0 S ( n , k )
ОЭСР	A002416	A006905	A053763	A006125	A000798	A001035	A000670	A000142	A000110

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

Связанные объекты

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

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

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

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

Утверждение: Если R — однолистный оператор , то R;R T транзитивен.

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

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

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

Тогда существуют a и b такие, что

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

Поскольку R является однолистным, yRb и aR ^Ty подразумевают a = b . Следовательно, x R a R ^Tz , отсюда x R;R ^Tz и R;R ^T транзитивны.

Следствие : Если R является однолистным, то R;R T является отношением эквивалентности на области определения R.

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

Вау!! 😲 Ты еще не читал? Это зря!

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

Исследование, описанное в статье про транзитивное отношение, подчеркивает ее значимость в современном мире. Надеюсь, что теперь ты понял что такое транзитивное отношение и для чего все это нужно, а если не понял, или есть замечания, то не стесняйся, пиши или спрашивай в комментариях, с удовольствием отвечу. Для того чтобы глубже понять настоятельно рекомендую изучить всю информацию из категории Дискретная математика. Теория множеств . Теория графов . Комбинаторика.

Ответы на вопросы для самопроверки пишите в комментариях, мы проверим, или же задавайте свой вопрос по данной теме.