Теория порядка - Order theory

Для актуального руководства по этой теме см. Краткое изложение теории порядка .

Теория порядка - это раздел математики, который исследует интуитивное понятие порядка с помощью бинарных отношений . Он обеспечивает формальную основу для описания таких утверждений, как «это меньше, чем это» или «это предшествует тому». Эта статья знакомит с полем и дает основные определения. Список терминов теории порядка можно найти в глоссарии теории порядка .

Предпосылки и мотивация

Заказы есть повсюду в математике и смежных областях, таких как информатика . Первый порядок, который часто обсуждается в начальной школе, - это стандартный порядок натуральных чисел, например, «2 меньше 3», «10 больше 5» или «У Тома меньше печенья, чем у Салли?». Эту интуитивно понятную концепцию можно распространить на заказы по другим наборам чисел , таким как целые и действительные числа . Идея быть больше или меньше другого числа является одной из основных интуиций систем счисления (по сравнению с системами счисления ) в целом (хотя обычно также интересует фактическая разница двух чисел, которая не задается порядком. ). Другими знакомыми примерами упорядочения являются алфавитный порядок слов в словаре и генеалогическое свойство линейного происхождения в группе людей.

Понятие порядка является очень общим, выходящим за рамки контекстов, которые имеют непосредственное интуитивное ощущение последовательности или относительной величины. В других контекстах приказы могут отражать понятия сдерживания или специализации. Абстрактно этот тип порядка составляет отношение подмножества , например, « Педиатры - это врачи » и « Круги - это просто эллипсы особого случая ».

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

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

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

Основные определения

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

Частично упорядоченные наборы

Заказы - это особые бинарные отношения. Предположим, что P - множество, а ≤ - отношение на P («отношение на множестве» означает «отношение между его обитателями»). Тогда ≤ является частичным порядком, если он рефлексивный , антисимметричный и транзитивный , то есть, если для всех a , b и c в P мы имеем следующее:

a ≤ a (рефлексивность)
если a ≤ b и b ≤ a, то a = b (антисимметрия)
если a ≤ b и b ≤ c, то a ≤ c (транзитивность).

Набор с частичным порядком на нем называется частично упорядоченным набором , poset или просто упорядоченным набором, если предполагаемое значение ясно. Проверяя эти свойства, можно сразу увидеть, что хорошо известные порядки натуральных , целых , рациональных и действительных чисел являются порядками в указанном выше смысле. Однако эти примеры обладают дополнительным свойством, заключающимся в том, что любые два элемента сопоставимы, то есть для всех a и b в P мы имеем следующее:

a ≤ b или b ≤ a .

Частичный заказ с этим свойством называется полным заказом . Эти порядки также можно назвать линейными порядками или цепочками . Хотя многие знакомые порядки линейны, порядок подмножеств в наборах является примером, когда это не так. Другой пример - отношение делимости (или "есть фактор ") |. Для двух натуральных чисел n и m мы пишем n | m, если n делит m без остатка. Легко видеть, что это дает частичный порядок. Отношение тождества = на любом множестве также является частичным порядком, в котором каждые два различных элемента несравнимы. Это также единственное отношение, которое одновременно является отношением частичного порядка и отношением эквивалентности . Многие расширенные свойства посетов интересны в основном для нелинейных порядков.

Визуализация позета

Диаграмма Хассе множества всех делителей числа 60, частично упорядоченных по делимости

Диаграммы Хассе могут визуально представлять элементы и отношения частичного упорядочения. Это чертежи графов, где вершины являются элементами poset, а отношение порядка указывается как ребрами, так и относительным расположением вершин. Ордера рисуются снизу вверх: если элемент x меньше (предшествует) y, то существует путь от x к y , направленный вверх. Часто бывает необходимо, чтобы кромки, соединяющие элементы, пересекались друг с другом, но элементы никогда не должны располагаться внутри кромки. Поучительное упражнение - нарисовать диаграмму Хассе для набора натуральных чисел, меньших или равных 13, в порядке следования | ( отношение делит ).

Даже некоторые бесконечные множества можно изобразить, наложив многоточие (...) на конечный подпорядок. Это хорошо работает для натуральных чисел, но не работает для действительных чисел, где нет непосредственного преемника выше 0; однако довольно часто можно получить интуицию, связанную с подобными диаграммами.

Особые элементы в заказе

В частично упорядоченном наборе могут быть элементы, играющие особую роль. Наиболее простой пример дается наименьшим элементом из более посета . Например, 1 - наименьший элемент положительных целых чисел, а пустой набор - наименьший набор в порядке подмножества. Формально элемент m является наименьшим элементом, если:

m ≤ a для всех элементов a порядка.

Обозначение 0 часто встречается для наименьшего элемента, даже если числа не рассматриваются. Однако в порядках наборов чисел это обозначение может быть неуместным или двусмысленным, поскольку число 0 не всегда является наименьшим. Пример дается указанным выше порядком делимости |, где 1 - наименьший элемент, поскольку он делит все остальные числа. Напротив, 0 - это число, которое делится на все остальные числа. Следовательно, это величайший элемент порядка. Другие частые термины для наименьшего и наибольшего элементов - это нижний и верхний или ноль и единица .

Наименьшие и самые большие элементы могут не существовать, как показывает пример реальных чисел. Но если они есть, то всегда уникальны. Напротив, рассмотрим отношение делимости | на множестве {2,3,4,5,6}. Хотя в этом наборе нет ни верха, ни низа, элементы 2, 3 и 5 не имеют элементов под ними, а элементы 4, 5 и 6 не имеют верхних элементов. Такие элементы называются минимальными и максимальными соответственно. Формально элемент т является минимальным , если:

a ≤ m влечет a = m для всех элементов a порядка.

Замена ≤ на ≥ дает определение максимальности . Как показывает пример, может быть много максимальных элементов, и некоторые элементы могут быть как максимальными, так и минимальными (например, 5 выше). Однако, если есть наименьший элемент, то это единственный минимальный элемент порядка. Опять же, в бесконечных множествах максимальные элементы не всегда существуют - множество всех конечных подмножеств данного бесконечного множества, упорядоченное по включению подмножества, дает один из многих контрпримеров. Важным инструментом для обеспечения существования максимальных элементов при определенных условиях является лемма Цорна .

Подмножества частично упорядоченных наборов наследуют порядок. Мы уже применили это, рассматривая подмножество {2, 3, 4, 5, 6} натуральных чисел с индуцированным порядком делимости. Теперь есть также элементы poset, которые являются специальными по отношению к некоторому подмножеству порядка. Это приводит к определению оценок сверху . Учитывая подмножество S некоторого посета P , верхняя граница S является элементом Ь из Р , который находится выше всех элементов S . Формально это означает, что

S & le ; б , для всех S в S .

Нижние границы снова определяются инвертированием порядка. Например, -5 - это нижняя граница натуральных чисел как подмножества целых чисел. Для данного набора наборов верхняя граница для этих наборов при упорядочении подмножеств дается их объединением . Фактически, эта верхняя граница довольно особенная: это наименьший набор, содержащий все наборы. Таким образом, мы нашли точную верхнюю границу множества множеств. Это понятие также называется супремумом или соединением , и для множества S пишут sup ( S ) или его наименьшую верхнюю границу. И наоборот, точная нижняя грань известна как infimum или meet и обозначается 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 ( х ). У них есть много приложений во всевозможных «замыканиях», которые появляются в математике.

Помимо совместимости с простыми отношениями порядка, функции между позициями могут также хорошо вести себя по отношению к специальным элементам и конструкциям. Например, когда мы говорим о позициях с наименьшим элементом, может показаться разумным рассматривать только монотонные функции, которые сохраняют этот элемент, т.е. которые отображают наименьшее количество элементов на наименьшее количество элементов. Если двоичная infima ∧ существует, то разумным свойством может быть требование, чтобы f ( x ∧ y ) = f ( x ) ∧ f ( y ) для всех x и y . Все эти свойства и многие другие могут быть скомпилированы под ярлыком функций, сохраняющих предел .

Наконец, можно перевернуть представление, переключившись с функций заказов на порядки функций . Действительно, функции между двумя множествами P и Q могут быть упорядочены через поточечный порядок . Для двух функций F и г , мы имеем F ≤ г , если Р ( х ) ≤ г ( х ) для всех элементов х из Р . Это происходит, например, в теории предметной области , где функциональные пространства играют важную роль.

Особые виды заказов

Многие структуры, изучаемые в рамках теории порядка, используют отношения порядка с дополнительными свойствами. На самом деле особый интерес представляют даже некоторые отношения, не являющиеся частичными порядками. В основном следует упомянуть концепцию предварительного заказа . Предварительный порядок - это отношение, которое является рефлексивным и транзитивным, но не обязательно антисимметричным. Каждый предварительный заказ индуцирует отношение эквивалентности между элементами, где a эквивалентно b , если a ≤ b и b ≤ a . Предварительные заказы можно превратить в заказы, указав все элементы, эквивалентные этому отношению.

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

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

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

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

x  ∧ ( y  ∨  z ) = ( x  ∧  y ) ∨ ( x  ∧  z ) для всех x , y и z .

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

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

Существует много других важных свойств позетов. Например, ч.у. является локально конечным, если каждый отрезок [ a , b ] в нем конечен . Локально конечные множества порождают алгебры инцидентности, которые, в свою очередь, могут использоваться для определения эйлеровой характеристики конечных ограниченных множеств.

Подмножества упорядоченных наборов

В упорядоченном наборе можно определить множество типов специальных подмножеств на основе заданного порядка. Простым примером являются верхние наборы ; т.е. наборы, которые содержат все элементы, расположенные над ними по порядку. Формально, верхнее замыкание множества S в ч.у.м. P задается множеством { x in P | есть некоторые у в S с у ≤ х }. Множество, равное его верхнему замыканию, называется верхним множеством. Нижние множества определяются двойственно.

Более сложные нижние подмножества - это идеалы , которые обладают дополнительным свойством, заключающимся в том, что каждые два их элемента имеют верхнюю границу в пределах идеала. Их двойники задаются фильтрами . Связанное понятие - это направленное подмножество , которое, как идеал, содержит верхние границы конечных подмножеств, но не обязательно должно быть нижним множеством. Кроме того, его часто обобщают на предварительно упорядоченные наборы.

Подмножество, которое - как подмножество - линейно упорядочено, называется цепочкой . Противоположное понятие, антицепь , представляет собой подмножество, которое не содержит двух сопоставимых элементов; т.е. это дискретный порядок.

Связанные математические области

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

Универсальная алгебра

Как уже упоминалось, методы и формализмы универсальной алгебры являются важным инструментом для многих теоретико-порядковых соображений. Помимо формализации порядков в терминах алгебраических структур , удовлетворяющих определенным тождествам, можно также установить другие связи с алгеброй. Пример дается соответствием между булевыми алгебрами и булевыми кольцами . Другие вопросы связаны с существованием свободных конструкций , таких как свободные решетки, основанные на заданном наборе образующих. Кроме того, операторы замыкания важны при изучении универсальной алгебры.

Топология

В топологии заказы играют очень важную роль. Фактически, набор открытых множеств представляет собой классический пример полной решетки, точнее полной алгебры Гейтинга (или « фрейма », или « локали »). Фильтры и сети - это понятия, тесно связанные с теорией порядка, и оператор замыкания множеств может использоваться для определения топологии. Помимо этих соотношений, топологию можно рассматривать исключительно в терминах открытых решеток множеств, что ведет к изучению бессмысленной топологии . Кроме того, естественный предварительный порядок элементов базового набора топологии задается так называемым порядком специализации , который на самом деле является частичным порядком, если топология T 0 .

И наоборот, в теории порядка часто используются топологические результаты. Существуют различные способы определения подмножеств порядка, которые можно рассматривать как открытые множества топологии. Рассматривая топологии на ч.у.н. ( X , ≤), которые, в свою очередь, индуцируют ≤ как порядок своей специализации, лучшей такой топологией является топология Александрова , заданная тем, что все верхние множества являются открытыми. И наоборот, самая грубая топология, которая индуцирует порядок специализации, - это верхняя топология , имеющая дополнения к главным идеалам (то есть множества вида { y in X | y ≤ x } для некоторого x ) в качестве подбазы . Кроме того, топология с порядком специализации ≤ может быть согласована по порядку , что означает, что их открытые множества «недоступны для направленной супремум» (по отношению к ≤). Согласованная топология наилучшего порядка - это топология Скотта , которая грубее топологии Александрова. Третьей важной топологией в этом духе является топология Лоусона . Между этими топологиями и концепциями теории порядка существует тесная связь. Например, функция сохраняет направленную супрему тогда и только тогда, когда она непрерывна относительно топологии Скотта (по этой причине это свойство теории порядка также называется непрерывностью Скотта ).

Теория категорий

Визуализация порядков с помощью диаграмм Хассе имеет простое обобщение: вместо отображения меньших элементов под большими, направление порядка также может быть изображено путем указания направлений к краям графа. Таким образом, каждый порядок рассматривается как эквивалент ориентированного ациклического графа , где узлы являются элементами poset, и существует направленный путь от a до b тогда и только тогда, когда a ≤ b . Отказавшись от ацикличности, можно также получить все предварительные заказы.

Когда они оснащены всеми транзитивными ребрами, эти графы, в свою очередь, представляют собой просто особые категории , где элементы являются объектами, а каждый набор морфизмов между двумя элементами не более чем одноэлементный. Функции между порядками становятся функторами между категориями. Многие идеи теории порядка - это просто концепции теории категорий в малом. Например, инфимум - это просто категориальный продукт . В более общем смысле, можно охватить инфиму и верхнюю границу абстрактным понятием категориального предела (или копредела , соответственно). Еще одно место, где возникают категориальные идеи, - это концепция (монотонной) связности Галуа , которая совпадает с парой сопряженных функторов .

Но теория категорий также оказывает влияние на теорию порядка в более широком масштабе. Классы положений с соответствующими функциями, как обсуждалось выше, образуют интересные категории. Часто также можно формулировать конструкции заказов, например, заказ продукта , в терминах категорий. Дальнейшее понимание достигается, когда категории порядков оказываются категорически эквивалентными другим категориям, например топологическим пространствам. Это направление исследований приводит к различным теоремам представления , которые часто собираются под названием двойственности Стоуна .

История

Как объяснялось ранее, порядки в математике используются повсеместно. Однако самые ранние явные упоминания о частичных заказах, вероятно, можно найти не ранее 19 века. В этом контексте большое значение имеют работы Джорджа Буля . Более того, в работах Чарльза Сандерса Пирса , Ричарда Дедекинда и Эрнста Шредера также рассматриваются концепции теории порядка.

Авторы упорядоченной геометрии были перечислены в учебнике 1961 года :

Это был Паши в 1882 году, который первый указал, что геометрия порядка может быть разработана без ссылки на измерения. Его система аксиом была постепенно улучшена Пеано (1889 г.), Гильбертом (1899 г.) и Вебленом (1904 г.).

-  HSM Coxeter , Введение в геометрию

В 1901 году Бертран Рассел написал «О понятии порядка», исследуя основы идеи посредством создания серий . Он вернулся к этой теме в части IV «Принципов математики» (1903 г.). Рассел заметил, что бинарное отношение aRb имеет смысл, идущий от a к b, причем обратное отношение имеет противоположный смысл, а смысл «является источником порядка и ряда». (стр. 95) Он признает, что Иммануил Кант «осознавал разницу между логическим противопоставлением и противопоставлением положительного и отрицательного». Он писал, что Кант заслуживает похвалы, поскольку он «впервые обратил внимание на логическую важность асимметричных отношений».

Термин « позет» как сокращение от частично упорядоченного множества был введен Гарреттом Биркгофом во втором издании его влиятельной книги « Теория решеток» .

Смотрите также

Примечания

использованная литература

внешние ссылки