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

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

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

Определение и примерыПравить

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

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

Множество $M$$M$ , на котором задано отношение частичного порядка, называется частично упорядоченным. Если быть совсем точным, то частично упорядоченным множеством называется пара $⟨<!--\; ⟨\; -->M,\mathrm{\phi <!--\; \phi \; -->}⟩<!--\; ⟩\; -->$$\langle M,\varphi \rangle$ , где $M$$M$  — множество, а $\mathrm{\phi <!--\; \phi \; -->}$$\varphi$  — отношение частичного порядка на $M$$M$ .

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

Терминология и обозначенияПравить

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

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

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

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

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

$\mathrm{\forall <!--\; \forall \; -->}a\mathrm{\neg <!--\; \neg \; -->}(a\mathrm{\phi <!--\; \phi \; -->}a)$$\forall a\;\neg (a\varphi a)$ 

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

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

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

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

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

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

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

ИнтервалПравить

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

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

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

ПримерыПравить

 

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

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

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

$f:<!--\; :\; -->[a,b]\to <!--\; \to \; -->\mathbb{R}$$f\colon [a,b]\to {\mathbb {R}}$ 

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Верхние и нижние граниПравить

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

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

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

 

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

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

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

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

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

$a_1⩽<!--\; ⩽\; -->a_2⩽<!--\; ⩽\; -->a_3⩽<!--\; ⩽\; -->\cdots <!--\; \cdots \; -->$$a_{1}\,\leqslant \,a_{2}\,\leqslant \,a_{3}\,\leqslant \,\cdots$ 

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

$a_n=a_{n+1}=a_{n+2}=\cdots <!--\; \cdots \; -->.$$a_{n}=a_{{n+1}}=a_{{n+2}}=\cdots .$ 

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Любое множество $M$$M$  можно превратить в полное частично упорядоченное выделением дна $\mathrm{\perp <!--\; \perp \; -->}$$\bot$  и определением порядка $⩽<!--\; ⩽\; -->$$\leqslant$  как $\mathrm{\perp <!--\; \perp \; -->}⩽<!--\; ⩽\; -->m$$\bot \leqslant m$  и $m⩽<!--\; ⩽\; -->m$$m\leqslant m$  для всех элементов $m$$m$  множества $M$$M$ .

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

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

В теории категорийПравить

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

См. такжеПравить

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