Утверждения, эквивалентные аксиоме выбора

В данной статье рассматриваются различные формулировки и доказывается эквивалентность следующих предложений:

Эквивалентность этих предложений следует понимать в том смысле, что любого из них, вместе с системой аксиом Цермело — Френкеля (ZF) для теории множеств достаточно, чтобы доказать остальные.

Лемма Цорна и принцип максимума Хаусдорфа

Формулировки леммы Цорна (Шаблон:Lang-en).

${𝒵 ℒ}_{1} .$ Частично упорядоченное множество, в котором любая цепь имеет верхнюю грань, содержит максимальный элемент.

${𝒵 ℒ}_{2} .$ Если всякая цепь в частично упорядоченном множестве $M$ имеет верхнюю грань, то всякий элемент из $M$ подчинен некоторому максимальному.

${𝒵 ℒ}_{3} .$ Пусть семейство множеств $𝔐$ обладает тем свойством, что объединение любой цепи множеств из $𝔐$ есть снова множество этого семейства. Тогда $𝔐$ содержит максимальное множество.

Формулировки принципа максимума Хаусдорфа (Шаблон:Lang-en):

${ℋ ℳ}_{1} .$ В любом частично упорядоченном множестве существует максимальное линейно упорядоченное подмножество

${ℋ ℳ}_{2} .$ В частично упорядоченном множестве всякая цепь содержится в некоторой его максимальной цепи.

Будем доказывать эквивалентность этих предложений по следующей схеме:

{𝒵 ℒ}_{1} \overset{(I)}{\Leftrightarrow} {𝒵 ℒ}_{2} \overset{(I I)}{\Rightarrow} {𝒵 ℒ}_{3} \overset{(I I I)}{\Rightarrow} {ℋ ℳ}_{2} \overset{(I V)}{\Rightarrow} {ℋ ℳ}_{1} \overset{(V)}{\Rightarrow} {𝒵 ℒ}_{1}

I . {𝒵 ℒ}_{1} \Leftrightarrow {𝒵 ℒ}_{2}

Ясно, что ${𝒵 ℒ}_{1}$ следует из ${𝒵 ℒ}_{2}$ , поскольку в ${𝒵 ℒ}_{2}$ утверждается большее: существует максимальный элемент, больший заданного $a$ . Обратно, пусть $M$ — частично упорядоченное множество, в котором всякая цепь имеет верхнюю грань, и пусть $a \in M$ . Применим ${𝒵 ℒ}_{1}$ к множеству $M^{'} = {m \in M ∣ m ⩾ a}$ . Его максимальный элемент $\overline{a}$ также является и максимальным элементом $M$ , и кроме того, удовлетворяет условию $a ⩽ \overline{a}$ .

I I . {𝒵 ℒ}_{2} \Rightarrow {𝒵 ℒ}_{3}

Семейство множеств $𝔐$ частично упорядочено по теоретико-множественному отношению включения $\subseteq$ . Любая цепь множеств ${M_{α}}$ имеет верхнюю грань — ей является множество $⋃ M_{α}$ , которое по предположению принадлежит системе $𝔐$ . В силу ${𝒵 ℒ}_{2}$ в семействе есть максимальный элемент, то есть максимальное по включению множество.

I I I . {𝒵 ℒ}_{3} \Rightarrow {ℋ ℳ}_{2}

Пусть $M$ — частично упорядоченное множество, $C_{0}$ — цепь в $M$ , $𝔐$ — множество всех цепей в $M$ , содержащих $C_{0}$ , упорядоченных по отношению включения. Существование максимальной цепи, содержащей $C_{0}$ теперь вытекает из ${𝒵 ℒ}_{3}$ , применительно к $𝔐$ , и того факта, что объединение всех множеств цепи в $𝔐$ («цепи цепей»), снова есть множество из $𝔐$ .

I V . {ℋ ℳ}_{2} \Rightarrow {ℋ ℳ}_{1}

Очевидно. ${ℋ ℳ}_{1}$ — частный случай ${ℋ ℳ}_{2}$ , когда исходная цепь — пустое множество $\emptyset$ .

V . {ℋ ℳ}_{1} \Rightarrow {𝒵 ℒ}_{1}

Пусть $M$ — частично упорядоченное множество в условии ${𝒵 ℒ}_{1}$ . Рассмотрим максимальную цепь $C$ в $M$ , существование которой вытекает из ${ℋ ℳ}_{1}$ . По условию эта цепь имеет верхнюю грань $\overline{a}$ . Тогда $\overline{a}$ является максимальным элементом $M$ , и кроме того, принадлежит цепи. Предположив противное, мы придем к противоречию с условием максимальности $C$ .

Эти рассуждения доказывают эквивалентность принципа максимума Хаусдорфа и леммы Цорна.

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

Формулировка теоремы Цермело (Шаблон:Lang-en)

$𝒲 𝒪 .$ Любое множество можно вполне упорядочить.

{𝒵 ℒ}_{1} \Rightarrow 𝒲 𝒪

Пусть $M$ — произвольное данное множество. Покажем, что его можно вполне упорядочить.

Рассмотрим совокупность $𝔐$ всех пар $⟨ A, ⩽_{A} ⟩$ , где $A \subseteq M$ , а $⩽_{A}$ — отношение полного порядка на $A$ . На множестве $𝔐$ введем естественное отношение порядка: $⟨ B, ⩽_{B} ⟩$ следует за $⟨ A, ⩽_{A} ⟩$ , если $⟨ A, ⩽_{A} ⟩$ есть начальный отрезок $⟨ B, ⩽_{B} ⟩$ , то есть если $A = {a \in B : a < b}$ для некоторого $b \in B$ и на множестве $A$ отношения $⩽_{B}$ совпадает с $⩽_{A}$ .

Далее докажем два утверждения.

I. В $𝔐$ существует максимальный элемент. Это следует из ${𝒵 ℒ}_{1}$ и того факта, что если $ℭ$ — цепь в $𝔐$ , то объединение всех элементов $C \in ℭ$ есть также элемент $𝔐$ , который является верхней гранью цепи $ℭ$ .

II. Если $⟨ A, ⩽_{A} ⟩$ — максимальный элемент, то $A = M$ . Если бы $M ∖ A$ было непусто, то взяв какой-нибудь элемент $b \in M ∖ A$ , и положив $b > a$ для любого $a \in A$ , мы получили бы вполне упорядоченное множество $A \cup {b}$ , начальным отрезком которого является $A$ . Это противоречит предположению о максимальности $⟨ A, ⩽_{A} ⟩$ .

Таким образом, мы имеем вполне упорядоченное множество $⟨ M, ⩽_{M} ⟩$ . Что и требовалось доказать.

𝒲 𝒪 \Rightarrow {ℋ ℳ}_{1}

Пусть $⟨ M, ⪯ ⟩$ — частично упорядоченное множество. В силу теоремы Цермело множество $M$ можно вполне упорядочить. Пусть $⩽$ — отношение вполнеупорядочивания на $M$ .

Определим разбиение множества $M$ на два подмножества $C$ и $\overline{C}$ индукцией по вполне упорядоченному множеству $⟨ M, ⩽ ⟩$ (такой способ также называется транфинитной рекурсией).

Пусть $a \in M$ и все элементы $b < a$ уже отнесены либо к $C$ , либо к $\overline{C}$ . Отнесем $a$ к $C$ , если он сравним со всеми элементами $C$ ; в противном случае отнесем его к $\overline{C}$ .

Проводя таким образом индуктивное построение по вполне упорядоченному множеству $⟨ M, ⩽ ⟩$ мы получим множества $C$ и $\overline{C}$ . Как видно из построения $C$ — цепь в $⟨ M, ⪯ ⟩$ . Кроме того ясно что она является максимальной. Таким образом, мы доказали принцип максимума Хаусдорфа.

Аксиома выбора

Формулировка аксиомы выбора (Шаблон:Lang-en).

$𝒜 𝒞 .$ Для всякого семейства непустых множеств ${S_{α}}, α \in A$ существует функция выбора $f$ , то есть $\forall α f (α) \in S_{α}$

Достаточно доказать, эквивалентность $𝒜 𝒞$ одному из предложений $𝒵 ℒ, ℋ ℳ, 𝒲 𝒪$ . Однако ниже приведены несколько доказательств.

$𝒜 𝒞 \Rightarrow 𝒲 𝒪$

См. книгу Хаусдорфа, или Куроша

$𝒜 𝒞 \Rightarrow ℋ ℳ$

Рассуждение аналогичное тому, что использовалось при доказательстве $𝒜 𝒞 \Rightarrow 𝒲 𝒪$ .

$𝒲 𝒪 \Rightarrow 𝒜 𝒞$

Упорядочим каждое ${S_{α}}$ , и затем определим функцию выбора как минимальный элемент множества:

f (α) = \min S_{α}

$𝒵 ℒ \Rightarrow 𝒜 𝒞$

См. книгу Куроша

Литература

Утверждения, эквивалентные аксиоме выбора

Содержание

Лемма Цорна и принцип максимума Хаусдорфа

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

Аксиома выбора

Литература

Навигация

Утверждения, эквивалентные аксиоме выбора

Лемма Цорна и принцип максимума Хаусдорфа

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

Аксиома выбора

Литература

Навигация

Поиск