Введение

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

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

Примеры

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

Порядочные разделы

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

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

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

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

Приложения

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