Квазитранзитивное отношение

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

Формальное определение

Бинарное отношение T над множеством X является квазитранзитивным , если для всех a , b и c в X выполняется следующее:

(a\operatorname {T} b)\wedge \neg (b\operatorname {T} a)\wedge (b\operatorname {T} c)\wedge \neg (c\operatorname {T} b)\Rightarrow (a\operatorname {T} c)\wedge \neg (c\operatorname {T} a).

Если отношение также антисимметрично , T транзитивно.

Альтернативно, для отношения T определите асимметричную или «строгую» часть P:

(a\operatorname {P} b)\Leftrightarrow (a\operatorname {T} b)\wedge \neg (b\operatorname {T} a).

Тогда T квазитранзитивен тогда и только тогда, когда P транзитивен.

Примеры

предпочтения Предполагается, что квазитранзитивны (а не транзитивны) в некоторых экономических контекстах. Классический пример — человек, безразличный к 7–8 граммам сахара и безразличный к 8–9 граммам сахара, но предпочитающий 9 граммов сахара 7. ^[1] Точно так же парадокс Сорита можно разрешить, ослабив предполагаемую транзитивность некоторых отношений до квазитранзитивности.

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

Отношение R является квазитранзитивным тогда и только тогда, когда оно представляет собой дизъюнктное объединение симметричного отношения J и транзитивного отношения P . ^[2] J и P не определяются однозначно данным R ; ^[3] однако P из части «только если» минимально. ^[4]
Как следствие, каждое симметричное отношение квазитранзитивно, как и каждое транзитивное отношение. ^[5] Более того, антисимметричное и квазитранзитивное отношение всегда транзитивно. ^[6]
Соотношение из приведенного выше примера сахара: {(7,7), (7,8), (7,9), (8,7), (8,8), (8,9), (9,8) , (9,9)} квазитранзитивен, но не транзитивен.
Квазитранзитивное отношение не обязательно должно быть ациклическим : для любого непустого множества A универсальное отношение A × A является одновременно циклическим и квазитранзитивным.
Отношение является квазитранзитивным тогда и только тогда, когда таковым является его дополнение .
Аналогично, отношение квазитранзитивно тогда и только тогда, когда таково обратное ему отношение .

См. также

Ссылки

^ Роберт Дункан Люс (апрель 1956 г.). «Полупорядки и теория дискриминации по полезности» (PDF) . Эконометрика . 24 (2): 178–191. дои : 10.2307/1905751 . JSTOR 1905751 . Здесь: стр.179; Исходный пример Люси состоит из 400 сравнений (кофейных чашек с разным количеством сахара), а не только из двух.
^ Название следует за Bossert & Suzumura (2009) , стр.2-3. — Для части «только если» определите xJy как xRy ∧ yRx и определите xPy как xRy ∧ ¬ yRx . — В части if предположим, что выполнено xRy ∧ ¬ yRx ∧ yRz ∧ ¬ zRy . Тогда xPy и yPz , поскольку xJy или yJz будут противоречить ¬yRx или ¬zRy . Следовательно, xPz по транзитивности, ¬ xJz по дизъюнктности, ¬ zJx по симметрии. Следовательно, из zRx будет следовать zPx и, по транзитивности, zPy , что противоречит ¬ zRy . В целом это доказывает xRz ∧ ¬ zRx .
^ Например, если R является отношением эквивалентности , J можно выбрать как пустое отношение или как R сам , а P как его дополнение.
^ Учитывая R , всякий раз, когда выполняется xRy ∧ ¬ yRx , пара ( x , y ) не может принадлежать симметричной части, но должна принадлежать транзитивной части.
^ Поскольку пустое отношение тривиально транзитивно и симметрично.
^ Антисимметрия R заставляет J быть корефлексивным ; следовательно, объединение J и транзитивного P снова транзитивно.

Сен, А. (1969). «Квазитранзитивность, рациональный выбор и коллективные решения». Преподобный экон. Стад . 36 (3): 381–393. дои : 10.2307/2296434 . JSTOR 2296434 . Збл 0181.47302 .
Фредерик Шик (июнь 1969 г.). «Доказательство Стрелы и логика предпочтения». Философия науки . 36 (2): 127–144. дои : 10.1086/288241 . JSTOR 186166 . S2CID 121427121 .
Амартия К. Сен (1970). Коллективный выбор и социальное благосостояние . Холден-Дэй, Инк.
Амартия К. Сен (июль 1971 г.). «Функции выбора и выявленные предпочтения» (PDF) . Обзор экономических исследований . 38 (3): 307–317. дои : 10.2307/2296384 . JSTOR 2296384 .
А. Мас-Колелл и Х. Зонненшайн (1972). «Общие теоремы о возможности групповых решений» (PDF) . Обзор экономических исследований . 39 (2): 185–192. дои : 10.2307/2296870 . JSTOR 2296870 . S2CID 7295776 . Архивировано из оригинала (PDF) 12 апреля 2018 г.
Д. Х. Блэр и Р. А. Поллак (1982). «Правила ациклического коллективного выбора». Эконометрика . 50 (4): 931–943. дои : 10.2307/1912770 . JSTOR 1912770 .
Боссерт, Уолтер; Судзумура, Котаро (апрель 2005 г.). Рациональный выбор в произвольных областях: комплексное рассмотрение (PDF) (технический отчет). Университет Монреаля, Университет Хитоцубаши, Токио.
Боссерт, Уолтер; Судзумура, Котаро (март 2009 г.). «Квазитранзитивные и непротиворечивые отношения Судзумуры» (PDF) . Социальный выбор и благосостояние (технический отчет). 39 (2–3). Университет Монреаля, Университет Васэда, Токио: 323–334. дои : 10.1007/s00355-011-0600-z . S2CID 38375142 . Архивировано из оригинала (PDF) 12 апреля 2018 г.
Боссерт, Уолтер; Судзумура, Котаро (2010). Последовательность, выбор и рациональность . Издательство Гарвардского университета. ISBN 978-0674052994 .
Алан Д. Миллер и Ширан Рахмилевич (февраль 2014 г.). Теорема Эрроу без транзитивности (PDF) (рабочий документ). Университет Хайфы.

[1] Роберт Дункан Люс (апрель 1956 г.). «Полупорядки и теория дискриминации по полезности» (PDF) . Эконометрика . 24 (2): 178–191. дои : 10.2307/1905751 . JSTOR 1905751 . Здесь: стр.179; Исходный пример Люси состоит из 400 сравнений (кофейных чашек с разным количеством сахара), а не только из двух.

[2] Название следует за Bossert & Suzumura (2009) , стр.2-3. — Для части «только если» определите xJy как xRy ∧ yRx и определите xPy как xRy ∧ ¬ yRx . — В части if предположим, что выполнено xRy ∧ ¬ yRx ∧ yRz ∧ ¬ zRy . Тогда xPy и yPz , поскольку xJy или yJz будут противоречить ¬yRx или ¬zRy . Следовательно, xPz по транзитивности, ¬ xJz по дизъюнктности, ¬ zJx по симметрии. Следовательно, из zRx будет следовать zPx и, по транзитивности, zPy , что противоречит ¬ zRy . В целом это доказывает xRz ∧ ¬ zRx .

[3] Например, если R является отношением эквивалентности , J можно выбрать как пустое отношение или как R сам , а P как его дополнение.

[4] Учитывая R , всякий раз, когда выполняется xRy ∧ ¬ yRx , пара ( x , y ) не может принадлежать симметричной части, но должна принадлежать транзитивной части.

[5] Поскольку пустое отношение тривиально транзитивно и симметрично.

[6] Антисимметрия R заставляет J быть корефлексивным ; следовательно, объединение J и транзитивного P снова транзитивно.

[1]

[2]

[3]

[4]

[5]

[6]