Твердження, еквівалентні аксіомі вибору

У статті розглядаються різні формулювання і доводиться еквівалентність таких тверджень:

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

Еквівалентність цих тверджень слід розуміти в тому сенсі, що будь-якого з них, разом із системою аксіом Цермело — Френкеля (ZF), достатньо, щоб довести інші.

Формулювання леми Цорна.

${\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 \{a\}}$, початковим відрізком якої є ${\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 }$. Крім того, ясно, що він є максимальним. Таким чином, ми довели принцип максимуму Гаусдорфа.

Формулювання аксіоми вибору:

${\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 \{S_{\alpha }\}}$, і потім визначимо функцію вибору як мінімальний елемент множини:

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

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

Див. книгу Куроша.

• Хаусдорф Ф. Теория множеств. — Москва ; Ленинград : ОНТИ, 1937. — 304 с. — ISBN 978-5-382-00127-2.(рос.)

• Александров П.С. Введение в теорию множеств и общую топологию. — Москва : Наука, 1977. — 368 с. — ISBN 5354008220.(рос.)
• Колмогоров А. Н., Фомин С. В. Элементы теории функций и функционального анализа. — 4-е изд. — Москва : Наука, 1976. — 544 с. — ISBN 5-9221-0266-4.(рос.)
• Курош А. Г. Лекции по общей алгебре. — 2 изд. — М. : Наука, 1973. — 400 с.(рос.)