MyBot в 22:59, 13 января 2014

2014-01-13T22:59:14Z

Новая страница

{{Остатье| ТИП СТАТЬИ = 1
| АВТОР1 =
| АВТОР2 =
| АВТОР3 =
| СУПЕРВАЙЗЕР =
| ПРОЕКТ =
| ПОДТЕМА =
| КАЧЕСТВО =
| УРОВЕНЬ =
| ДАТА СОЗДАНИЯ =
| ВИКИПЕДИЯ =
| НЕОДНОЗНАЧНОСТЬ =
}} [[Файл:Hasse diagram of powerset of 3.svg|right|thumb|250px|Подмножества {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>), удовлетворяющее следующим условиям<ref name="Колмогоров-36">
{{книга
|автор = Колмогоров А. Н., Фомин С. В.
|заглавие = Элементы теории функций и функционального анализа
|издание = 7-е изд
|место = М.
|издательство = «ФИЗМАТЛИТ»
|год = 2004
|страницы = 36
|страниц = 572
|isbn = 5-9221-0266-4
}}</ref>:
* [[Рефлексивность|''Рефлексивность'']]: <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>, на котором задано отношение частичного порядка, называется '''частично упорядоченным''' ({{lang-en|partially ordered set, poset}}). Если быть совсем точным<ref name="Александров-78">
{{книга
|автор = Александров П. С.
|заглавие = Введение в теорию множеств и общую топологию
|место = М.
|издательство = «НАУКА»
|год = 1977
|страницы = 78
|страниц = 368
}}</ref>, то частично упорядоченным множеством называется пара <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|right|thumb|250px|Подмножества {x, y, z}, упорядоченные отношением включения]]

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

<math>\vartriangleright</math> Пусть <math>M</math> — множество всех действительнозначных [[Функция (математика)|функций]], определенных на [[Отрезок|отрезке]] <math>[a,b]</math>, то есть функций вида
<center><math>
f \colon [a,b] \to \mathbb{R}
</math>
</center>
Введем отношение порядка <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> — действительные числа, то имет место одно и только из соотношений:
<center><math>
a < b, \qquad a=b, \qquad b<a
</math>
</center>

В случае, если <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> будут несравнимы. Возможность существования несравнимых элементов объясняет смысл термина ''«частично упорядоченное множество»''.

=== Минимальный/максимальный и наименьший/наибольший элементы ===
{{main|Максимум (математика)|Минимум (математика)}}

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

Элемент <math>a \in M</math> называется ''минимальным'' ({{lang-en|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> называется ''наименьшим'' ({{lang-en|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>. Здесь минимальными элементами будут [[Простое число|простые числа]], а вот наименьшего элемента не существует.

Аналогично вводятся понятия ''максимального'' ({{lang-en|maximal element}}) и ''наибольшего'' ({{lang-en|greatest element}}) элементов.

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

Любой элемент, больший, чем некоторая верхняя грань <math>A</math>, также будет верхней гранью <math>A</math>. А любой элемент, меньший, чем некоторая нижняя грань <math>A</math>, также будет нижней гранью <math>A</math>. Эти соображения ведут к введению понятий [[Супремум|''наименьшей верхней грани'']] ({{lang-en|least upper bound}}) и [[Инфимум|''наибольшей нижней грани'']] ({{lang-en|greatest lower bound}}).

== Специальные типы частично упорядоченных множеств ==
=== Линейно упорядоченные множества ===
{{main|Линейно упорядоченное множество}}

Пусть <math>\langle M, \leqslant\rangle</math> — частично упорядоченное множество. Если в <math>M</math> любые два элемента сравнимы, то множество <math>M</math> называется ''линейно упорядоченным'' ({{lang-en|linearly ordered set}}). Линейно упорядоченное множество также называют ''совершенно упорядоченным'' ({{lang-en|totally ordered set}}), или просто, ''упорядоченным множеством''<ref name="Колмогоров-38">
{{книга
|автор = Колмогоров А. Н., Фомин С. В.
|заглавие = Элементы теории функций и функционального анализа
|издание = 7-е изд
|место = М.
|издательство = «ФИЗМАТЛИТ»
|год = 2004
|страницы = 38
|страниц = 572
|isbn = 5-9221-0266-4
}}</ref>. Таким образом, в линейно упорядоченном множество для любых двух элементов <math>a</math> и <math>b</math> имеет место одно и только одно из соотношений: либо <math>a<b</math>, либо <math>a=b</math>, либо <math>b<a</math>.

Также всякое линейно упорядоченное подмножество частично упорядоченного множества называют ''цепью'' ({{lang-en|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>), натуральные числа с отношением делимости — не являются линейно упорядоченными.

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

=== Вполне упорядоченные множества ===
{{main|Вполне упорядоченное множество}}

Линейно упорядоченное множество называется ''вполне упорядоченным'' ({{lang-en|well-ordered}}), если каждое его непустое подмножество имеет наименьший элемент<ref name="Колмогоров-40">
{{книга
|автор = Колмогоров А. Н., Фомин С. В.
|заглавие = Элементы теории функций и функционального анализа
|издание = 7-е изд
|место = М.
|издательство = «ФИЗМАТЛИТ»
|год = 2004
|страницы = 40
|страниц = 572
|isbn = 5-9221-0266-4
}}</ref>. Соответственно, порядок на множестве называется ''полным порядком'' ({{lang-en|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žina]]
[[de:Ordnungsrelation]]
[[en:Partially ordered set]]
[[eo:Partordo]]
[[es:Conjunto parcialmente ordenado]]
[[he:סדר חלקי]]
[[hu:Részbenrendezett halmaz]]
[[it:Relazione d'ordine]]
[[ko:부분순서]]
[[nl:Partiële orde]]
[[oc:Relacion d'òrdre]]
[[ro:Relaţie de ordine]]
[[sl:Relacija urejenosti]]
[[uk:Частково впорядкована множина]]
[[zh:偏序关系]]

{{WikiCopyRight}}

{{checked_final}}[[Категория:Local]]

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

MyBot в 22:59, 13 января 2014