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

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

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

Определение и примеры

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

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

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

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

Терминология и обозначения

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

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

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

Строгий и нестрогий порядок

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

$\forall a\;\neg (a\varphi a)$

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

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

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

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

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

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

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

Интервал

Для $a\leqslant b$ замкнутый интервал [a,b] — это множество элементов x, удовлетворяющих неравенству $a\leqslant x\leqslant b$ (то есть $a\leqslant x$ и $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] определяются аналогичным образом.

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

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

Примеры

Подмножества {x, y, z}, упорядоченные отношением включения

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

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

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

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

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

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

Связанные определения

Несравнимые элементы

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

$a<b,\qquad a=b,\qquad b<a$

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

Минимальный/максимальный и наименьший/наибольший элементы

Основная статья: Максимальные и минимальные элементы

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

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

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

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

Верхние и нижние грани

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

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

Верхнее и нижнее множество

Элементы верхнего множества $2^{\{1,2,3,4\}}\uparrow \{1\}$ отмечены зелёным

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

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

Условия обрыва цепей

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

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

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

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

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

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

Тривиально упорядоченные множества

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

$a\leqslant b\Leftrightarrow a=b$

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

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

$\lnot (a<b)$

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

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

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

Основная статья: Линейно упорядоченное множество

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

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

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

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

Вполне упорядоченные множества

Основная статья: Вполне упорядоченное множество

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

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

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

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

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

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

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

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

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

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

Каждое частично упорядоченное множество (и каждый предпорядок) можно рассматривать как категорию, в которой каждое множество морфизмов $\mathrm {Hom} (A,B)$ состоит не более чем из одного элемента. Например, эту категорию можно определить так: $\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.

См. также

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