Нетранзитивность

В математике , нетранзитивность (иногда называемая нетранзитивностью ) — это свойство бинарных отношений которые не являются транзитивными отношениями . которое не является транзитивным, или более сильное свойство антитранзитивности Это может включать любое отношение , , которое описывает отношение, которое никогда не является транзитивным.

Нетранзитивность [ править ]

Отношение является транзитивным, если всякий раз, когда оно связывает некоторое А с некоторым В и какое-то В с некоторым С, оно также связывает это А с этим С. Некоторые авторы называют отношение интранзитивным , если оно не транзитивно, то есть (если отношение о котором идет речь, называется $R$ )

\lnot \left(\forall a,b,c:aRb\land bRc\implies aRc\right).

Это утверждение эквивалентно

\exists a,b,c:aRb\land bRc\land \lnot (aRc).

Например, рассмотрим отношение R к целым числам таким, что a R b тогда и только тогда, когда a кратно b или делителю b . Это отношение непереходно, поскольку, например, 2 R 6 (2 делитель 6) и 6 R 3 (6 кратно 3), но 2 не является ни кратным, ни делителем 3. Это не означает, что отношение антитранзитивно (см. ниже); например, 2 R 6, 6 R 12 и 2 R 12.

Другой пример: в пищевой цепи волки питаются оленями, а олени питаются травой, но волки травой не питаются. ^[1] Таким образом, связь между формами жизни в этом смысле нетранзитивна.

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

Антитранзитивность [ править ]

Часто термин «интранзитивность» используется для обозначения более сильного свойства антитранзитивности.

В приведенном выше примере отношение питания не является транзитивным, но все же содержит некоторую транзитивность: например, люди питаются кроликами, кролики питаются морковью, а люди также питаются морковью.

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

\forall a,b,c:aRb\land bRc\implies \lnot (aRc).

Многие авторы используют термин «интранзитивность» для обозначения антитранзитивности . ^[2]^[3]

Например, отношение R к целым числам, такое что a R b тогда и только тогда, когда a + b нечетно, является нетранзитивным. Если a R b и b R c , то либо a и c нечетны, а b четно, или наоборот. В любом случае a + c четно.

Второй пример антитранзитивного отношения: отношение побежденного в турнирах на выбывание . Если игрок A победил игрока B, а игрок B победил игрока C, то A никогда не мог сыграть с C, и, следовательно, A не победил C.

Путем транспонирования каждая из следующих формул эквивалентна антитранзитивности R :

{\begin{aligned}&\forall a,b,c:aRb\land aRc\implies \lnot (bRc)\\[3pt]&\forall a,b,c:aRc\land bRc\implies \lnot (aRb)\end{aligned}}

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

Антитранзитивное отношение всегда иррефлексивно .
Антитранзитивное отношение на множестве из ≥4 элементов никогда не является связным . На трехэлементном множестве изображенный цикл обладает обоими свойствами.
Иррефлексивное и левое (или правое ) уникальное отношение всегда антитранзитивно. ^[4] Примером первого является материнское отношение. Если А — мать В , а В — мать С то А не может быть матерью С. ,
Если отношение R антитранзитивно, то антитранзитивным является и каждое его подмножество .

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

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

А предпочтительнее Б
B предпочтительнее C
C предпочтительнее A

Камень, бумага, ножницы ; непереходные игральные кости ; и игра Пенни являются примерами. Настоящие боевые отношения конкурирующих видов, ^[5] стратегии отдельных животных, ^[6] и бои дистанционно управляемых машин в шоу BattleBots («робот-дарвинизм») ^[7] может быть и циклическим.

Если предположить, что ни один вариант не является предпочтительным для самого себя, т. е. отношение иррефлексивно , отношение предпочтения с циклом не является транзитивным. Если это так, то каждая опция в цикле предпочтительнее каждой опции, включая саму себя. Это можно проиллюстрировать на примере цикла между A, B и C. Предположим, что отношение транзитивно. Тогда, поскольку A предпочтительнее B, а B предпочтительнее C, то и A предпочтительнее C. Но тогда, поскольку C предпочтительнее A, также и A предпочтительнее A.

Поэтому такая петля предпочтений (или цикл ) известна как интранзитивность .

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

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

	камень	ножницы	бумага
камень	0	1	0
ножницы	0	0	1
бумага	1	0	0

Первый аргумент отношения — это строка, а второй — столбец. Единицы указывают на то, что отношение выполняется, ноль указывает на то, что оно не выполняется. Теперь обратите внимание, что следующее утверждение верно для любой пары элементов x и y, взятых (с заменой) из набора {камень, ножницы, бумага}: если x побеждает y, а y побеждает z, то x не побеждает z. Следовательно, отношение антитранзитивно.

Таким образом, цикл не является ни необходимым, ни достаточным для того, чтобы бинарное отношение было антитранзитивным.

Вхождения в предпочтениях [ править ]

Нетранзитивность может возникнуть при правиле большинства , в вероятностных результатах теории игр и в методе голосования Кондорсе , при котором ранжирование нескольких кандидатов может создать петлю предпочтений при сравнении весов (см. Парадокс голосования ).
Непереходные игральные кости демонстрируют, что отношение «на кубике X выбрасывается большее число, чем на кубике Y , более чем в половине случаев» не обязательно должно быть транзитивным.
В психологии ) человека часто возникает нетранзитивность в системе ценностей (или предпочтений , или вкусов , потенциально приводящая к неразрешимым конфликтам.
Аналогично, в экономике нетранзитивность может проявляться в потребительских предпочтениях . Это может привести к поведению потребителей , не соответствующему совершенной экономической рациональности . Экономисты и философы задавались вопросом, обязательно ли нарушение транзитивности должно приводить к «иррациональному поведению» (см. Ананд (1993)).

Вероятность [ править ]

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

В таких случаях нетранзитивность сводится к более широкому уравнению численности людей и весов их единиц измерения при оценке кандидатов.

Такой как:

30% предпочитают соотношение 60/40 между общественным сознанием и финансовым консерватизмом.
50% выступают за соотношение 50/50 между общественным сознанием и финансовым консерватизмом.
20% выступают за соотношение 40/60 между общественным сознанием и финансовым консерватизмом.

Хотя каждый избиратель не может одинаково оценивать единицы измерения, тогда тенденция становится единым вектором , который, согласно консенсусу , является предпочтительным балансом критериев кандидата.

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

↑ Волки . действительно едят траву – см Энгель, Синди (2003). Здоровье дикой природы: уроки естественного благополучия из царства животных (изд. в мягкой обложке). Хоутон Миффлин. п. 141. ИСБН 0-618-34068-8 . .
^ «Руководство по логике, отношениям II» . Архивировано из оригинала 16 сентября 2008 г. Проверено 13 июля 2006 г.
^ «Интранзитивное отношение» . Архивировано из оригинала 3 марта 2016 г. Проверено 13 июля 2006 г.
^ Если aRb , bRc и aRc будут выполняться для некоторых a , b , c , то $a = b$ в силу левой уникальности, что противоречит aRb из-за иррефлексивности.
^ Керр, Бенджамин; Райли, Маргарет А.; Фельдман, Маркус В.; Боханнан, Брендан Дж. М. (2002). «Локальное расселение способствует сохранению биоразнообразия в реальной игре в камень-ножницы-бумага». Природа . 418 (6894): 171–174. Бибкод : 2002Natur.418..171K . дои : 10.1038/nature00823 . ПМИД 12110887 . S2CID 4348391 .
^ Лейтвайлер, К. (2000). Спаривающиеся ящерицы играют в игру «камень-ножницы-бумага». Научный американец.
^ Атертон, К.Д. (2013). Краткая история упадка боевых ботов.

Дальнейшее чтение [ править ]

Ананд, П. (1993). Основы рационального выбора в условиях риска . Оксфорд: Издательство Оксфордского университета. .
Бар-Хилель М. и Маргалит А. (1988). Насколько порочны циклы нетранзитивного выбора? Теория и решение, 24 (2), 119–145.
Клименко, Александр Юрьевич (2014). «Сложность и нетранзитивность в технологическом развитии» (PDF) . Журнал системной науки и системной инженерии . 23 (2): 128–152. дои : 10.1007/s11518-014-5245-x . S2CID 59390606 .
Клименко, Александр (2015). «Нетранзитивность в теории и в реальном мире» . Энтропия . 17 (12): 4364–4412. arXiv : 1507.03169 . Бибкод : 2015Entrp..17.4364K . дои : 10.3390/e17064364 .

[1] Волки . действительно едят траву – см Энгель, Синди (2003). Здоровье дикой природы: уроки естественного благополучия из царства животных (изд. в мягкой обложке). Хоутон Миффлин. п. 141. ИСБН 0-618-34068-8 . .

[2] «Руководство по логике, отношениям II» . Архивировано из оригинала 16 сентября 2008 г. Проверено 13 июля 2006 г.

[3] «Интранзитивное отношение» . Архивировано из оригинала 3 марта 2016 г. Проверено 13 июля 2006 г.

[4] Если aRb , bRc и aRc будут выполняться для некоторых a , b , c , то $a = b$ в силу левой уникальности, что противоречит aRb из-за иррефлексивности.

[5] Керр, Бенджамин; Райли, Маргарет А.; Фельдман, Маркус В.; Боханнан, Брендан Дж. М. (2002). «Локальное расселение способствует сохранению биоразнообразия в реальной игре в камень-ножницы-бумага». Природа . 418 (6894): 171–174. Бибкод : 2002Natur.418..171K . дои : 10.1038/nature00823 . ПМИД 12110887 . S2CID 4348391 .

[6] Лейтвайлер, К. (2000). Спаривающиеся ящерицы играют в игру «камень-ножницы-бумага». Научный американец.

[7] Атертон, К.Д. (2013). Краткая история упадка боевых ботов.

[1]

[2]

[3]

[4]

[5]

[6]

[7]