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

В данной статье рассматриваются различные формулировки и доказывается эквивалентность следующих предложений:
* [[Аксиома выбора]]
* [[Теорема Цермело]]
* [[Принцип максимума Хаусдорфа]]
* [[Лемма Цорна]]

Эквивалентность этих предложений следует понимать в том смысле, что любого из них, вместе с системой [[Аксиоматика теории множеств|аксиом Цермело — Френкеля]] (ZF) для теории множеств достаточно, чтобы доказать остальные.

== Лемма Цорна и принцип максимума Хаусдорфа ==
Формулировки леммы Цорна ({{lang-en|Zorn's Lemma}}).

<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> — частично упорядоченное множество, в котором всякая цепь имеет верхнюю грань, и пусть <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> имеет верхнюю грань — ей является множество <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> — частично упорядоченное множество, <math>C_0</math> — цепь в <math>M</math>, <math>\mathfrak{M}</math> — множество всех цепей в <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> — частный случай <math>\mathcal{HM}_2</math>, когда исходная цепь — пустое множество <math>\varnothing</math>.

: <math>V.\;\mathcal{HM}_1 {\Rightarrow} \mathcal{ZL}_1</math>
Пусть <math>M</math> — частично упорядоченное множество в условии <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> — произвольное данное множество. Покажем, что его можно вполне упорядочить.

Рассмотрим совокупность <math>\mathfrak{M}</math> всех пар <math>\langle A, \leqslant_A \rangle</math>, где <math>A \subseteq M</math>, а <math>\leqslant_A</math> — отношение полного порядка на <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> — цепь в <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> — максимальный элемент, то <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 \{ b \}</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>. Кроме того ясно что она является максимальной. Таким образом, мы доказали принцип максимума Хаусдорфа.

== Аксиома выбора ==
Формулировка аксиомы выбора ({{lang-en|Axiom of Сhoice}}).

<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>\mathcal{WO} \Rightarrow \mathcal{AC}</math>

Упорядочим каждое <math>\{ S_{\alpha}\}</math>, и затем определим функцию выбора как минимальный элемент множества:
: <math>f(\alpha) = \min S_{\alpha}</math>

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

См. книгу Куроша

== Литература ==
* {{книга
|автор        = Александров П. С. 
|заглавие     = Введение в теорию множеств и общую топологию
|место        = М.
|издательство = «НАУКА»
|год          = 1977
|страниц      = 368
}}
* {{книга
|автор        = Колмогоров А. Н., Фомин С. В.
|заглавие     = Элементы теории функций и функционального анализа
|издание      = 7-е изд
|место        = М.
|издательство = «ФИЗМАТЛИТ»
|год          = 2004
|страниц      = 572
|isbn         = 5-9221-0266-4
}}
* {{книга
|автор        = Курош А. Г. 
|заглавие     = Лекции по общей алгебре
|издание      = 2-е изд
|место        = М.
|издательство = «НАУКА»
|год          = 1973
|страниц      = 400
}}
* {{книга
|автор        = Хаусдорф Ф.
|заглавие     = Теория множеств
|издание      = 4-е изд
|место        = М.
|издательство = УРСС
|год          = 2007
|страниц      =  304
|isbn         = 978-5-382-00127-2
}}

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