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

Тип статьи:	Регулярная статья

Файл:Hasse diagram of powerset of 3.svg

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

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

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

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

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

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

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

Множество <math>M</math>, на котором задано отношение частичного порядка, называется частично упорядоченным (англ. partially ordered set, poset). Если быть совсем точным, то частично упорядоченным множеством называется пара <math>\langle M, \varphi \rangle</math>, где <math>M</math> — множество, а <math>\varphi</math> — отношение частичного порядка на <math>M</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>

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

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

Примеры

Файл:Hasse diagram of powerset of 3.svg

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

<math>\vartriangleright</math> Как уже указывалось выше, множество действительных чисел <math>\mathbb{R}</math> частично упорядочено по отношению «меньше либо равно» <math>\leqslant</math>.

<math>\vartriangleright</math> Пусть <math>M</math> — множество всех действительнозначных функций, определенных на отрезке <math>[a,b]</math>, то есть функций вида

<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>\vartriangleright</math> Пусть <math>M</math> — некоторое множество. Множество <math>\mathcal{P}(M)</math> всех подмножеств <math>M</math> (так называемый булеан), частично упорядочено по включению <math>M \subseteq N</math>.

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

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

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

Если <math>a</math> и <math>b</math> — действительные числа, то имет место одно и только из соотношений:

<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> называется минимальным (англ. minimal element), если не существует элемента <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> называется наименьшим (англ. least element, lower bound (opp. upper bound)), если для любого элемента <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>. Здесь минимальными элементами будут простые числа, а вот наименьшего элемента не существует.

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

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

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

Любой элемент, больший, чем некоторая верхняя грань <math>A</math>, также будет верхней гранью <math>A</math>. А любой элемент, меньший, чем некоторая нижняя грань <math>A</math>, также будет нижней гранью <math>A</math>. Эти соображения ведут к введению понятий наименьшей верхней грани (англ. least upper bound) и наибольшей нижней грани (англ. greatest lower bound).

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

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

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

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

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

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

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

Линейно упорядоченное множество называется вполне упорядоченным (англ. well-ordered), если каждое его непустое подмножество имеет наименьший элемент. Соответственно, порядок на множестве называется полным порядком (англ. well-order).

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

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

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

К числу фундаментальных теорем о частично упорядоченных множествах относятся принцип максимума Хаусдорфа и лемма Куратовского-Цорна. Эти утверждения эквивалентны между собой и существенно опираются на так называемую аксиому выбора (в действительности, эквивалентны аксиоме выбора).

Литература

• Александров П. С. Введение в теорию множеств и общую топологию. — М.: «НАУКА», 1977. — 368 с.

• Колмогоров А. Н., Фомин С. В. Элементы теории функций и функционального анализа. — 7-е изд. — М.: «ФИЗМАТЛИТ», 2004. — 572 с. — ISBN 5-9221-0266-4
• Хаусдорф Ф. Теория множеств. — 4-е изд. — М.: УРСС, 2007. — 304 с. — ISBN 978-5-382-00127-2

См. также

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

cs:Uspořádaná množinaeo:Partordohu:Részbenrendezett halmazko:부분순서 nl:Partiële orde oc:Relacion d'òrdre ro:Relaţie de ordine sl:Relacija urejenostizh:偏序关系

Уведомление: Предварительной основой данной статьи была аналогичная статья в http://ru.wikipedia.org, на условиях CC-BY-SA, http://creativecommons.org/licenses/by-sa/3.0, которая в дальнейшем изменялась, исправлялась и редактировалась.