Слабый порядок - Weak ordering

Бинарные отношения

	Симметричный	Антисимметричный	Connex	Обоснованный	Присоединяется	Встречается
Отношение эквивалентности	✓	✗	✗	✗	✗	✗
Предварительный заказ (Квазипорядок)	✗	✗	✗	✗	✗	✗
Частичный заказ	✗	✓	✗	✗	✗	✗
Всего предзаказ	✗	✗	✓	✗	✗	✗
Общий заказ	✗	✓	✓	✗	✗	✗
Предварительный заказ	✗	✗	✓	✓	✗	✗
Ну квази-упорядочивание	✗	✗	✗	✓	✗	✗
Хороший порядок	✗	✓	✓	✓	✗	✗
Решетка	✗	✓	✗	✗	✓	✓
Соединение-полурешетка	✗	✓	✗	✗	✓	✗
Встреча-полурешетка	✗	✓	✗	✗	✗	✓

А "✓"указывает, что свойство столбца требуется в определении строки.
Например, определение отношения эквивалентности требует, чтобы оно было симметричным.
Все определения молчаливо требуют транзитивность и рефлексивность.

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

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

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

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

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

Примеры

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

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

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

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

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

А строгий слабый порядок это бинарное отношение <на съемочной площадке S это строгий частичный порядок (а переходное отношение то есть иррефлексивный, или эквивалентно,^[6] то есть асимметричный ), в котором отношение "ни а < б ни б < а"переходно.^[1] Следовательно, строгое слабое упорядочение обладает следующими свойствами:

Для всех Икс в S, это не тот случай, когда Икс < Икс (нерефлексивность ).
Для всех Икс, у в S, если Икс < у тогда это не тот случай, когда у < Икс (асимметрия ).
Для всех Икс, у, z в S, если Икс < у и у < z тогда Икс < z (транзитивность ).
Для всех Икс, у, z в S, если Икс несравнимо с у (ни один Икс < у ни у < Икс держать), и у несравнимо с z, тогда Икс несравнимо с z (транзитивность несравнимости).

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

«Отношение несравнимости» - это отношение эквивалентности, и это классы эквивалентности разделить элементы S, и являются полностью заказанный пользователем <. И наоборот, любой полный порядок на раздел из S приводит к строгому слабому порядку, в котором Икс < у тогда и только тогда, когда существуют множества А и B в разделе с Икс в А, у в B, и А < B в полном порядке.

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

Транзитивность несравнимости (вместе с транзитивностью) также может быть сформулирована в следующих формах:

Если Икс < у, то для всех z, либо Икс < z или же z < у или оба.

Или же:

Если Икс несравнимо с у, то для всех z ≠ Икс, z ≠ у, либо (Икс < z и у < z) или же (z < Икс и z < у) или же (z несравнимо с Икс и z несравнимо с у).

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

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

Для всех Икс, у, и z, если Икс ${ displaystyle lesssim}$ у и у ${ displaystyle lesssim}$ z тогда Икс ${ displaystyle lesssim}$ z (транзитивность).
Для всех Икс и у, Икс ${ displaystyle lesssim}$ $lesssim$ у или же у ${ displaystyle lesssim}$ $lesssim$ Икс (связь).
- Следовательно, для всех Икс, Икс ${ displaystyle lesssim}$ Икс (рефлексивность).

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

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

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

Заказанные перегородки

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

{а}, {б},

{б}, {а}, и

{а, б}.

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

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

Для наборов достаточно малых мощность возможна третья аксиоматизация, основанная на действительных функциях. Если Икс любой набор и ж действительная функция на Икс тогда ж индуцирует строгий слабый порядок на Икс установив а < б если и только если ж(а) < ж(б). Соответствующий общий предварительный заказ задается установкой а ${ displaystyle {} lesssim {}}$ б если и только если ж(а) ≤ ж(б), и соответствующую эквивалентность, положив а ${ displaystyle {} sim {}}$ б если и только если ж(а) = ж(б).

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

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

В более общем смысле, если Икс это набор, и Y - множество со строгим слабым порядком "<", и ж функция от Икс к Y, тогда ж индуцирует строгий слабый порядок на Икс установив а < б если и только если ж(а) < ж(б). Как и прежде, соответствующий общий предварительный заказ задается установкой а ${ displaystyle {} lesssim {}}$ б если и только если ж(а) ${ displaystyle {} lesssim {}}$ ж(б), и соответствующую эквивалентность, положив а ${ displaystyle {} sim {}}$ б если и только если ж(а) ${ displaystyle {} sim {}}$ ж(б). Здесь не предполагается, что ж является инъективная функция, поэтому класс двух эквивалентных элементов на Y может вызвать больший класс эквивалентных элементов на Икс. Также, ж не считается сюръективная функция, поэтому класс эквивалентных элементов на Y может вызвать меньший или пустой класс на Икс. Однако функция ж индуцирует инъективную функцию, отображающую разбиение на Икс к этому на Y. Таким образом, в случае конечных разбиений количество классов в Икс меньше или равно количеству занятий на Y.

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

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

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

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

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

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

Количество п-элементные бинарные отношения разных типов
Элементы	Любой	Переходный	Рефлексивный	Предварительный заказ	Частичный заказ	Всего предзаказ	Общий заказ	Отношение эквивалентности
0	1	1	1	1	1	1	1	1
1	2	2	1	1	1	1	1	1
2	16	13	4	4	3	3	2	2
3	512	171	64	29	19	13	6	5
4	65,536	3,994	4,096	355	219	75	24	15
п	2^п²		2^п²−п			$\sum п k =0 k! S (п, k)$	п!	$\sum п k =0 S (п, k)$
OEIS	A002416	A006905	A053763	A000798	A001035	A000670	A000142	A000110

Эти числа также называют Числа Фубини или же заказанные номера Bell.

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

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

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

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

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

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

Приложения

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

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

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