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

проверено

Упорядоченные множества

Определение 1. Множество $ S $ называется частично упорядоченным1), если на нем задано отношение частичного порядка $\preccurlyeq$.

Определение 2. Множество $ S $ называется линейно упорядоченным2), если на нем задано некоторое отношение линейного порядка $\preccurlyeq$.

Пример 1. Множество $\mathcal{P}(X)=\{U\vert U\subseteq X\}$ всех подмножеств конечного множества $X$ является частично упорядоченным множеством с бинарным отношением $\subseteq$. Но неверно, что из двух произвольных подмножеств в $X$ одно из них содержится в другом, поэтому множество $\mathcal{P}(X)$ не является линейно упорядоченным.

Верхняя и нижняя грань множества

Определение 3. Элемент $ t $ частично упорядоченного множества $ S $ называется максимальным3), если $t\preccurlyeq s$ влечет за собой $t=s$.

Определение 4. Элемент $ t $ частично упорядоченного множества $ S $ называется минимальным4), если $s\preccurlyeq t$ влечет за собой $t=s$.

Если множество $ S $ линейно упорядочено, то минимальный и максимальный элементы этого множества, если они существуют, определены единственным образом и называются наименьшим и наибольшим элементом множества, соответственно.

Определение 5. Пусть $S_0$ — подмножество частично упорядоченного множества $ S $. Говорят, что элемент $t\in S$верхняя грань5) для множества $S_0$, если $s\preccurlyeq t$ для всех $s\in S_0$. Минимальный элемент среди всех верхних граней для множества $S_0$, если он существует, называется наименьшей верхней гранью6) для множества $S_0$.

Определение 6. Пусть $S_0$ — подмножество частично упорядоченного множества $ S $. Говорят, что элемент $t\in S$нижняя грань7) для множества $S_0$, если $t\preccurlyeq s$ для всех $s\in S_0$. Максимальный элемент среди всех нижних граней для множества $S_0$, если он существует, называется наибольшей нижней гранью8) для множества $S_0$.

Пример 2. Подмножество $(-1,1)$ в $\mathbb{R}$ не имеет максимального элемента, но имеет верхнюю грань в множестве $\mathbb{R}$, в качестве которой можно выбрать любое число, не меньшее 1. Наименьшая верхняя грань для $(-1,1)$ равна 1.

Лемма Цорна

Определение 7. Множество $ S $ называется индуктивно упорядоченным9), если

  1. $ S $ — частично упорядоченное множество;
  2. любое линейно упорядоченное подмножество в $ S $ имеет верхнюю грань.

Предложение 1 (Лемма Цорна). Пусть $ S $ — непустое индуктивно упорядоченное множество, тогда в $ S $ существует по крайней мере один максимальный элемент.

Теорема Цермело

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

Пример 3. Множество натуральных чисел $\mathbb{N}$ со стандартным отношением порядка является вполне упорядоченным множеством.

Теорема 1 (Теорема Цермело). Каждое множество может быть вполне упорядочено.

См. также

Литература

1) partially ordered set
2) linearly ordered set
3) maximal element
4) minimal element
5) upper bound
6) supremum
7) lower bound
8) infimum
9) inductively ordered set
10) well-ordered set
glossary/set/ordered/partially.txt · Последние изменения: 01.10.2013 09:49:46 — master
Наверх
Яндекс.Метрика
CC Attribution-Noncommercial-Share Alike 3.0 Unported
chimeric.de = chi`s home Valid CSS Driven by DokuWiki do yourself a favour and use a real browser - get firefox!! Recent changes RSS feed Valid XHTML 1.0