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

Слабый порядок на множестве { 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]

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

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

Строгий слабый порядок является бинарным отношением на множество S , что является строгим частичным порядком (а транзитивное отношение , что является иррефлексивным , или , что эквивалентно, ^[6] , что является асимметричным ) , в котором отношение «ни < б , ни б < » транзитивен. ^[1] Следовательно, строгий слабый порядок обладает всеми четырьмя из следующих свойств:${\ Displaystyle \, <\,}$

1. Иррефлексивность : для всех x в S это не так, что x < x ,
2. Транзитивность : для всех x , y , z в S , если x < y и y < z, то x < z ,
3. Асимметрия : для всех x , y в S , если x < y, то y < x не так ,
4. Транзитивность несравнимости : для всех x , y , z в S , если x несравнимо с y (это означает, что ни x < y, ни y < x не выполняется), и y несравнимо с z , то x несравним с z ,

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

«Несравнимость отношение» является отношением эквивалентности , ^[7] и его классы эквивалентности разделить элементы S , и вполне упорядочены по Наоборот, любому строгому общему порядку на перегородку из S приводит к строгому слабому порядку , в котором х < y тогда и только тогда, когда в разбиении существуют множества A и B с x ∈ A , y ∈ B и A < B в полном порядке.${\displaystyle \,<.}$

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

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

• Если x < y , то для всех z либо x < z, либо z < y, либо оба.

Или же:

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

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

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

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

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

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

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

Заказанные разделы [ править ]

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

{ a }, { b },

{ b }, { a } и

{ а , б }.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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