Русская Википедия:Частично упорядоченное множество
Шаблон:Значения Части́чно упоря́доченное мно́жество (сокр. ЧУМ) — математическое понятие, которое формализует интуитивные идеи упорядочения, расположения элементов в определённой последовательности. Неформально, множество частично упорядочено, если указано, какие элементы следуют за какими (какие элементы больше каких). В общем случае может оказаться так, что некоторые пары элементов не связаны отношением «следуетШаблон:Nbspза».
В качестве абстрактного примера можно привести совокупность подмножеств множества из трёх элементов <math>\left\{ x, y, z \right\}</math> (булеан данного множества), упорядоченную по отношению включения.
Определение и примеры
Отношением порядка, или частичным порядком, на множестве <math>M</math> называется бинарное отношение <math>\varphi</math> на <math>M</math> (определяемое некоторым множеством <math> R_{\varphi} \subset M \times M </math>), удовлетворяющее следующим условиямШаблон:Sfn:
- Рефлексивность: <math>\forall a \; \left( a \varphi a \right)</math>
- Транзитивность: <math>\forall a, b, c \; \left( a \varphi b \right) \wedge \left( b \varphi c \right) \Rightarrow a \varphi c</math>
- Антисимметричность: <math>\forall a, b \; \left( a \varphi b \right) \wedge \left( b \varphi a \right) \Rightarrow a = b</math>
Множество <math>M</math>, на котором задано отношение частичного порядка, называется частично упорядоченным. Если быть совсем точнымШаблон:Sfn, то частично упорядоченным множеством называется пара <math>\langle M, \varphi \rangle</math>, где <math>M</math> — множество, а <math>\varphi</math> — отношение частичного порядка на <math>M</math>.
Размерность частично упорядоченного множества <math>\langle M,\varphi\rangle</math> равна максимальной численности совокупности линейных порядков <math><_{i}</math> (<math>i \in I</math>). В основе этого определения находится свойство продолжаемости частичного порядка до линейного.
Терминология и обозначения
Отношение частичного порядка обычно обозначают символом <math>\leqslant</math>, по аналогии с отношением «меньше либо равно» на множестве вещественных чисел. При этом, если <math>a \leqslant b</math>, то говорят, что элемент <math>a</math> не превосходит <math>b</math>, или что <math>a</math> подчинён <math>b</math>.
Если <math>a \leqslant b</math> и <math>a \neq b</math>, то пишут <math>a < b</math>, и говорят, что <math>a</math> меньше <math>b</math>, или что <math>a</math> строго подчинен <math>b</math>.
Иногда, чтобы отличить произвольный порядок на некотором множестве от известного отношения «меньше либо равно» на множестве действительных чисел, вместо <math>\leqslant</math> и <math><</math> используют специальные символы <math>\preccurlyeq</math> и <math>\prec</math> соответственно.
Строгий и нестрогий порядок
Отношение, удовлетворяющее условиям рефлексивности, транзитивности и антисимметричности, также называют нестрогим, или рефлексивным порядком. Если условие рефлексивности заменить на условие антирефлексивности (тогда свойство антисимметричности заменится на асимметричность):
- <math>\forall a \; \neg (a \varphi a)</math>
то получим определение строгого, или антирефлексивного порядка.
Если <math>\leqslant</math> — нестрогий порядок на множестве <math>M</math>, то отношение <math><</math>, определяемое как:
- <math>a < b \; \overset{\mathrm{def}}{\Longleftrightarrow} \; (a \leqslant b) \wedge (a \neq b)</math>
является строгим порядком на <math>M</math>. Обратно, если <math><</math> — строгий порядок, то отношение <math>\leqslant</math>, определённое как
- <math>a \leqslant b \; \overset{\mathrm{def}}{\Longleftrightarrow} \; (a < b) \vee (a = b)</math>
является нестрогим порядком.
Поэтому всё равно — задать на множестве нестрогий порядок или строгий порядок. В результате получится одна и та же структура. Разница только в терминологии и обозначениях.
Интервал
Для <math>a \leqslant b</math> замкнутый интервал [a,b] — это множество элементов x, удовлетворяющих неравенству <math>a \leqslant x \leqslant b</math> (то есть <math>a \leqslant x</math> и <math>x \leqslant b</math>). Интервал содержит, по меньшей мере, элементы 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] определяются аналогичным образом.
Частично упорядоченное множество является Шаблон:Не переведено 5, если любой интервал конечен. Например, целые числа локально конечны по их естественному упорядочению. Лексикографический порядок на прямом произведении ℕ×ℕ не является локально конечным, поскольку, например, <math>(1,2) \leqslant (1,3) \leqslant (1,4) \leqslant (1,5) \leqslant \ldots \leqslant (2,1)</math>.
Концепцию интервала в частично упорядоченных множествах не следует путать со специфичным классом частичных упорядоченных множеств, известных как Шаблон:Не переведено 5.
Примеры
- Множество вещественных чисел <math>\mathbb{R}</math> частично упорядочено по отношению «меньше либо равно» — <math>\leqslant</math>.
- Пусть <math>M</math> — множество всех вещественнозначных функций, определённых на отрезке <math>[a,b]</math>, то есть функций вида
f \colon [a,b] \to \mathbb{R} </math>
Введём отношение порядка <math>\leqslant</math> на <math>M</math> следующим образом: <math>f \leqslant g</math>, если для всех <math>x \in [a,b]</math> выполнено неравенство <math>f(x) \leqslant g(x)</math>. Очевидно, введенное отношение в самом деле является отношением частичного порядка.
- Пусть <math>M</math> — некоторое множество. Множество <math>\mathcal{P}(M)</math> всех подмножеств <math>M</math> (так называемый булеан), частично упорядочено по включению <math>M \subseteq N</math>.
- Множество всех натуральных чисел <math>\mathbb{N}</math> частично упорядочено по отношению делимости <math>m \mid n</math>.
Связанные определения
Несравнимые элементы
Если <math>a</math> и <math>b</math> — вещественные числа, то имеет место только одно из следующих соотношений:
a < b, \qquad a=b, \qquad b<a </math>
В случае, если <math>a</math> и <math>b</math> — элементы произвольного частично упорядоченного множества, то существует четвёртая логическая возможность: не выполнено ни одно из указанных трех соотношений. В этом случае элементы <math>a</math> и <math>b</math> называются несравнимыми. Например, если <math>M</math> — множество действительнозначных функций на отрезке <math>[0,1]</math>, то элементы <math>f(x) = x</math> и <math>g(x) = 1-x</math> будут несравнимы. Возможность существования несравнимых элементов объясняет смысл термина «частично упорядоченное множество».
Минимальный/максимальный и наименьший/наибольший элементы
Из-за того, что в частично упорядоченном множестве могут быть пары несравнимых элементов, вводятся два различных определения: минимального элемента и наименьшего элемента.
Элемент <math>a \in M</math> называется минимальным, если не существует элемента <math>b < a</math>. Другими словами, <math>a</math> — минимальный элемент, если для любого элемента <math>b \in M</math> либо <math>b>a</math>, либо <math>b=a</math>, либо <math>b</math> и <math>a</math> несравнимы. Элемент <math>a</math> называется наименьшим, если для любого элемента <math>b \in M</math> имеет место неравенство <math>b \geqslant a</math>. Очевидно, всякий наименьший элемент является также минимальным, но обратное в общем случае неверно: минимальный элемент <math>a</math> может и не быть наименьшим, если существуют элементы <math>b</math>, не сравнимые с <math>a</math>.
Очевидно, что если в множестве существует наименьший элемент, то он единственнен. А вот минимальных элементов может быть несколько. В качестве примера рассмотрим множество <math>\mathbb{N}\setminus \{ 1 \} = \{ 2, 3, \ldots \}</math> натуральных чисел без единицы, упорядоченное по отношению делимости <math>\mid</math>. Здесь минимальными элементами будут простые числа, а вот наименьшего элемента не существует.
Аналогично вводятся понятия максимального и наибольшего элементов.
Верхние и нижние грани
Пусть <math>A</math> — подмножество частично упорядоченного множества <math>\langle M, \leqslant\rangle</math>. Элемент <math>u \in M</math> называется верхней гранью <math>A</math>, если любой элемент <math>a \in A</math> не превосходит <math>u</math>. Аналогично вводится понятие нижней грани множества <math>A</math>.
Любой элемент, больший, чем некоторая верхняя грань <math>A</math>, также будет верхней гранью <math>A</math>. А любой элемент, меньший, чем некоторая нижняя грань <math>A</math>, также будет нижней гранью <math>A</math>. Эти соображения ведут к введению понятий наименьшей верхней грани и наибольшей нижней грани.
Верхнее и нижнее множество
Для элемента <math>m</math> частично упорядоченного множества <math>\langle M, \leqslant\rangle</math> верхним множеством называется множество <math>M \uparrow m</math> всех элементов, которым <math>m</math> предшествует (<math>\{ x \in M \mid m \leqslant x\}</math>).
Двойственным образом определяется нижнее множество, как множество всех элементов, предшествующих заданному: <math>M \downarrow m \stackrel{\mathrm{def}}{ = } \{ x \in M \mid x \leqslant m\}</math>.
Условия обрыва цепей
Частично упорядоченное множество <math>M</math> называется удовлетворяющим условию обрыва строго возрастающих цепей, если не существует бесконечной строго возрастающей последовательности <math>(a_i \,<\, a_{i+1})</math>. Это условие эквивалентно условию стабилизации нестрого возрастающих цепей: любая нестрого <math>(a_i \,\leqslant\, a_{i+1})</math> возрастающая последовательность его элементов стабилизируется. То есть, для любой последовательности вида
- <math>a_1 \,\leqslant\, a_2 \,\leqslant\, a_3 \,\leqslant\, \cdots</math>
существует натуральное <math>n,</math> такое что
- <math>a_n = a_{n+1} = a_{n+2} = \cdots.</math>
Аналогичным образом определяется для убывающих цепей, тогда очевидно, <math>M</math> удовлетворяет условию обрыва убывающих цепей, тогда и только тогда, когда любая нестрого убывающая последовательность его элементов стабилизируется. Эти понятия часто используются в общей алгебре — см., например, нётерово кольцо, артиново кольцо.
Специальные типы частично упорядоченных множеств
Линейно упорядоченные множества
Пусть <math>\langle M, \leqslant\rangle</math> — частично упорядоченное множество. Если в <math>M</math> любые два элемента сравнимы, то множество <math>M</math> называется линейно упорядоченным. Линейно упорядоченное множество также называют совершенно упорядоченным, или просто, упорядоченным множествомШаблон:Sfn. Таким образом, в линейно упорядоченном множестве для любых двух элементов <math>a</math> и <math>b</math> имеет место одно и только одно из соотношений: либо <math>a<b</math>, либо <math>a=b</math>, либо <math>b<a</math>.
Также всякое линейно упорядоченное подмножество частично упорядоченного множества называют цепью, то есть цепь в частично упорядоченном множестве <math>\langle M, \leqslant \rangle</math> — такое его подмножество, в котором любые два элемента сравнимы.
Из приведенных выше примеров частично упорядоченных множеств только множество действительных чисел является линейно упорядоченным. Множество действительнозначных функций на отрезке <math>[a, b]</math> (при условии <math>a<b</math>), булеан <math>\mathcal{P}(M)</math> (при <math>|M|\geqslant 2</math>), натуральные числа с отношением делимости — не являются линейно упорядоченными.
В линейно упорядоченном множестве понятия наименьшего и минимального, а также наибольшего и максимального, совпадают.
Вполне упорядоченные множества
Линейно упорядоченное множество называется вполне упорядоченным, если каждое его непустое подмножество имеет наименьший элементШаблон:Sfn. Такой порядок на множестве называется полным порядком, в контексте, где его невозможно спутать с полным порядком в смысле полных частично упорядоченных множеств.
Классический пример вполне упорядоченного множества — множество натуральных чисел <math>\mathbb{N}</math>. Утверждение о том, что любое непустое подмножество <math>\mathbb{N}</math> содержит наименьший элемент, равносильно принципу математической индукции. В качестве примера линейно упорядоченного, но не вполне упорядоченного множества можно привести множество неотрицательных чисел, упорядоченное естественным образом <math>\mathbb{R}_{+} = \{ x: x \geqslant 0\}</math>. Действительно, его подмножество <math>\{x: x > 1\}</math> не имеет наименьшего элемента.
Вполне упорядоченные множества играют исключительно важную роль в общей теории множеств.
Полное частично упорядоченное множество
Полное частично упорядоченное множество — частично упорядоченное множество, у которого есть дно — единственный элемент, который предшествует любому другому элементу и у каждого направленного подмножества которого есть точная верхняя границаШаблон:Sfn. Полные частично упорядоченные множества применяются в λ-исчислении и информатике, в частности, на них вводится топология Скотта, на основе которой строится непротиворечивая модель λ-исчисления и Шаблон:Iw. Специальным случаем полного частично упорядоченного множества является полная решётка — если любое подмножество, не обязательно направленное, имеет точную верхнюю грань, то оно оказывается полной решёткой.
Упорядоченное множество <math>M</math> тогда и только тогда является полным частично упорядоченным, когда каждая функция <math>f \colon M\rightarrow M</math>, монотонная относительно порядка (<math>a \leqslant b \Rightarrow f(a) \leqslant f(b)</math>) обладает хотя бы одной неподвижной точкой: <math>\exists _{x \in M} f(x)=x</math>.
Любое множество <math>M</math> можно превратить в полное частично упорядоченное выделением дна <math>\bot</math> и определением порядка <math>\leqslant</math> как <math>\bot \leqslant m</math> и <math>m \leqslant m</math> для всех элементов <math>m</math> множества <math>M</math>.
Теоремы о частично упорядоченных множествах
К числу фундаментальных теорем о частично упорядоченных множествах относятся принцип максимума Хаусдорфа и лемма Куратовского — Цорна. Каждая из этих теорем эквивалентна аксиоме выбора.
В теории категорий
Каждое частично упорядоченное множество (и каждый предпорядок) можно рассматривать как категорию, в которой каждое множество морфизмов <math>\mathrm{Hom}(A,B)</math> состоит не более чем из одного элемента. Например, эту категорию можно определить так: <math>\mathrm{Hom}(A,B)=\{(A,B)\}</math>, если A ≤ B (и пустое множество в противном случае); правило композиции морфизмов: (y, z)∘(x, y) = (x, z). Каждая категория-предпорядок эквивалентна частично упорядоченному множеству.
Функтор из категории-частично упорядоченного множества (то есть диаграмма, категория индексов которой является частично упорядоченным множеством) — это коммутативная диаграмма.
Примечания
Литература
См. также
