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

Части́чно упоря́доченное мно́жество (сокр. ЧУМ) — математическое понятие, которое формализует интуитивные идеи упорядочения, расположения элементов в определённой последовательности. Неформально, множество частично упорядочено, если указано, какие элементы следуют за какими (какие элементы больше каких). В общем случае может оказаться так, что некоторые пары элементов не связаны отношением «следует за».

В качестве абстрактного примера можно привести совокупность подмножеств множества из трёх элементов ${\displaystyle \left\{x,y,z\right\}}$ (булеан данного множества), упорядоченную по отношению включения.

Отношением порядка, или частичным порядком, на множестве ${\displaystyle M}$ называется бинарное отношение ${\displaystyle \varphi }$ на ${\displaystyle M}$ (определяемое некоторым множеством ${\displaystyle R_{\varphi }\subset M\times M}$), удовлетворяющее следующим условиям^[1]:

• Рефлексивность: ${\displaystyle \forall a\;\left(a\varphi a\right)}$
• Транзитивность: ${\displaystyle \forall a,b,c\;\left(a\varphi b\right)\wedge \left(b\varphi c\right)\Rightarrow a\varphi c}$
• Антисимметричность: ${\displaystyle \forall a,b\;\left(a\varphi b\right)\wedge \left(b\varphi a\right)\Rightarrow a=b}$

Множество ${\displaystyle M}$, на котором задано отношение частичного порядка, называется частично упорядоченным. Если быть совсем точным^[2], то частично упорядоченным множеством называется пара ${\displaystyle \langle M,\varphi \rangle }$, где ${\displaystyle M}$ — множество, а ${\displaystyle \varphi }$ — отношение частичного порядка на ${\displaystyle M}$.

Размерность частично упорядоченного множества ${\displaystyle \langle M,\varphi \rangle }$ равна максимальной численности совокупности линейных порядков ${\displaystyle <_{i}}$ (${\displaystyle i\in I}$). В основе этого определения находится свойство продолжаемости частичного порядка до линейного.

Отношение частичного порядка обычно обозначают символом ${\displaystyle \leqslant }$, по аналогии с отношением «меньше либо равно» на множестве вещественных чисел. При этом, если ${\displaystyle a\leqslant b}$, то говорят, что элемент ${\displaystyle a}$ не превосходит ${\displaystyle b}$, или что ${\displaystyle a}$ подчинён ${\displaystyle b}$.

Если ${\displaystyle a\leqslant b}$ и ${\displaystyle a\neq b}$, то пишут ${\displaystyle a<b}$, и говорят, что ${\displaystyle a}$ меньше ${\displaystyle b}$, или что ${\displaystyle a}$ строго подчинен ${\displaystyle b}$.

Иногда, чтобы отличить произвольный порядок на некотором множестве от известного отношения «меньше либо равно» на множестве действительных чисел, вместо ${\displaystyle \leqslant }$ и ${\displaystyle <}$ используют специальные символы ${\displaystyle \preccurlyeq }$ и ${\displaystyle \prec }$ соответственно.

Отношение, удовлетворяющее условиям рефлексивности, транзитивности и антисимметричности, также называют нестрогим, или рефлексивным порядком. Если условие рефлексивности заменить на условие антирефлексивности (тогда свойство антисимметричности заменится на асимметричность):

${\displaystyle \forall a\;\neg (a\varphi a)}$

то получим определение строгого, или антирефлексивного порядка.

Если ${\displaystyle \leqslant }$ — нестрогий порядок на множестве ${\displaystyle M}$, то отношение ${\displaystyle <}$, определяемое как:

${\displaystyle a<b\;{\overset {\mathrm {def} }{\Longleftrightarrow }}\;(a\leqslant b)\wedge (a\neq b)}$

является строгим порядком на ${\displaystyle M}$. Обратно, если ${\displaystyle <}$ — строгий порядок, то отношение ${\displaystyle \leqslant }$, определённое как

${\displaystyle a\leqslant b\;{\overset {\mathrm {def} }{\Longleftrightarrow }}\;(a<b)\vee (a=b)}$

является нестрогим порядком.

Поэтому всё равно — задать на множестве нестрогий порядок или строгий порядок. В результате получится одна и та же структура. Разница только в терминологии и обозначениях.

Для ${\displaystyle a\leqslant b}$ замкнутый интервал [a,b] — это множество элементов x, удовлетворяющих неравенству ${\displaystyle a\leqslant x\leqslant b}$ (то есть ${\displaystyle a\leqslant x}$ и ${\displaystyle x\leqslant b}$). Интервал содержит, по меньшей мере, элементы a и b.

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

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

Полуоткрытые интервалы [a,b) и (a,b] определяются аналогичным образом.

Частично упорядоченное множество является локально конечным^[англ.], если любой интервал конечен. Например, целые числа локально конечны по их естественному упорядочению. Лексикографический порядок на прямом произведении ℕ×ℕ не является локально конечным, поскольку, например, ${\displaystyle (1,2)\leqslant (1,3)\leqslant (1,4)\leqslant (1,5)\leqslant \ldots \leqslant (2,1)}$.

Концепцию интервала в частично упорядоченных множествах не следует путать со специфичным классом частичных упорядоченных множеств, известных как интервальные порядки^[англ.].

• Множество вещественных чисел ${\displaystyle \mathbb {R} }$ частично упорядочено по отношению «меньше либо равно» — ${\displaystyle \leqslant }$.

• Пусть ${\displaystyle M}$ — множество всех вещественнозначных функций, определённых на отрезке ${\displaystyle [a,b]}$, то есть функций вида

${\displaystyle f\colon [a,b]\to \mathbb {R} }$

Введём отношение порядка ${\displaystyle \leqslant }$ на ${\displaystyle M}$ следующим образом: ${\displaystyle f\leqslant g}$, если для всех ${\displaystyle x\in [a,b]}$ выполнено неравенство ${\displaystyle f(x)\leqslant g(x)}$. Очевидно, введенное отношение в самом деле является отношением частичного порядка.

• Пусть ${\displaystyle M}$ — некоторое множество. Множество ${\displaystyle {\mathcal {P}}(M)}$ всех подмножеств ${\displaystyle M}$ (так называемый булеан), частично упорядочено по включению ${\displaystyle M\subseteq N}$.

• Множество всех натуральных чисел ${\displaystyle \mathbb {N} }$ частично упорядочено по отношению делимости ${\displaystyle m\mid n}$.

Если ${\displaystyle a}$ и ${\displaystyle b}$ — вещественные числа, то имеет место только одно из следующих соотношений:

${\displaystyle a<b,\qquad a=b,\qquad b<a}$

В случае, если ${\displaystyle a}$ и ${\displaystyle b}$ — элементы произвольного частично упорядоченного множества, то существует четвёртая логическая возможность: не выполнено ни одно из указанных трех соотношений. В этом случае элементы ${\displaystyle a}$ и ${\displaystyle b}$ называются несравнимыми. Например, если ${\displaystyle M}$ — множество действительнозначных функций на отрезке ${\displaystyle [0,1]}$, то элементы ${\displaystyle f(x)=x}$ и ${\displaystyle g(x)=1-x}$ будут несравнимы. Возможность существования несравнимых элементов объясняет смысл термина «частично упорядоченное множество».

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

Элемент ${\displaystyle a\in M}$ называется минимальным, если не существует элемента ${\displaystyle b<a}$. Другими словами, ${\displaystyle a}$ — минимальный элемент, если для любого элемента ${\displaystyle b\in M}$ либо ${\displaystyle b>a}$, либо ${\displaystyle b=a}$, либо ${\displaystyle b}$ и ${\displaystyle a}$ несравнимы. Элемент ${\displaystyle a}$ называется наименьшим, если для любого элемента ${\displaystyle b\in M}$ имеет место неравенство ${\displaystyle b\geqslant a}$. Очевидно, всякий наименьший элемент является также минимальным, но обратное в общем случае неверно: минимальный элемент ${\displaystyle a}$ может и не быть наименьшим, если существуют элементы ${\displaystyle b}$, не сравнимые с ${\displaystyle a}$.

Очевидно, что если в множестве существует наименьший элемент, то он единственнен. А вот минимальных элементов может быть несколько. В качестве примера рассмотрим множество ${\displaystyle \mathbb {N} \setminus \{1\}=\{2,3,\ldots \}}$ натуральных чисел без единицы, упорядоченное по отношению делимости ${\displaystyle \mid }$. Здесь минимальными элементами будут простые числа, а вот наименьшего элемента не существует.

Аналогично вводятся понятия максимального и наибольшего элементов.

Пусть ${\displaystyle A}$ — подмножество частично упорядоченного множества ${\displaystyle \langle M,\leqslant \rangle }$. Элемент ${\displaystyle u\in M}$ называется верхней гранью ${\displaystyle A}$, если любой элемент ${\displaystyle a\in A}$ не превосходит ${\displaystyle u}$. Аналогично вводится понятие нижней грани множества ${\displaystyle A}$.

Любой элемент, больший, чем некоторая верхняя грань ${\displaystyle A}$, также будет верхней гранью ${\displaystyle A}$. А любой элемент, меньший, чем некоторая нижняя грань ${\displaystyle A}$, также будет нижней гранью ${\displaystyle A}$. Эти соображения ведут к введению понятий наименьшей верхней грани и наибольшей нижней грани.

Для элемента ${\displaystyle m}$ частично упорядоченного множества ${\displaystyle \langle M,\leqslant \rangle }$ верхним множеством называется множество ${\displaystyle M\uparrow m}$ всех элементов, которым ${\displaystyle m}$ предшествует (${\displaystyle \{x\in M\mid m\leqslant x\}}$).

Двойственным образом определяется нижнее множество, как множество всех элементов, предшествующих заданному: ${\displaystyle M\downarrow m{\stackrel {\mathrm {def} }{=}}\{x\in M\mid x\leqslant m\}}$.

Частично упорядоченное множество ${\displaystyle M}$ называется удовлетворяющим условию обрыва строго возрастающих цепей, если не существует бесконечной строго возрастающей последовательности ${\displaystyle (a_{i}\,<\,a_{i+1})}$. Это условие эквивалентно условию стабилизации нестрого возрастающих цепей: любая нестрого ${\displaystyle (a_{i}\,\leqslant \,a_{i+1})}$ возрастающая последовательность его элементов стабилизируется. То есть, для любой последовательности вида

${\displaystyle a_{1}\,\leqslant \,a_{2}\,\leqslant \,a_{3}\,\leqslant \,\cdots }$

существует натуральное ${\displaystyle n,}$ такое что

${\displaystyle a_{n}=a_{n+1}=a_{n+2}=\cdots .}$

Аналогичным образом определяется для убывающих цепей, тогда очевидно, ${\displaystyle M}$ удовлетворяет условию обрыва убывающих цепей, тогда и только тогда, когда любая нестрого убывающая последовательность его элементов стабилизируется. Эти понятия часто используются в общей алгебре — см., например, нётерово кольцо, артиново кольцо.

Пусть ${\displaystyle M}$ — произвольное множество. Тривиальным (диагональным^[3]) нестрогим порядком на ${\displaystyle M}$ называется отношение, определяемое следующим образом:

${\displaystyle a\leqslant b\Leftrightarrow a=b}$

Тривиальный порядок есть наименьший по включению частичный порядок, который можно задать на множестве.

Строгий тривиальный порядок определяется так:

${\displaystyle \lnot (a<b)}$

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

Тривиальное упорядоченное множество (антицепь) — частично упорядоченное множество ${\displaystyle (M,\leqslant )}$, где ${\displaystyle \leqslant }$ — тривиальный порядок на ${\displaystyle M}$.^[4][5]

Пусть ${\displaystyle \langle M,\leqslant \rangle }$ — частично упорядоченное множество. Если в ${\displaystyle M}$ любые два элемента сравнимы, то множество ${\displaystyle M}$ называется линейно упорядоченным. Линейно упорядоченное множество также называют совершенно упорядоченным, или просто, упорядоченным множеством^[6]. Таким образом, в линейно упорядоченном множестве для любых двух элементов ${\displaystyle a}$ и ${\displaystyle b}$ имеет место одно и только одно из соотношений: либо ${\displaystyle a<b}$, либо ${\displaystyle a=b}$, либо ${\displaystyle b<a}$.

Также всякое линейно упорядоченное подмножество частично упорядоченного множества называют цепью, то есть цепь в частично упорядоченном множестве ${\displaystyle \langle M,\leqslant \rangle }$ — такое его подмножество, в котором любые два элемента сравнимы.

Из приведенных выше примеров частично упорядоченных множеств только множество действительных чисел является линейно упорядоченным. Множество действительнозначных функций на отрезке ${\displaystyle [a,b]}$ (при условии ${\displaystyle a<b}$), булеан ${\displaystyle {\mathcal {P}}(M)}$ (при ${\displaystyle |M|\geqslant 2}$), натуральные числа с отношением делимости — не являются линейно упорядоченными.

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

Линейно упорядоченное множество называется вполне упорядоченным, если каждое его непустое подмножество имеет наименьший элемент^[7]. Такой порядок на множестве называется полным порядком, в контексте, где его невозможно спутать с полным порядком в смысле полных частично упорядоченных множеств.

Классический пример вполне упорядоченного множества — множество натуральных чисел ${\displaystyle \mathbb {N} }$. Утверждение о том, что любое непустое подмножество ${\displaystyle \mathbb {N} }$ содержит наименьший элемент, равносильно принципу математической индукции. В качестве примера линейно упорядоченного, но не вполне упорядоченного множества можно привести множество неотрицательных чисел, упорядоченное естественным образом ${\displaystyle \mathbb {R} _{+}=\{x:x\geqslant 0\}}$. Действительно, его подмножество ${\displaystyle \{x:x>1\}}$ не имеет наименьшего элемента.

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

Полное частично упорядоченное множество — частично упорядоченное множество, у которого есть дно — единственный элемент, который предшествует любому другому элементу и у каждого направленного подмножества которого есть точная верхняя граница^[8]. Полные частично упорядоченные множества применяются в λ-исчислении и информатике, в частности, на них вводится топология Скотта, на основе которой строится непротиворечивая модель λ-исчисления и денотационная семантика^[англ.]. Специальным случаем полного частично упорядоченного множества является полная решётка — если любое подмножество, не обязательно направленное, имеет точную верхнюю грань, то оно оказывается полной решёткой.

Упорядоченное множество ${\displaystyle M}$ тогда и только тогда является полным частично упорядоченным, когда каждая функция ${\displaystyle f\colon M\rightarrow M}$, монотонная относительно порядка (${\displaystyle a\leqslant b\Rightarrow f(a)\leqslant f(b)}$) обладает хотя бы одной неподвижной точкой: ${\displaystyle \exists _{x\in M}f(x)=x}$.

Любое множество ${\displaystyle M}$ можно превратить в полное частично упорядоченное выделением дна ${\displaystyle \bot }$ и определением порядка ${\displaystyle \leqslant }$ как ${\displaystyle \bot \leqslant m}$ и ${\displaystyle m\leqslant m}$ для всех элементов ${\displaystyle m}$ множества ${\displaystyle M}$.

К числу фундаментальных теорем о частично упорядоченных множествах относятся принцип максимума Хаусдорфа и лемма Куратовского — Цорна. Каждая из этих теорем эквивалентна аксиоме выбора.

Каждое частично упорядоченное множество (и каждый предпорядок) можно рассматривать как категорию, в которой каждое множество морфизмов ${\displaystyle \mathrm {Hom} (A,B)}$ состоит не более чем из одного элемента. Например, эту категорию можно определить так: ${\displaystyle \mathrm {Hom} (A,B)=\{(A,B)\}}$, если A ≤ B (и пустое множество в противном случае); правило композиции морфизмов: (y, z)∘(x, y) = (x, z). Каждая категория-предпорядок эквивалентна частично упорядоченному множеству.

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

• Александров П. С. Введение в теорию множеств и общую топологию. — М.: Наука, 1977. — 368 с.
• Барендрегт, Хенк. Ламбда-исчисление. Его синтаксис и семантика = The Lambda Calculus. Its syntax and semantics. — М.: Мир, 1985. — 606 с. — 4800 экз.
• Колмогоров А. Н., Фомин С. В. Элементы теории функций и функционального анализа. — 7-е изд. — М.: Физматлит, 2004. — 572 с. — ISBN 5-9221-0266-4.
• Хаусдорф Ф. Теория множеств. — 4-е изд. — М.: УРСС, 2007. — 304 с. — ISBN 978-5-382-00127-2.
• Гуров С.И. Булевы алгебры, упорядоченные множества, решетки: Определения, свойства, примеры. — 2-е изд. — М.: Либроком, 2013. — 352 с. — ISBN 978-5-397-03899-7.
• Harzheim E. Ordered Sets (англ.). — Springer, 2005. — ISBN 9789810235895.

• Решётка
• Порядковое число
• Предпорядок