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

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

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

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

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

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

Примеры [ править ]

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

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

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

Аксиоматизация [ править ]

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

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

Говорят, что два элемента и из несравнимы по отношению к, если ни одно, ни истинно. ^[1] Несравнимость по отношению к сама по себе является однородным симметричным отношением на. Определите также индуцированное однородное отношение на , объявив, что оно истинно тогда и только тогда, когда оно ложно . Затем два элемента не сравнимы по отношению к тогда и только тогда , когда и являются эквивалентны относительно индуцированного отношения , которые с помощью определения , что как и${\displaystyle x}$${\displaystyle y}$${\displaystyle S}$${\displaystyle \,<}$${\displaystyle x<y}$${\displaystyle y<x}$${\displaystyle \,<\,}$${\displaystyle S.}$${\displaystyle \,\leq \,}$${\displaystyle S}$${\displaystyle x\leq y}$${\displaystyle y<x}$${\displaystyle x,y\in S}$${\displaystyle \,<\,}$${\displaystyle x}$${\displaystyle y}$${\displaystyle \,\leq ,\,}$${\displaystyle x\leq y}$${\displaystyle y\leq x}$верны. Отношение «несравнимы по отношению к », таким образом, идентично (т. Е. Равно) отношению »эквивалентны по отношению к « В частности, отношение «несравнимы по отношению к » является транзитивным отношением в том и только в том случае, если это истинное отношение "эквивалентны по отношению к " ${\displaystyle \,<}$${\displaystyle \,\leq .}$${\displaystyle \,<}$${\displaystyle S}$${\displaystyle \,\leq .}$

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

Строгий слабый порядок на множестве является строгим частичным порядком на , для которых несравнимости отношения индуцированного на по является транзитивным отношением . ^{[1] В} явном виде строгий слабый порядок на - это однородное отношение на, которое обладает всеми четырьмя из следующих свойств:${\displaystyle S}$ ${\displaystyle \,<\,}$${\displaystyle S}$${\displaystyle S}$${\displaystyle \,<\,}$${\displaystyle S}$ ${\displaystyle \,<\,}$${\displaystyle S}$

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

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

${\displaystyle A<B}$тогда и только тогда, когда для некоторых (или, что эквивалентно, для всех) представителей и${\displaystyle a<b}$${\displaystyle a\in A}$${\displaystyle b\in B.}$

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

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

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

• Если затем для всех либо или или обоих.${\displaystyle x<y}$${\displaystyle z,}$${\displaystyle x<z}$${\displaystyle z<y}$

Или же:

• Если несопоставимо с, то для всех либо ( и ), либо ( и ), либо ( несопоставимо с и несопоставимо с ).${\displaystyle x}$${\displaystyle y}$${\displaystyle z\neq x,}$ ${\displaystyle z\neq y,}$${\displaystyle x<z}$${\displaystyle y<z}$${\displaystyle z<x}$${\displaystyle z<y}$${\displaystyle z}$${\displaystyle x}$${\displaystyle z}$${\displaystyle y}$

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

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

• Для всех x , y и z , если и затем (транзитивность).${\displaystyle x\lesssim y}$${\displaystyle y\lesssim z}$${\displaystyle x\lesssim z}$
• Для всех х и у , или (сильной связности).${\displaystyle x\lesssim y}$${\displaystyle y\lesssim x}$
  • Следовательно, для всех х , (рефлексивность).${\displaystyle x\lesssim x}$

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

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

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

Упорядоченные разделы [ править ]

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

{ a }, { b },

{ b }, { a } и

{ а , б }.

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

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

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

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

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

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

Связанные типы заказа [ править ]

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

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

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

Комбинаторное перечисление [ править ]

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

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

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

Структура смежности [ править ]

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

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

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

Приложения [ править ]

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

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

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

Ссылки [ править ]