Непроницаемость - Intransitivity - Wikipedia

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

Непроницаемость

Отношение является транзитивным, если всякий раз, когда оно связывает некоторый A с некоторым B, а B с некоторым C, оно также связывает это A с этим C. Некоторые авторы называют отношением непереходный если оно не транзитивно, т.е. (если рассматриваемое отношение названо )

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

Например, в пищевая цепочка Волки питаются оленями, олени - травой, но волки не питаются травой.[1] Таким образом питаться отношения между формами жизни в этом смысле непереходны.

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

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

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

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

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

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

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

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

Антитранзитивное отношение всегда иррефлексивно. оставили- (или же верно- ) уникальное отношение всегда антитранзитивно. Примером первого является отношение мать связь. Если А мать B, и B мать C, тогда А не может быть матерью C.

Циклы

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

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

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

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

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

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

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

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

каменьножницыбумага
камень010
ножницы001
бумага100

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

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

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

Вероятность

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

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

Такие как:

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

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

Рекомендации

  1. ^ Волки делать на самом деле едят траву - смотрите Энгель, Синди (2003). Здоровье дикой природы: уроки естественного благополучия из царства животных (под ред. в мягкой обложке). Хоутон Миффлин. п. 141. ISBN  0-618-34068-8..
  2. ^ "Путеводитель по логике, отношения II". Архивировано из оригинал на 2008-09-16. Получено 2006-07-13.
  3. ^ "Непереходное отношение". Архивировано из оригинал на 2016-03-03. Получено 2006-07-13.
  4. ^ Поддяков, Александр (2018). «Непереходные машины». arXiv:1809.03869 [math.HO ].
  5. ^ Керр, Бенджамин; Райли, Маргарет А .; Фельдман, Маркус У .; Боханнан, Брендан Дж. М. (2002). «Локальное рассредоточение способствует сохранению биоразнообразия в реальной игре камень-ножницы-бумага». Природа. 418 (6894): 171–174. Дои:10.1038 / природа00823. PMID  12110887.
  6. ^ Leutwyler, K. (2000). Спаривание ящериц играет в игру «камень-ножницы-бумага». Scientific American.
  7. ^ Атертон, К. Д. (2013). Краткая история исчезновения боевых ботов.

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