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

Не путать со слабым порядком перестановок .

showТранзитивные   бинарные отношения
Symmetric Antisymmetric Connected Well-founded Has joins Has meets Reflexive Irreflexive Asymmetric Total, Semiconnex Anti- reflexive Equivalence relation Y ✗ ✗ ✗ ✗ ✗ Y ✗ ✗ Preorder (Quasiorder) ✗ ✗ ✗ ✗ ✗ ✗ Y ✗ ✗ Partial order ✗ Y ✗ ✗ ✗ ✗ Y ✗ ✗ Total preorder ✗ ✗ Y ✗ ✗ ✗ Y ✗ ✗ Total order ✗ Y Y ✗ ✗ ✗ Y ✗ ✗ Prewellordering ✗ ✗ Y Y ✗ ✗ Y ✗ ✗ Well-quasi-ordering ✗ ✗ ✗ Y ✗ ✗ Y ✗ ✗ Well-ordering ✗ Y Y Y ✗ ✗ Y ✗ ✗ Lattice ✗ Y ✗ ✗ Y Y Y ✗ ✗ Join-semilattice ✗ Y ✗ ✗ Y ✗ Y ✗ ✗ Meet-semilattice ✗ Y ✗ ✗ ✗ Y Y ✗ ✗ Strict partial order ✗ Y ✗ ✗ ✗ ✗ ✗ Y Y Strict weak order ✗ Y ✗ ✗ ✗ ✗ ✗ Y Y Strict total order ✗ Y Y ✗ ✗ ✗ ✗ Y Y Symmetric Antisymmetric Connected Well-founded Has joins Has meets Reflexive Irreflexive Asymmetric Definitions, for all $a,b$ and $S\neq \varnothing :$ ${\begin{aligned}&aRb\\\Rightarrow {}&bRa\end{aligned}}$ ${\begin{aligned}aRb{\text{ and }}&bRa\\\Rightarrow a={}&b\end{aligned}}$ ${\begin{aligned}a\neq {}&b\Rightarrow \\aRb{\text{ or }}&bRa\end{aligned}}$ ${\begin{aligned}\min S\\{\text{exists}}\end{aligned}}$ ${\begin{aligned}a\vee b\\{\text{exists}}\end{aligned}}$ ${\begin{aligned}a\wedge b\\{\text{exists}}\end{aligned}}$ $aRa$ ${\text{not }}aRa$ ${\begin{aligned}aRb\Rightarrow \\{\text{not }}bRa\end{aligned}}$
Y indicates that the column's property is always true the row's term (at the very left), while ✗ indicates that the property is not guaranteed in general (it might, or might not, hold). For example, that every equivalence relation is symmetric, but not necessarily antisymmetric, is indicated by Y in the "Symmetric" column and ✗ in the "Antisymmetric" column, respectively. All definitions tacitly require the homogeneous relation $R$ be transitive: for all $a,b,c,$ if $aRb$ and $bRc$ then $aRc.$ A term's definition may require additional properties that are not listed in this table.

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

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

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

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

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

Примеры

В скачках использование фотофиниша устранило некоторые, но не все, ничьи или (как их называют в этом контексте) ничьи , поэтому результат скачек можно смоделировать с помощью слабого порядка. В примере с препятствиями на Кубок Мэриленда по охоте в 2007 году Брюс был явным победителем, но две лошади Баг Ривер и Лир Чарм разделили второе место, а остальные лошади отстали; три лошади не финишировали. В слабом порядке, описывающем этот результат, Брюс будет первым, Баг Ривер и Лир Чарм будут ранжироваться после Брюса, но перед всеми другими лошадьми, которые финишировали, а три лошади, которые не финишировали, будут помещены последними в порядке, но связаны друг с другом.

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

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

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

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

Строгие слабые порядки

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

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

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

Определение

Строгая слабая упорядоченность множества. $S$ это строгий частичный порядок $\,<\,$ на $S$ для которого соотношение несравнимости, индуцированное на $S$ к $\,<\,$ является транзитивным отношением . Явно, строгий слабый приказ по $S$ это однородное отношение $\,<\,$ на $S$ который обладает всеми четырьмя из следующих свойств:

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

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

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

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

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

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

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

Всего предзаказов

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

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

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

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

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

Заказанные разделы

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

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

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

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

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

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

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

Сопутствующие виды заказа

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

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

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

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

Основная статья: заказанный номер звонка

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

Количество n -элементных бинарных отношений разных типов

Elem­ents	Любой	Переходный	Рефлексивный	Симметричный	Предварительный заказ	Частичный заказ	Общий предзаказ	Общий заказ	Отношение эквивалентности
0	1	1	1	1	1	1	1	1	1
1	2	2	1	2	1	1	1	1	1
2	16	13	4	8	4	3	3	2	2
3	512	171	64	64	29	19	13	6	5
4	65,536	3,994	4,096	1,024	355	219	75	24	15
н	2 н 2		2 п ( п -1)	2 п ( п +1)/2			∑ н к = 0 к ! С ( п , к )	н !	∑ н k =0 S ( n , k )
ОЭИС	А002416	А006905	А053763	А006125	А000798	А001035	А000670	А000142	А000110

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

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

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

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

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

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

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

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

Приложения

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

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

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

См. также

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