Теория порядка — это раздел математики , который исследует интуитивное понятие порядка с помощью бинарных отношений . Он обеспечивает формальную основу для описания таких утверждений, как «это меньше того» или «это предшествует тому». В этой статье представлено поле и приведены основные определения. Список терминов теории порядка можно найти в глоссарии теории порядка .
Заказы повсюду в математике и смежных областях, таких как информатика . Первый порядок, который часто обсуждают в начальной школе, - это стандартный порядок натуральных чисел , например: «2 меньше 3», «10 больше 5 » или «У Тома меньше печенья, чем у Салли?». Эта интуитивная концепция может быть распространена на порядки других наборов чисел , таких как целые и действительные числа . Идея того, что число больше или меньше другого числа, является одной из основных интуиций систем счисления (сравните с системами счисления ) в целом (хотя обычно также интересует фактическая разница двух чисел, которая не задается порядком ). Другими известными примерами упорядочения являются алфавитный порядок слов в словаре и генеалогическое свойство линейного происхождения внутри группы людей.
Понятие порядка является очень общим и выходит за рамки контекстов, в которых возникает непосредственное интуитивное ощущение последовательности или относительного количества. В других контекстах приказы могут отражать понятия сдерживания или специализации. Абстрактно этот тип порядка представляет собой отношение подмножества , например: « Педиатры — врачи » и « Круги — это просто эллипсы особого случая ».
Некоторые порядки, такие как «меньше чем» в натуральных числах и алфавитный порядок в словах, обладают особым свойством: каждый элемент можно сравнивать с любым другим элементом, т. е. он меньше (раньше), больше (позже) или идентичен. Однако многие другие заказы этого не делают. Рассмотрим, например, порядок подмножеств в коллекции наборов : хотя набор птиц и набор собак являются подмножествами множества животных, ни птицы, ни собаки не составляют подмножества другого. Такие порядки, как отношение «подмножество», для которых существуют несравнимые элементы, называются частичными порядками ; Заказы, для которых каждая пара элементов сопоставима, являются полными заказами .
Теория порядка отражает интуитивное представление о порядках, которое возникает из таких примеров в общей обстановке. Это достигается путем указания свойств, согласно которым отношение ≤ должно быть математическим порядком. Этот более абстрактный подход имеет большой смысл, поскольку можно вывести множество теорем в общем случае, не уделяя внимания деталям какого-либо конкретного порядка. Эти идеи затем можно легко перенести во многие менее абстрактные приложения.
Благодаря широкому практическому использованию порядков были определены многочисленные специальные виды упорядоченных множеств, некоторые из которых превратились в собственные математические области. Кроме того, теория порядка не ограничивается различными классами отношений порядка, но также рассматривает соответствующие функции между ними. Простой пример свойства теории порядка для функций можно получить из анализа , в котором часто встречаются монотонные функции.
В этом разделе представлены упорядоченные множества, основанные на понятиях теории множеств , арифметики и бинарных отношений .
Заказы — это особые бинарные отношения. Предположим, что P — это множество и что ≤ — это отношение на P («отношение на множестве» понимается как «отношение между его обитателями»). Тогда ≤ является частичным порядком , если он рефлексивен , антисимметричен и транзитивен , то есть если для всех a , b и c в P имеем следующее:
Набор с частичным порядком называется частично упорядоченным набором , частично упорядоченным набором или просто упорядоченным набором, если предполагаемое значение ясно. Проверив эти свойства, сразу видно, что все известные порядки натуральных , целых , рациональных и действительных чисел являются порядками в указанном выше смысле. Однако эти примеры обладают дополнительным свойством: любые два элемента сравнимы, то есть для всех a и b в P имеем следующее:
Частичный порядок, обладающий этим свойством, называется полным порядком . Эти заказы также можно назвать линейными заказами или цепочками . Хотя многие знакомые порядки являются линейными, порядок подмножеств множеств представляет собой пример, когда это не так. Другой пример дает отношение делимости (или «является фактором ») |. Для двух натуральных чисел n и m пишем n | m , если n делит m без остатка. Легко видеть, что это дает частичный порядок. Отношение тождества = на любом множестве также является частичным порядком, в котором каждые два различных элемента несравнимы. Это также единственное отношение, которое является одновременно отношением частичного порядка и отношением эквивалентности . Многие расширенные свойства ЧУМ интересны в основном для нелинейных порядков.
Диаграммы Хассе могут наглядно представлять элементы и отношения частичного упорядочения. Это рисунки графов , где вершины являются элементами частичного множества, а отношение порядка указывается как ребрами, так и относительным расположением вершин. Ордера рисуются снизу вверх: если элемент x меньше (предшествует) y , то существует путь от x до y , направленный вверх. Часто бывает необходимо, чтобы края, соединяющие элементы, пересекали друг друга, но элементы никогда не должны располагаться внутри края. Поучительным упражнением является построение диаграммы Хассе для набора натуральных чисел, меньших или равных 13, упорядоченных по | ( отношение делит ).
Даже некоторые бесконечные множества можно изобразить в виде диаграммы, наложив многоточие (...) на конечный подпорядок. Это хорошо работает для натуральных чисел, но не работает для действительных чисел, где нет непосредственного преемника выше 0; однако довольно часто можно получить интуицию, связанную с диаграммами подобного рода [ неопределенно ] .
В частично упорядоченном множестве могут быть элементы, играющие особую роль. Самый простой пример — наименьший элемент частичного набора . Например, 1 — это наименьший элемент из положительных целых чисел, а пустой набор — наименьший набор в порядке подмножества. Формально элемент m является наименьшим элементом, если:
Обозначение 0 часто встречается для наименьшего элемента, даже если речь не идет о числах. Однако в заказах наборов чисел это обозначение может быть неуместным или двусмысленным, поскольку число 0 не всегда является наименьшим. Примером может служить приведенный выше порядок делимости |, где 1 — наименьший элемент, поскольку он делит все остальные числа. Напротив, 0 — это число, которое делится на все остальные числа. Следовательно, это величайший элемент порядка. Другие частые термины для наименьшего и наибольшего элементов — это нижний и верхний или ноль и единица .
Наименьший и наибольший элементы могут не существовать, как показывает пример действительных чисел. Но если они существуют, то они всегда уникальны. Напротив, рассмотрим отношение делимости | на множестве {2,3,4,5,6}. Хотя в этом наборе нет ни верха, ни низа, элементы 2, 3 и 5 не имеют элементов ниже них, а элементы 4, 5 и 6 не имеют ни одного элемента выше. Такие элементы называются минимальными и максимальными соответственно. Формально элемент m является минимальным, если:
Замена ≤ на ≥ дает определение максимальности . Как показывает пример, максимальных элементов может быть много, а некоторые элементы могут быть как максимальными, так и минимальными (например, 5 выше). Однако если существует наименьший элемент, то это единственный минимальный элемент порядка. Опять же, в бесконечных частично упорядоченных множествах максимальные элементы не всегда существуют - набор всех конечных подмножеств данного бесконечного множества, упорядоченных путем включения подмножества, представляет собой один из многих контрпримеров. Важным инструментом, обеспечивающим существование максимальных элементов при определенных условиях, является лемма Цорна .
Подмножества частично упорядоченных множеств наследуют порядок. Мы уже применяли это, рассматривая подмножество {2,3,4,5,6} натуральных чисел с индуцированным порядком делимости. Теперь есть также элементы ЧУМ, которые являются особенными по отношению к некоторому подмножеству порядка. Это приводит к определению верхних границ . Учитывая подмножество S некоторого частично упорядоченного множества P , верхняя граница S — это элемент b из P , который находится выше всех элементов S. Формально это означает, что
Нижние границы снова определяются путем инвертирования порядка. Например, -5 — это нижняя граница натуральных чисел как подмножества целых чисел. Для данного набора множеств верхняя граница этих множеств при упорядочении подмножеств определяется их объединением . На самом деле эта верхняя граница весьма специфична: это наименьшее множество, содержащее все множества. Таким образом, мы нашли наименьшую верхнюю границу множества множеств. Эту концепцию также называют супремумом или соединением , а для множества S пишут sup( S ) или его наименьшую верхнюю границу. И наоборот, наибольшая нижняя граница известна как нижняя грань или встреча и обозначается inf( S ) или . Эти концепции играют важную роль во многих приложениях теории порядка. Для двух элементов x и y также пишутся and для sup({ x , y }) и inf({ x , y }) соответственно.
Например, 1 — это нижняя грань положительных целых чисел как подмножества целых чисел.
В качестве другого примера рассмотрим еще раз отношение | на натуральных числах. Наименьшая верхняя граница двух чисел — это наименьшее число, которое делится на них оба, то есть наименьшее общее кратное этих чисел. Наибольшие нижние оценки, в свою очередь, определяются наибольшим общим делителем .
В предыдущих определениях мы часто отмечали, что понятие можно определить, просто изменив порядок в предыдущем определении. Это касается «наименьшего» и «наибольшего», «минимального» и «максимального», «верхней границы» и «нижней границы» и так далее. Это общая ситуация в теории порядка: данный порядок можно инвертировать, просто поменяв его направление, наглядно перевернув диаграмму Хассе сверху вниз. Это приводит к так называемому двойственному , обратному или противоположному порядку .
Каждое определение теории порядка имеет двойственное определение: это понятие, которое получается путем применения определения к обратному порядку. Поскольку все понятия симметричны, эта операция сохраняет теоремы о частичных порядках. Для данного математического результата можно просто перевернуть порядок и заменить все определения двойственными, и получить еще одну действительную теорему. Это важно и полезно, поскольку можно получить две теоремы ценой одной. Еще некоторые подробности и примеры можно найти в статье о двойственности в теории порядка .
Существует множество способов создания заказов из заданных заказов. Двойной порядок является одним из примеров. Другая важная конструкция — это декартово произведение двух частично упорядоченных множеств, взятое вместе с порядком произведения пар элементов. Порядок определяется формулой ( a , x ) ≤ ( b , y ), если (и только если) a ≤ b и x ≤ y . (Обратите внимание, что в этом определении символ отношения ≤ имеет три различных значения.) Непересекающееся объединение двух частично упорядоченных множеств — еще один типичный пример построения порядка, где порядок — это просто (непересекающееся) объединение исходных порядков.
Каждый частичный порядок ≤ порождает так называемый строгий порядок <, определяя a < b , если a ≤ b , а не b ≤ a . Это преобразование можно инвертировать, установив a ≤ b , если a < b или a = b . Эти две концепции эквивалентны, хотя в некоторых случаях работать с одной может быть удобнее, чем с другой.
Разумно рассматривать функции между частично упорядоченными множествами, обладающие некоторыми дополнительными свойствами, связанными с отношениями порядка двух множеств. Самым фундаментальным условием, которое возникает в этом контексте, является монотонность . Функция f из частично упорядоченного множества P в частично упорядоченное множество Q является монотонной или сохраняющей порядок , если a ≤ b в P влечет за собой f ( a ) ≤ f ( b ) в Q (отметим, что, строго говоря, эти два отношения здесь различны, поскольку они применимы к разным наборам.). Обратное к этой импликации приводит к функциям, отражающим порядок , то есть к функциям f , указанным выше, для которых f ( a ) ≤ f ( b ) влечет a ≤ b . С другой стороны, функция также может быть изменяющей порядок или антитонной , если из a ≤ b следует f ( a ) ≥ f ( b ).
Встраивание порядка — это функция f между заказами, которая одновременно сохраняет и отражает порядок. Примеры этих определений находятся легко. Например, функция, отображающая натуральное число в его последующий элемент, очевидно, монотонна относительно натурального порядка. Любая функция из дискретного порядка, т. е. из множества, упорядоченного по тождественному порядку "=", также является монотонной. Сопоставление каждого натурального числа с соответствующим действительным числом дает пример встраивания порядка. Дополнение множества в наборе мощности является примером функции антитона.
Важный вопрос: когда два порядка «по сути равны», т.е. когда они одинаковы с точностью до переименования элементов. Изоморфизмы порядка — это функции, определяющие такое переименование. Порядковый изоморфизм — это монотонная биективная функция, имеющая монотонную обратную. Это эквивалентно сюръективному вложению порядка. Следовательно, образ f ( P ) порядкового вложения всегда изоморфен P , что оправдывает термин «вложение».
Более сложный тип функций дают так называемые связи Галуа . Монотонные связи Галуа можно рассматривать как обобщение порядковых изоморфизмов, поскольку они представляют собой пару двух функций в обратных направлениях, которые «не совсем» обратны друг другу, но все же имеют тесные связи.
Другим специальным типом самоотображений на частично упорядоченном множестве являются операторы замыкания , которые являются не только монотонными, но и идемпотентными , т.е. f ( x ) = f ( f ( x )), и экстенсивными (или инфляционными ), т.е. x ≤ f ( Икс ). Они имеют множество применений во всех видах «замыканий», встречающихся в математике.
Помимо совместимости с простыми отношениями порядка, функции между частично упорядоченными множествами могут также хорошо вести себя по отношению к специальным элементам и конструкциям. Например, когда речь идет о ЧУП с наименьшим элементом, может показаться разумным рассматривать только монотонные функции, которые сохраняют этот элемент, т.е. которые отображают наименьшее количество элементов наименьшее количество элементов. Если двоичная инфима ∧ существует, то разумным свойством может быть требование, чтобы f ( x ∧ y ) = f ( x ) ∧ f ( y ) для всех x и y . Все эти свойства, как и многие другие, можно объединить под названием функций, сохраняющих пределы .
Наконец, можно инвертировать представление, переключаясь с функций порядков на порядки функций . Действительно, функции между двумя частично упорядоченными множествами P и Q можно упорядочить через поточечный порядок . Для двух функций f и g мы имеем f ≤ g , если f ( x ) ≤ g ( x ) для всех элементов x из P. Это происходит, например, в теории предметной области , где функциональные пространства играют важную роль.
Многие структуры, изучаемые в теории порядка, используют отношения порядка с дополнительными свойствами. В действительности, даже некоторые отношения, не являющиеся частичным порядком, представляют особый интерес. В первую очередь следует упомянуть концепцию предзаказа . Предварительный порядок — это отношение, которое является рефлексивным и транзитивным, но не обязательно антисимметричным. Каждый предварительный порядок вызывает отношение эквивалентности между элементами, где a эквивалентно b , если a ≤ b и b ≤ a . Предварительные заказы можно превратить в заказы, определив все элементы, эквивалентные по этому отношению.
На основе числовых данных о позициях заказа можно определить несколько типов заказов: общий заказ получается в результате присвоения отдельных действительных чисел каждому элементу и использования числовых сравнений для упорядочивания элементов; вместо этого, если разным элементам разрешено иметь равные числовые оценки, получается строгий слабый порядок . Требование, чтобы две оценки были разделены фиксированным порогом, прежде чем их можно будет сравнить, приводит к концепции полупорядка , в то время как разрешение порога варьироваться для каждого элемента создает интервальный порядок .
Дополнительное простое, но полезное свойство приводит к так называемым хорошо обоснованным , для которых все непустые подмножества имеют минимальный элемент. Обобщая хорошие порядки от линейных до частичных, можно сказать, что множество является частично упорядоченным, если все его непустые подмножества имеют конечное число минимальных элементов.
Многие другие типы порядков возникают, когда гарантировано существование нижних и верхних множеств определенных множеств. Ориентируясь на этот аспект, обычно называемый полнотой заказов, получается:
Однако можно пойти еще дальше: если все конечные непустые инфимы существуют, то ∧ можно рассматривать как тотальную бинарную операцию в смысле универсальной алгебры . Следовательно, в решетке доступны две операции ∧ и ∨, и можно определить новые свойства, задав тождества, такие как
Это условие называется дистрибутивностью и приводит к возникновению дистрибутивных решеток . Есть и другие важные законы дистрибутивности, которые обсуждаются в статье о дистрибутивности в теории порядка . Некоторые дополнительные структуры порядка, которые часто задаются с помощью алгебраических операций и определения тождеств:
обе они вводят новую операцию ~, называемую отрицанием . Обе структуры играют роль в математической логике , и особенно булевы алгебры имеют широкое применение в информатике . Наконец, различные структуры в математике сочетают порядки с еще большим количеством алгебраических операций, как в случае с кванталами , которые позволяют определить операцию сложения.
Существует множество других важных свойств частично упорядоченных множеств. Например, ЧУ-множество является локально конечным, если каждый замкнутый интервал [ a , b ] в нем конечен . Локально конечные ЧУМ порождают алгебры инцидентности , которые, в свою очередь, можно использовать для определения эйлеровой характеристики конечных ограниченных ЧУМ.
В упорядоченном наборе можно определить множество типов специальных подмножеств на основе заданного порядка. Простым примером являются верхние множества ; т.е. наборы, содержащие все элементы, находящиеся выше них в порядке. Формально верхнее замыкание множества S в частично упорядоченном множестве P задается множеством { x в P | в S существует некоторый y такой, что y ≤ x }. Множество, равное своему верхнему замыканию, называется верхним множеством. Нижние множества определяются двойственно.
Более сложные нижние подмножества — это идеалы , которые обладают дополнительным свойством: каждые два их элемента имеют верхнюю границу внутри идеала. Их двойники задаются фильтрами . Родственной концепцией является понятие направленного подмножества , которое, как идеал, содержит верхние границы конечных подмножеств, но не обязательно должно быть нижним множеством. Более того, его часто обобщают на предварительно упорядоченные наборы.
Подмножество, которое, как и подмножество, линейно упорядочено, называется цепью . Противоположное понятие, антицепь , представляет собой подмножество, не содержащее двух сопоставимых элементов; т.е. это дискретный порядок.
Хотя в большинстве математических областей порядки так или иначе используются , существует также несколько теорий, отношения которых выходят далеко за рамки простого применения. Некоторые из них вместе с основными точками соприкосновения с теорией порядка будут представлены ниже.
Как уже упоминалось, методы и формализмы универсальной алгебры являются важным инструментом для многих рассуждений теории порядка. Помимо формализации порядков в терминах алгебраических структур , удовлетворяющих определенным тождествам, можно установить и другие связи с алгеброй. Примером может служить соответствие между булевыми алгебрами и булевыми кольцами . Другие вопросы связаны с существованием свободных конструкций , таких как свободные решетки , основанные на заданном наборе образующих. Более того, операторы замыкания важны при изучении универсальной алгебры.
В топологии порядки играют очень важную роль. Фактически, совокупность открытых множеств представляет собой классический пример полной решетки, точнее, полной алгебры Гейтинга (или « фрейма », или « локали »). Фильтры и сети — это понятия, тесно связанные с теорией порядка, и оператор замыкания множеств можно использовать для определения топологии. За пределами этих отношений топологию можно рассматривать исключительно с точки зрения решеток открытых множеств, что приводит к изучению бессмысленной топологии . Более того, естественный предварительный порядок элементов базового набора топологии задается так называемым порядком специализации , который на самом деле является частичным порядком, если топология равна T 0 .
И наоборот, в теории порядка часто используются топологические результаты. Существуют различные способы определения подмножеств порядка, которые можно рассматривать как открытые множества топологии. Если рассматривать топологии на ЧУ-множестве ( X , ≤ ), которые, в свою очередь, индуцируют ≤ в качестве порядка специализации, лучшей такой топологией является топология Александрова , заданная путем рассмотрения всех верхних множеств как открытых. И наоборот, самая грубая топология, которая вызывает порядок специализации, - это верхняя топология , имеющая в качестве подбазы дополнения к главным идеалам (т.е. множества формы { y в X | y ≤ x } для некоторого x ) . Кроме того, топология с порядком специализации ≤ может быть согласованной по порядку , что означает, что их открытые множества «недоступны для направленных супремумов» (относительно ≤). Топология наилучшего согласованного порядка — это топология Скотта , которая более грубая, чем топология Александрова. Третьей важной топологией в этом духе является топология Лоусона . Между этими топологиями и концепциями теории порядка существует тесная связь. Например, функция сохраняет направленные супремумы тогда и только тогда, когда она непрерывна относительно топологии Скотта (по этой причине это теоретико-порядковое свойство также называется Скотт-непрерывностью ).
Визуализация заказов с помощью диаграмм Хассе имеет прямое обобщение: вместо отображения меньших элементов под большими можно также изобразить направление заказа, задав направления краям графа. Таким образом, каждый порядок рассматривается как эквивалент ориентированного ациклического графа , где узлы являются элементами частично упорядоченного множества и существует направленный путь от a до b тогда и только тогда, когда a ≤ b . Отбросив требование ацикличности, можно также получить все предварительные заказы.
Когда эти графы снабжены всеми транзитивными ребрами, они, в свою очередь, представляют собой просто специальные категории , где элементы являются объектами, а каждый набор морфизмов между двумя элементами не более чем одноэлементный. Функции между порядками становятся функторами между категориями. Многие идеи теории порядка — это всего лишь концепции теории категорий в маленьком смысле. Например, инфимум — это просто категориальное произведение . В более общем смысле, можно охватить нижнюю и верхнюю границы абстрактным понятием категориального предела (или копредела соответственно). Еще одно место, где встречаются категориальные идеи, — это концепция (монотонной) связности Галуа , которая представляет собой то же самое, что пара сопряженных функторов .
Но теория категорий также оказывает влияние на теорию порядка в более широком масштабе. Классы ЧУМ с соответствующими функциями, как обсуждалось выше, образуют интересные категории. Часто можно также сформулировать конструкции заказов, например заказ продукта , в терминах категорий. Дальнейшее понимание возникает, когда категории порядков оказываются категорически эквивалентными другим категориям, например топологическим пространствам. Это направление исследований приводит к различным теоремам о представлении , часто собираемым под названием двойственности Стоуна .
Как объяснялось ранее, порядки широко распространены в математике. Однако самые ранние явные упоминания о частичных порядках, вероятно, можно найти не ранее XIX века. В этом контексте большое значение имеют работы Джорджа Буля . Более того, работы Чарльза Сандерса Пирса , Ричарда Дедекинда и Эрнста Шредера также рассматривают концепции теории порядка.
Авторы упорядоченной геометрии были перечислены в учебнике 1961 года :
Именно Паш в 1882 году первым указал, что геометрию порядка можно разработать без привязки к измерениям. Его система аксиом постепенно улучшалась Пеано (1889 г.), Гильбертом (1899 г.) и Вебленом (1904 г.).
- HSM Коксетер , Введение в геометрию
В 1901 году Бертран Рассел написал «О понятии порядка» [2] , исследуя основы этой идеи посредством генерации рядов . Он вернулся к этой теме в части IV « Основ математики» (1903 г.). Рассел отметил, что бинарное отношение aRb имеет смысл, исходящий от a к b , а обратное отношение имеет противоположный смысл, а смысл «является источником порядка и ряда». (стр. 95) Он признает, что Иммануил Кант [3] «осознавал разницу между логической оппозицией и оппозицией положительного и отрицательного». Он писал, что Кант заслуживает похвалы, поскольку он «впервые обратил внимание на логическую важность асимметричных отношений».
Термин частично упорядоченное множество приписывается Гаррету Биркгофу во втором издании его влиятельной книги «Теория решеток» . [4] [5]
