Слабая упорядоченность

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

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

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

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

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

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

Примеры

В скачках использование фотофиниша устранило некоторые, но не все, ничьи или (как их называют в этом контексте) ничьи , поэтому результат скачек можно смоделировать с помощью слабого порядка. ^[3] В примере с препятствиями на Кубок Мэриленда по охоте в 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}}}$$

неотносительно-equiвалентноименноклассе эквивалентности ${\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, Николай М. (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, стр. 113ff, ISBN 9780521536660.
6. Флашка, В.; Ежек, Дж.; Кепка, Т.; Кортелайнен, Дж. (2007), Транзитивные замыкания бинарных отношений I (PDF) , Прага: Школа математики - Карлов университет физики, с. 1, S2CID  47676001, заархивировано из оригинала (PDF) 6 апреля 2018 г., Лемма 1.1 (iv). Обратите внимание, что в этом источнике асимметричные отношения называются «строго антисимметричными».
7. Такое отношение еще называют сильно связным .
8. Эрготт, Маттиас (2005), Многокритериальная оптимизация, Springer, Предложение 1.9, стр. 10, ISBN 9783540276593.
9. Стэнли, Ричард П. (1997), Перечислительная комбинаторика, Vol. 2 , Кембриджские исследования по высшей математике, том. 62, Издательство Кембриджского университета, с. 297.
10. Моцкин, Теодор С. (1971), «Сортировка чисел для цилиндров и других классификационных чисел», Комбинаторика (Proc. Sympos. Pure Math., Vol. XIX, Univ. California, Лос-Анджелес, Калифорния, 1968) , Провиденс, РИ: Амер. Математика. Соц., стр. 167–176, МР  0332508..
11. Гросс, О.А. (1962), «Преференциальные соглашения», The American Mathematical Monthly , 69 (1): 4–8, doi : 10.2307/2312725, JSTOR  2312725, MR  0130837.
12. Робертс, Фред С. (1979), Теория измерения с приложениями к принятию решений, полезности и социальным наукам , Энциклопедия математики и ее приложений, том. 7, Аддисон-Уэсли, теорема 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. Веллеман, Дэниел Дж. (2006), Как это доказать: структурированный подход, Cambridge University Press, стр. 204, ISBN 9780521675994.
15. Эппштейн, Дэвид ; Фальмань, Жан-Клод ; Овчинников, Сергей (2008), Теория медиа: междисциплинарная прикладная математика , Springer, раздел 9.4, Слабые порядки и кубические комплексы, стр. 188–196..
16. Циглер, Гюнтер М. (1995), Лекции по многогранникам , Тексты для выпускников по математике, том. 152, Спрингер, с. 18.
17. Хватал, Вашек (1983), Линейное программирование, Macmillan, стр. 29–38, ISBN 9780716715870.
18. Хабиб, Мишель; Пол, Кристоф; Вьенно, Лоран (1999), «Методы уточнения разделов: интересный набор алгоритмических инструментов», International Journal of Foundations of Computer Science , 10 (2): 147–170, doi : 10.1142/S0129054199000125, MR  1759929.