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

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


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

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

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

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

Примеры

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

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

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

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

Предположим, что это однородное бинарное отношение на множестве (то есть является его подмножеством ), и, как обычно, напишите и скажите, что выполняется или истинно тогда и только тогда, когда

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

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

Говорят, что два элемента и of несравнимы по отношению к, если ни один из них не является истинным. Несопоставимость относительно само по себе является однородным симметричное отношение на том , что рефлексивно тогда и только тогда , когда это иррефлексивное ( это означает , что всегда ложно), которую можно считать , так что транзитивность является единственным свойством этого «несравнимости отношение» потребности для того , чтобы быть отношение эквивалентности . Определим также индуцированное однородное отношение on , объявив, что

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

Строгий слабый порядок на множестве является

строгим частичным порядком на , для которых несравнимости отношения индуцированного на по является транзитивным отношением . Явно строгий слабый порядок на - это однородное отношение на, которое обладает всеми четырьмя из следующих свойств:
  1. Безрезультатность :
Вообще- то это неправда, что
  • Это условие выполняется тогда и только тогда, когда индуцированное отношение on является
рефлексивным , где определяется объявлением, что истинно тогда и только тогда, когда оно ложно .
  • Транзитивность : для всех,еслито
  • Асимметрия : для всех,еслиистинно, толожно.
  • Транзитивность несравнимости : для всех,еслинесравнимо с(что означает, что ни одно,ниистинно), а еслинесравнимо с,тонесравнимо с
    • Два элемента несравнимы по отношению к тому и только тогда, когда они эквивалентны по отношению к индуцированному отношению (что по определению означает, что оба являются истинными), где, как и раньше, объявляется истинным тогда и только тогда, когда оно ложно. Таким образом , это условие имеет место тогда и только тогда , когда
  • симметричное отношение на определяется « эквивалентно по отношению к » представляет собой транзитивное отношение, а это означает , что всякий раз , когда есть -эквивалентны , а также являются -эквивалентны то обязательно являются -эквивалентны. Это также можно переформулировать как: всякий раз, а также тогда обязательно

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

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

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

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

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

    • Если затем для всех либо или обоих.

    Или:

    • Если несравнимо с then для всех, удовлетворяющих либо ( ), либо ( ), либо ( несопоставимо с и несравнимо с ).

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

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

    • Транзитивность : для всех, если то
    • Сильная связанность : для всех
      • Что подразумевает рефлексивность : для всех

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

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

    В любом предварительном заказе существует соответствующее отношение эквивалентности, в котором два элемента и определяются как

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

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

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

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

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

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

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

    Соответствующий общий предварительный заказ задается установкой, а соответствующая эквивалентность - установкой

    Отношения не меняются при замене на (

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

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

    лексикографического порядка на. Таким образом, хотя в большинстве моделей отношения предпочтений отношение определяет функцию полезности с точностью до сохраняющих порядок преобразований, такой функции нет для лексикографических предпочтений .

    В более общем смысле, если является набором, является набором со строгим слабым порядком и является функцией, то индуцирует строгий слабый порядок , задавая

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

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

    Полупорядки обобщают строгие слабые

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

    Для строгого слабого порядка другим ассоциированным рефлексивным отношением является его

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

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

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

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

    A000670 в OEIS ):
    Количество n -элементных бинарных отношений разных типов
    Элементы Любой Переходный Рефлексивный Предзаказ Частичный заказ Всего предзаказ Общий заказ Отношение эквивалентности
    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 4096 355 219 75 24 15
    п 2 п 2 2 п 2 - п S ( п , к ) п ! S ( п , к )
    OEIS A002416 A006905 A053763 A000798 A001035 A000670 A000142 A000110

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

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

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

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

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

    Геометрически общие порядки данного конечного множества могут быть представлены как вершины

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

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

    Приложения

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

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

    В стандартной библиотеке для языка программирования

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

    Смотрите также

    использованная литература