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

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

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

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

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

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

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

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

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

${\displaystyle {\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}}$

${\displaystyle I.\;{\mathcal {ZL}}_{1}{\Leftrightarrow }{\mathcal {ZL}}_{2}}$

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

${\displaystyle II.\;{\mathcal {ZL}}_{2}{\Rightarrow }{\mathcal {ZL}}_{3}}$

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

${\displaystyle III.\;{\mathcal {ZL}}_{3}{\Rightarrow }{\mathcal {HM}}_{2}}$

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

${\displaystyle IV.\;{\mathcal {HM}}_{2}{\Rightarrow }{\mathcal {HM}}_{1}}$

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

${\displaystyle V.\;{\mathcal {HM}}_{1}{\Rightarrow }{\mathcal {ZL}}_{1}}$

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

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

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

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

${\displaystyle {\mathcal {ZL}}_{1}\Rightarrow {\mathcal {WO}}}$

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

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

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

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

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

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

${\displaystyle {\mathcal {WO}}\Rightarrow {\mathcal {HM}}_{1}}$

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

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

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

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

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

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

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

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

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

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

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

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

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

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

${\displaystyle {\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.