Квазитранзитивное отношение
Квазитранзитивное отношение x ≤ ⁠5/4⁠ y . Его симметричная и транзитивная части показаны синим и зеленым цветом соответственно.

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

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

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

( а Т ⁡ б ) ∧ ¬ ( б Т ⁡ а ) ∧ ( б Т ⁡ с ) ∧ ¬ ( с Т ⁡ б ) ⇒ ( а Т ⁡ с ) ∧ ¬ ( с Т ⁡ а ) . {\displaystyle (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:

( а П ⁡ б ) ⇔ ( а Т ⁡ б ) ∧ ¬ ( б Т ⁡ а ) . {\displaystyle (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 является как циклическим, так и квазитранзитивным.
  • Отношение квазитранзитивно тогда и только тогда, когда его дополнение квазитранзитивно.
  • Аналогично, отношение квазитранзитивно тогда и только тогда, когда его обратное отношение квазитранзитивно.

Смотрите также

Ссылки

  1. ↑ Роберт Дункан Люс (апрель 1956 г.). «Полупорядки и теория дискриминации по полезности» (PDF) . Econometrica . 24 (2): 178– 191. doi :10.2307/1905751. JSTOR  1905751.Здесь: стр. 179; Исходный пример Люса состоит из 400 сравнений (чашек кофе с разным количеством сахара), а не только из 2.
  2. ^ Название следует Bossert & Suzumura (2009), p.2-3. — Для части «только если» определим xJy как xRy ∧ yRx и определим xPy как xRy ∧ ¬ yRx . — Для части «если» предположим, что выполняется 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 снова транзитивно.
  • Сен, А. (1969). «Квазитранзитивность, рациональный выбор и коллективные решения». Rev. Econ. Stud . 36 (3): 381– 393. doi :10.2307/2296434. JSTOR  2296434. Zbl  0181.47302.
  • Фредерик Шик (июнь 1969 г.). «Доказательство Эрроу и логика предпочтения». Философия науки . 36 (2): 127– 144. doi :10.1086/288241. JSTOR  186166. S2CID  121427121.
  • Амартия К. Сен (1970). Коллективный выбор и социальное благосостояние . Holden-Day, Inc.
  • Амартия К. Сен (июль 1971 г.). «Функции выбора и выявленные предпочтения» (PDF) . Обзор экономических исследований . 38 (3): 307–317 . doi :10.2307/2296384. JSTOR  2296384.
  • A. Mas-Colell и H. Sonnenschein (1972). "Общие теоремы о возможности для групповых решений" (PDF) . The Review of Economic Studies . 39 (2): 185– 192. doi :10.2307/2296870. JSTOR  2296870. S2CID  7295776. Архивировано из оригинала (PDF) 2018-04-12.
  • DH Blair и RA Pollak (1982). «Ациклические правила коллективного выбора». Econometrica . 50 (4): 931– 943. doi :10.2307/1912770. JSTOR  1912770.
  • Боссерт, Уолтер; Судзумура, Котаро (апрель 2005 г.). Рациональный выбор в произвольных областях: всестороннее рассмотрение (PDF) (технический отчет). Университет Монреаля, Университет Хитоцубаши, Токио.
  • Bossert, Walter; Suzumura, Kotaro (март 2009). «Квазитранзитивные и согласованные по Судзумуре отношения» (PDF) . Social Choice and Welfare (технический отчет). 39 ( 2–3 ). Université de Montréal, Waseda University Tokyo: 323–334 . doi :10.1007/s00355-011-0600-z. S2CID  38375142. Архивировано из оригинала (PDF) 2018-04-12.
  • Боссерт, Уолтер; Судзумура, Котаро (2010). Последовательность, выбор и рациональность . Издательство Гарвардского университета. ISBN 978-0674052994.
  • Алан Д. Миллер и Ширан Рахмилевич (февраль 2014 г.). Теорема Эрроу без транзитивности (PDF) (рабочий документ). Университет Хайфы.
Взято с "https://en.wikipedia.org/w/index.php?title=Квазитранзитивная_отношение&oldid=1198625736"