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

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

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

Эквивалентность этих предложений следует понимать в том смысле, что любого из них, вместе с системой аксиом Цермело — Френкеля (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 \{b\}$, начальным отрезком которого является $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.