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

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

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

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

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

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

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

Аксіома вибору

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

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

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

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

${\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 с.(рос.)