Непереходность

Свойство математических отношений

В математике интранзитивность (иногда называемая нетранзитивностью ) — это свойство бинарных отношений , которые не являются транзитивными отношениями . То есть, мы можем найти три значения , и , где условие транзитивности не выполняется. ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle c}$

Антитранзитивность — более сильное свойство , описывающее отношение, в котором для любых трех значений условие транзитивности никогда не выполняется.

Будьте осторожны, некоторые авторы используют термин «непереходный» для обозначения антитранзитивности. ^{[1] [2]}

Непереходность

Отношение транзитивно, если всякий раз, когда оно связывает некоторое A с некоторым B, а то B с некоторым C, оно также связывает то A с тем C. Отношение нетранзитивно , если оно не транзитивно. Предполагая, что отношение названо , оно нетранзитивно, если: ${\displaystyle R}$

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

Это утверждение эквивалентно $${\displaystyle \exists a,b,c:aRb\land bRc\land \lnot (aRc).}$$

Например, отношение неравенства, , является нетранзитивным. Это можно продемонстрировать, заменив на и выбрав , , и . Имеем и и неверно, что . ${\displaystyle \neq }$ ${\displaystyle R}$ ${\displaystyle \neq }$ ${\displaystyle a=1}$ ${\displaystyle b=2}$ ${\displaystyle c=1}$ ${\displaystyle 1\neq 2}$ ${\displaystyle 2\neq 1}$ ${\displaystyle 1\neq 1}$

Обратите внимание, что для того, чтобы отношение было нетранзитивным, условие транзитивности просто должно быть неверным при некоторых , , и . Оно может по-прежнему выполняться для других. Например, оно выполняется, когда , , и , тогда и и верно, что . ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle c}$ ${\displaystyle a=1}$ ${\displaystyle b=2}$ ${\displaystyle c=3}$ ${\displaystyle 1\neq 2}$ ${\displaystyle 2\neq 3}$ ${\displaystyle 1\neq 3}$

Для более сложного примера интранзитивности рассмотрим отношение 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 также.

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

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

Антитранзитивность отношения означает, что условие транзитивности не выполняется ни для каких трех значений.

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

Отношение антитранзитивно , если это вообще никогда не происходит. Формальное определение: $${\displaystyle \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 : $${\displaystyle {\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 элементов никогда не является connex . На множестве из 3 элементов изображенный цикл обладает обоими свойствами.
• Нерефлексивное и лево- (или право- ) уникальное отношение всегда антитранзитивно. ^[4] Примером первого является отношение матери . Если A является матерью B , а B является матерью C , то A не может быть матерью C .
• Если отношение R антитранзитивно, то таковым является и каждое подмножество R.

Циклы

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

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

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

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

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

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

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

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

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

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

Вхождения в предпочтения

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

Вероятность

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

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

Такой как:

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

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

Ссылки

1. "Руководство по логике, отношения II". Архивировано из оригинала 2008-09-16 . Получено 2006-07-13 .
2. "IntransitiveRelation". Архивировано из оригинала 2016-03-03 . Получено 2006-07-13 .
3. Волки на самом деле едят траву – см. Engel, Cindy (2003). Wild Health: Lessons in Natural Wellness from the Animal Kingdom (мягкая обложка). Houghton Mifflin. стр. 141. ISBN 0-618-34068-8..
4. Если бы aRb , bRc и aRc выполнялись для некоторых a , b , c , то a = b по левой единственности, что противоречит aRb по иррефлексивности.
5. Керр, Бенджамин; Райли, Маргарет А.; Фельдман, Маркус В.; Боханнан, Брендан Дж. М. (2002). «Локальное расселение способствует биоразнообразию в реальной игре «камень-ножницы-бумага». Nature . 418 (6894): 171–174. Bibcode :2002Natur.418..171K. doi :10.1038/nature00823. PMID  12110887. S2CID  4348391.
6. Лойтвайлер, К. (2000). Спаривающиеся ящерицы играют в «камень-ножницы-бумага». Scientific American.
7. Атертон, К. Д. (2013). Краткая история упадка боевых роботов.

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

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