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

Статья на основе материалов из Википедии
Есть другие значения: Упорядоченное множество

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

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

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

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

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

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

Отношение частичного порядка обычно обозначают символом `\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)` является нестрогим порядком.

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

Интервал

Для ab замкнутый интервал a,b — это множество элементов x, удовлетворяющих неравенству axb (т.е. ax и xb). Интервал содержит, по меньшей мере, элементы a и b.

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

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

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

Частично упорядоченное множество является , если любой интервал конечен. Например, целые числа локально конечны по их естественному упорядочению. Лексикографический порядок на прямом произведении ℕ×ℕ не является локально конечным, поскольку, например, (1,2)≤(1,3)≤(1,4)≤(1,5)≤...≤(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` и `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` удовлетворяет условию обрыва убывающих цепей, тогда и только тогда, когда любая нестрого убывающая последовательность его элементов стабилизируется. Эти понятия часто используются в общей алгебре — см., например, нётерово кольцо, артиново кольцо.

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

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

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

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

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

Из приведенных выше примеров частично упорядоченных множеств только множество действительных чисел является линейно упорядоченным. Множество действительнозначных функций на отрезке `b ` (при условии `a

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

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

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

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

Классический пример вполне упорядоченного множества — множество натуральных чисел `\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)\}` , если AB (и пустое множество в противном случае); правило композиции морфизмов: (y, z)∘(x, y) = (x, z''). Каждая категория-предпорядок эквивалентна частично упорядоченному множеству.

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

Примечания

    Литература

      См. также