Содержание

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

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

проверено

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

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

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

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

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

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

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

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

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

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

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

Лемма Цорна

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

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

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

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

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

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

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

См. также

Трансфинитная индукция

Литература

теория множеств, верхняя грань, вполне упорядоченное множество, индуктивно упорядоченное множество, лемма цорна, линейно упорядоченное множество, максимальный элемент, минимальный элемент, наибольший элемент, наименьший элемент, нижняя грань, отношение линейного порядка, отношение частичного порядка, теорема цермело, частично упорядоченное множество

¹⁾

partially ordered set

²⁾

linearly ordered set

³⁾

maximal element

⁴⁾

minimal element

⁵⁾

upper bound

⁶⁾

supremum

⁷⁾

lower bound

⁸⁾

infimum

⁹⁾

inductively ordered set

¹⁰⁾

well-ordered set

glossary/set/ordered/partially.txt · Последние изменения: 01.10.2013 05:49:46 — Администратор

Наверх