Бинарные отношения | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
« ✓ » указывает, что свойство столбца требуется в определении строки. Например, определение отношения эквивалентности требует, чтобы оно было симметричным. Все определения неявно требуют транзитивности и рефлексивности . |
В математике , особенно теории порядка , слабый порядок является математическая формализация интуитивного понятия ранга из набора , некоторые члены которого могут быть связаны друг с другом. Слабые порядки являются обобщением полностью упорядоченных множеств (ранжирование без связей) и, в свою очередь, обобщаются частично упорядоченными множествами и предпорядками . [1]
Существует несколько общих способов формализации слабых порядков, которые отличаются друг от друга, но являются криптоморфными (взаимопревращаемыми без потери информации): они могут быть аксиоматизированы как строгие слабые порядки (частично упорядоченные множества, в которых несравнимость является транзитивным отношением ), как общее предварительные порядки (транзитивные бинарные отношения, в которых существует хотя бы одно из двух возможных отношений между каждой парой элементов) или как упорядоченные разбиения ( разбиения элементов на непересекающиеся подмножества вместе с общим порядком на подмножествах). Во многих случаях также возможно другое представление, называемое предпочтительным соглашением, основанное на функции полезности .
Слабые порядки подсчитываются по упорядоченным номерам Белла . Они используются в информатике как часть алгоритмов уточнения разделов и в стандартной библиотеке C ++ . [2]
Примеры
В скачках использование фотофиниша устранило некоторые, но не все, галстуки или (как их называют в этом контексте) мертвые заплывы , поэтому результат скачек может быть смоделирован с помощью слабого упорядочивания. [3] В примере с соревнований по бегу с препятствиями Maryland Hunt Cup в 2007 году Брюс был явным победителем, но две лошади Баг Ривер и Лир Чарм разделили второе место, а остальные лошади остались позади; три лошади не финишировали. [4] В слабом порядке, описывающем этот результат, Брюс будет первым, Баг-Ривер и Лирское очарование будут ранжироваться после Брюса, но перед всеми другими лошадьми, которые финишировали, а три лошади, которые не финишировали, будут помещены последними в порядок, но связаны друг с другом.
Точки евклидовой плоскости могут быть упорядочены по их расстоянию от начала координат , что дает еще один пример слабого упорядочения с бесконечным количеством элементов, бесконечным множеством подмножеств связанных элементов (наборов точек, которые принадлежат общей окружности с центром в начале координат) , и бесконечно много точек внутри этих подмножеств. Хотя этот порядок имеет наименьший элемент (сам источник), он не имеет ни второго по величине элемента, ни какого-либо самого большого элемента.
Опрос общественного мнения на политических выборах представляет собой пример типа упорядочения, который напоминает слабый порядок, но лучше моделируется математически другими способами. В результатах опроса один кандидат может явно опережать другого, или два кандидата могут быть статистически связаны, что означает не то, что их результаты опроса равны, а скорее то, что они находятся в пределах погрешности друг друга. Однако если кандидат статистически связано с а также статистически связано с это все еще может быть возможно для быть явно лучше чем поэтому связь в данном случае не является транзитивным отношением . Из-за этой возможности рейтинги этого типа лучше моделировать как полуупорядоченные, чем как слабые. [5]
Аксиоматизации
- Предварительные мероприятия
Предположим на протяжении всего этого является однородным бинарным отношением на множестве (это, это подмножество ) и как обычно пишем и скажи, что выполняется или истинно тогда и только тогда, когда
Два элемента а также из считаются несравнимыми по отношению к если ни то, ни другое ни правда. [1] Несравнимость по отношению ксам по себе является однородным симметричным отношением на Определим также индуцированное однородное отношение на заявив, что верно тогда и только тогда, когда является ложным . Тогда два элемента несравнимы по отношению к если и только если а также являются эквивалентны относительно индуцированного отношения что по определению означает, что оба а также верны. Отношение "несравнимо по отношению к"таким образом идентично (т. е. равно) отношению" эквивалентны по отношению к «В частности, отношения» несравнимы по отношению к "является транзитивным отношением на тогда и только тогда, когда это верно для отношения "эквивалентны по отношению к "
Строгие слабые порядки
Строгий слабый порядок на множествеэто строгий частичный заказ на для которых отношение несравнимости, индуцированное на от является транзитивным отношением . [1] Явно строгий слабый порядок наэто однородное отношение на обладающий всеми четырьмя из следующих свойств:
- Безрезультатность : для всех это неправда, что
- Это условие выполняется тогда и только тогда, когда индуцированное соотношение на является рефлексивным , где определяется заявлением, что верно тогда и только тогда, когда является ложным .
- Транзитивность : Для всех если а также тогда
- Асимметрия : Для всех если верно тогда ложно.
- Транзитивность несравнимости : Для всех если несравнимо с (это означает, что ни ни верно) и если несравнимо с тогда несравнимо с
- Два элемента а также несравнимы по отношению к тогда и только тогда, когда они эквивалентны относительно индуцированного отношения (что по определению означает, что а также оба верны), где, как и раньше, объявляется истинным тогда и только тогда, когда ложно. Таким образом, это условие выполняется тогда и только тогда, когда симметричное соотношение на определяется " а также эквивалентны относительно "- это переходное отношение.
Свойства (1), (2) и (3) являются определяющими свойствами строгого частичного порядка, хотя этот список этих трех свойств в некоторой степени избыточен, поскольку асимметрия подразумевает иррефлексивность, а иррефлексивность и транзитивность вместе подразумевают асимметрию. [6] Отношение несравнимости всегда симметрично и будет рефлексивным тогда и только тогда, когдаявляется иррефлексивным отношением (которое предполагается в соответствии с приведенным выше определением). Следовательно, строгий частичный порядокявляется строгим слабым порядком тогда и только тогда, когда его отношение индуцированной несравнимости является отношением эквивалентности . В этом случае его классы эквивалентности разбивают и, кроме того, набор из этих классов эквивалентности может быть строго вполне упорядочены по бинарным отношением , также обозначается что определено для всех от:
- если и только если для некоторых (или, что эквивалентно, для всех) представителей а также
И наоборот, любой строгий полный порядок на разбиении из приводит к строгой слабой упорядоченности на определяется тогда и только тогда, когда существуют множества в этом разделе такой, что а также
Не всякий частичный порядок подчиняется транзитивному закону несравнимости. Например, рассмотрим частичный порядок в наборе определяется отношениями Пары а также несравненные, но а также связаны между собой, поэтому несравнимость не образует отношения эквивалентности, и этот пример не является строгим слабым порядком.
Транзитивность несравнимости (вместе с транзитивностью) также может быть выражена в следующих формах:
- Если тогда для всех либо или же или оба.
Или же:
- Если несравнимо с тогда для всех либо ( а также ) или же ( а также ) или же ( несравнимо с а также несравнимо с ).
Всего предварительных заказов
Строгие слабые порядки очень тесно связаны с полными предварительными заказами или (нестрогими) слабыми порядками , и те же математические концепции, которые можно смоделировать с помощью строгих слабых порядков, можно также смоделировать с помощью полных предварительных заказов. Полный предварительный заказ или слабый заказ - это предварительный заказ, в котором любые два элемента сопоставимы. [7] Всего предзаказ удовлетворяет следующим свойствам:
- Для всех а также если а также тогда (транзитивность).
- Для всех а также или же (сильная связность).
- Следовательно, для всех (рефлексивность).
Общий порядок является общей предпорядок , который является антисимметричным, другими словами, что также является частичным порядком . Тотальные предварительные заказы иногда также называют отношениями предпочтений .
Дополнение строгого слабого порядка является общей предзаказ, и наоборот, но это , кажется , более естественно связать строгие слабые заказы и всего предзаказы таким образом , что сохраняет , а не изменяет порядок элементов. Таким образом, мы возьмем обратное к дополнению: для строгого слабого порядка <определим полный предпорядок установив когда это не так, В другом направлении, чтобы определить строгое слабое упорядочение <от полного предпорядка набор когда это не так, [8]
В любом предпорядке имеется соответствующее отношение эквивалентности, в котором два элемента а также определяются как эквивалентные, если а также В случае полного предварительного заказа соответствующий частичный порядок на множестве классов эквивалентности является полным порядком. Два элемента эквивалентны в полном предпорядке тогда и только тогда, когда они несравнимы в соответствующем строгом слабом порядке.
Заказанные перегородки
Разбиение множества семейство непустых непересекающихся подмножеств который имеет как их союз. Перегородка, вместе с общим порядка на множествах перегородки, дает структуру , называемую по Ричард П. Стенли упорядоченное разбиение [9] и Теодор Моцкин список наборов . [10] Упорядоченное разбиение конечного множества может быть записано как конечная последовательность множеств в разбиении: например, три упорядоченных разбиения множества находятся
- а также
В строгом слабом порядке классы эквивалентности несравнимости дают разбиение множеств, в котором наборы наследуют полный порядок от своих элементов, что приводит к упорядоченному разбиению. С другой стороны, любое упорядоченное разбиение порождает строгий слабый порядок, при котором два элемента несравнимы, если они принадлежат одному и тому же набору в разбиении, и в противном случае наследуют порядок наборов, которые их содержат.
Представление по функциям
Для множеств достаточно малой мощности возможна третья аксиоматизация, основанная на действительных функциях. Если является любым множеством, тогда действительнозначная функция на индуцирует строгий слабый порядок на установив если и только если Соответствующий общий предварительный заказ задается установкой если и только если и соответствующую эквивалентность, установив если и только если
Отношения не меняются, когда заменяется на ( составная функция ), гдеявляется строго возрастающей действительной функцией, определенной по крайней мере в диапазоне значенийТак, например, функция полезности определяет отношение предпочтений . В этом контексте слабые порядки также известны как преференциальные порядки . [11]
Если конечно или счетно, любой слабый порядок на таким образом может быть представлена функцией. [12] Однако существуют строгие слабые порядки, которым нет соответствующей действительной функции. Например, нет такой функции для лексикографического порядка наТаким образом, хотя в большинстве моделей отношения предпочтения отношение определяет функцию полезности с точностью до преобразований, сохраняющих порядок, для лексикографических предпочтений такой функции нет .
В более общем смысле, если это набор, - множество со строгим слабым упорядочением а также функция, то индуцирует строгий слабый порядок на установив если и только если Как и прежде, соответствующий общий предварительный заказ задается установкой если и только если и соответствующую эквивалентность, установив если и только если Здесь не предполагается, что является инъективной функцией , поэтому класс двух эквивалентных элементов на может вызвать больший класс эквивалентных элементов на Также, не считается сюръективной функцией , поэтому класс эквивалентных элементов на может вызвать меньший или пустой класс на Однако функция индуцирует инъективную функцию, отображающую разбиение на к этому на Таким образом, в случае конечных разбиений количество классов в меньше или равно количеству занятий на
Связанные типы заказа
Полупорядки обобщают строгие слабые порядки , но не предполагают транзитивность несравнимости. [13] Строгий слабый порядок, являющийся трихотомическим , называется строгим полным порядком . [14] Общий предварительный заказ, который является обратным его дополнению, в данном случае является полным заказом .
Для строгого слабого порядка другое ассоциированное рефлексивное отношение - это его рефлексивное замыкание , (нестрогий) частичный порядок Два ассоциированных рефлексивных отношения различаются а также для которого ни ни : в полном предзаказе, соответствующем строгому слабому порядку, получаем а также в то время как в частичном порядке, заданном рефлексивным замыканием, мы не получаем ни ни Для строгих итоговых порядков эти два ассоциированных рефлексивных отношения одинаковы: соответствующий (нестрогий) тотальный порядок. [14] Рефлексивное замыкание строгого слабого порядка - это разновидность последовательно-параллельного частичного порядка .
Все слабые порядки на конечном множестве
Комбинаторное перечисление
Количество отдельных слабых порядков (представленных либо в виде строгих слабых порядков, либо в виде общих предварительных заказов) на -элементный набор задается следующей последовательностью (последовательность 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 | 4096 | 355 | 219 | 75 | 24 | 15 |
п | 2 п 2 | 2 п 2 - п | ∑п к = 0 к ! S ( п , к ) | п ! | ∑п к = 0 S ( п , к ) | |||
OEIS | A002416 | A006905 | A053763 | A000798 | A001035 | A000670 | A000142 | A000110 |
Эти числа также называют числами Фубини или упорядоченными числами Белла .
Например, для набора из трех помеченных элементов существует один слабый порядок, в котором все три элемента связаны. Существует три способа разбивки элементов на один синглтон- набор и одну группу из двух связанных элементов, и каждое из этих разделов дает два слабых порядка (один, в котором синглтон меньше, чем группа из двух элементов, и один, в котором этот порядок упорядочен). перевернутый), давая шесть слабых порядков этого типа. И есть единственный способ разбить набор на три отдельных элемента, которые можно полностью упорядочить шестью различными способами. Таким образом, всего существует 13 различных слабых заказов по трем позициям.
Структура смежности
В отличие от частичных порядков, семейство слабых порядков на данном конечном множестве, как правило, не связано движениями, которые добавляют или удаляют отношение одного порядка к данному порядку или из него. Например, для трех элементов порядок, в котором связаны все три элемента, отличается по крайней мере на две пары от любого другого слабого порядка в том же наборе, либо в строгом слабом порядке, либо в аксиоматизации полного предварительного порядка. Однако возможен другой вид хода, в котором слабые порядки на множестве более тесно связаны. Определите дихотомию как слабый порядок с двумя классами эквивалентности и определите дихотомию, чтобы быть совместимым с данным слабым порядком, если каждые два элемента, которые связаны в упорядочении, либо связаны одинаковым образом, либо связаны в дихотомии. В качестве альтернативы дихотомия может быть определена как разрез Дедекинда для слабого упорядочения. Тогда слабое упорядочение можно охарактеризовать набором совместимых дихотомий. Для конечного набора помеченных элементов каждая пара слабых порядков может быть связана друг с другом последовательностью ходов, которые добавляют или удаляют по одной дихотомии за раз в этот набор дихотомий или из него. Более того, неориентированный граф , у которого слабые порядки являются вершинами, а эти движения - его ребрами, образует частичный куб . [15]
Геометрически общий порядок данного конечного множества может быть представлен как вершины пермутоэдра , а дихотомии на этом же множестве - как фасеты пермутоэдра. В этом геометрическом представлении слабые порядки на множестве соответствуют граням всех различных размеров пермутоэдра (включая сам пермутоэдр, но не пустое множество, как грань). Коразмерность от лица дает число классов эквивалентности в соответствующей слабой упорядоченности. [16] В этом представлении геометрического парциальные куб двигается на слабых упорядочениях является график , описывающий охватывающего соотношения в лицевой решетке в перестановочном многограннике.
Например, для пермутоэдр на трех элементах - это просто правильный шестиугольник. Решетка граней шестиугольника (опять же, включая сам шестиугольник как грань, но не включая пустое множество) имеет тринадцать элементов: один шестиугольник, шесть ребер и шесть вершин, соответствующих одному полностью связанному слабому порядку, шести слабым порядкам с одним галстуком и шестью заказами. График ходов по этим 13 слабым порядкам показан на рисунке.
Приложения
Как упоминалось выше, слабые порядки имеют приложения в теории полезности. [12] В линейном программировании и других типах задач комбинаторной оптимизации приоритет решений или баз часто задается слабым порядком, определяемым действительной целевой функцией ; явление связей в этих порядках называется «вырождением», и несколько типов правил разрыва связей были использованы для преобразования этого слабого упорядочения в полное упорядочение, чтобы предотвратить проблемы, вызванные вырождением. [17]
Слабые порядки также использовались в информатике в алгоритмах, основанных на уточнении разделов , для лексикографического поиска в ширину и лексикографического топологического упорядочения . В этих алгоритмах слабый порядок вершин графа (представленный как семейство множеств, которые разделяют вершины, вместе с двусвязным списком, обеспечивающим общий порядок множеств) постепенно уточняется в ходе алгоритма, в конечном итоге создание полного упорядочивания, которое является результатом работы алгоритма. [18]
В стандартной библиотеке для языка программирования C ++ типы данных set и multiset сортируют свои входные данные с помощью функции сравнения, которая указывается во время создания экземпляра шаблона и которая, как предполагается, реализует строгий слабый порядок. [2]
Смотрите также
- Сопоставимость
- Предварительный заказ - рефлексивное и транзитивное бинарное отношение
Рекомендации
- ^ a b c Робертс, Фред; Тесман, Барри (2011), Прикладная комбинаторика (2-е изд.), CRC Press, Раздел 4.2.4 Слабые порядки, стр. 254–256, ISBN 9781420099836.
- ^ а б Джосуттис, Николай М. (2012), Стандартная библиотека C ++: Учебное пособие и справочник , Addison-Wesley, стр. 469, ISBN 9780132977739.
- ^ де Конинк, JM (2009), Те увлекательные числа , Американское математическое общество, стр. 4, ISBN 9780821886311.
- ^ Бейкер, Кент (29 апреля 2007 г.), «Брюс держится за победу в Кубке Охоты: Баг-Ривер, Лир Чарм финишируют в ничьей на втором месте» , The Baltimore Sun , заархивировано из оригинала 29 марта 2015 г..
- ^ Регенветтер, Мишель (2006), Поведенческий социальный выбор: вероятностные модели, статистический вывод и приложения , Cambridge University Press, стр. 113ff , ISBN 9780521536660.
- ^ Флашка, В .; Ježek, J .; Кепка, Т .; Кортелайнен, Дж. (2007), Транзитивные замыкания бинарных отношений I (PDF) , Прага: Школа математики - Физический университет Карлова, стр. 1, S2CID 47676001 , архивировано из оригинального (PDF) 06.04.2018, Лемма 1.1 (iv). Обратите внимание, что в этом источнике асимметричные отношения называются «строго антисимметричными».
- ^ Такое отношение также называют сильно связным .
- ^ Эрготт, Маттиас (2005), Многокритериальная оптимизация , Springer, предложение 1.9, стр. 10, ISBN 9783540276593.
- ^ Стэнли, Ричард П. (1997), Перечислительная комбинаторика, Vol. 2 , Кембриджские исследования в области высшей математики, 62 , Cambridge University Press, стр. 297.
- ^ Моцкин, Теодор С. (1971), "Сортировочные числа для цилиндров и другие классификационные числа", Комбинаторика (Proc. Sympos. Pure Math., Том XIX, Калифорнийский университет, Лос-Анджелес, Калифорния, 1968) , Провиденс, Род-Айленд. : Амер. Математика. Soc., Стр. 167–176, MR 0332508.
- ^ Гросс, О. А. (1962), "Льготные соглашения", Американский Математический Месячный , 69 (1): 4-8, DOI : 10,2307 / 2312725 , JSTOR 2312725 , MR 0130837.
- ^ а б Робертс, Фред С. (1979), Теория измерений, с приложениями к принятию решений, полезности и социальным наукам , Энциклопедия математики и ее приложений, 7 , Аддисон-Уэсли, теорема 3.1 , ISBN 978-0-201-13506-0.
- ^ Luce, Р. Дункан (1956), "Semiorders и теория полезности дискриминации" (PDF) , Эконометрика , 24 (2): 178-191, DOI : 10,2307 / 1905751 , JSTOR 1905751 , MR 0078632.
- ^ а б Веллеман, Дэниел Дж. (2006), Как это доказать: структурированный подход , Cambridge University Press, стр. 204, ISBN 9780521675994.
- ^ Эпштейн, Дэвид ; Фальмань, Жан-Клод ; Овчинников, Сергей (2008), Теория медиа: междисциплинарная прикладная математика , Springer, раздел 9.4, Слабые порядки и кубические комплексы, стр. 188–196.
- ^ Циглер, Гюнтер М. (1995), Лекции по многогранникам , Тексты для выпускников по математике, 152 , Springer, стр. 18.
- ^ Chvátal, Vašek (1983), линейное программирование , Macmillan, стр. 29–38, ISBN 9780716715870.
- ^ Хабиб, Мишель; Пол, Кристоф; Viennot, Laurent (1999), "Методы Partition уточнения: интересная алгоритмическая Набор инструментов", Международный журнал Основы информатики , 10 (2): 147-170, DOI : 10,1142 / S0129054199000125 , MR 1759929.