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

Математическое множество с упорядочением

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

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

Формально частичный порядок — это однородное бинарное отношение , которое является рефлексивным , антисимметричным и транзитивным . Частично упорядоченный набор ( сокращенно ЧУМ) — это упорядоченная пара, состоящая из набора (называемого базовым набором ) и частичного порядка на . Когда значение ясно из контекста и нет двусмысленности относительно частичного порядка, само множество иногда называют ЧУМ. ${\displaystyle P=(X,\leq )}$ ${\displaystyle X}$ ${\displaystyle P}$ ${\displaystyle \leq }$ ${\displaystyle X}$ ${\displaystyle X}$

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

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

Частичные заказы

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

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

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

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

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

1. Иррефлексивность : , т.е. ни один элемент не связан сам с собой (также называется антирефлексивностью). ${\displaystyle \neg \left(a<a\right)}$
2. Асимметрия : если да, то нет . ${\displaystyle a<b}$ ${\displaystyle b<a}$
3. Транзитивность : если и то . ${\displaystyle a<b}$ ${\displaystyle b<c}$ ${\displaystyle a<c}$

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

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

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

Рис. 2 Коммутативная диаграмма о связях между строгими/нестрогими отношениями и их дуальными отношениями посредством операций рефлексивного замыкания ( cls ), иррефлексивного ядра ( ker ) и обратного отношения ( cnv ). Каждое отношение изображается своей логической матрицей для частично упорядоченного множества, диаграмма Хассе которого изображена в центре. Например, строка 3, столбец 4 нижней левой матрицы пусты. ${\displaystyle 3\not \leq 4}$

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

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

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

Обозначение

При наличии множества и отношения частичного порядка, обычно нестрогого частичного порядка , мы можем однозначно расширить нашу нотацию, чтобы определить четыре отношения частичного порядка и , где — отношение нестрогого частичного порядка на , — связанное отношение строгого частичного порядка на ( иррефлексивное ядро ​​) , — двойственное к , а — двойственное к . Строго говоря, термин частично упорядоченный набор относится к множеству со всеми этими отношениями, определенными соответствующим образом. Но на практике нужно рассматривать только одно отношение, или , или, в редких случаях, нестрогие и строгие отношения вместе, . ^[5] ${\displaystyle P}$ ${\displaystyle \leq }$ ${\displaystyle \leq ,}$ ${\displaystyle <,}$ ${\displaystyle \geq ,}$ ${\displaystyle >}$ ${\displaystyle \leq }$ ${\displaystyle P}$ ${\displaystyle <}$ ${\displaystyle P}$ ${\displaystyle \leq }$ ${\displaystyle \geq }$ ${\displaystyle \leq }$ ${\displaystyle >}$ ${\displaystyle <}$ ${\displaystyle (P,\leq )}$ ${\displaystyle (P,<)}$ ${\displaystyle (P,\leq ,<)}$

Термин упорядоченный набор иногда используется как сокращение для частично упорядоченного набора , если из контекста ясно, что никакой другой вид порядка не подразумевается. В частности, полностью упорядоченные наборы также могут называться «упорядоченными наборами», особенно в областях, где эти структуры более распространены, чем частично упорядоченные множества. Некоторые авторы используют другие символы, чем, например, ^[6] или ^[7], чтобы отличать частичные порядки от полных порядков. ${\displaystyle \leq }$ ${\displaystyle \sqsubseteq }$ ${\displaystyle \preceq }$

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

Альтернативные определения

Другой способ определения частичного порядка, найденный в информатике , — это понятие сравнения . В частности, учитывая, как определено ранее, можно заметить, что два элемента x и y могут находиться в любом из четырех взаимоисключающих отношений друг к другу: либо x < y , либо x = y , либо x > y , либо x и y несравнимы . Это можно представить функцией , которая возвращает один из четырех кодов, когда даны два элемента. ^{[8] [9]} Это определение эквивалентно частичному порядку на сетоиде , где равенство считается определенным отношением эквивалентности, а не равенством множеств. ^[10] ${\displaystyle \leq ,<,\geq ,{\text{ and }}>}$ ${\displaystyle {\text{compare}}:P\times P\to \{<,>,=,\vert \}}$

Уоллис определяет более общее понятие отношения частичного порядка как любое однородное отношение , которое является транзитивным и антисимметричным . Это включает в себя как рефлексивные, так и нерефлексивные частичные порядки как подтипы. ^[1]

Конечный частично упорядоченный набор может быть визуализирован с помощью его диаграммы Хассе . ^[11] В частности, принимая отношение строгого частичного порядка , можно построить направленный ациклический граф (DAG), взяв каждый элемент из за узел, а каждый элемент из за ребро. Транзитивное сокращение этого DAG ^[b] тогда является диаграммой Хассе. Аналогично этот процесс может быть обращен для построения строгих частичных порядков из определенных DAG. Напротив, граф, связанный с нестрогим частичным порядком, имеет самопетли в каждом узле и, следовательно, не является DAG; когда говорят, что нестрогий порядок изображен диаграммой Хассе, на самом деле показан соответствующий строгий порядок. ${\displaystyle (P,<)}$ ${\displaystyle P}$ ${\displaystyle <}$

Примеры

Рис. 3 График делимости чисел от 1 до 4. Этот набор частично, но не полностью, упорядочен, поскольку существует связь между 1 и каждым другим числом, но нет связи между 2 и 3 или 3 и 4.

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

• Действительные числа или вообще любой полностью упорядоченный набор, упорядоченный стандартным отношением «меньше или равно» ≤, является частичным порядком.
• На действительных числах обычное отношение «меньше, чем » < является строгим частичным порядком. То же самое относится и к обычному отношению «больше, чем » > на . ${\displaystyle \mathbb {R} }$ ${\displaystyle \mathbb {R} }$
• По определению, каждый строгий слабый порядок является строгим частичным порядком.
• Множество подмножеств данного множества (его мощности множества ), упорядоченное по включению (см. рис. 1). Аналогично, множество последовательностей, упорядоченное по подпоследовательности , и множество строк, упорядоченное по подстроке .
• Множество натуральных чисел , снабженное отношением делимости . (см. рис. 3 и рис. 6)
• Множество вершин ориентированного ациклического графа, упорядоченное по достижимости .
• Множество подпространств векторного пространства, упорядоченное по включению.
• Для частично упорядоченного множества P , пространство последовательностей , содержащее все последовательности элементов из P , где последовательность a предшествует последовательности b , если каждый элемент в a предшествует соответствующему элементу в b . Формально, тогда и только тогда, когда для всех ; то есть покомпонентный порядок . ${\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 и частично упорядоченного множества P функциональное пространство , содержащее все функции из X в P , где f ≤ g тогда и только тогда, когда f ( x ) ≤ g ( x ) для всех ${\displaystyle x\in X.}$
• Забор , частично упорядоченное множество, определяемое чередующейся последовательностью отношений порядка a < b > c < d ...
• Множество событий в специальной теории относительности и, в большинстве случаев, ^[c] общей теории относительности , где для двух событий X и Y , X ≤ Y тогда и только тогда, когда Y находится в будущем световом конусе X. Событие Y может быть причинно затронуто X , только если X ≤ Y.

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

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

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

• лексикографический порядок :   ( a , b ) ≤ ( c , d ), если a < c или ( a = c и b ≤ d );
• порядок произведения : ( a , b ) ≤ ( c , d ), если a ≤ c и b ≤ d ;
• рефлексивное замыкание прямого произведения соответствующих строгих порядков:   ( a , b ) ≤ ( c , d ) , если ( a < c и b < d ) или ( a = c и b = d ).

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

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

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

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

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

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

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

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

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

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

• a связано с b, когда a ≤ b . Это не означает, что b также связано с a , поскольку отношение не обязательно должно быть симметричным . Например, связано с, но не наоборот. ${\displaystyle \{x\}}$ ${\displaystyle \{x,y\},}$
• a и b сравнимы , если a ≤ b или b ≤ a . В противном случае они несравнимы . Например, и сравнимы, а и — нет. ${\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 < b , но не a < c < b для любого c ». Например, покрывается но не покрывается ${\displaystyle a\neq b}$ ${\displaystyle a\neq c\neq b.}$ ${\displaystyle \{x\}}$ ${\displaystyle \{x,z\},}$ ${\displaystyle \{x,y,z\}.}$

Экстремумы

Рис. 5 Рисунок выше с удаленными наибольшими и наименьшими элементами. В этом сокращенном посете верхний ряд элементов — все максимальные элементы, а нижний ряд — все минимальные элементы, но нет наибольшего и наименьшего элемента.

В частично упорядоченном множестве существует несколько понятий «наибольшего» и «наименьшего» элемента, а именно: ${\displaystyle P,}$

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

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

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

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

Для двух частично упорядоченных множеств ( S , ≤) и ( T , ≼) функция называется сохраняющей порядок , или монотонной , или изотонной , если для всех влечет f ( x ) ≼ f ( y ) . Если ( U , ≲) также является частично упорядоченным множеством, и оба и сохраняют порядок, их композиция также сохраняет порядок. Функция называется отражающей порядок , если для всех f ( x ) ≼ f ( y ) влечет Если f является как сохраняющей порядок, так и отражающей порядок, то она называется вложением порядка ( S , ≤) в ( T , ≼) . В последнем случае f обязательно инъективна , поскольку влечет и , в свою очередь, согласно антисимметрии Если существует вложение порядка между двумя частично упорядоченными множествами S и T , говорят, что S может быть вложено в T . Если вложение порядка является биективным , оно называется изоморфизмом порядка , а частичные порядки ( S , ≤) и ( T , ≼) называются изоморфными . Изоморфные порядки имеют структурно подобные диаграммы Хассе (см. рис. 7a). Можно показать, что если существуют сохраняющие порядок отображения и такие, что и дает функцию тождества на S и T , соответственно, то S и T являются изоморфными порядком. ^[15] ${\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,}$ ${\displaystyle x\leq y.}$ ${\displaystyle f(x)=f(y)}$ ${\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}$

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

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

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

Обратите внимание, что S ( n , k ) относится к числам Стирлинга второго рода .

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

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

Подгруппы

ЧУМ называется подмножеством другого ЧУМ , если является подмножеством и является подмножеством . Последнее условие эквивалентно требованию, что для любого и в (и, следовательно, также в ), если , то . ${\displaystyle P^{*}=(X^{*},\leq ^{*})}$ ${\displaystyle P=(X,\leq )}$ ${\displaystyle X^{*}}$ ${\displaystyle X}$ ${\displaystyle \leq ^{*}}$ ${\displaystyle \leq }$ ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle X^{*}}$ ${\displaystyle X}$ ${\displaystyle x\leq ^{*}y}$ ${\displaystyle x\leq y}$

Если является подмножеством и, кроме того, для всех и в , всякий раз, когда мы также имеем , то мы называем подмножество , индуцированное , и пишем . ${\displaystyle P^{*}}$ ${\displaystyle P}$ ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle X^{*}}$ ${\displaystyle x\leq y}$ ${\displaystyle x\leq ^{*}y}$ ${\displaystyle P^{*}}$ ${\displaystyle P}$ ${\displaystyle X^{*}}$ ${\displaystyle P^{*}=P[X^{*}]}$

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

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

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

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

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

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

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

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

Интервалы

Выпуклое множество в частично упорядоченном множестве P — это подмножество I множества P , обладающее тем свойством, что для любых x и y из I и любого z из P , если x ≤ z ≤ y , то z также принадлежит I. Это определение обобщает определение интервалов действительных чисел . Когда возможна путаница с выпуклыми множествами геометрии , вместо «выпуклый» используют порядково-выпуклый .

Выпуклая подрешетка решетки L — это подрешетка решетки L , которая также является выпуклым множеством решетки L. Каждая непустая выпуклая подрешетка может быть единственным образом представлена ​​как пересечение фильтра и идеала решетки L.

Интервал в частично упорядоченном множестве P — это подмножество, которое можно определить с помощью интервальной нотации:

• Для a ≤ b замкнутый интервал [ a , b ] — это множество элементов x, удовлетворяющих a ≤ x ≤ b (то есть a ≤ x и x ≤ b ). Он содержит по крайней мере элементы a и b .
• Используя соответствующее строгое отношение "<", открытый интервал ( a , b ) — это множество элементов x, удовлетворяющих a < x < b (т.е. a < x и x < b ). Открытый интервал может быть пустым, даже если a < b . Например, открытый интервал (0, 1) для целых чисел пуст, поскольку не существует целого числа x, такого что 0 < x < 1 .
• Аналогично определяются полуинтервалы [ a , b ) и ( a , b ] .

Если a ≤ b не выполняется, все эти интервалы пусты. Каждый интервал является выпуклым множеством, но обратное не выполняется; например, в частично упорядоченном множестве делителей числа 120, упорядоченном по делимости (см. рис. 7b), множество {1, 2, 4, 5, 8} является выпуклым, но не интервалом.

Интервал 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\}.}$

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

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

• Антиматроид , формализация упорядочений на множестве, которая допускает более общие семейства упорядочений, чем частично упорядоченные множества
• Причинно-следственный набор , подход к квантовой гравитации на основе частично упорядоченных множеств
• Граф сравнимости  – граф, связывающий пары сравнимых элементов в частичном порядке.
• Полный частичный порядок  – термин, используемый в математической теории порядка.Pages displaying wikidata descriptions as a fallback
• Направленный набор  – Математическое упорядочение с верхними границами
• Градуированное частично упорядоченное множество  – частично упорядоченное множество, снабженное ранговой функциейPages displaying wikidata descriptions as a fallback
• Алгебра инцидентности  – ассоциативная алгебра, используемая в комбинаторике, разделе математики.
• Решетка  – множество, пары которых имеют минимумы и максимумы.
• Локально конечный посет  – МатематикаPages displaying wikidata descriptions as a fallbackPages displaying short descriptions with no spaces
• Функция Мёбиуса на частично упорядоченных множествах  – Ассоциативная алгебра, используемая в комбинаторике, разделе математики
• Вложенная коллекция наборов
• Заказать многогранник
• Упорядоченное поле  – алгебраический объект с упорядоченной структурой.
• Упорядоченная группа  – Группа с совместимым частичным порядкомPages displaying short descriptions of redirect targets
• Упорядоченное векторное пространство  – векторное пространство с частичным порядком
• Топология частично упорядоченных множеств , вид топологического пространства, которое может быть определено из любого частично упорядоченного множества.
• Непрерывность Скотта – непрерывность функции между двумя частичными порядками.
• Полурешетка  – Частичный порядок с соединениями
• Полупорядок  – числовой порядок с допустимой погрешностью
• Теорема Шпильрайна о расширении – каждый частичный порядок содержится в некотором полном порядке.
• Стохастическое доминирование  – Частичный порядок между случайными величинами
• Строгий слабый порядок – строгий частичный порядок «<», в котором отношение «ни a < b , ни b < a » является транзитивным.
• Полный порядок  – порядок, все элементы которого сравнимы.
• Лемма Цорна  – Математическое предложение, эквивалентное аксиоме выбора

Примечания

1. Доказательство можно найти здесь .
2. который всегда существует и является единственным, поскольку предполагается конечным ${\displaystyle P}$
3. См . Общая теория относительности § Путешествия во времени .

Цитаты

1. Wallis, WD (14 марта 2013 г.). Руководство для начинающих по дискретной математике. Springer Science & Business Media. стр. 100. ISBN 978-1-4757-3826-1.
2. Simovici, Dan A. & Djeraba, Chabane (2008). "Частично упорядоченные множества". Математические инструменты для интеллектуального анализа данных: теория множеств, частичные порядки, комбинаторика . Springer. ISBN 9781848002012.
3. Флашка, В.; Йежек, Й.; Кепка, Т.; Кортелайнен, Й. (2007). «Транзитивные замыкания бинарных отношений I». Acta Universitatis Carolinae. Mathematica et Physica . 48 (1). Прага: Школа математики – физики Карлова университета: 55–69.Лемма 1.1 (iv). Этот источник называет асимметричные отношения «строго антисимметричными».
4. Дэйви и Пристли (2002), стр. 14–15.
5. Авигад, Джереми; Льюис, Роберт Й.; ван Дорн, Флорис (29 марта 2021 г.). "13.2. Подробнее об упорядочениях". Логика и доказательство (выпуск 3.18.4 ред.) . Получено 24 июля 2021 г. Таким образом, мы можем рассматривать каждый частичный порядок как пару, состоящую из слабого частичного порядка и связанного с ним строгого.
6. Раундс, Уильям С. (7 марта 2002 г.). "Слайды лекций" (PDF) . EECS 203: ДИСКРЕТНАЯ МАТЕМАТИКА . Получено 23 июля 2021 г.
7. Квонг, Харрис (25 апреля 2018 г.). «7.4: Частичный и полный порядок». Спиральная рабочая тетрадь по дискретной математике . Получено 23 июля 2021 г.
8. "Конечные частично упорядоченные множества". Sage 9.2.beta2 Справочное руководство: комбинаторика . Получено 5 января 2022 г. compare_elements( x , y ): Сравнить x и y в частично упорядоченном множестве. Если x < y , вернуть −1. Если x = y , вернуть 0. Если x > y , вернуть 1. Если x и y несравнимы, вернуть None.
9. Чен, Питер; Дин, Гуоли; Сейден, Стив. On Poset Merging (PDF) (Технический отчет). стр. 2. Получено 5 января 2022 г. Сравнение двух элементов s, t в S возвращает одно из трех различных значений, а именно s≤t, s>t или s|t.
10. Превосто, Виржиле; Жауме, Матье (11 сентября 2003 г.). Создание доказательств в иерархии математических структур. CALCULEMUS-2003 – 11-й симпозиум по интеграции символических вычислений и механизированного рассуждения. Рим, Италия: Aracne. С. 89–100.
11. Меррифилд, Ричард Э.; Симмонс, Говард Э. (1989). Топологические методы в химии . Нью-Йорк: John Wiley & Sons. С. 28. ISBN 0-471-83817-9. Получено 27 июля 2012 г. Частично упорядоченное множество удобно представлять диаграммой Хассе ...
12. Неггерс, Дж.; Ким, Хи Сик (1998), «4.2 Порядок продукта и лексикографический порядок», Basic Posets , World Scientific, стр. 62–63, ISBN 9789810235895
13. Дэйви и Пристли (2002), стр. 17–18.
14. PR Halmos (1974). Наивная теория множеств . Springer. стр. 82. ISBN 978-1-4757-1645-0.
15. Дэйви и Пристли (2002), стр. 23–24.
16. Jech, Thomas (2008) [1973]. Аксиома выбора . Dover Publications . ISBN 978-0-486-46624-8.
17. Уорд, Л. Э. Младший (1954). «Частично упорядоченные топологические пространства». Труды Американского математического общества . 5 (1): 144–161. doi : 10.1090/S0002-9939-1954-0063016-5 . hdl :10338.dmlcz/101379.

Ссылки

• Davey, BA; Priestley, HA (2002). Введение в решетки и порядок (2-е изд.). Нью-Йорк: Cambridge University Press. ISBN 978-0-521-78451-1.
• Дешпанде, Джаянт В. (1968). «О непрерывности частичного порядка». Труды Американского математического общества . 19 (2): 383–386. doi : 10.1090/S0002-9939-1968-0236071-7 .
• Шмидт, Гюнтер (2010). Реляционная математика . Энциклопедия математики и ее приложений. Том 132. Cambridge University Press. ISBN 978-0-521-76268-7.
• Бернд Шрёдер (11 мая 2016 г.). Упорядоченные множества: введение со связями из комбинаторики в топологию. Биркхойзер. ISBN 978-3-319-29788-0.
• Стэнли, Ричард П. (1997). Перечислительная комбинаторика 1. Кембриджские исследования по высшей математике. Том 49. Cambridge University Press. ISBN 0-521-66351-2.
• Эйленберг, С. (2016). Основы алгебраической топологии . Princeton University Press.
• Калмбах, Г. (1976). «Расширение теории гомологии на частично упорядоченные множества». J. Reine Angew. Math . 280 : 134–156.

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

• Последовательность OEIS A001035 (Количество частично упорядоченных множеств с n помеченными элементами)
• Последовательность OEIS A000112 (Число частично упорядоченных множеств («частично упорядоченных множеств») с n непомеченными элементами.)