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

Транзитивные  бинарные отношения
Симметричный Антисимметричный Связаны Обоснованный Присоединяется Встречается Рефлексивный Нерефлексивный Асимметричный Также известный как: Итого, Semiconnex Антирефлексивный Отношение эквивалентности ✓ ✗ ✗ ✗ ✗ ✗ ✓ ✗ ✗ Предзаказ (Квазипорядок) ✗ ✗ ✗ ✗ ✗ ✗ ✓ ✗ ✗ Частичный заказ ✗ ✓ ✗ ✗ ✗ ✗ ✓ ✗ ✗ Всего предзаказ ✗ ✗ ✓ ✗ ✗ ✗ ✓ ✗ ✗ Общий заказ ✗ ✓ ✓ ✗ ✗ ✗ ✓ ✗ ✗ Предварительный заказ ✗ ✗ ✓ ✓ ✗ ✗ ✓ ✗ ✗ Хорошо-квазиупорядоченный ✗ ✗ ✗ ✓ ✗ ✗ ✓ ✗ ✗ Хороший порядок ✗ ✓ ✓ ✓ ✗ ✗ ✓ ✗ ✗ Решетка ✗ ✓ ✗ ✗ ✓ ✓ ✓ ✗ ✗ Соединение-полурешетка ✗ ✓ ✗ ✗ ✓ ✗ ✓ ✗ ✗ Встреча-полурешетка ✗ ✓ ✗ ✗ ✗ ✓ ✓ ✗ ✗ Строгий частичный заказ ✗ ✗ ✗ ✗ ✗ ✗ ✗ ✓ ✓ Строгий слабый порядок ✗ ✗ ✗ ✗ ✗ ✗ ✗ ✓ ✓ Строгий общий порядок ✗ ✗ ✓ ✗ ✗ ✗ ✗ ✓ ✓ Симметричный Антисимметричный Связаны Обоснованный Присоединяется Встречается Рефлексивный Нерефлексивный Асимметричный Определения: ${\displaystyle \scriptstyle {{\text{For all}}\,a,b\,{\text{and}}\,S\neq \varnothing :}}$ ${\displaystyle \scriptstyle {aRb\Rightarrow bRa}}$ ${\displaystyle \scriptstyle {aRb\,{\text{and}}\,bRa\Rightarrow a=b}}$ ${\displaystyle \scriptstyle {a\neq b\Rightarrow aRb\,{\text{or}}\,bRa}}$ ${\displaystyle \scriptstyle {\min S\,{\text{exists}}}}$ ${\displaystyle \scriptstyle {a\vee b\,{\text{exists}}}}$ ${\displaystyle \scriptstyle {a\wedge b\,{\text{exists}}}}$ ${\displaystyle \scriptstyle {aRa}}$ ${\displaystyle \scriptstyle {{\text{not}}\,aRa}}$ ${\displaystyle \scriptstyle {aRb\Rightarrow {\text{not}}\,bRa}}$
Все определения неявно требуют, чтобы однородное отношение было транзитивным : « ✓ » указывает, что свойство столбца требуется в определении строки. Например, определение отношения эквивалентности требует, чтобы оно было симметричным. Упомянутые здесь дополнительные свойства , что однородное отношение может удовлетворять.${\displaystyle R}$${\displaystyle \scriptstyle {{\text{For all}}\,a,b,c,{\text{ if }}aRb{\text{ and }}bRc{\text{ then }}aRc}.}$

Рис.1 Диаграмма Хассе из множества всех подмножеств из множества трехэлементного упорядочены по включению . Множества, соединенные восходящим путем, например и , сопоставимы, а например, и нет.${\displaystyle \{x,y,z\},}$${\displaystyle \emptyset }$${\displaystyle \{x,y\}}$${\displaystyle \{x\}}$${\displaystyle \{y\}}$

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

Неформальное определение

Частичный порядок определяет понятие сравнения. Два элемента х и у может стоять в любом из четырех взаимоисключающих отношений друг к другу: либо х  <  у или х  =  у , или х  >  у или х и у не несравнимо (ни один из трех других). Напротив, полностью упорядоченный набор следует трихотомии и исключает возможность несравнимости: все пары элементов сопоставимы.

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

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

Отношение частичного порядка

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

Нестрогий частичный заказ

Рефлексивный , слабый , ^[2] илинестрогий частичный порядок ^[3] - этооднородное отношение≤ надмножеством, которое являетсярефлексивным,антисимметричнымитранзитивным. То есть для всегоон должен удовлетворять:${\displaystyle P}$${\displaystyle a,b,c\in P,}$

1. рефлексивность :, т.е. каждый элемент связан с самим собой.${\displaystyle a\leq a}$
2. антисимметрия : если , т.е. никакие два различных элемента не предшествуют друг другу.${\displaystyle a\leq b{\text{ and }}b\leq a{\text{ then }}a=b}$
3. транзитивность : если .${\displaystyle a\leq b{\text{ and }}b\leq c{\text{ then }}a\leq c}$

Нестрогий частичный порядок также известен как антисимметричный предпорядок .

Строгий частичный заказ

Иррефлексивное , сильный , ^[2] илистрогий частичный порядок на- это однородное отношение <on,которое являетсяиррефлексивным,транзитивнымиасимметричным; то есть удовлетворяет следующим условиям для всех${\displaystyle P}$${\displaystyle P}$${\displaystyle a,b,c\in P:}$

1. Безрезультатность : нет , т.е. ни один элемент не связан с самим собой${\displaystyle a<a}$
2. Транзитивность : если${\displaystyle a<b{\text{ and }}b<c{\text{ then }}a<c,}$
3. Асимметрия : если нет .${\displaystyle a<b}$${\displaystyle b<a}$

Безрефлексивность и транзитивность вместе подразумевают асимметрию. Также асимметрия подразумевает иррефлексивность. Другими словами, транзитивное отношение асимметрично тогда и только тогда, когда оно иррефлексивно. ^[4] Таким образом, определение будет таким же, если оно не включает иррефлексивность или асимметрию (но не обе сразу).

Строгий частичный заказ также известен как строгий предварительный заказ .

Соответствие строгих и нестрогих отношений частичного порядка

Строгие и нестрогие частичные заказы на множестве тесно связаны. Нестрогий частичный порядок может быть преобразован в строгий частичный порядок, удаляя все отношения формы , то есть строгий частичный порядок является множеством , где этим отношение идентичности на и обозначает набор вычитания . И наоборот, строгий частичный порядок <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 P}$${\displaystyle \leq \;:=\;\Delta _{P}\;\cup \;<\;}$${\displaystyle \leq }$

$${\displaystyle a<b{\text{ if }}a\leq b{\text{ and }}a\neq b.}$$

${\displaystyle \leq }$

$${\displaystyle a\leq b{\text{ if }}a<b{\text{ or }}a=b.}$$

Двойные заказы

Двойной (или напротив ) из отношения частичного порядка определяется позволяя быть обратное отношение из , то есть тогда и только тогда . Двойственный к нестрогому частичному порядку является нестрогим частичным порядком ^[5], а двойственный к строгому частичному порядку является строгим частичным порядком. Дуальным к двойственному отношению является исходное отношение.${\displaystyle (P,R^{\text{op}})}$${\displaystyle (P,R)}$${\displaystyle R^{\text{op}}}$${\displaystyle R}$${\displaystyle xR^{\text{op}}y}$${\displaystyle yRx}$

Обозначение

Мы можем рассмотреть частично упорядоченное множество в качестве 3-кортежа , ^[6] или даже 5-кортежа , ^{[ править ]} , где и не являемся жесткими частичными отношениями порядка, и жесткие частичные отношения порядка, двойственным является и и являемся аналогично двойники друг друга.${\displaystyle (P,\leq ,<)}$${\displaystyle (P,\leq ,<,\geq ,>)}$${\displaystyle (P,\leq )}$${\displaystyle (P,\geq )}$${\displaystyle (P,<)}$${\displaystyle (P,>)}$${\displaystyle (P,\geq )}$${\displaystyle (P,\leq )}$${\displaystyle (P,<)}$${\displaystyle (P,>)}$

Любое из четырех отношений частичного порядка на данном наборе однозначно определяет остальные три. Следовательно, в качестве обозначений мы можем написать или и предположить, что другие отношения определены соответствующим образом. Чаще всего используется нестрогий частичный порядок . Некоторые авторы используют символы, отличные от таких, как ^[7] или ^[8], чтобы отличать частичные заказы от общих заказов.${\displaystyle \leq ,<,\geq ,{\text{ and }}>}$${\displaystyle (P,\leq )}$${\displaystyle (P,<)}$${\displaystyle \leq }$${\displaystyle \leq }$${\displaystyle \sqsubseteq }$${\displaystyle \preceq }$

Когда речь идет о частичных порядков, не следует принимать в качестве дополнения в . является обратным к иррефлексивному ядру , которое всегда является подмножеством дополнения , но равно дополнению тогда и только тогда , когда является полным порядком. ^[а]${\displaystyle \leq }$${\displaystyle >}$${\displaystyle >}$${\displaystyle \leq }$${\displaystyle \leq }$${\displaystyle >}$${\displaystyle \leq }$ ${\displaystyle \leq }$

Примеры

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

• В действительных числах , или вообще любой вполне упорядоченное множество, упорядочены по стандарту менее чем или равных отношению ≤, не является строгим частичным порядком.
• Для действительных чисел обычное отношение « меньше, чем» <является строгим частичным порядком, и то же самое верно и для обычного отношения « больше, чем» > на${\displaystyle P:=\mathbb {R} ,}$${\displaystyle \mathbb {R} .}$
• По определению каждый строгий слабый порядок является строгим частичным порядком.
• Множество подмножеств данного множества (его набор мощности ), упорядоченное по включению (см. Рис.1). Точно так же набор последовательностей, упорядоченных по подпоследовательности , и набор строк, упорядоченных по подстроке .
• Множество натуральных чисел с отношением делимости .
• Множество вершин ориентированного ациклического графа, упорядоченное по достижимости .
• Множество подпространств одного векторного пространства упорядочены по включению.
• Для частично упорядоченного множества Р , то пространство последовательностей , содержащее все последовательности элементов из Р , где последовательность последовательности предшествует Ь , если каждый элемент в течение предшествует соответствующий пункт в б . Формально тогда и только тогда, когда для всех ; то есть покомпонентный порядок .${\displaystyle \left(a_{n}\right)_{n\in \mathbb {N} }\leq \left(b_{n}\right)_{n\in \mathbb {N} }}$${\displaystyle a_{n}\leq b_{n}}$${\displaystyle n\in \mathbb {N} }$
• Для множества X и частично упорядоченного множества Р , тем функциональное пространство , содержащее все функции из X в Р , где Р ≤ г тогда и только тогда , когда F ( х ) ≤ г ( х ) для всех${\displaystyle x\in X.}$
• Забор , частично упорядоченное множество , определенное с помощью переменной последовательности порядковых отношений < Ь > с < д ...
• Множество событий в специальной теории относительности и, в большинстве случаев, ^[б] общая теория относительности , где в течение двух событий X и Y , X ≤ Y тогда и только тогда , когда Y в будущем светового конуса в X . Событие Y может быть каузально зависит только от X , если X ≤ Y .

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

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

Рис.4 Заказ продукции на${\displaystyle \mathbb {N} \times \mathbb {N} }$

Рис.5 Рефлексивное закрытие строгого прямого заказа продукта на элементах, охваченных (3,3) и покрывающих (3,3), выделены зеленым и красным соответственно.${\displaystyle \mathbb {N} \times \mathbb {N} .}$

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

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

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

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

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

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

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

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

Если два посета хорошо упорядочены , то их порядковая сумма тоже . ^[11]

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

Производные понятия

В примерах используется ЧУМ, состоящий из множества всех подмножеств трехэлементного множества, упорядоченных по включению множества (см. Рис.1). ${\displaystyle (P(\{x,y,z\}),\subseteq )}$${\displaystyle \{x,y,z\},}$

• Когда ≤ Ь , мы говорим , что это связано с б . Это не означает, что b также связано с a , потому что отношение не обязательно должно быть симметричным . Например, это связано с, но не наоборот. ${\displaystyle \{x\}}$${\displaystyle \{x,y\},}$
• Принимая во внимание элементы а , б частично упорядоченного множества Р , если ≤ б или б ≤ , то и б являются сопоставимыми . В остальном они несравнимы . Например, и сопоставимы, а пока и нет.${\displaystyle \{x\}}$${\displaystyle \{x,y,z\}}$${\displaystyle \{x\}}$${\displaystyle \{y\}}$
• Частичный порядок, при котором каждая пара элементов сопоставима, называется полным или линейным порядком . Например, натуральные числа в стандартном порядке.
• Подмножество чугуна, которое является полностью упорядоченным множеством, называется цепочкой . Например, это цепочка.${\displaystyle \{\{\,\},\{x\},\{x,y,z\}\}}$
• Подмножество чугуна, в котором никакие два различных элемента не сопоставимы, называется антицепью . Например, набор синглтонов ${\displaystyle \{\{x\},\{y\},\{z\}\}.}$
• Элемент a называется строго меньшим, чем элемент b , если a ≤ b и, например, строго меньше, чем${\displaystyle a\neq b.}$${\displaystyle \{x\}}$${\displaystyle \{x,y\}.}$
• Элемент a называется покрытым другим элементом b , обозначаемым как a ⋖ b (или a <: b ), если a строго меньше b и между ними не помещается третий элемент c ; формально: если и a ≤ b, и истинны, и a ≤ c ≤ b ложно для каждого c с использованием строгого порядка <, отношение a ⋖ b может быть эквивалентно перефразировано как « a <${\displaystyle a\neq b}$${\displaystyle a\neq c\neq b.}$b, но не a < b < c для любого c ". Например, покрывается, но не покрывается${\displaystyle \{x\}}$${\displaystyle \{x,z\},}$${\displaystyle \{x,y,z\}.}$

Extrema

В частности, есть несколько понятий «наибольший» и «наименьший» элементы :${\displaystyle P,}$

• Наибольший элемент и наименьший элемент: элемент является наибольшим элементом, если для каждого элемента Элемент является наименьшим элементом, если для каждого элемента в poset может быть только один наибольший или наименьший элемент. В нашем текущем примере набор является самым большим элементом и наименьшим.${\displaystyle g\in P}$${\displaystyle a\in P,a\leq g.}$${\displaystyle m\in P}$${\displaystyle a\in P,m\leq a.}$${\displaystyle \{x,y,z\}}$${\displaystyle \{\,\}}$
• Максимальные элементы и минимальные элементы: элемент является максимальным элементом, если нет такого элемента , что. Аналогично, элемент является минимальным элементом, если нет такого элемента , что если элемент poset имеет наибольший элемент, он должен быть единственным максимальным элементом, но в противном случае может быть более одного максимального элемента, и аналогично для наименьших элементов и минимальных элементов. В нашем запущенном примере и - это максимальный и минимальный элементы. Удалив их, мы получим 3 максимальных элемента и 3 минимальных элемента (см. Рис.6).${\displaystyle g\in P}$${\displaystyle a\in P}$${\displaystyle a>g.}$${\displaystyle m\in P}$${\displaystyle a\in P}$${\displaystyle a<m.}$${\displaystyle \{x,y,z\}}$${\displaystyle \{\,\}}$
• Верхние и нижние границы : Для подмножества А из Р , элемент х в Р есть верхняя граница А , если  ≤  х , для каждого элемента а в A . В частности, й не должен быть в A , чтобы быть верхней границей A . Аналогичным образом , элемент х в Р является нижней гранью А , если  ≥  х , для каждого элемента а в A . Наибольший элемент P - это верхняя границаР сама по себе, и наименьший элемент является нижняя граница Р . В нашем примере набор - это верхняя граница для набора элементов${\displaystyle \{x,y\}}$${\displaystyle \{\{x\},\{y\}\}.}$

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

Отображения между частично упорядоченными наборами

Рис.8 Сохраняющая порядок, но не отражающая порядок (поскольку f ( u ) ≼ f ( v ), но не u v) отображение.${\displaystyle \leq }$

Рис.9 Порядковый изоморфизм между делителями 120 (частично упорядоченными по делимости) и замкнутыми по делителям подмножествами {2, 3, 4, 5, 8 } (частично упорядоченными по включению множества)

Для двух частично упорядоченных множеств ( S , ≤) и ( T , ≼), ^[c] функция называется сохраняющей порядок , или монотонной , или изотонной , если для всех следует, что f ( x ) ≼ f ( y ). Если ( U , ≲) также частично упорядоченное множество, и оба , и это с сохранением порядка их композиция сохраняет порядок, тоже. Функция называется упорядоченно отражающей, если для всех f ( x ) ≼ f ( y${\displaystyle f:S\to T}$${\displaystyle x,y\in S,}$ ${\displaystyle x\leq y}$${\displaystyle f:S\to T}$${\displaystyle g:T\to U}$ ${\displaystyle g\circ f:S\to U}$${\displaystyle f:S\to T}$${\displaystyle x,y\in S,}$ ) следует, что If одновременно сохраняет и отражает порядок, то это называется упорядоченным вложением ( S , ≤) в ( T , ≼). В последнем случае, обязательно инъективны , так как предполагает , и в свою очередь в соответствии с антисимметричности Если заказ-вложение между двумя ч.у.м. S и Т существует, то говорят , что S может быть встроен в T . Если заказ-вложение является взаимно однозначным , оно называется порядковым изоморфизмом , а частичные порядки ( S${\displaystyle x\leq y.}$${\displaystyle f}$${\displaystyle f}$${\displaystyle f(x)=f(y)}$${\displaystyle x\leq y{\text{ and }}y\leq x}$${\displaystyle x=y}$${\displaystyle \leq .}$${\displaystyle f:S\to T}$, ≤) и ( T , ≼) называются изоморфными . Изоморфные порядки имеют структурно похожие диаграммы Хассе (см. Рис.8). Можно показать, что если сохраняющие порядок отображения и существуют такие, что и дает тождественную функцию на S и T соответственно, то S и T изоморфны по порядку. ^[12]${\displaystyle f:S\to T}$${\displaystyle g:T\to U}$${\displaystyle g\circ f}$${\displaystyle f\circ g}$

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

Количество частичных заказов

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

Количество n -элементных бинарных отношений разных типов

Элементы	Любой	Переходный	Рефлексивный	Предзаказ	Частичный заказ	Всего предзаказ	Общий заказ	Отношение эквивалентности
0	1	1	1	1	1	1	1	1
1	2	2	1	1	1	1	1	1
2	16	13	4	4	3	3	2	2
3	512	171	64	29	19	13	6	5
4	65 536	3,994	4096	355	219	75	24	15
п	2 п 2		2 п 2 - п			${\textstyle \sum _{k=0}^{n}k!}$S ( п , к )	п !	${\textstyle \sum _{k=0}^{n}}$S ( п , к )
OEIS	A002416	A006905	A053763	A000798	A001035	A000670	A000142	A000110

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

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

Линейное расширение

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

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

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

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

В теории категорий

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

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

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

Если это частично упорядоченное множество, которому также была задана структура топологического пространства , то принято считать, что это замкнутое подмножество пространства топологического произведения. При этом предположении отношения частичного порядка хорошо себя ведут в пределах в том смысле, что если и для всех тогда ^[14]${\displaystyle P}$${\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 ограничен, если существуют такие элементы , что I ⊆ [ a , b ] . Каждый интервал, который может быть представлен в обозначении интервалов, очевидно, ограничен, но обратное неверно. Например, пусть P = (0, 1) ∪ (1, 2) ∪ (2, 3) как подмножество действительных чисел . Подмножество (1, 2) является ограниченным интервалом, но это не имеет никакого инфимуму или супремума в P , поэтому он не может быть записан в интервале обозначений с использованием элементов P .${\displaystyle a,b\in P}$

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

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

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

Примечания

Цитаты

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

• Дэйви, BA; Пристли, HA (2002). Введение в решетки и порядок (2-е изд.). Нью-Йорк: Издательство Кембриджского университета. ISBN 978-0-521-78451-1.
• Дешпанде, Джаянт В. (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 непомеченными элементами.)