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