Слабое упорядочение

Математическое ранжирование множества

Слабый порядок на множестве , где и имеют одинаковый ранг, ранжируется ниже их, а ранг — выше них. I) представление в виде строгого слабого порядка , где показано стрелкой от к ; II) представление в виде полного предпорядка , показано стрелками; III) представление в виде упорядоченного разбиения, с множествами разбиения в виде пунктирных эллипсов и полным порядком на этих множествах, показанным стрелками. ${\displaystyle \{a,b,c,d\}}$ ${\displaystyle b}$ ${\displaystyle c}$ ${\displaystyle a}$ ${\displaystyle d}$
${\displaystyle \,<\,}$ ${\displaystyle x<y}$ ${\displaystyle x}$ ${\displaystyle y}$
${\displaystyle \,\leq \,}$

13 возможных строгих слабых порядков на наборе из трех элементов . Единственные полные порядки показаны черным цветом. Два порядка соединены ребром, если они отличаются одной дихотомией. ${\displaystyle \{a,b,c\}.}$

В математике , особенно в теории порядка , слабое упорядочение — это математическая формализация интуитивного понятия ранжирования множества , некоторые члены которого могут быть связаны друг с другом. Слабые порядки являются обобщением полностью упорядоченных множеств (ранжирования без связей) и в свою очередь обобщаются (строго) частично упорядоченными множествами и предпорядками . ^[1]

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

Слабые упорядочения подсчитываются с помощью упорядоченных чисел Белла . Они используются в информатике как часть алгоритмов уточнения разделов и в стандартной библиотеке C++ . ^[2]

Примеры

В скачках использование фотофинишей устранило некоторые, но не все, ничьи или (как их называют в этом контексте) ничьё , поэтому исход скачек может быть смоделирован слабым упорядочением. ^[3] В примере с стипль-чезом Maryland Hunt Cup в 2007 году Брюс был явным победителем, но две лошади Баг Ривер и Лир Чарм разделили второе место, а остальные лошади оказались дальше; три лошади не финишировали. ^[4] В слабом упорядочении, описывающем этот результат, Брюс был бы первым, Баг Ривер и Лир Чарм были бы ранжированы после Брюса, но перед всеми другими лошадьми, которые финишировали, а три лошади, которые не финишировали, были бы размещены последними в порядке, но сравнялись бы друг с другом.

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

Опрос общественного мнения на политических выборах дает пример типа упорядочения, который напоминает слабые упорядочения, но лучше моделируется математически другими способами. В результатах опроса один кандидат может быть явно впереди другого, или два кандидата могут быть статистически равны, что означает не то, что их результаты опроса равны, а то, что они находятся в пределах погрешности друг друга. Однако, если кандидат статистически равен и статистически равен, то все еще может быть возможно, чтобы быть явно лучше, чем так что равенство в этом случае не является транзитивным отношением . Из-за этой возможности рейтинги этого типа лучше моделируются как полупорядки, чем как слабые упорядочения. ^[5] ${\displaystyle x}$ ${\displaystyle y,}$ ${\displaystyle y}$ ${\displaystyle z,}$ ${\displaystyle x}$ ${\displaystyle z,}$

Аксиоматизации

Предположим, что это однородное бинарное отношение на множестве (то есть, является подмножеством ) и, как обычно, запишем и скажем, что выполняется или является истинным тогда и только тогда, когда ${\displaystyle \,<\,}$ ${\displaystyle S}$ ${\displaystyle \,<\,}$ ${\displaystyle S\times S}$ ${\displaystyle x<y}$ ${\displaystyle x<y}$ ${\displaystyle (x,y)\in \,<.\,}$

Строгие слабые упорядочения

Предварительные сведения о несравнимости и транзитивности несравнимости

Два элемента и из называются несравнимыми относительно , ​​если ни один из них не является истинным. ^[1] Строгий частичный порядок является строгим слабым порядком тогда и только тогда, когда несравнимость относительно является отношением эквивалентности . Несравнимость относительно всегда является однородным симметричным отношением на Оно рефлексивно тогда и только тогда, когда является иррефлексивным (то есть всегда ложно), что будет предполагаться, так что транзитивность является единственным свойством, необходимым этому «отношению несравнимости» для того, чтобы быть отношением эквивалентности . ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle S}$ ${\displaystyle \,<\,}$ ${\displaystyle x<y}$ ${\displaystyle y<x}$ ${\displaystyle \,<\,}$ ${\displaystyle \,<\,}$ ${\displaystyle \,<\,}$ ${\displaystyle S.}$ ${\displaystyle \,<\,}$ ${\displaystyle x<x}$

Определите также индуцированное однородное отношение на , объявив , что где важно, это определение не обязательно совпадает с: если и только если Два элемента несравнимы относительно , ​​если и только если эквивалентны относительно (или менее многословно, -эквивалентны ), что по определению означает, что оба являются истинными. Отношение "несравнимы относительно " таким образом, идентично (то есть равно) отношению "являются -эквивалентными " (так что, в частности, первое является транзитивным тогда и только тогда, когда последнее является). Когда является иррефлексивным, то свойство, известное как "транзитивность несравнимости" (определенное ниже), является именно тем условием, необходимым и достаточным для того, чтобы гарантировать, что отношение "являются -эквивалентными" действительно образует отношение эквивалентности на Когда это так, это позволяет любым двум удовлетворяющим элементам быть идентифицированными как один объект (в частности, они идентифицируются вместе в их общем классе эквивалентности ). ${\displaystyle \,\lesssim \,}$ ${\displaystyle S}$ $${\displaystyle x\lesssim y{\text{ is true }}\quad {\text{ if and only if }}\quad y<x{\text{ is false}}}$$ ${\displaystyle x\lesssim y}$ ${\displaystyle x<y{\text{ or }}x=y.}$ ${\displaystyle x,y\in S}$ ${\displaystyle \,<\,}$ ${\displaystyle x{\text{ and }}y}$ ${\displaystyle \,\lesssim \,}$ ${\displaystyle \,\lesssim }$ ${\displaystyle x\lesssim y{\text{ and }}y\lesssim x}$ ${\displaystyle \,<}$ ${\displaystyle \,\lesssim }$ ${\displaystyle \,<\,}$ ${\displaystyle \,\lesssim }$ ${\displaystyle S.}$ ${\displaystyle x,y\in S}$ ${\displaystyle x\lesssim y{\text{ and }}y\lesssim x}$

Определение

Строгий слабый порядок на множестве — это строгий частичный порядок на , для которого отношение несравнимости, индуцированное на , является транзитивным отношением . ^[1] В явном виде строгий слабый порядок на — это однородное отношение на , обладающее всеми четырьмя из следующих свойств: ${\displaystyle S}$ ${\displaystyle \,<\,}$ ${\displaystyle S}$ ${\displaystyle S}$ ${\displaystyle \,<\,}$ ${\displaystyle S}$ ${\displaystyle \,<\,}$ ${\displaystyle S}$

1. Иррефлексивность : Для всехэто неправда, что ${\displaystyle x\in S,}$ ${\displaystyle x<x.}$
   • Это условие выполняется тогда и только тогда, когда индуцированное отношение является рефлексивным , где определяется объявлением того, что является истинным тогда и только тогда, когда является ложным . ${\displaystyle \,\lesssim \,}$ ${\displaystyle S}$ ${\displaystyle \,\lesssim \,}$ ${\displaystyle x\lesssim y}$ ${\displaystyle y<x}$
2. Транзитивность : Для всехеслито ${\displaystyle x,y,z\in S,}$ ${\displaystyle x<y{\text{ and }}y<z}$ ${\displaystyle x<z.}$
3. Асимметрия : для всехеслиистинно, толожно. ${\displaystyle x,y\in S,}$ ${\displaystyle x<y}$ ${\displaystyle y<x}$
4. Транзитивность несравнимости : для всехеслинесравнимо с(то есть ни то,ни другоеявляется истинным) и еслинесравнимо стонесравнимо с ${\displaystyle x,y,z\in S,}$ ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle x<y}$ ${\displaystyle y<x}$ ${\displaystyle y}$ ${\displaystyle z,}$ ${\displaystyle x}$ ${\displaystyle z.}$
   • Два элемента несравнимы относительно тогда и только тогда, когда они эквивалентны относительно индуцированного отношения (что по определению означает, что оба являются истинными), где, как и прежде, объявляется истинным тогда и только тогда, когда является ложным. Таким образом, это условие выполняется тогда и только тогда, когда симметричное отношение относительно, определяемое как « эквивалентны относительно », является транзитивным отношением, означающим, что всякий раз, когда являются -эквивалентными и также являются -эквивалентными, то обязательно являются -эквивалентными. Это также можно переформулировать как: всякий раз, когда и также, то обязательно ${\displaystyle x{\text{ and }}y}$ ${\displaystyle \,<\,}$ ${\displaystyle \,\lesssim \,}$ ${\displaystyle x\lesssim y{\text{ and }}y\lesssim x}$ ${\displaystyle x\lesssim y}$ ${\displaystyle y<x}$ ${\displaystyle S}$ ${\displaystyle x{\text{ and }}y}$ ${\displaystyle \,\lesssim \,}$ ${\displaystyle x{\text{ and }}y}$ ${\displaystyle \,\lesssim }$ ${\displaystyle y{\text{ and }}z}$ ${\displaystyle \,\lesssim }$ ${\displaystyle x{\text{ and }}z}$ ${\displaystyle \,\lesssim }$ ${\displaystyle x\lesssim y{\text{ and }}y\lesssim x}$ ${\displaystyle y\lesssim z{\text{ and }}z\lesssim y}$ ${\displaystyle x\lesssim z{\text{ and }}z\lesssim x.}$

Свойства (1), (2) и (3) являются определяющими свойствами строгого частичного порядка, хотя в этом списке есть некоторая избыточность, поскольку асимметрия (3) подразумевает иррефлексивность (1), а также потому, что иррефлексивность (1) и транзитивность (2) вместе подразумевают асимметрию (3). ^[6] Отношение несравнимости всегда симметрично и будет рефлексивным тогда и только тогда, когда является иррефлексивным отношением (что предполагается приведенным выше определением). Следовательно, строгий частичный порядок является строгим слабым порядком тогда и только тогда, когда его индуцированное отношение несравнимости является отношением эквивалентности . В этом случае его классы эквивалентности разбиваются и, более того, множество этих классов эквивалентности может быть строго полностью упорядочено бинарным отношением , также обозначаемым , которое определяется для всех следующим образом: ${\displaystyle \,<\,}$ ${\displaystyle \,<\,}$ ${\displaystyle S}$ ${\displaystyle {\mathcal {P}}}$ ${\displaystyle \,<,}$ ${\displaystyle A,B\in {\mathcal {P}}}$

${\displaystyle A<B{\text{ if and only if }}a<b}$для некоторых (или, что то же самое, для всех) представителей ${\displaystyle a\in A{\text{ and }}b\in B.}$

Наоборот, любой строгий полный порядок на разбиении порождает строгий слабый порядок на , определяемый соотношением тогда и только тогда, когда существуют множества в этом разбиении такие, что ${\displaystyle {\mathcal {P}}}$ ${\displaystyle S}$ ${\displaystyle \,<\,}$ ${\displaystyle S}$ ${\displaystyle a<b}$ ${\displaystyle A,B\in {\mathcal {P}}}$ ${\displaystyle a\in A,b\in B,{\text{ and }}A<B.}$

Не каждый частичный порядок подчиняется транзитивному закону для несравнимости. Например, рассмотрим частичный порядок в наборе, определяемом отношением Пары несравнимы, но и связаны, поэтому несравнимость не образует отношения эквивалентности, и этот пример не является строгим слабым порядком. ${\displaystyle \{a,b,c\}}$ ${\displaystyle b<c.}$ ${\displaystyle a,b{\text{ and }}a,c}$ ${\displaystyle b}$ ${\displaystyle c}$

Для транзитивности несравнимости каждое из следующих условий необходимо , а для строгих частичных порядков также достаточно :

• Если тогда для всех одно из них или оба. ${\displaystyle x<y}$ ${\displaystyle z,}$ ${\displaystyle x<z{\text{ or }}z<y}$
• Если несравнимо с , то для всех либо ( ), либо ( ), либо ( несравнимо с , а также несравнимо с ). ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle z}$ ${\displaystyle x<z{\text{ and }}y<z}$ ${\displaystyle z<x{\text{ and }}z<y}$ ${\displaystyle z}$ ${\displaystyle x}$ ${\displaystyle z}$ ${\displaystyle y}$

Всего предварительных заказов

Строгие слабые порядки очень тесно связаны с полными предпорядками или (нестрогими) слабыми порядками , и те же математические концепции, которые могут быть смоделированы с помощью строгих слабых порядков, могут быть смоделированы с равным успехом с помощью полных предпорядков. Полный предпорядок или слабый порядок — это предпорядок , в котором любые два элемента сравнимы. ^[7] Полный предпорядок удовлетворяет следующим свойствам: ${\displaystyle \,\lesssim \,}$

• Транзитивность : Для всех если то ${\displaystyle x,y,{\text{ and }}z,}$ ${\displaystyle x\lesssim y{\text{ and }}y\lesssim z}$ ${\displaystyle x\lesssim z.}$
• Сильная связанность : Для всех ${\displaystyle x{\text{ and }}y,}$ ${\displaystyle x\lesssim y{\text{ or }}y\lesssim x.}$
  • Что подразумевает рефлексивность : для всех ${\displaystyle x,}$ ${\displaystyle x\lesssim x.}$

Полный порядок — это полный предпорядок, который является антисимметричным, другими словами, который также является частичным порядком . Полные предпорядки иногда также называют отношениями предпочтения .

Дополнение строгого слабого порядка является полным предпорядком, и наоборот, но кажется более естественным связать строгие слабые порядки и полные предпорядки таким образом, чтобы сохранить, а не обратить порядок элементов. Таким образом, мы принимаем обратное дополнение : для строгого слабого порядка определяем полный предпорядок , устанавливая всякий раз, когда это не так, что В другом направлении, чтобы определить строгий слабый порядок < из полного предпорядка, установите всякий раз, когда это не так, что ^[8] ${\displaystyle \,<,}$ ${\displaystyle \,\lesssim \,}$ ${\displaystyle x\lesssim y}$ ${\displaystyle y<x.}$ ${\displaystyle \,\lesssim ,}$ ${\displaystyle x<y}$ ${\displaystyle y\lesssim x.}$

В любом предпорядке существует соответствующее отношение эквивалентности , где два элемента и определяются как эквивалентные , если В случае полного предпорядка соответствующий частичный порядок на множестве классов эквивалентности является полным порядком. Два элемента эквивалентны в полном предпорядке тогда и только тогда, когда они несравнимы в соответствующем строгом слабом порядке. ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle x\lesssim y{\text{ and }}y\lesssim x.}$

Упорядоченные разделы

Разбиение множества — это семейство непустых непересекающихся подмножеств , объединение которых равно . Разбиение вместе с полным порядком множеств разбиения дает структуру, названную Ричардом П. Стэнли упорядоченным разбиением ^[9], а Теодором Моцкиным — списком множеств . ^[10] Упорядоченное разбиение конечного множества может быть записано как конечная последовательность множеств в разбиении: например, три упорядоченных разбиения множества имеют вид ${\displaystyle S}$ ${\displaystyle S}$ ${\displaystyle S}$ ${\displaystyle \{a,b\}}$ $${\displaystyle \{a\},\{b\},}$$ $${\displaystyle \{b\},\{a\},\;{\text{ and }}}$$ $${\displaystyle \{a,b\}.}$$

В строгом слабом порядке классы эквивалентности несравнимости дают разбиение множеств, в котором множества наследуют общий порядок от своих элементов, порождая упорядоченное разбиение. В другом направлении любое упорядоченное разбиение порождает строгое слабое упорядочение, в котором два элемента несравнимы, когда они принадлежат одному и тому же множеству в разбиении, и в противном случае наследуют порядок множеств, которые их содержат.

Представление по функциям

Для множеств достаточно малой мощности возможна четвертая аксиоматизация, основанная на функциях с действительными значениями. Если — любое множество, то функция с действительными значениями на индуцирует строгий слабый порядок на устанавливая Связанный с этим полный предварительный порядок задается устанавливая и связанная с этим эквивалентность устанавливая ${\displaystyle X}$ ${\displaystyle f:X\to \mathbb {R} }$ ${\displaystyle X}$ ${\displaystyle X}$ $${\displaystyle a<b{\text{ if and only if }}f(a)<f(b).}$$ ${\displaystyle a{}\lesssim {}b{\text{ if and only if }}f(a)\leq f(b)}$ ${\displaystyle a{}\sim {}b{\text{ if and only if }}f(a)=f(b).}$

Отношения не меняются, когда заменяется на ( составная функция ), где — строго возрастающая вещественная функция, определенная по крайней мере в диапазоне Так, например, функция полезности определяет отношение предпочтения . В этом контексте слабые упорядочения также известны как предпочтительные расположения . ^[11] ${\displaystyle f}$ ${\displaystyle g\circ f}$ ${\displaystyle g}$ ${\displaystyle f.}$

Если является конечным или счетным, то каждый слабый порядок на может быть представлен функцией таким образом. ^[12] Однако существуют строгие слабые порядки, которые не имеют соответствующей действительной функции. Например, для лексикографического порядка на такой функции не существует. Таким образом, в то время как в большинстве моделей отношения предпочтений отношение определяет функцию полезности с точностью до преобразований, сохраняющих порядок, для лексикографических предпочтений такой функции не существует . ${\displaystyle X}$ ${\displaystyle X}$ ${\displaystyle \mathbb {R} ^{n}.}$

В более общем случае, если является множеством, является множеством со строгим слабым порядком и является функцией, то индуцирует строгий слабый порядок на , устанавливая Как и прежде, связанный полный предпорядок задается установкой , а связанная эквивалентность - установкой Здесь не предполагается, что является инъективной функцией , поэтому класс из двух эквивалентных элементов на может индуцировать больший класс эквивалентных элементов на Также не предполагается, что является сюръективной функцией , поэтому класс эквивалентных элементов на может индуцировать меньший или пустой класс на Однако функция индуцирует инъективную функцию , которая отображает разбиение на на разбиение на Таким образом, в случае конечных разбиений число классов в меньше или равно числу классов на ${\displaystyle X}$ ${\displaystyle Y}$ ${\displaystyle \,<,\,}$ ${\displaystyle f:X\to Y}$ ${\displaystyle f}$ ${\displaystyle X}$ $${\displaystyle a<b{\text{ if and only if }}f(a)<f(b).}$$ ${\displaystyle a{}\lesssim {}b{\text{ if and only if }}f(a){}\lesssim {}f(b),}$ ${\displaystyle a{}\sim {}b{\text{ if and only if }}f(a){}\sim {}f(b).}$ ${\displaystyle f}$ ${\displaystyle Y}$ ${\displaystyle X.}$ ${\displaystyle f}$ ${\displaystyle Y}$ ${\displaystyle X.}$ ${\displaystyle f}$ ${\displaystyle X}$ ${\displaystyle Y.}$ ${\displaystyle X}$ ${\displaystyle Y.}$

Связанные типы заказов

Полупорядки обобщают строгие слабые упорядочения, но не предполагают транзитивности несравнимости. ^[13] Строгий слабый порядок, который является трихотомическим, называется строгим полным порядком . ^[14] Полный предпорядок, который является обратным своему дополнению, в этом случае является полным порядком .

Для строгого слабого порядка другим связанным рефлексивным отношением является его рефлексивное замыкание , (нестрогий) частичный порядок. Два связанных рефлексивных отношения различаются относительно различных и для которых ни , ни : в общем предпорядке, соответствующем строгому слабому порядку, мы получаем и в то время как в частичном порядке, заданном рефлексивным замыканием, мы получаем ни , ни Для строгих общих порядков эти два связанных рефлексивных отношения одинаковы: соответствующий (нестрогий) полный порядок. ^[14] Рефлексивное замыкание строгого слабого порядка является типом последовательно-параллельного частичного порядка . ${\displaystyle \,<\,}$ ${\displaystyle \,\leq .}$ ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle a<b}$ ${\displaystyle b<a}$ ${\displaystyle a\lesssim b}$ ${\displaystyle b\lesssim a,}$ ${\displaystyle a\leq b}$ ${\displaystyle b\leq a.}$

Все слабые порядки на конечном множестве

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

Число различных слабых порядков (представленных либо как строгие слабые порядки, либо как общие предпорядки) на -элементном наборе задается следующей последовательностью (последовательность A000670 в OEIS ): ${\displaystyle n}$

Обратите внимание, что S ( n , k ) относится к числам Стирлинга второго рода .

Эти числа также называются числами Фубини или упорядоченными числами Белла .

Например, для набора из трех помеченных элементов существует один слабый порядок, в котором все три элемента связаны. Существует три способа разбиения элементов на один синглтон- набор и одну группу из двух связанных элементов, и каждое из этих разбиений дает два слабых порядка (один, в котором синглтон меньше группы из двух, и один, в котором этот порядок обратный), что дает шесть слабых порядков этого типа. И существует единственный способ разбиения набора на три синглтона, которые могут быть полностью упорядочены шестью различными способами. Таким образом, всего существует 13 различных слабых порядков для трех элементов.

Структура смежности

Пермутоэдр на четырех элементах, трехмерный выпуклый многогранник . Имеет 24 вершины, 36 ребер и 14 двумерных граней, которые вместе со всем трехмерным многогранником соответствуют 75 слабым упорядочениям на четырех элементах.

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

Геометрически, все упорядочения данного конечного множества могут быть представлены как вершины пермутоэдра , а дихотомии на этом же множестве как грани пермутоэдра. В этом геометрическом представлении слабые упорядочения на множестве соответствуют граням всех различных измерений пермутоэдра (включая сам пермутоэдр, но не пустое множество как грань). Коразмерность грани дает число классов эквивалентности в соответствующем слабом упорядочении. ^[16] В этом геометрическом представлении частичный куб перемещений на слабых упорядочениях является графом, описывающим отношение покрытия решетки граней пермутоэдра.

Например, для пермутоэдра на трех элементах это просто правильный шестиугольник. Решетка граней шестиугольника (опять же, включая сам шестиугольник как грань, но не включая пустое множество) имеет тринадцать элементов: один шестиугольник, шесть ребер и шесть вершин, что соответствует одному полностью связанному слабому порядку, шести слабым порядкам с одной связью и шести полным порядкам. Граф перемещений на этих 13 слабых порядках показан на рисунке. ${\displaystyle n=3,}$

Приложения

Как упоминалось выше, слабые порядки имеют приложения в теории полезности. ^[12] В линейном программировании и других типах задач комбинаторной оптимизации приоритет решений или баз часто задается слабым порядком, определяемым действительной целевой функцией ; явление связей в этих порядках называется «вырожденностью», и несколько типов правил разрешения связей использовались для уточнения этого слабого порядка до полного порядка с целью предотвращения проблем, вызванных вырожденностью. ^[17]

Слабые порядки также использовались в информатике , в алгоритмах уточнения разбиения для лексикографического поиска в ширину и лексикографического топологического упорядочения . В этих алгоритмах слабое упорядочение вершин графа (представленное как семейство множеств, которые разделяют вершины, вместе с двусвязным списком, обеспечивающим общий порядок множеств) постепенно уточняется в ходе алгоритма, в конечном итоге производя общий порядок, который является выходом алгоритма. ^[18]

В стандартной библиотеке языка программирования C++ типы данных set и multiset сортируют свои входные данные с помощью функции сравнения, которая указывается во время создания экземпляра шаблона и которая, как предполагается, реализует строгий слабый порядок. ^[2]

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

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

Ссылки

1. Робертс, Фред; Тесман, Барри (2011), Прикладная комбинаторика (2-е изд.), CRC Press, Раздел 4.2.4 Слабые порядки, стр. 254–256, ISBN 9781420099836.
2. Josuttis, Nicolai M. (2012), Стандартная библиотека C++: Учебное пособие и справочник, Addison-Wesley, стр. 469, ISBN 9780132977739.
3. де Конинк, Дж. М. (2009), Эти увлекательные числа , Американское математическое общество, стр. 4, ISBN 9780821886311.
4. Бейкер, Кент (29 апреля 2007 г.), «Брюс держится за победу в Кубке охоты: Баг Ривер, Лир Чарм финишируют вничью за второе место», The Baltimore Sun , архивировано из оригинала 29 марта 2015 г..
5. Регенветтер, Мишель (2006), Поведенческий социальный выбор: вероятностные модели, статистический вывод и приложения, Cambridge University Press, стр. 113 и далее, ISBN 9780521536660.
6. Флашка, В.; Ежек, Й.; Кепка, Т.; Кортелайнен, Й. (2007), Транзитивные замыкания бинарных отношений I (PDF) , Прага: Школа математики - Физика Карлова университета, стр. 1, S2CID  47676001, архивировано из оригинала (PDF) 2018-04-06, Лемма 1.1 (iv). Обратите внимание, что этот источник называет асимметричные отношения «строго антисимметричными».
7. Такое отношение также называется сильно связанным .
8. Эрготт, Маттиас (2005), Многокритериальная оптимизация, Springer, Предложение 1.9, стр. 10, ISBN 9783540276593.
9. Стэнли, Ричард П. (1997), Перечислительная комбинаторика, т. 2 , Кембриджские исследования по высшей математике, т. 62, Cambridge University Press, стр. 297.
10. Моцкин, Теодор С. (1971), «Сортировочные числа для цилиндров и другие классификационные числа», Комбинаторика (Proc. Sympos. Pure Math., Vol. XIX, Univ. California, Los Angeles, Calif., 1968) , Провиденс, Род-Айленд: Amer. Math. Soc., стр. 167–176, MR  0332508.
11. Гросс, О.А. (1962), «Преференциальные соглашения», The American Mathematical Monthly , 69 (1): 4–8, doi : 10.2307/2312725, JSTOR  2312725, MR  0130837.
12. Roberts, Fred S. (1979), Теория измерений с приложениями к принятию решений, полезности и социальным наукам , Энциклопедия математики и ее приложений, т. 7, Addison-Wesley, Теорема 3.1, ISBN 978-0-201-13506-0.
13. Люс, Р. Дункан (1956), «Полупорядки и теория дискриминации полезности» (PDF) , Econometrica , 24 (2): 178–191, doi :10.2307/1905751, JSTOR  1905751, MR  0078632.
14. Velleman, Daniel J. (2006), Как это доказать: структурированный подход, Cambridge University Press, стр. 204, ISBN 9780521675994.
15. Эппштейн, Дэвид ; Фальмань, Жан-Клод ; Овчинников, Сергей (2008), Теория медиа: междисциплинарная прикладная математика , Springer, Раздел 9.4, Слабые порядки и кубические комплексы, стр. 188–196.
16. Циглер, Гюнтер М. (1995), Лекции по многогранникам , Graduate Texts in Mathematics, т. 152, Springer, стр. 18.
17. Хватал, Вашек (1983), Линейное программирование, Macmillan, стр. 29–38, ISBN 9780716715870.
18. Хабиб, Мишель; Поль, Кристоф; Вьенно, Лоран (1999), «Методы уточнения разделов: интересный алгоритмический набор инструментов», Международный журнал по основам компьютерной науки , 10 (2): 147–170, doi :10.1142/S0129054199000125, MR  1759929.