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

Вы находитесь на сайте "Архив статей из ЭЕЭ и статей на еврейские темы из Википедии"

(Различия между версиями)

Версия 10:09, 19 апреля 2010


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

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

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

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

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

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

Содержание

1 Определение и примеры
2 Связанные определения
3 Специальные типы частично упорядоченных множеств
- 3.1 Линейно упорядоченные множества
- 3.2 Вполне упорядоченные множества
4 Теоремы о частично упорядоченных множествах
5 Примечания
6 Литература
7 См. также

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

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

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

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

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

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

Примеры

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

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

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

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

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

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

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

$\vartriangleright$ Множество всех натуральных чисел $\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$ называется минимальным (англ. minimal element), если не существует элемента $b < a$ . Другими словами, $a$ — минимальный элемент, если для любого элемента $b \in M$ либо $b > a$ , либо $b = a$ , либо $b$ и $a$ несравнимы. Элемент $a$ называется наименьшим (англ. least element, lower bound (opp. upper bound)), если для любого элемента $b \in M$ имеет место неравенство $b \geqslant a$ . Очевидно, всякий наименьший элемент является также минимальным, но обратное в общем случае неверно: минимальный элемент $a$ может и не быть наименьшим, если существуют элементы $b$ , не сравнимые с $a$ .

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Примечания

↑ Колмогоров А. Н., Фомин С. В. Элементы теории функций и функционального анализа. — 7-е изд. — М.: «ФИЗМАТЛИТ», 2004. — С. 36. — 572 с. — ISBN 5-9221-0266-4
↑ Александров П. С. Введение в теорию множеств и общую топологию. — М.: «НАУКА», 1977. — С. 78. — 368 с.
↑ Колмогоров А. Н., Фомин С. В. Элементы теории функций и функционального анализа. — 7-е изд. — М.: «ФИЗМАТЛИТ», 2004. — С. 38. — 572 с. — ISBN 5-9221-0266-4
↑ Колмогоров А. Н., Фомин С. В. Элементы теории функций и функционального анализа. — 7-е изд. — М.: «ФИЗМАТЛИТ», 2004. — С. 40. — 572 с. — ISBN 5-9221-0266-4

Литература

Александров П. С. Введение в теорию множеств и общую топологию. — М.: «НАУКА», 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, которая в дальнейшем изменялась, исправлялась и редактировалась.

[.D0.9A.D0.BE.D0.BB.D0.BC.D0.BE.D0.B3.D0.BE.D1.80.D0.BE.D0.B2-36-0] Колмогоров А. Н., Фомин С. В. Элементы теории функций и функционального анализа. — 7-е изд. — М.: «ФИЗМАТЛИТ», 2004. — С. 36. — 572 с. — ISBN 5-9221-0266-4

[.D0.90.D0.BB.D0.B5.D0.BA.D1.81.D0.B0.D0.BD.D0.B4.D1.80.D0.BE.D0.B2-78-1] Александров П. С. Введение в теорию множеств и общую топологию. — М.: «НАУКА», 1977. — С. 78. — 368 с.

[.D0.9A.D0.BE.D0.BB.D0.BC.D0.BE.D0.B3.D0.BE.D1.80.D0.BE.D0.B2-38-2] Колмогоров А. Н., Фомин С. В. Элементы теории функций и функционального анализа. — 7-е изд. — М.: «ФИЗМАТЛИТ», 2004. — С. 38. — 572 с. — ISBN 5-9221-0266-4

[.D0.9A.D0.BE.D0.BB.D0.BC.D0.BE.D0.B3.D0.BE.D1.80.D0.BE.D0.B2-40-3] Колмогоров А. Н., Фомин С. В. Элементы теории функций и функционального анализа. — 7-е изд. — М.: «ФИЗМАТЛИТ», 2004. — С. 40. — 572 с. — ISBN 5-9221-0266-4

[1]

[2]

[3]

[4]

@@ Строка 11: / Строка 11: @@
 | ВИКИПЕДИЯ =
 | НЕОДНОЗНАЧНОСТЬ   =
-}}[[Файл:Hasse diagram of powerset of 3.svg|right|thumb|250px|Подмножества {x, y, z}, упорядоченные отношением включения]]
+}}  [[Файл:Hasse diagram of powerset of 3.svg|right|thumb|250px|Подмножества {x, y, z}, упорядоченные отношением включения]]
 '''Частично упорядоченное множество''' — [[Математика|математическое]] понятие, которое формализует интуитивные идеи упорядочивания, расположения в определенной последовательности и т. п. Неформально говоря, множество частично упорядочено, если указано, какие элементы ''следуют'' (''больше'' и т. п.) за какими. При этом в общем случае может оказаться так, что некоторые пары элементов не связаны отношением «следует за».