Частично заказанный набор

Диаграмма Хассе из множества всех подмножеств некоторого множества из трех элементов { х , у , г }, упорядоченное по включению. Разные наборы на одном горизонтальном уровне несопоставимы друг с другом. Некоторые другие пары, такие как { x } и { y , z }, также несравнимы.

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

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

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

Позиционирование может быть визуализировано через его диаграмму Хассе , которая изображает отношение упорядочения. ^[1]

Формальное определение [ править ]

(Нестрогий) частичный порядок ^[2] - это однородное бинарное отношение ≤ над множеством P, удовлетворяющее конкретным аксиомам, которые обсуждаются ниже. Когда ≤ Ь , мы говорим , что это связано с б . (Это не означает, что b также связано с a , потому что отношение не обязательно должно быть симметричным .)

Аксиомы для нестрогого частичного порядка утверждают, что отношение ≤ рефлексивно , антисимметрично и транзитивно . То есть для всех a , b и c в P он должен удовлетворять:

1. a ≤ a ( рефлексивность : каждый элемент связан сам с собой).
2. если a ≤ b и b ≤ a , то a = b ( антисимметрия : два различных элемента не могут быть связаны в обоих направлениях).
3. если a ≤ b и b ≤ c , то a ≤ c ( транзитивность : если первый элемент связан со вторым элементом, и, в свою очередь, этот элемент связан с третьим элементом, то первый элемент связан с третьим элементом. элемент).

Другими словами, частичный порядок - это антисимметричный предпорядок .

Набор с частичным порядком называется частично упорядоченным набором (также называемым poset ). Иногда также используется термин упорядоченный набор , если из контекста ясно, что никакой другой вид порядка не подразумевается. В частности, полностью упорядоченные множества также могут называться «упорядоченные множества», особенно в областях, где эти структуры более распространены, чем посеты.

Для получения более , б , элементы частично упорядоченного множества Р , если ≤ б или б ≤ , то и б являются сопоставимыми . В остальном они несравнимы . На рисунке вверху справа, например, { x } и { x ,  y ,  z } сопоставимы, а { x } и { y } - нет. Частичный порядок, при котором каждая пара элементов сравнима, называется полным порядком или линейным порядком.; полностью упорядоченное множество также называется цепочкой (например, натуральные числа с их стандартным порядком). Подмножество чугуна, в котором никакие два различных элемента не сопоставимы, называется антицепью (например, набор одиночных элементов {{ x }, { y }, { z }} на верхнем правом рисунке). Элемент a называется строго меньшим, чем элемент b , если a ≤ b и a ≠ b . Говорят, что элемент a покрывается другим элементом b , что записываетсяa ⋖ b (или a <: b ), если a строго меньше b и между ними не помещается третий элемент c ; формально: если и a ≤ b, и a ≠ b истинны, и a ≤ c ≤ b ложно для каждого c с a ≠ c ≠ b . Более определение краткого будет дано ниже с использованием строгого порядка , соответствующий «≤». Например, { x } покрывается { x , z } на верхнем правом рисунке, но не через { x ,  y ,  z }.

Примеры [ править ]

Стандартные примеры позы, возникающие в математике, включают:

• В действительных числах упорядочены по стандарту менее чем или равные отношению ≤ (полностью упорядоченное множество, а).
• Набор подмножеств данного набора (его набор мощности ), упорядоченный по включению (см. Рисунок вверху справа). Точно так же набор последовательностей, упорядоченных по подпоследовательности , и набор строк, упорядоченных по подстроке .
• Множество натуральных чисел с отношением делимости .
• Множество вершин ориентированного ациклического графа, упорядоченное по достижимости .
• Множество подпространств одного векторного пространства упорядочены по включению.
• Для частично упорядоченного множества Р , то пространство последовательностей , содержащее все последовательности элементов из Р , где последовательность последовательности предшествует Ь , если каждый элемент в течение предшествует соответствующий пункт в б . Формально ( a _n ) _{n ∈ℕ} ≤ ( b _n ) _{n ∈ℕ} тогда и только тогда, когда a _n ≤ b _n для всех n в ℕ, то есть покомпонентный порядок .
• Для множества X и частично упорядоченного множества Р , тем функциональное пространство , содержащее все функции из X в Р , где Р ≤ г тогда и только тогда , когда F ( х ) ≤ г ( х ) для всех х в X .
• Забор , частично упорядоченное множество , определенное с помощью переменной последовательности порядковых отношений < Ь > с < д ...
• Множество событий в специальной теории относительности и, в большинстве случаев ^[3] общая теория относительности , где в течение двух событий X и Y , X ≤ Y тогда и только тогда , когда Y в будущем светового конуса в X . Событие Y может быть каузально зависит только от X , если X ≤ Y .

Extrema [ править ]

Есть несколько понятий «наибольшего» и «наименьшего» элемента в позиционном множестве P , а именно:

• Наибольший элемент и наименьший элемент: элемент г в Р является наибольшим элементом , если для каждого элемента а в P ,  ≤  г . Элемент т в P является наименьшим элементом , если для каждого элемента а в P , в  ≥  м . У посета может быть только один наибольший или наименьший элемент.
• Максимальные элементы и минимальные элементы: элемент g в P является максимальным элементом, если нет такого элемента a в P , что a  >  g . Аналогично, элемент m в P является минимальным элементом, если в P нет такого элемента a , что a  <  m . Если ЧУМ имеет наибольший элемент, он должен быть единственным максимальным элементом, но в противном случае может быть более одного максимального элемента, и то же самое для наименьших элементов и минимальных элементов.
• Верхние и нижние границы : Для подмножества А из Р , элемент х в Р есть верхняя граница А , если  ≤  х , для каждого элемента а в A . В частности, й не должен быть в A , чтобы быть верхней границей A . Аналогичным образом , элемент х в Р является нижней гранью А , если  ≥  х , для каждого элемента а в A . Наибольший элемент P - это верхняя границаР сама по себе, и наименьший элемент является нижняя граница Р .

Например, рассмотрим положительные целые числа , упорядоченные по делимости: 1 - наименьший элемент, так как он делит все остальные элементы; с другой стороны, этот poset не имеет наибольшего элемента (хотя, если бы один включил в poset 0, кратное любому целому числу, это было бы наибольшим элементом; см. рисунок). В этом частично упорядоченном множестве нет даже максимальных элементов, так как любой g делит, например, 2 g , отличных от него, поэтому g не является максимальным. Если число 1 исключено, сохраняя при этом делимость упорядочением по элементам больше 1, то результирующий элемент poset не будет иметь наименьшего элемента, а будет иметь любое простое число.минимальный элемент для него. В этом наборе 60 - это верхняя граница (хотя и не наименьшая верхняя граница) подмножества {2, 3, 5, 10}, которое не имеет никакой нижней границы (поскольку 1 не входит в набор); с другой стороны, 2 - это нижняя граница подмножества степеней двойки, которая не имеет никакой верхней границы.

Заказы на декартово произведение частично упорядоченных множеств [ править ]

В порядке возрастания силы, т. Е. Уменьшения наборов пар, три из возможных частичных порядков на декартовом произведении двух частично упорядоченных наборов следующие (см. Рисунки):

• Лексикографическое порядок : ( , б ) ≤ ( с , d ) , если < с или ( = с и б ≤ d );
• заказ продукции : ( , б ) ≤ ( с , d ) , если ≤ C и B ≤ d ;
• рефлексивное замыкание на прямом произведении соответствующих строгих порядков: ( , б ) ≤ ( с , d ) , если ( < с и б < д ) или ( = с и Ь = д ).

Все три аналогично можно определить для декартова произведения более двух наборов.

Применительно к упорядоченным векторным пространствам над тем же полем результат в каждом случае также является упорядоченным векторным пространством.

См. Также заказы на декартово произведение полностью упорядоченных наборов .

Суммы частично упорядоченных множеств [ править ]

Другой способ объединения двух множеств - это порядковая сумма ^[4] (или линейная сумма ^[5] ), Z = X ⊕  Y , определенная на объединении базовых множеств X и Y в порядке a ≤ _Z b тогда и только тогда, когда :

• a , b ∈ X с a ≤ _X b , или
• a , b ∈ Y с a ≤ _Y b , или
• ∈ X и B ∈ Y .

Если два посета хорошо упорядочены , то их порядковая сумма тоже . ^[6] Операция порядкового суммирования - одна из двух операций, используемых для формирования последовательно-параллельных частичных порядков , и в этом контексте называется составлением серий. Другая операция, используемая для формирования этих порядков, несвязное объединение двух частично упорядоченных наборов (без отношения порядка между элементами одного набора и элементами другого набора), называется в этом контексте параллельной композицией.

Строгие и нестрогие частичные заказы [ править ]

Частичный порядок может называться нестрогим (или рефлексивным ) частичным порядком для выделения или контраста строгим частичным порядкам . Строгий (или иррефлексивный ) частичный порядок- также известный как строгий предпорядке - на это однородное бинарное отношение на том , что это иррефлексивное , транзитивны и асимметричное ; то есть он удовлетворяет следующим условиям для всех :${\ displaystyle P}$${\ Displaystyle \, <\,}$${\ displaystyle P}$${\ displaystyle a, b, c \ in P}$

1. Безрезультатность : не а < а ,
2. Транзитивность : если a < b и b < c, то a < c , и
3. Асимметрия : если a < b, то не b < a .

Вместе иррефлексивность и транзитивность подразумевают асимметрию ^[7], поэтому однородное отношение является строгим частичным порядком тогда и только тогда, когда оно транзитивно и иррефлексивно. Кроме того, асимметрия подразумевает иррефлексивность ^[7], поэтому однородное отношение является строгим частичным порядком тогда и только тогда, когда оно транзитивно и асимметрично. Другими словами, транзитивное отношение асимметрично тогда и только тогда, когда оно иррефлексивно.

По определению каждый строгий слабый порядок является строгим частичным порядком. Для действительных чисел обычное отношение « меньше чем» является строгим частичным порядком, и то же самое верно и для обычного отношения « больше чем» на${\ Displaystyle P: = \ mathbb {R},}$${\ Displaystyle \, <\,}$${\ Displaystyle \,> \,}$${\ displaystyle \ mathbb {R}.}$

Эквивалентность [ править ]

Строгие и нестрогие частичные заказы на множестве тесно связаны. Нестрогий частичный порядок может быть преобразован в строгий частичный порядок путем удаления всех взаимосвязей в форме, то есть строгий частичный порядок - это набор, где - диагональ, и обозначает вычитание набора . И наоборот, строгий частичный порядок on может быть преобразован в нестрогий частичный порядок путем присоединения всех отношений этой формы; то есть является нестрогим частичным порядком. Таким образом, если - нестрогий частичный порядок, то соответствующий строгий частичный порядок - это иррефлексивное ядро, задаваемое формулой${\ displaystyle P}$${\ Displaystyle \, \ Leq \,}$${\ displaystyle a \ leq a;}$${\ Displaystyle \, <\;: = \; \ Leq \; \ setminus \; \ Delta _ {P}}$${\displaystyle \Delta _{P}:=\{(p,p):p\in P\}}$${\displaystyle P\times P}$${\displaystyle \;\setminus \;}$${\displaystyle \,<\,}$${\displaystyle P}$${\displaystyle \,\leq \;:=\;<\;\cup \;\Delta _{P}}$${\displaystyle \,\leq \,}$${\displaystyle \,<\,}$

${\displaystyle a<b}$если и${\displaystyle a\leq b}$${\displaystyle a\neq b.}$

И наоборот, если является строгим частичным порядком, то соответствующий нестрогий частичный порядок является рефлексивным замыканием, задаваемым формулой:${\displaystyle \,<\,}$${\displaystyle \,\leq \,}$

${\displaystyle a\leq b}$если или${\displaystyle a<b}$${\displaystyle a=b.}$

Это причина использования обозначений ${\displaystyle \,\leq .}$

Используя строгий порядок отношение « будет покрыта путем » может быть эквивалентно перефразировать « но не для любого ».${\displaystyle \,<,}$${\displaystyle a}$${\displaystyle b}$${\displaystyle a<b,}$${\displaystyle a<c<b}$${\displaystyle c}$

Направленные ациклические графы [ править ]

Строгие частичные порядки более точно соответствуют ориентированным ациклическим графам (DAG). Если граф построен, принимая каждый элемент как узел, а каждый элемент - как ребро, то каждый строгий частичный порядок является DAG, а транзитивное закрытие DAG является как строгим частичным порядком, так и самим DAG. . Напротив, нестрогий частичный порядок будет иметь петли на каждом узле и, следовательно, не будет DAG.${\displaystyle P}$${\displaystyle \,\leq \,}$

Обратный и двойной порядок [ править ]

Обратное (или обратное) отношение частичного порядка ≤ является обратным к ≤. Обычно обозначается ≥, это отношение, которое удовлетворяет x  ≥  y тогда и только тогда, когда y  ≤  x . Обратное отношение частичного порядка является рефлексивным, транзитивным и антисимметричным и, следовательно, само является отношением частичного порядка. Порядок двойного частично упорядоченного множества является тот же набор с отношением частичного порядка заменена на обратную. Иррефлексивное отношение> к ≥, как <к ≤.

Любое из четырех отношений ≤, <, ≥ и> на данном множестве однозначно определяет остальные три.

В общем случае два элемента х и у частичного порядка может стоять в любом из четырех взаимоисключающих отношений друг к другу: либо х  <  у или х  =  у , или х  >  у или х и у не несравнимы (ни один из другога в-третьих, определение несравнимости здесь отличается от определения в слабом порядке ). Вполне упорядоченное множество один , что исключает эту четвертую возможность: все пары элементов сравнимы и мы тогда сказать , что трихотомия держит. В натуральных числах, целые числа , рациональные числа и действительные числа полностью упорядочены по своей алгебраической (знаковой) величине, тогда как комплексные числа - нет. Это не означает, что комплексные числа не могут быть полностью упорядочены; мы могли бы, например, упорядочить их лексикографически через x + i y  <  u + i v тогда и только тогда, когда x  <  u или ( x  =  u и y  <  v ), но это не упорядочение по величине в любом разумном смысле, поскольку оно дает 1 больше 100 я. Упорядочивание их по абсолютной величине дает предварительный порядок, в котором все пары сопоставимы, но это не частичный порядок, поскольку 1 и i имеют одинаковую абсолютную величину, но не равны, что нарушает антисимметрию.

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

Для двух частично упорядоченных множеств ( S , ≤) и ( T , ≼), ^[8] функция f : S → T называется сохраняющей порядок , или монотонной , или изотонной , если для всех x и y в S , x ≤ y влечет f ( x ) ≼ f ( y ). Если ( U , ≲) также является частично упорядоченным множеством, и оба f : S → T и g :T → U сохраняют порядок, их композиция g ∘ f  : S → U также сохраняет порядок. Функция F : S → T называется порядком-отражающим , если для всех х и у в S , F ( х ) ≼ е ( у ) влечет е ≤ у . Если f одновременно сохраняет и отражает порядок, то это называется упорядоченным вложением ( S, ≤) в ( T , ≼). В последнем случае f обязательно инъективно , поскольку f ( x ) = f ( y ) влечет x ≤ y и y ≤ x и, в свою очередь, x = y в соответствии с антисимметрией ≤. Если заказ-вложение между двумя Posets S и T существует, то говорят , что S может быть встроен в T . Если заказ-вложение F : S → T являетсябиективный , он называется изоморфизмом порядка , а частичные порядки ( S , ≤) и ( T , ≼) называются изоморфными . Изоморфные порядки имеют структурно похожие диаграммы Хассе (см. Рисунок справа). Можно показать, что если сохраняющие порядок отображения f : S → T и g : T → S существуют такие, что g ∘ f и f ∘ g порождают тождественную функцию на S и T соответственно, то Sи T изоморфны по порядку. ^[9]

Например, отображение f : ℕ → ℙ (ℕ) из набора натуральных чисел (упорядоченных по делимости) в набор степеней натуральных чисел (упорядоченных по включению множества) может быть определено путем преобразования каждого числа в набор его простых чисел. делители . Это сохраняет порядок: если x делит y , то каждый простой делитель x также является простым делителем y . Однако он не является ни инъективным (поскольку он отображает как 12, так и 6 в {2, 3}), ни отражением порядка (поскольку 12 не делит 6). Взамен взамен каждое число набору его простых делителей степени определяет отображение g: ℕ → ℙ (ℕ), который сохраняет порядок, отражает порядок и, следовательно, является вложением порядка. Это не изоморфизм порядка (так как он, например, не отображает какое-либо число в набор {4}), но его можно сделать так, ограничив его область значений до g (ℕ). На правом рисунке показано подмножество и его изоморфный образ при g . Построение такого изоморфизма порядка в набор степеней может быть обобщено на широкий класс частичных порядков, называемых дистрибутивными решетками , см. « Теорема Биркгофа о представлении ».

Количество частичных заказов [ править ]

Последовательность A001035 в OEIS дает количество частичных порядков для набора из n помеченных элементов:

Количество строгих частичных заказов такое же, как и количество частичных заказов.

Если подсчет производится только до изоморфизма, получается последовательность 1, 1, 2, 5, 16, 63, 318,… (последовательность A000112 в OEIS ).

Линейное расширение [ править ]

Частичный порядок ≤ ^* на множестве X является расширением другого частичного порядка ≤ на X при условии, что для всех элементов x и y из X , всякий раз, когда x ≤ y , также верно, что x  ≤ ^*  y . Линейное расширение является расширением , что также является линейной (т.е. всего) порядка. Классический пример: лексикографический порядок полностью упорядоченных множеств является линейным продолжением порядка их продуктов. Каждый частичный заказ может быть расширен до полного заказа ( принцип расширения заказа ). ^[10]

В информатике алгоритмы поиска линейных расширений частичных порядков (представленных как порядки достижимости ориентированных ациклических графов ) называются топологической сортировкой .

В теории категорий [ править ]

Каждый упорядоченный набор (и каждый предварительно упорядоченный набор ) можно рассматривать как категорию, в которой для объектов x и y существует не более одного морфизма от x к y . Более явно, пусть hom ( x , y ) = {( x , y )}, если x ≤ y (а в противном случае - пустое множество) и ( y , z ) ∘ ( x , y ) = ( x , z ). Такие категории иногда называют позетальными .

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

Частичные порядки в топологических пространствах [ править ]

Если P - частично упорядоченное множество, которому также была задана структура топологического пространства , то обычно предполагается, что это замкнутое подмножество пространства топологического произведения . При этом предположении отношения частичного порядка хорошо себя ведут в пределах в том смысле, что если , и , и для всех , то . ^[11]${\displaystyle \{(a,b):a\leq b\}}$ ${\displaystyle P\times P}$${\displaystyle a_{i}\to a}$${\displaystyle b_{i}\to b}$${\displaystyle i}$   ${\displaystyle a_{i}\leq b_{i}}$${\displaystyle a\leq b}$

Интервалы [ править ]

Интервал в посете P является подмножеством я из P со свойством , что для любых х и у в I и любой г в Р , если X ≤ Z ≤ у , то г также находится в I . (Это определение обобщает определение интервала для действительных чисел.)

Для получения более ≤ б , то отрезок [ , Ь ] есть множество элементов х , удовлетворяющих а ≤ х ≤ B (т.е. ≤ х и х ≤ б ). Он содержит как минимум элементы a и b .

Используя соответствующее строгое отношение «<», открытый интервал ( a , b ) представляет собой набор элементов x, удовлетворяющих a < x < b (то есть a < x и x < b ). Открытый интервал может быть пустым, даже если a < b . Например, открытый интервал (1, 2) для целых чисел пуст, поскольку нет таких целых I , что 1 < I <2 .

В полуинтервалах [ , б ) и ( , Ь ] определяются аналогично.

Иногда определения расширяются, чтобы разрешить a > b , и в этом случае интервал пуст.

Интервал I ограничен, если существуют такие элементы a и b из P , что I ⊆ [ a , b ] . Каждый интервал, который может быть представлен в обозначении интервалов, очевидно, ограничен, но обратное неверно. Например, пусть P = (0, 1) ∪ (1, 2) ∪ (2, 3) как подмножество действительных чисел . Подмножество (1, 2) является ограниченным интервалом, но у него нет точной или супремума в P, Поэтому он не может быть записан в интервале обозначений с использованием элементов P .

ЧУМ называется локально конечным, если конечен любой ограниченный интервал. Например, целые числа локально конечны при их естественном порядке. Лексикографический порядок на декартовом произведении ℕ × ℕ не является локально конечным, поскольку (1, 2) ≤ (1, 3) ≤ (1, 4) ≤ (1, 5) ≤ ... ≤ (2, 1) . Используя обозначение интервалов, свойство « a покрывается b » можно эквивалентно перефразировать как [ a , b ] = { a , b }.

Эту концепцию интервала в частичном порядке не следует путать с конкретным классом частичных порядков, известным как интервальные порядки .

См. Также [ править ]

Заметки [ править ]

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

• Дешпанде, Джаянт В. (1968). «О непрерывности частичного порядка» . Труды Американского математического общества . 19 (2): 383–386. DOI : 10.1090 / S0002-9939-1968-0236071-7 .
• Шмидт, Гюнтер (2010). Реляционная математика . Энциклопедия математики и ее приложений. 132 . Издательство Кембриджского университета. ISBN 978-0-521-76268-7.
• Бернд Шредер (11 мая 2016 г.). Упорядоченные множества: введение со связями от комбинаторики к топологии . Birkhäuser. ISBN 978-3-319-29788-0.
• Стэнли, Ричард П. (1997). Перечислительная комбинаторика 1 . Кембриджские исследования в области высшей математики. 49 . Издательство Кембриджского университета. ISBN 0-521-66351-2.

Внешние ссылки [ править ]

Викискладе есть медиафайлы, связанные с диаграммой Хассе .

• Последовательность OEIS A001035 (количество позиций с n помеченными элементами)
• Последовательность OEIS A000112 (количество частично упорядоченных наборов («наборов») с n непомеченными элементами.)