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

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

• Аксиома выбора
• Теорема Цермело
• Принцип максимума Хаусдорфа
• Лемма Куратовского-Цорна

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

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

Формулировки леммы Цорна (англ. Zorn's Lemma).

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

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

$\mathcal{ZL}_3.$ Пусть семейство множеств $\mathfrak{M}$ обладает тем свойством, что объединение любой цепи множеств из $\mathfrak{M}$ есть снова множество этого семейства. Тогда $\mathfrak{M}$ содержит максимальное множество.

Формулировки принципа максимума Хаусдорфа (англ. Hausdorff Maximal Principle):

$\mathcal{HM}_1.$ В любом частично упорядоченном множестве существует максимальное линейно упорядоченное подмножество

$\mathcal{HM}_2.$ В частично упорядоченном множестве всякая цепь содержится в некоторой его максимальной цепи.

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

$\mathcal{ZL}_1 \quad \overset{(I)}{\Leftrightarrow} \quad \mathcal{ZL}_2 \quad \overset{(II)}{\Rightarrow} \quad \mathcal{ZL}_3 \quad \overset{(III)}{\Rightarrow} \quad \mathcal{HM}_2 \quad \overset{(IV)}{\Rightarrow} \quad \mathcal{HM}_1 \quad \overset{(V)}{\Rightarrow} \quad \mathcal{ZL}_1$

$I.\;\mathcal{ZL}_1 {\Leftrightarrow} \mathcal{ZL}_2$

Ясно, что $\mathcal{ZL}_1$ следует из $\mathcal{ZL}_2$, поскольку в $\mathcal{ZL}_2$ утверждается большее: существует максимальный элемент, больший заданного $a$. Обратно, пусть $M$ — частично упорядоченное множество, в котором всякая цепь имеет верхную грань, и пусть $a \in M$. Применим $\mathcal{ZL}_1$ к множеству $M^{'} = \{ m \in M \mid m \geqslant a\}$. Его максимальный элемент $\overline{a}$ также является и максимальным элементом $M$, и кроме того, удовлетворяет условию $a \leqslant \overline{a}$.

$II.\;\mathcal{ZL}_2 {\Rightarrow} \mathcal{ZL}_3$

Семейство множеств $\mathfrak{M}$ частично упорядочено по теоретико-множественному отношению включения $\subseteq$. Любая цепь множеств $\{M_{\alpha}\}$ имеет верхнюю грань — ей является множество $\bigcup M_{\alpha}$, которое по предположению принадлежит системе $\mathfrak{M}$. В силу $\mathcal{ZL}_2$ в семействе есть максимальный элемент, то есть максимальное по включению множество.

$III.\;\mathcal{ZL}_3 {\Rightarrow} \mathcal{HM}_2$

Пусть $M$ — частично упорядоченное множество, $C_0$ — цепь в $M$, $\mathfrak{M}$ — множество всех цепей в $M$, содержащих $C_0$, упорядоченных по отношению включения. Существование максимальной цепи, содержащей $C_0$ теперь вытекает из $\mathcal{ZL}_3$, применительно к $\mathfrak{M}$, и того факта, что объединение всех множеств цепи в $\mathfrak{M}$ («цепи цепей»), снова есть множество из $\mathfrak{M}$.

$IV.\;\mathcal{HM}_2 {\Rightarrow} \mathcal{HM}_1$

Очевидно. $\mathcal{HM}_1$ — частный случай $\mathcal{HM}_2$, когда исходная цепь — пустое множество $\varnothing$.

$V.\;\mathcal{HM}_1 {\Rightarrow} \mathcal{ZL}_1$

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

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

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

Формулировка теоремы Цермело (англ. Well Ordering Principle)

$\mathcal{WO}.$ Любое множество можно вполне упорядочить.

$\mathcal{ZL}_1 \Rightarrow \mathcal{WO}$

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

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

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

I. В $\mathfrak{M}$ существует максимальный элемент. Это следует из $\mathcal{ZL}_1$ и того факта, что если $\mathfrak{C}$ — цепь в $\mathfrak{M}$, то объединение всех элементов $C \in \mathfrak{C}$ есть также элемент $\mathfrak{M}$, который является верхней гранью цепи $\mathfrak{C}$.

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

Таким образом, мы имеем вполне упорядоченное множество $\langle M, \leqslant_M \rangle$. Что и требовалось доказать.

$\mathcal{WO} \Rightarrow \mathcal{HM}_1$

Пусть $\langle M, \preceq \rangle$ — частично упорядоченное множество. В силу теоремы Цермело множество $M$ можно вполне упорядочить. Пусть $\leqslant$ — отношение вполнеупорядочивания на $M$.

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

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

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

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

Формулировка аксиомы выбора (англ. Axiom of Сhoice).

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

Достаточно доказать, эквивалентность $\mathcal{AC}$ одному из предложений $\mathcal{ZL}, \mathcal{HM}, \mathcal{WO}$. Однако ниже приведены несколько доказательств.

$\mathcal{AC} \Rightarrow \mathcal{WO}$

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

$\mathcal{AC} \Rightarrow \mathcal{HM}$

Рассуждение аналогичное тому, что использовалось при доказательстве $\mathcal{AC} \Rightarrow \mathcal{WO}$.

$\mathcal{WO} \Rightarrow \mathcal{AC}$

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

$f(\alpha) = \min S_{\alpha}$

$\mathcal{ZL} \Rightarrow \mathcal{AC}$

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

Литература

• Александров П. С. Введение в теорию множеств и общую топологию. — М.: «НАУКА», 1977. — 368 с.
• Колмогоров А. Н., Фомин С. В. Элементы теории функций и функционального анализа. — 7-е изд. — М.: «ФИЗМАТЛИТ», 2004. — 572 с. — ISBN 5-9221-0266-4
• Курош А. Г. Лекции по общей алгебре. — 2-е изд. — М.: «НАУКА», 1973. — 400 с.
• Хаусдорф Ф. Теория множеств. — 4-е изд. — М.: УРСС, 2007. — 304 с. — ISBN 978-5-382-00127-2