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

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

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

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

== Лема Цорна і принцип максимуму Гаусдорфа ==
Формулювання леми Цорна.

<math>\mathcal{ZL}_1.</math> [[Частково впорядкована множина]], в якій будь-який ланцюг має верхню грань, містить максимальний елемент.

<math>\mathcal{ZL}_2.</math> Якщо будь-який ланцюг у частково впорядкованій множині <math>M</math> має верхню грань, то будь-який елемент із <math>M</math> підпорядкований деякому максимальному.

<math>\mathcal{ZL}_3.</math> Нехай [[сімейство множин]] <math>\mathfrak{M}</math> володіє тією властивістю, що об'єднання будь-якого ланцюга множин з <math>\mathfrak{M}</math> є знову множиною цього сімейства. Тоді <math>\mathfrak{M}</math> містить максимальну множину.

Формулювання принципу максимуму Гаусдорфа ({{Lang-en|Hausdorff Maximal Principle}}):

<math>\mathcal{HM}_1.</math> У будь-якій частково впорядкованій множині існує максимальна лінійно впорядкована підмножина.

<math>\mathcal{HM}_2.</math> У частково впорядкованій множині кожен ланцюг міститься в деякому її максимальному ланцюгу.

Еквівалентність цих пропозицій доводитимемо за такою схемою:<center><math>
\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
</math></center>

: <math>I.\;\mathcal{ZL}_1 {\Leftrightarrow} \mathcal{ZL}_2</math>

Ясно, що <math>\mathcal{ZL}_1</math> випливає із <math>\mathcal{ZL}_2</math>, оскільки в <math>\mathcal{ZL}_2</math> стверджується більше: існує максимальний елемент, більший від заданого <math>a</math>. І навпаки, нехай <math>M</math>&nbsp;— частково впорядкована множина, в якій будь-який ланцюг має верхню грань, і нехай <math>a \in M</math>. Застосуємо <math>\mathcal{ZL}_1</math> до множини <math>M^{'} = \{ m \in M \mid m \geqslant a\}</math>. Її максимальний елемент <math>\overline{a}</math> також є і максимальним елементом <math>M</math>, і, крім того, задовольняє умові <math>a \leqslant \overline{a}</math>.

: <math>II.\;\mathcal{ZL}_2 {\Rightarrow} \mathcal{ZL}_3</math>

Сімейство множин <math>\mathfrak{M}</math> частково впорядковане за теоретико-множинним відношенням включення <math>\subseteq</math>. Будь-який ланцюг множин <math>\{M_{\alpha}\}</math> має верхню грань&nbsp;— це множина <math>\bigcup M_{\alpha}</math>, яка, за припущенням, належить системі <math>\mathfrak{M}</math>. У силу <math>\mathcal{ZL}_2</math> в сімействі є максимальний елемент, тобто максимальна за включенням множина.

: <math>III.\;\mathcal{ZL}_3 {\Rightarrow} \mathcal{HM}_2</math>

Нехай <math>M</math>&nbsp;— частково впорядкована множина, <math>C_0</math>&nbsp;— ланцюг у <math>M</math>, <math>\mathfrak{M}</math>&nbsp;— множина всіх ланцюгів у <math>M</math>, що містять <math>C_0</math>, упорядкованих відносно включення. Існування максимального ланцюга, що містить <math>C_0</math>, тепер випливає із <math>\mathcal{ZL}_3</math>, стосовно до <math>\mathfrak{M}</math>, і того факту, що об'єднання всіх множин ланцюга в <math>\mathfrak{M}</math> («ланцюги ланцюгів»), знову є множиною з <math>\mathfrak{M}</math>.

: <math>IV.\;\mathcal{HM}_2 {\Rightarrow} \mathcal{HM}_1</math>

Очевидно. <math>\mathcal{HM}_1</math>&nbsp;— окремий випадок <math>\mathcal{HM}_2</math>, коли початковий ланцюг&nbsp;— порожня множина <math>\varnothing</math>.

: <math>V.\;\mathcal{HM}_1 {\Rightarrow} \mathcal{ZL}_1</math>

Нехай <math>M</math>&nbsp;— частково впорядкована множина в умові <math>\mathcal{ZL}_1</math>. Розглянемо максимальний ланцюг <math>C</math> в <math>M</math>, існування якого випливає з <math>\mathcal{HM}_1</math>. За умовою цей ланцюг має верхню грань <math>\overline{a}</math>. Тоді <math>\overline{a}</math> є максимальним елементом <math>M</math>, і крім того, належить ланцюгу. Припустивши протилежне, ми прийдемо до суперечності з умовою максимальності <math>C</math>.

Ці міркування доводять еквівалентність принципу максимуму Гаусдорфа і леми Цорна.

== Теорема Цермело ==
{{Докладніше|Теорема Цермело}}
Формулювання теореми Цермело ({{Lang-en|Well Ordering Principle}})

<math>\mathcal{WO}.</math> Будь-яку множину можна цілком упорядкувати.

: <math>\mathcal{ZL}_1 \Rightarrow \mathcal{WO}</math>

Нехай <math>M</math>&nbsp;— довільна дана множина. Покажемо, що її можна цілком упорядкувати.

Розглянемо сукупність <math>\mathfrak{M}</math> усіх пар <math>\langle A, \leqslant_A \rangle</math>, де <math>A \subseteq M</math>, а <math>\leqslant_A</math>&nbsp;— відношення повного порядку на <math>A</math>. На множині <math>\mathfrak{M}</math> уведемо природне відношення порядку: <math>\langle B, \leqslant_B \rangle</math> слідує за <math>\langle A, \leqslant_A \rangle</math>, якщо <math>\langle A, \leqslant_A \rangle</math> є [[початковий відрізок]] <math>\langle B, \leqslant_B \rangle</math>, тобто якщо <math>A = \{ a \in B: a < b\}</math> для деякого <math>b \in B</math> і на множині <math>A</math> відношення <math>\leqslant_B</math> збігається з <math>\leqslant_A</math>.

Далі доведемо два твердження.

I. ''В <math>\mathfrak{M}</math> існує максимальний елемент.'' Це випливає із <math>\mathcal{ZL}_1</math> і того факту, що якщо <math>\mathfrak{C}</math>&nbsp;— ланцюг у <math>\mathfrak{M}</math>, то об'єднання всіх елементів <math>C \in \mathfrak{C}</math> є також елементом <math>\mathfrak{M}</math>, який є верхньою гранню ланцюга <math>\mathfrak{C}</math>.

II. ''Якщо <math>\langle A, \leqslant_A \rangle</math>&nbsp;— максимальний елемент, то <math>A=M</math>''. Якби <math>M \setminus A</math> була непорожньою, то взявши який-небудь елемент <math>b \in M \setminus A</math>, і поклавши <math>b>a</math> для будь-якого <math>a \in A</math>, ми отримали б цілком упорядковану множину <math>A \cup \{ a \}</math>, початковим відрізком якої є <math>A</math>. Це суперечить припущенню про максимальність <math>\langle A, \leqslant_A \rangle</math>.

Таким чином, ми маємо цілком упорядковану множину <math>\langle M, \leqslant_M \rangle</math>. Що й потрібно було довести.

: <math>\mathcal{WO} \Rightarrow \mathcal{HM}_1</math>

Нехай <math>\langle M, \preceq \rangle</math>  частково впорядкована множина. В силу теореми Цермело множину <math>M</math> можна цілком упорядкувати. Нехай <math>\leqslant</math> ''—'' відношення цілкомупорядкування на <math>M</math>.

Визначимо розбиття множини <math>M</math> на дві підмножини <math>C</math> і <math>\overline{C}</math> індукцією за цілком упорядкованою множиною <math>\langle M, \leqslant \rangle</math> (такий спосіб також називають [[Трансфінітна рекурсія|трансфінітною рекурсією]]).

Нехай <math>a \in M</math> і всі елементи <math>b < a</math> вже віднесено або до <math>C</math>, або до <math>\overline{C}</math>. Віднести <math>a</math> до <math>C</math>, якщо він порівняємо з усіма елементами <math>C</math>; в іншому випадку віднесемо його до <math>\overline{C}</math>.

Проводячи таким чином індуктивну побудову за цілком впорядкованою множиною <math>\langle M, \leqslant \rangle</math> ми отримаємо множини <math>C</math> і <math>\overline{C}</math>. Як видно з побудови <math>C</math> ''—'' ланцюг в <math>\langle M, \preceq \rangle</math>. Крім того, ясно, що він є максимальним. Таким чином, ми довели принцип максимуму Гаусдорфа.

== Аксіома вибору ==
{{Докладніше|Аксіома вибору}}
Формулювання аксіоми вибору:

<math>\mathcal{AC}.</math> Для кожного сімейства непорожніх множин <math>\{ S_{\alpha}\}, \alpha \in A</math> існує функція вибору <math>f</math>, тобто <math>\forall \alpha \; f(\alpha) \in S_{\alpha}</math>

Достатньо довести еквівалентність <math>\mathcal{AC}</math> одному з тверджень <math>\mathcal{ZL}, \mathcal{HM}, \mathcal{WO}</math>. Однак нижче наведено декілька доведень.

<math>\mathcal{AC} \Rightarrow \mathcal{WO}</math>

Див. книгу Гаусдорфа, або Куроша.

<math>\mathcal{AC} \Rightarrow \mathcal{HM}</math>

Міркування аналогічне тому, що використовувалося для доведення <math>\mathcal{AC} \Rightarrow \mathcal{WO}</math>.

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

: <math>f(\alpha) = \min S_{\alpha}</math>

<math>\mathcal{ZL} \Rightarrow \mathcal{AC}</math>

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

== Джерела ==
* {{Хаусдорф.Теория множеств}}
* {{Александров.Введение в теорию множеств и общую топологию}}
* {{Колмогоров.Фомин}}
* {{Курош.Лекции по общей алгебре}}


[[Категорія:Аксіома вибору]]
[[Категорія:Теорія множин]]