|
|
| (5 промежуточных версий не показаны.) |
| Строка 1: |
Строка 1: |
| - | {{Остатье| ТИП СТАТЬИ = 1
| + | #redirect [[:ej:Частично упорядоченное множество]] |
| - | | АВТОР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
| + | |
| - | }}
| + | |
| - | | + | |
| - | <!-- * {{книга
| + | |
| - | |автор = Верещагин Н. К., Шень А.
| + | |
| - | |часть = 1
| + | |
| - | |заглавие = Лекции по математической логике и теории алгоритмов
| + | |
| - | |ссылка = http://www.mccme.ru/free-books/
| + | |
| - | |место = М.
| + | |
| - | |издательство = МЦНМО
| + | |
| - | |год = 2002
| + | |
| - | }}
| + | |
| - | -->
| + | |
| - | * {{книга
| + | |
| - | |автор = Колмогоров А. Н., Фомин С. В.
| + | |
| - | |заглавие = Элементы теории функций и функционального анализа
| + | |
| - | |издание = 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}}
| + | |
