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

Эта статья о нетранзитивности в математике. Чтобы узнать о других значениях, см. Непереходный (значения) .

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

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

Отношение является транзитивным, если всякий раз, когда оно связывает некоторое А с некоторым В и какое-то В с некоторым С, оно также связывает это А с этим С. Некоторые авторы называют отношение интранзитивным , если оно не транзитивно, то есть (если отношение о котором идет речь, называется $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.

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

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

Антитранзитивность

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

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

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

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

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

Например, отношение 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 элементов никогда не является связным . На трехэлементном множестве изображенный цикл обладает обоими свойствами.
• Иррефлексивное и левое (или правое ) уникальное отношение всегда антитранзитивно. Примером первого является материнское отношение. Если А — мать В , а В — мать С то А не может быть матерью С. ,
• Если отношение R антитранзитивно, то антитранзитивным является и каждое его подмножество .

Циклы

Иногда, когда людей спрашивают об их предпочтениях с помощью серии бинарных вопросов, они дают логически невозможные ответы: 1 лучше, чем 2, 2 лучше, чем 3, но 3 лучше, чем 1.

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

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

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

Предполагая, что ни один вариант не является предпочтительным для самого себя, т.е. отношение иррефлексивно , отношение предпочтения с циклом не является транзитивным. Если это так, то каждая опция в цикле предпочтительнее каждой опции, включая саму себя. Это можно проиллюстрировать на примере цикла между 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 между общественным сознанием и финансовым консерватизмом.

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

Дальнейшее чтение

• Ананд, П. (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 .