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

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

Рис. 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. Антисимметрия : if и then , т.е. никакие два различных элемента не предшествуют друг другу. ${\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 a<a}$
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}$

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

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

Двойственное (или противоположное ) отношению частичного порядка определяется путем обозначения обратного отношения к , т.е. тогда и только тогда, когда . Двойственным к нестрогому частичному порядку является нестрогий частичный порядок ^[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 }$

Когда речь идет о частичных заказах, их не следует воспринимать как дополнение к . Отношение является обратным иррефлексивному ядру , которое всегда является подмножеством дополнения , но равно дополнению if и только тогда, когда , является полным порядком. ^[а] ${\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 и б € 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 , ≼) называются изоморфными . Изоморфные порядки имеют структурно схожие диаграммы Хассе (см. рис. 7а). Можно показать, что если сохраняющие порядок отображения и существуют такие, что и дают тождественную функцию на 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 ).

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

Частичный порядок на множестве является расширением другого частичного порядка при условии, что для всех элементов всякий раз, когда это также имеет место, Линейное расширение — это расширение, которое также является линейным (то есть полным) порядком. Классический пример: лексикографический порядок полностью упорядоченных множеств является линейным расширением порядка их произведений. Каждый частичный порядок может быть расширен до полного порядка ( принцип расширения порядка ). ^[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 ( а в противном случае — пустое множество ) и такие категории иногда называют посетальными . В дифференциальной топологии теория гомологии (HT) используется для классификации эквивалентных гладких многообразий M, связанных с геометрическими формами M. ${\displaystyle x}$ ${\displaystyle y,}$ ${\displaystyle x}$ ${\displaystyle y.}$ ${\displaystyle (y,z)\circ (x,y)=(x,z).}$

Частные множества эквивалентны друг другу тогда и только тогда, когда они изоморфны . В частичном наборе наименьший элемент, если он существует, является начальным объектом , а самый большой элемент, если он существует, является конечным объектом . Кроме того, каждый предварительно упорядоченный набор эквивалентен частичному множеству. Наконец, каждая подкатегория ЧУМ является изоморфизм-замкнутой . В дифференциальной топологии теория гомологии (HT) используется для классификации эквивалентных гладких многообразий M, связанных с геометрическими формами M. В теории гомологии дается аксиоматический подход HT, особенно к сингулярным гомологиям. ^{[ необходимо разъяснение ]} Члены HT являются алгебраическими инвариантами относительно диффеоморфизмов. Аксиоматическая категория HT взята у Г. Калмбаха из книги Эйленберга-Стинрода (см. ссылки) для того, чтобы показать, что теоретико-множественная топологическая концепция для определения HT может быть расширена до частично упорядоченных множеств P. Важными являются цепи и фильтры в P (заменяет формы M) для определения классификаций HT, доступен для многих приложений P, не связанных с теорией множеств.

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

Если это частично упорядоченное множество, которое также имеет структуру топологического пространства , то принято предполагать, что это замкнутое подмножество топологического пространства произведения . При этом предположении отношения частичного порядка хорошо ведут себя на пределе в том смысле, что если и и для всех тогда ^[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 (см. рис. 7б) множество {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 fallback
• Решетка  - набор, пары которого имеют минимумы и максимумы.
• Локально конечное ЧУУ  - МатематикаPages displaying wikidata descriptions as a fallbackPages displaying short descriptions with no spaces
• Функция Мёбиуса на частично упорядоченных множествах  - ассоциативная алгебра, используемая в комбинаторике, разделе математики.Pages displaying wikidata descriptions as a fallback
• Коллекция вложенных наборов
• Заказать многогранник
• Упорядоченное поле  – алгебраический объект с упорядоченной структурой.
• Упорядоченная группа  - группа с совместимым частичным порядком.Pages displaying short descriptions of redirect targets
• Упорядоченное векторное пространство  - векторное пространство с частичным порядком.
• Топология ЧУМ — своего рода топологическое пространство, которое можно определить из любого ЧУМ.
• Непрерывность Скотта – непрерывность функции между двумя частичными порядками.
• Полурешетка  - Частичный порядок с соединениями
• Полупорядок  – числовой порядок с погрешностью.
• Теорема расширения Шпильрайна - каждый частичный порядок содержится в некотором полном порядке.
• Стохастическое доминирование  - частичный порядок между случайными величинами.
• Строгий слабый порядок – строгий частичный порядок «<», при котором отношение «ни a < b , ни b < a » не является транзитивным.
• Общий порядок  - заказ, все элементы которого сопоставимы.
• Дерево – структура данных включения набора.
• Лемма Цорна  - математическое утверждение, эквивалентное аксиоме выбора.

Примечания

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

Цитаты

1. Уоллис, WD (14 марта 2013 г.). Руководство для начинающих по дискретной математике. Springer Science & Business Media. п. 100. ИСБН 978-1-4757-3826-1.
2. Симовичи, Дэн А. и Джераба, Чабане (2008). «Частично упорядоченные множества». Математические инструменты для интеллектуального анализа данных: теория множеств, частичные порядки, комбинаторика . Спрингер. ISBN 9781848002012.
3. Флашка, В.; Ежек, Дж.; Кепка, Т.; Кортелайнен, Дж. (2007). «Транзитивные замыкания бинарных отношений I». Acta Universitatis Carolinae. Математика и физика . Прага: Школа математики – Физика Карлова университета. 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. Чен, Питер; Дин, Гуоли; Сейден, Стив. Об объединении Poset (PDF) (Технический отчет). п. 2 . Проверено 5 января 2022 г. Сравнение двух элементов s, t в S возвращает одно из трех различных значений, а именно s≤t, s>t или s|t.
10. Превосто, Вергилий; Жауме, Матье (11 сентября 2003 г.). Проведение доказательств в иерархии математических структур. CALCULEMUS-2003 – 11-й симпозиум по интеграции символических вычислений и механизированного мышления. Рим, Италия: Аракне. стр. 89–100.
11. Меррифилд, Ричард Э.; Симмонс, Ховард Э. (1989). Топологические методы в химии . Нью-Йорк: Джон Уайли и сыновья. стр. 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 Халмош (1974). Наивная теория множеств . Спрингер. п. 82. ИСБН 978-1-4757-1645-0.
15. Дэйви и Пристли (2002), стр. 23–24.
16. Джех, Томас (2008) [1973]. Аксиома выбора . Дуврские публикации . ISBN 978-0-486-46624-8.
17. Уорд, Л.Э. младший (1954). «Частично упорядоченные топологические пространства». Труды Американского математического общества . 5 (1): 144–161. дои : 10.1090/S0002-9939-1954-0063016-5 . hdl :10338.dmlcz/101379.

Рекомендации

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

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

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