Полузаказ

Диаграмма Хассе полупорядка. Два объекта считаются сопоставимыми, если их вертикальные координаты отличаются хотя бы на одну единицу (расстояние между сплошными синими линиями).

В теории порядка , разделе математики, полупорядок — это тип упорядочивания элементов с числовыми оценками, при котором элементы с сильно различающимися оценками сравниваются по их баллам и где баллы в пределах заданной погрешности считаются несравнимыми . Полупорядки были введены и применены в математической психологии Дунканом Люсом ( 1956 ) как модель человеческих предпочтений. Они обобщают строгую слабую упорядоченность , при которой элементы с одинаковыми баллами могут быть связаны, но при этом отсутствует погрешность. Они представляют собой частный случай частичных порядков и интервальных порядков и могут быть охарактеризованы среди частичных порядков дополнительными аксиомами или двумя запрещенными подзаказами из четырех предметов.

Теория полезности

Первоначальной мотивацией введения полупорядков было моделирование человеческих предпочтений без предположения, что несравнимость является транзитивным отношением . Например, предположим, что $x$, $y$, и $z$ представляют собой три количества одного и того же материала, и что $x$ больше, чем $z$ на наименьшую величину, воспринимаемую как разницу, в то время как $y$ находится на полпути между ними двумя. Тогда человек, которому нужно больше материала, предпочтет $x$ к $z$, но не будет иметь предпочтения между двумя другими парами. В этом примере $x$ и $y$ несравнимы в порядке предпочтений, как и $y$ и $z$, но $x$ и $z$ сравнимы, поэтому несравнимость не подчиняется переходному закону.

Чтобы смоделировать это математически, предположим, что объектам заданы числовые значения полезности , полагая $u$ любая функция полезности , которая отображает сравниваемые объекты (набор $X$) к действительным числам . Установите числовой порог (который можно нормализовать до 1), чтобы коммунальные услуги в пределах этого порога были объявлены несравнимыми, и определите бинарное отношение. $<$ на объектах, установив $x<y$ в любое время $u(x)\leq u(y)-1$. Затем $(X,<)$ образует полупорядок. Если вместо этого объекты объявляются сравнимыми всякий раз, когда их полезности различаются, результатом будет строгое слабое упорядочение , для которого несравнимость объектов (основанная на равенстве чисел) будет транзитивной.

Аксиоматика

Запрещено: два взаимно несравнимых двухточечных линейных порядка.

Запрещено: три линейно упорядоченные точки и четвертая несравнимая точка.

Полупорядок, определенный из функции полезности, как указано выше, представляет собой частично упорядоченный набор со следующими двумя свойствами:

• Всякий раз, когда две непересекающиеся пары элементов сравнимы, например, как $w<x$ и $y<z$, должно быть дополнительное сравнение между этими элементами, потому что $u(w)\leq u(y)$ будет означать $w<z$ пока $u(w)\geq u(y)$ будет означать $y<x$. Поэтому невозможно иметь два взаимно несравнимых двухточечных линейных порядка .
• Если три элемента образуют линейный порядок $w<x<y$, то каждая четвертая точка $z$ должно быть сравнимо хотя бы с одним из них, поскольку $u(z)\leq u(x)$ будет означать $z<y$ пока $u(z)\geq u(x)$ будет означать $w<z$, в любом случае показывая, что $z$ сравнимо с $w$ или чтобы $y$. Поэтому невозможно иметь трехточечный линейный порядок с четвертой несравнимой точкой.

И наоборот, каждому конечному частичному порядку, который позволяет избежать двух запрещенных четырехточечных порядков, описанных выше, можно присвоить значения полезности, превращая его в полупорядок. не являются следствием определения с точки зрения полезности Следовательно, эти запрещенные порядки или эквивалентные системы аксиом , а могут быть приняты как комбинаторное определение полупорядков. Если полузаказ на $n$ элементов задан только через отношение порядка между его парами элементов, подчиняющихся этим аксиомам, то можно построить функцию полезности, которая представляет порядок во времени. $O(n^{2})$, где $O$ является примером большой записи O.

Для порядков на бесконечных множествах элементов порядки, которые могут быть определены функциями полезности, и порядки, которые могут быть определены запрещенными четырехточечными порядками, отличаются друг от друга. Например, если полупорядок $(X,<)$ (согласно определению запрещенных порядков) включает в себя несчетное полностью упорядоченное подмножество , то не существует достаточного количества достаточно хорошо расположенных действительных чисел, чтобы его можно было представить функцией полезности. Фишберн (1973) дает точную характеристику полупорядков, которые можно определить численно.

Связь с другими видами заказов

Частичные заказы

Можно определить частичный порядок $(X,\leq )$ из полузаказа $(X,<)$ заявив, что $x\leq y$ всякий раз, когда либо $x<y$ или $x=y$. Из аксиом, которым должен подчиняться частичный порядок, рефлексивность ( $x\leq x$) автоматически следует из этого определения. Антисимметрия (если $x\leq y$ и $y\leq x$ затем $x=y$) следует из аксиомы первого полупорядка. Транзитивность (если $x\leq y$ и $y\leq z$ затем $x\leq z$) следует из аксиомы второго полупорядка. Следовательно, бинарное отношение $(X,\leq )$ определенный таким образом, отвечает трем требованиям частичного порядка: он должен быть рефлексивным, антисимметричным и транзитивным.

Обратно, предположим, что $(X,\leq )$ представляет собой частичный порядок, построенный таким образом из полупорядка. Тогда полупорядок можно восстановить, заявив, что $x<y$ в любое время $x\leq y$ и $x\neq y$. Однако не каждый частичный порядок таким образом приводит к полупорядку: первая из перечисленных выше аксиом полупорядка автоматически следует из аксиом, определяющих частичный порядок, а остальные — нет. Частичный порядок, включающий четыре элемента, образующие две двухэлементные цепи, привел бы к отношению $(X,<)$ что нарушает аксиому второго полупорядка,а частичный порядок, включающий четыре элемента, образующих цепочку из трех элементов, и несвязанный элемент нарушает аксиому третьего полупорядка (см. рисунки в разделе #Аксиоматика ).

Слабые заказы

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

Интервальные ордера

Полупорядок, определенный из функции полезности $u$ эквивалентно может быть определен как порядок интервалов, определяемый интервалами $[u(x),u(x)+1]$, поэтому каждый полупорядок является примером интервального порядка.Отношение является полупорядком тогда и только тогда, когда оно может быть получено как интервальный порядок интервалов единичной длины. $(\ell _{i},\ell _{i}+1)$.

отношения

По словам Амартии К. Сена , полузаказы исследовали Дин Т. Джеймисон и Лоуренс Дж. Лау. и оказалось частным случаем квазитранзитивных отношений . Фактически, каждый полупорядок квазитранзитивен, а квазитранзитивность инвариантна к добавлению всех пар несравнимых элементов. Удаление всех невертикальных красных линий из самого верхнего изображения приводит к созданию диаграммы Хассе для отношения, которое по-прежнему является квазитранзитивным, но нарушает как аксиому 2, так и аксиому 3; это отношение может больше не быть полезным в качестве упорядочения предпочтений.

Комбинаторное перечисление

Число различных полупорядков на $n$ немаркированные предметы обозначаются каталонскими числами.

$${\frac {1}{n+1}}{\binom {2n}{n}},$$

а количество полузаказов на $n$ помеченные элементы задаются последовательностью

1, 1, 3, 19, 183, 2371, 38703, 763099, 17648823, ... (последовательность A006531 в OEIS )

Другие результаты

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

Среди всех частичных порядков с фиксированным числом элементов и фиксированным числом сравнимых пар частичные порядки, имеющие наибольшее число линейных расширений, являются полупорядками.

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

Множество полупорядков на $n$-множество элементов хорошо градуировано : если два полупорядка в одном и том же множестве отличаются друг от друга добавлением или удалением $k$ отношения порядка, то можно найти путь $k$ шаги от первого полупорядка ко второму таким образом, что каждый шаг пути добавляет или удаляет одно отношение порядка, а каждое промежуточное состояние на пути само по себе является полупорядком.

Графы несравнимости полупорядков называются графами безразличия и являются частным случаем интервальных графов .

Ссылки

• Эйвери, Питер (1992), «Алгоритмическое доказательство представимости полупорядков», Journal of Algorithms , 13 (1): 144–147, doi : 10.1016/0196-6774(92)90010-A , MR   1146337 .
• Брайтуэлл, Грэм Р. (1989), «Полупорядки и гипотеза 1/3–2/3», Order , 5 (4): 369–380, doi : 10.1007/BF00353656 , S2CID   86860160 .
• Шандон, Ж.-Л.; Лемэр, Дж.; Пуже, Дж. (1978), «Подсчет квазипорядков на конечном множестве», Центр социальной математики. Практическая школа повышения квалификации. Математика и гуманитарные науки (62): 61–80, 83, MR   0517680 .
• Дин, РА; Келлер, Гордон (1968), «Естественные частичные порядки», Canadian Journal of Mathematics , 20 : 535–554, doi : 10.4153/CJM-1968-055-7 , MR   0225686 .
• Дуаньон, Жан-Поль; Фальмань, Жан-Клод (1997), «Хорошо оцененные семейства отношений», Discrete Mathematics , 173 (1–3): 35–44, doi : 10.1016/S0012-365X(96)00095-7 , MR   1468838 .
• Фишберн, Питер К. (1970), «Нетранзитивное безразличие с неравными интервалами безразличия», Журнал математической психологии , 7 : 144–149, doi : 10.1016/0022-2496(70)90062-3 , MR   0253942 .
• Фишберн, Питер К. (1973), «Интервальные представления для интервальных порядков и полупорядков», Журнал математической психологии , 10 : 91–105, doi : 10.1016/0022-2496(73)90007-2 , MR   0316322 .
• Фишберн, Питер С .; Троттер, В.Т. (1992), «Линейные расширения полупорядков: проблема максимизации», Discrete Mathematics , 103 (1): 25–40, doi : 10.1016/0012-365X(92)90036-F , MR   1171114 .
• Джеймисон, Дин Т .; Лау, Лоуренс Дж. (сентябрь 1973 г.), «Полупорядки и теория выбора», Econometrica , 41 (5): 901–912, doi : 10.2307/1913813 , JSTOR   1913813 .
• Джеймисон, Дин Т.; Лау, Лоуренс Дж. (сентябрь – ноябрь 1975 г.), «Полупорядки и теория выбора: коррекция», Econometrica , 43 (5–6): 979–980, doi : 10.2307/1911339 , JSTOR   1911339 .
• Джеймисон, Дин Т.; Лау, Лоуренс Дж. (июль 1970 г.), Полузаказы, выявленные предпочтения и теория потребительского спроса , Стэнфордский университет, Институт математических исследований в социальных науках . Представлено на Всемирном экономическом конгрессе в Кембридже в сентябре 1970 г.
• Джеймисон, Дин Т.; Лау, Лоуренс Дж. (октябрь 1977 г.), «Природа равновесия с полуупорядоченными предпочтениями», Econometrica , 45 (7): 1595–1605, doi : 10.2307/1913952 , JSTOR   1913952 .
• Ким, К.Х.; Руш, Ф.В. (1978), «Перечисление классов изоморфизма полупорядков», Журнал комбинаторики, информации и системных наук , 3 (2): 58–61, MR   0538212 .
• Люс, Р. Дункан (1956), «Полупорядки и теория дискриминации полезности» (PDF) , Econometrica , 24 (2): 178–191, doi : 10.2307/1905751 , JSTOR   1905751 , MR   0078632 .
• Рабинович, Исси (1977), «Теорема Скотта-Суппса о полупорядках», Журнал математической психологии , 15 (2): 209–212, doi : 10.1016/0022-2496(77)90030-x , MR   0437404 .
• Рабинович, Исси (1978), «Размерность полупорядков», Журнал комбинаторной теории, серия A , 25 (1): 50–61, doi : 10.1016/0097-3165(78)90030-4 , MR   0498294 .
• Робертс, Фред С. (1969), «Графики безразличия», Методы доказательства в теории графов (Труды Второй конференции по теории графов в Анн-Арборе, Анн-Арбор, Мичиган, 1968) , Academic Press, Нью-Йорк, стр. 139–146. , МР   0252267 .
• Скотт, Дана ; Суппес, Патрик (1958), «Основные аспекты теорий измерения», Журнал символической логики , 23 (2): 113–128, doi : 10.2307/2964389 , JSTOR   2964389 , MR   0115919 .
• Сен, Амартия К. (июль 1971 г.), «Функции выбора и выявленные предпочтения» (PDF) , Обзор экономических исследований , 38 (3): 307–317, doi : 10.2307/2296384 , JSTOR   2296384 .

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

• Пирлот, М.; Винке, доктор философии (1997), Полупорядки: свойства, представления, приложения , теория и библиотека решений. Серия Б: Математические и статистические методы, вып. 36, Дордрехт: Группа академических издателей Kluwer, ISBN  0-7923-4617-3 , МР   1472236 .