Войти
| Бинарные отношения | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Знак «✓» указывает, что свойство столбца требуется в определении строки.. Например, определение отношения эквивалентности требует, чтобы оно было симметричным.. Все определения неявно требуют транзитивности и рефлексивности. |
13 возможных строгих слабых порядков на множестве из трех элементов {a, b, c}. Только частично упорядоченные наборы окрашены, а полностью упорядоченные - черным. Два порядка показаны соединенными ребром, если они отличаются одной дихотомией. В математике, особенно в теории порядка, слабое упорядочение является математическая формализация интуитивного понятия ранжирования набора набора, некоторые из элементов которого могут быть связаны друг с другом. Слабые порядки - это обобщение полностью упорядоченных множеств (ранжирование без связей) и, в свою очередь, обобщение частично упорядоченных множеств и предварительных заказов.
Существует несколько распространенных способов формализации слабые порядки, которые отличаются друг от друга, но криптоморфны (взаимопревращаемы без потери информации): они могут быть аксиоматизированы как строгие слабые порядки (частично упорядоченные множества, в которых несравнимость является транзитивное отношение ), как общее количество предварительных заказов (транзитивные бинарные отношения, в которых существует хотя бы одно из двух возможных отношений между каждой парой элементов) или как упорядоченные разделы (разбивает элементы на непересекающиеся подмножества, вместе с общим порядком на подмножествах). Во многих случаях также возможно другое представление, называемое предпочтительным расположением на основе функции полезности.
Слабые порядки подсчитываются с помощью упорядоченных номеров Bell. Они используются в информатике как часть алгоритмов уточнения разделов и в стандартной библиотеке C ++.
В скачках использование фотофиниша устранило некоторые, но не все, ничьи или (как они называются в этом контексте) мертвые заплывы, поэтому исход скачек может быть смоделирован с помощью слабого упорядочивания. В примере с соревнований по бегу с препятствиями Maryland Hunt Cup в 2007 году Брюс был явным победителем, но две лошади Баг Ривер и Лир Чарм разделили второе место, а остальные лошади остались позади; три лошади не финишировали. В слабом порядке, описывающем этот результат, Брюс будет первым, Баг-Ривер и Лирское очарование будут ранжироваться после Брюса, но перед всеми другими лошадьми, которые финишировали, а три лошади, которые не финишировали, будут помещены последними в порядке, но связаны друг с другом.
Точки евклидовой плоскости могут быть упорядочены по их расстоянию от начала координат, что дает еще один пример слабого упорядочения с бесконечным множеством элементов, бесконечно много подмножеств связанных элементов (множества точек, которые принадлежат общей окружности с центром в начале координат) и бесконечно много точек внутри этих подмножеств. Хотя этот порядок имеет наименьший элемент (сам источник), он не имеет ни второго по величине элемента, ни какого-либо самого большого элемента.
Опрос на политических выборах представляет собой пример типа упорядочивания, который напоминает слабый порядок, но лучше моделируется математически другими способами. В результатах опроса один кандидат может явно опережать другого, или два кандидата могут быть статистически связаны, что означает не то, что их результаты опроса равны, а скорее то, что они находятся в пределах погрешности друг друга. Однако, если кандидат x статистически связан с y, а y статистически связан с z, все же возможно, что x будет явно лучше, чем z, поэтому привязка в этом случае не является транзитивным отношением. Из-за этой возможности ранжирование этого типа лучше моделируется как полуупорядочение, чем как слабое упорядочение.
A строгий слабый порядок является бинарным отношением < on a set S that is a строгим частичным порядком (транзитивным отношением, которое является нерефлексивным, или, что эквивалентно, асимметричным ), в котором отношение "ни a < b nor b < a" is transitive. Therefore, a strict weak ordering has the following properties:
Этот список свойств несколько избыточен в том смысле, что асимметрия подразумевает иррефлексивность, и в этой иррефлексивности и транзитивности вместе подразумевается асимметрия.
«Отношение несравнимости» - это отношение эквивалентности, и его классы эквивалентности разделяют элементы S, и полностью упорядочены <. Conversely, any total order on a разделом S приводит к строгому слабый порядок, в котором x < y if and only if there exists sets A and B in the partition with x in A, y in B, and A < B in the total order.
Не каждый частичный порядок подчиняется транзитивному закону несравнимости. Например, рассмотрим частичный порядок в множестве {a, b, c}, определяемый соотношением b < c. The pairs a, b and a, c are incomparable but b and c are related, so incomparability does not form an equivalence relation and this example is not a strict weak ordering.
Транзитивность несравнимости (вместе с транзитивностью) также может быть выражена в следующих формах:
Или:
Строгие слабые заказы очень тесно связаны с общее количество предварительных заказов или (нестрогих) слабых порядков, и те же математические концепции, которые можно смоделировать с помощью строгих слабых порядков, можно одинаково хорошо смоделировать с помощью общих предварительных заказов. Общий предварительный заказ или слабый порядок - это предварительный заказ, который также является отношением связности ; то есть ни одна пара элементов не является несравнимой. Общий предварительный заказ 
y и y z, затем x z (транзитивность).y или y x (связь). x (рефлексивность).A total order - это общий предварительный заказ, который является антисимметричным, другими словами, это также частичный заказ. Общие предварительные заказы иногда также называют отношениями предпочтения .
дополнение строгого слабого порядка является полным предварительным заказом, и наоборот, но кажется более естественным связать строгие слабые порядки и общие предварительные заказы в способ, который сохраняет, а не меняет порядок элементов. Таким образом, мы берем обратный дополнения: для строгого слабого упорядочения <, define a total preorder
в любом предварительном заказе является соответствующим отношением эквивалентности, где два элемента x и y определены как эквивалент, если x
A разбиение набора S - это семейство непустых непересекающихся подмножеств S, объединение которых имеет S. Раздел вместе с общим порядком на множествах раздела дает структуру, которую Ричард П. Стэнли назвал упорядоченным разделом и Теодор Моцкин список наборов . Упорядоченное разбиение конечного набора может быть записано как конечная последовательность наборов в разделе: например, три упорядоченных разбиения набора {a, b} равны
При строгом слабом упорядочивании классы эквивалентности несравнимости дают заданное разбиение, в котором наборы наследуют полный порядок от своих элементов, что приводит к упорядоченному разделу. С другой стороны, любое упорядоченное разбиение порождает строгий слабый порядок, при котором два элемента несравнимы, если они принадлежат одному и тому же набору в разбиении, и в противном случае наследуют порядок наборов, которые их содержат.
Для множеств достаточно малой мощности возможна третья аксиоматизация, основанная на функциях с действительными значениями. Если X - любое множество и fa вещественнозначная функция на X, то f индуцирует строгий слабый порядок на X, задавая < b if and only if f(a) < f(b). The associated total preorder is given by setting a
Отношения не изменяются при замене f на g o f (составная функция ), где g - строго возрастающая действительная значная функция, определенная по крайней мере на диапазоне f. Таким образом, например, функция полезности определяет отношение предпочтения . В этом контексте слабые порядки также известны как предпочтительные расположения .
. Если X конечно или счетно, каждый слабый порядок на X может быть представлен функцией таким образом. Однако существуют строгие слабые порядки, которым нет соответствующей действительной функции. Например, такой функции нет для лексикографического порядка на R . Таким образом, хотя в большинстве моделей отношения предпочтений отношение определяет функцию полезности от до сохраняющих порядок преобразований, такой функции нет для лексикографических предпочтений.
В более общем смысле, если X является набором, а Y - набор со строгим слабым порядком "<", and f a function from X to Y, then f induces a strict weak ordering on X by setting a < b if and only if f(a) < f(b). As before, the associated total preorder is given by setting a
Полупорядки обобщают строгие слабые порядки, но не предполагают транзитивность несравнимости. Строгий слабый порядок, который является трихотомическим, называется строгим полным порядком . Общий предварительный порядок, который является обратным его дополнению, в этом случае является полным порядком.
. Для строгого слабого порядка «<" another associated reflexive relation is its рефлексивное замыкание, (нестрогий) частичный порядок« ≤ ». Два связанных рефлексивных отношения различаются в отношении различных a и b, для которых ни a < b nor b < a: in the total preorder corresponding to a strict weak order we get a
Число различных слабых порядков (представленных либо как строгие слабые порядки, либо как общие предварительные заказы) в наборе из n элементов задается следующей последовательностью (последовательность 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 |
| n | 2 | 2 | ∑n. k = 0 k! S (n, k) | n! | ∑n. k = 0 S (n, k) | |||
| OEIS | A002416 | A006905 | A053763 | A000798 | A001035 | A000670 | A000142 | A000110 |
Эти числа также называются числами Фубини или упорядоченными числами Bell .
. Например, для набора из трех помеченных элементов существует один слабый порядок, в котором все завязаны три предмета. Есть три способа разделить элементы на один набор singleton и одну группу из двух связанных элементов, и каждое из этих разделов дает два слабых порядка (один, в котором одноэлемент меньше, чем группа из двух, и один, в котором этот порядок обратный), давая шесть слабых порядков этого типа. И есть единственный способ разбить набор на три отдельных элемента, которые можно полностью упорядочить шестью различными способами. Таким образом, всего существует 13 различных слабых заказов по трем позициям.
Пермутоэдр на четырех элементах, трехмерный выпуклый многогранник. Он имеет 24 вершины, 36 ребер и 14 двумерных граней, которые вместе со всем трехмерным многогранником соответствуют 75 слабым порядкам на четырех элементах. В отличие от частичных порядков, семейство слабых порядков на элементе данное конечное множество, как правило, не связано ходами, которые добавляют или удаляют отношение единственного порядка к данному порядку или из него. Например, для трех элементов порядок, в котором связаны все три элемента, отличается по крайней мере на две пары от любого другого слабого упорядочения в том же наборе либо в строгом слабом порядке, либо в аксиоматизации полного предварительного порядка. Однако возможен другой вид хода, в котором слабые порядки на множестве более тесно связаны. Определите дихотомию как слабый порядок с двумя классами эквивалентности и определите дихотомию, чтобы быть совместимым с данным слабым порядком, если каждые два элемента, которые связаны в упорядочении, либо связаны одинаковым образом, либо связаны в дихотомии. В качестве альтернативы дихотомия может быть определена как разрез Дедекинда для слабого упорядочения. Тогда слабое упорядочение можно охарактеризовать набором совместимых дихотомий. Для конечного набора помеченных элементов каждая пара слабых порядков может быть связана друг с другом последовательностью ходов, которые добавляют или удаляют по одной дихотомии за раз в этот набор дихотомий или из него. Более того, неориентированный граф, который имеет слабые упорядочения в качестве вершин и эти движения в качестве его ребер, образует частичный куб.
Геометрически общие порядки данного конечного множества могут быть представлены как вершины пермутоэдра, а дихотомии на том же наборе, что и грани пермутоэдра. В этом геометрическом представлении слабые порядки на множестве соответствуют граням всех различных размеров пермутоэдра (включая сам пермутоэдр, но не пустое множество как грань). коразмерность грани дает количество классов эквивалентности в соответствующем слабом порядке. В этом геометрическом представлении частичный куб движений в слабых порядках - это граф, описывающий отношение покрытия решетки граней пермутоэдра.
Например, для n = 3 пермутоэдр на трех элементах - это просто правильный шестиугольник. Решетка граней шестиугольника (опять же, включая сам шестиугольник как грань, но не включая пустое множество) имеет тринадцать элементов: один шестиугольник, шесть ребер и шесть вершин, соответствующих одному полностью связанному слабому порядку, шести слабым порядкам с одним галстуком и шестью заказами. График ходов по этим 13 слабым порядкам показан на рисунке.
Как упоминалось выше, слабые порядки имеют приложения в теории полезности. В линейном программировании и других типах задач комбинаторной оптимизации приоритезация решений или баз часто задается слабым порядком, определяемым вещественной целевой функцией ; явление связей в этих порядках называется «вырождением», и несколько типов правил разрыва связей использовались для преобразования этого слабого упорядочения в полное упорядочение, чтобы предотвратить проблемы, вызванные вырождением.
Слабые порядки также использовались в информатике, в алгоритмах на основе уточнения раздела для лексикографического поиска в ширину и лексикографического топологического упорядочивания. В этих алгоритмах слабый порядок в вершинах графа (представленный как семейство множеств, разбивающих вершины, вместе с двусвязным списком, обеспечивающим полный порядок на множествах) постепенно уточняется в ходе работы алгоритма, в конечном итоге приводя к общему упорядочиванию, которое является результатом работы алгоритма.
В стандартной библиотеке для программирования C ++ языка, типы данных set и multiset сортируют свои входные данные с помощью функции сравнения, которая указывается во время создания экземпляра шаблона и которая, как предполагается, реализует строгий слабый порядок.
