Частично заказанный комплект - Partially ordered set

Транзитивные бинарные отношения

	Симметричный	Антисимметричный	Связаны	Обоснованный	Присоединяется	Встречается	Рефлексивный	Нерефлексивный	Асимметричный
Также известный как:			Итого, Semiconnex					Антирефлексивный
Отношение эквивалентности	Y	✗	✗	✗	✗	✗	Y	✗	✗
Предзаказ (Квазипорядок)	✗	✗	✗	✗	✗	✗	Y	✗	✗
Частичный заказ	✗	Y	✗	✗	✗	✗	Y	✗	✗
Всего предзаказ	✗	✗	Y	✗	✗	✗	Y	✗	✗
Общий заказ	✗	Y	Y	✗	✗	✗	Y	✗	✗
Предварительный заказ	✗	✗	Y	Y	✗	✗	Y	✗	✗
Хорошо-квазиупорядоченный	✗	✗	✗	Y	✗	✗	Y	✗	✗
Хороший порядок	✗	Y	Y	Y	✗	✗	Y	✗	✗
Решетка	✗	Y	✗	✗	Y	Y	Y	✗	✗
Соединение-полурешетка	✗	Y	✗	✗	Y	✗	Y	✗	✗
Встреча-полурешетка	✗	Y	✗	✗	✗	Y	Y	✗	✗


Строгий частичный заказ	✗	✗	✗	✗	✗	✗	✗	Y	Y
Строгий слабый порядок	✗	✗	✗	✗	✗	✗	✗	Y	Y
Строгий общий порядок	✗	✗	Y	✗	✗	✗	✗	Y	Y
	Симметричный	Антисимметричный	Связаны	Обоснованный	Присоединяется	Встречается	Рефлексивный	Нерефлексивный	Асимметричный
Определения: ${\ displaystyle \ scriptstyle {{\ text {Для всех}} \, 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 {или}} \, bRa}}$	${\ displaystyle \ scriptstyle {\ min S \, {\ text {exists}}}}$	${\ displaystyle \ scriptstyle {a \ vee b \, {\ text {exists}}}}$	${\ Displaystyle \ scriptstyle {а \ клин б \, {\ текст {существует}}}}$	${\ displaystyle \ scriptstyle {aRa}}$	${\ displaystyle \ scriptstyle {{\ text {not}} \, aRa}}$	${\ displaystyle \ scriptstyle {aRb \ Rightarrow {\ text {not}} \, bRa}}$

Все определения неявно требуют, чтобы однородное отношение было транзитивным : " " указывает, что свойство столбца требуется по определению термина строки (в самом левом углу). Например, определение отношения эквивалентности требует, чтобы оно было симметричным. Упомянутые здесь дополнительные свойства , что однородное отношение может удовлетворять.

{\ displaystyle R}

{\ displaystyle \ scriptstyle {{\ text {Для всех}} \, a, b, c, {\ text {if}} aRb {\ text {and}} bRc {\ text {then}} aRc}.}

Рис.1 Диаграмма Хассе из множества всех подмножеств из множества трехэлементного упорядочены по включению . Множества, соединенные восходящим путем, например, и , сопоставимы, а например, и нет.

{\ Displaystyle \ {х, у, г \},}

{\ displaystyle \ emptyset}

{\ Displaystyle \ {х, у \}}

{\ Displaystyle \ {х \}}

{\ Displaystyle \ {у \}}

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Рис.2 Коммутативная диаграмма о связи между рефлексивным замыканием ( cls ), иррефлексивным ядром ( ker ) и обратным отношением ( cnv ) на примере отношения ( изображена диаграмма Хассе ).

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

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

Двойной (или напротив ) из отношения частичного порядка определяется позволяя быть

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

{\ displaystyle (P, R ^ {\ text {op}})}

{\ displaystyle (P, R)}

{\ displaystyle R ^ {\ text {op}}}

{\ displaystyle R}

{\ displaystyle xR ^ {\ text {op}} y}

{\ displaystyle yRx}

Обозначение

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

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

Когда речь идет о частичных порядков, не следует принимать в качестве

дополнения в . является обратным к иррефлексивному ядру , которое всегда является подмножеством дополнения , но равно дополнению тогда и только тогда , когда является полным порядком.

{\ 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 п \ в \ mathbb {N}}

Для множества X и частично упорядоченного множества Р , тем функциональное пространство , содержащее все функции из X в Р , где Р ≤ г тогда и только тогда , когда F ( х ) ≤ г ( х ) для всех

{\ displaystyle x \ in X.}

Забор , частично упорядоченное множество , определенное с помощью переменной последовательности порядковых отношений <

Ь > с < д ...

Множество событий в специальной теории относительности и, в большинстве случаев, общая теория относительности , где в течение двух событий X и Y , X ≤ Y тогда и только тогда , когда Y в будущем светового конуса в X . Событие Y может быть каузально зависит только от X , если X ≤ Y .

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

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

Рис.3 Лексикографический порядок на

{\ Displaystyle \ mathbb {N} \ times \ mathbb {N}}

Рис.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 ) , если ( < с и б < д ) или ( = с и Ь = д ).

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

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

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

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

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

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

Если два посета хорошо упорядочены , то их порядковая сумма

тоже .

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

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

В примерах используется ЧУМ, состоящий из

множества всех подмножеств трехэлементного множества, упорядоченных по включению множества (см. Рис. 1).

{\ Displaystyle ({\ mathcal {P}} (\ {х, y, z \}), \ substeq)}

{\ Displaystyle \ {х, у, г \},}

имеет отношение к Ь когда это ≤

б . Это не означает, что b также связано с a , потому что отношение не обязательно должно быть симметричным . Например, это связано с, но не наоборот.

{\ Displaystyle \ {х \}}

{\ Displaystyle \ {х, у \},}

и б являются сопоставимыми , если ≤

б или б ≤ . В остальном они несравнимы . Например, и сопоставимы, а пока и нет.

{\ Displaystyle \ {х \}}

{\ Displaystyle \ {х, у, г \}}

{\ Displaystyle \ {х \}}

{\ Displaystyle \ {у \}}

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

Цепь представляет собой подмножество посета , который представляет собой упорядоченное множество. Например, это цепочка.

{\ Displaystyle \ {\ {\, \}, \ {х \}, \ {х, у, г \} \}}

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

{\ displaystyle \ {\ {x \}, \ {y \}, \ {z \} \}.}

Элемент a называется строго меньшим, чем элемент b , если a ≤ b и, например, строго меньше, чем

{\ displaystyle a \ neq b.}

{\ Displaystyle \ {х \}}

{\ displaystyle \ {x, y \}.}

Элемент a называется покрытым другим элементом b , записываемым как a b (или a <: b ), если a строго меньше, чем b, и между ними не помещается третий элемент c ; формально: если и a ≤ b, и истинны, и

a ≤ c ≤ b ложно для каждого c с использованием строгого порядка <, отношение a ⋖ b может быть эквивалентно перефразировано как « a < b, но не a < c < b для любого c ". Например, покрывается, но не покрывается

{\ displaystyle a \ neq b}

{\ displaystyle a \ neq c \ neq b.}

{\ Displaystyle \ {х \}}

{\ Displaystyle \ {х, г \},}

{\ displaystyle \ {x, y, z \}.}

Extrema

Рис.6 Рисунок выше с удаленными наибольшим и наименьшим элементами. В этом сокращенном ЧУМе верхний ряд элементов - это все максимальные элементы, а нижний ряд - все минимальные элементы, но нет ни наибольшего, ни наименьшего элемента.

В частности, есть несколько понятий «наибольший» и «наименьший» элементы : ${\ 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 \ {х, у, г \}}

{\ 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 \ {х, у, г \}}

{\ Displaystyle \ {\, \}}

Верхние и нижние границы : Для подмножества А из Р , элемент х в Р есть верхняя граница А , если ≤

х , для каждого элемента а в A . В частности, й не должен быть в A , чтобы быть верхней границей A . Аналогичным образом , элемент х в Р является нижней гранью А , если ≥ х , для каждого элемента а в A . Наибольший элемент из Р представляет собой верхнюю грань Р самого, и наименьший элемент является нижняя граница Р . В нашем примере набор - это верхняя граница для набора элементов

{\ Displaystyle \ {х, у \}}

{\ Displaystyle \ {\ {х \}, \ {у \} \}.}

Рис.7 неотрицательные целые числа, упорядоченных по делимости

В качестве другого примера рассмотрим положительные целые числа , упорядоченные по делимости: 1 - наименьший элемент, так как он делит все остальные элементы; с другой стороны, у этого poset нет наибольшего элемента (хотя, если бы один включил 0 в poset, который кратен любому целому числу, это был бы наибольший элемент; см. Рис.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 , ≼) функция называется

сохраняющей порядок , или монотонной , или изотонной , если для всех следует, что f ( x ) ≼ f ( y ). Если ( U , ≲) также частично упорядоченное множество, и оба , и это с сохранением порядка их композиция сохраняет порядок, тоже. Функция называется отражающей порядок, если для всех f ( x ) ≼ f ( y ) подразумевает, что If одновременно сохраняет порядок и отражает порядок, то она называется упорядоченным вложением ( S , ≤) в ( T , ≼ ). В последнем случае, обязательно инъективны , так как предполагает , и в свою очередь в соответствии с антисимметричности Если заказ-вложение между двумя ч.у.м. S и Т существует, то говорят , что S может быть встроен в T . Если заказ-вложение является взаимно однозначным , оно называется порядковым изоморфизмом , а частичные порядки ( S , ≤) и ( Т , ≼) называются изоморфными . Изоморфные порядки имеют структурно похожие диаграммы Хассе (см. Рис.8). Можно показать, что если сохраняющие порядок отображения и существуют такие, что и дает тождественную функцию на S и T соответственно, то S и T изоморфны по порядку.

{\ displaystyle f: S \ to T}

{\ Displaystyle х, у \ в 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 х, у \ в S,}

{\ displaystyle x \ leq y.}

{\ displaystyle f}

{\ displaystyle f}

{\ Displaystyle е (х) = е (у)}

{\ displaystyle x \ leq y {\ text {and}} y \ leq x}

{\ displaystyle x = y}

{\ displaystyle \ leq.}

{\ displaystyle f: S \ to T}

{\ displaystyle f: S \ to T}

{\ displaystyle g: T \ to U}

{\ displaystyle g \ circ f}

{\ displaystyle f \ circ g}

Например, отображение набора натуральных чисел (упорядоченных по делимости) в

набор степеней натуральных чисел (упорядоченных по включению множества) может быть определено путем преобразования каждого числа в набор его простых делителей . Он сохраняет порядок: если делит, то каждый простой делитель числа также является простым делителем числа. Однако он не является ни инъективным (поскольку он отображает как 12, так и 6 ), ни отражающим порядок (поскольку 12 не делит 6). Вместо этого взятие каждого числа в набор его простых делителей мощности определяет отображение , которое сохраняет порядок, отражает порядок и, следовательно, является вложением порядка. Это не изоморфизм порядка (так как он, например, не отображает какое-либо число в набор ), но его можно сделать так, ограничив его область значений до Фиг.9 показывает подмножество и его изоморфный образ в соответствии с построением такой изоморфизм порядка в набор степеней может быть обобщен на широкий класс частичных порядков, называемых дистрибутивными решетками , см. « Теорема Биркгофа о представлении ».

{\ 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 \}}

{\ 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 ^{п ² - п}			${\ textstyle \ sum _ {k = 0} ^ {n} k!}$	п !	${\ textstyle \ сумма _ {к = 0} ^ {п}}$
OEIS	A002416	A006905	A053763	A000798	A001035	A000670	A000142	A000110

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

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

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

Частичный порядок на множестве является

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

{\ Displaystyle \ leq ^ {*}}

{\ displaystyle X}

{\ displaystyle \ leq}

{\ displaystyle X}

{\ displaystyle x, y \ in X,}

{\ displaystyle x \ leq y,}

{\ Displaystyle х \ leq ^ {*} у.}

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

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

Строгие частичные порядки напрямую соответствуют ориентированным ациклическим графам (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. Наконец, каждая подкатегория чугуна изоморфизм-замкнута .

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

Если это частично упорядоченное множество, которому также была задана структура

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

{\ displaystyle P}

{\ Displaystyle \ {(а, Ь): а \ 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

\subseteq

[

a

,

b

]

. Каждый интервал, который может быть представлен в обозначении интервалов, очевидно, ограничен, но обратное неверно. Например, пусть

P

=

(0, 1)

\cup

(1, 2)

\cup

(2, 3)

как подмножество действительных чисел . Подмножество

(1, 2)

является ограниченным интервалом, но это не имеет никакого инфимуму или супремума в P , поэтому он не может быть записан в интервале обозначений с использованием элементов P .

{\ displaystyle a, b \ in P}

ЧУМ называется локально конечным, если

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

(1, 2) \leq (1, 3) \leq (1, 4) \leq (1, 5) \leq ... \leq (2, 1)

. Используя обозначение интервалов, свойство « a покрывается b » можно эквивалентно перефразировать как

{\ Displaystyle \ mathbb {N} \ times \ mathbb {N}}

{\ displaystyle [a, b] = \ {a, b \}.}

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

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

Антиматроид , формализация порядков на множестве, которая позволяет использовать более общие семейства порядков, чем посеты.
Причинная совокупность , подход к квантовой гравитации на основе позета
График сопоставимости
Полный частичный заказ
Направленный набор - набор с предварительным порядком, в котором любые два элемента всегда меньше или равны некоторому третьему элементу.
Градуированный посет
Алгебра инцидентности
Решетка - абстрактная структура, изучаемая в математических дисциплинах теории порядка и абстрактной алгебры.
Локально конечный ЧУМ
Функция Мёбиуса на позах
Вложенная коллекция наборов
Многогранник порядка
Заказанное поле
Заказанная группа
Упорядоченное векторное пространство
Топология Poset , своего рода топологическое пространство, которое может быть определено из любого poset
Непрерывность Скотта - непрерывность функции между двумя частичными порядками.
Полурешетка
Полупорядок
Стохастическое доминирование
Строгий слабый порядок - строгий частичный порядок «<», в котором отношение «ни a < b, ни b < a » не является транзитивным.
Общий заказ - заказ, все элементы которого сопоставимы.
Дерево - Структура данных включения набора
Лемма Цорна - Математическое предложение, эквивалентное выбранной аксиоме

Примечания

Цитаты

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

Дэйви, 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.

Languages

In other projects