Утверждения, эквивалентные аксиоме выбора
В данной статье рассматриваются различные формулировки и доказывается эквивалентность следующих предложений:
Эквивалентность этих предложений следует понимать в том смысле, что любого из них, вместе с системой аксиом Цермело — Френкеля (ZF) для теории множеств достаточно, чтобы доказать остальные.
Лемма Цорна и принцип максимума Хаусдорфа
Формулировки леммы Цорна (англ. Zorn's Lemma).
[math]\displaystyle{ \mathcal{ZL}_1. }[/math] Частично упорядоченное множество, в котором любая цепь имеет верхнюю грань, содержит максимальный элемент.
[math]\displaystyle{ \mathcal{ZL}_2. }[/math] Если всякая цепь в частично упорядоченном множестве [math]\displaystyle{ M }[/math] имеет верхнюю грань, то всякий элемент из [math]\displaystyle{ M }[/math] подчинен некоторому максимальному.
[math]\displaystyle{ \mathcal{ZL}_3. }[/math] Пусть семейство множеств [math]\displaystyle{ \mathfrak{M} }[/math] обладает тем свойством, что объединение любой цепи множеств из [math]\displaystyle{ \mathfrak{M} }[/math] есть снова множество этого семейства. Тогда [math]\displaystyle{ \mathfrak{M} }[/math] содержит максимальное множество.
Формулировки принципа максимума Хаусдорфа (англ. Hausdorff Maximal Principle):
[math]\displaystyle{ \mathcal{HM}_1. }[/math] В любом частично упорядоченном множестве существует максимальное линейно упорядоченное подмножество
[math]\displaystyle{ \mathcal{HM}_2. }[/math] В частично упорядоченном множестве всякая цепь содержится в некоторой его максимальной цепи.
Будем доказывать эквивалентность этих предложений по следующей схеме:
- [math]\displaystyle{ I.\;\mathcal{ZL}_1 {\Leftrightarrow} \mathcal{ZL}_2 }[/math]
Ясно, что [math]\displaystyle{ \mathcal{ZL}_1 }[/math] следует из [math]\displaystyle{ \mathcal{ZL}_2 }[/math], поскольку в [math]\displaystyle{ \mathcal{ZL}_2 }[/math] утверждается большее: существует максимальный элемент, больший заданного [math]\displaystyle{ a }[/math]. Обратно, пусть [math]\displaystyle{ M }[/math] — частично упорядоченное множество, в котором всякая цепь имеет верхнюю грань, и пусть [math]\displaystyle{ a \in M }[/math]. Применим [math]\displaystyle{ \mathcal{ZL}_1 }[/math] к множеству [math]\displaystyle{ M^{'} = \{ m \in M \mid m \geqslant a\} }[/math]. Его максимальный элемент [math]\displaystyle{ \overline{a} }[/math] также является и максимальным элементом [math]\displaystyle{ M }[/math], и кроме того, удовлетворяет условию [math]\displaystyle{ a \leqslant \overline{a} }[/math].
- [math]\displaystyle{ II.\;\mathcal{ZL}_2 {\Rightarrow} \mathcal{ZL}_3 }[/math]
Семейство множеств [math]\displaystyle{ \mathfrak{M} }[/math] частично упорядочено по теоретико-множественному отношению включения [math]\displaystyle{ \subseteq }[/math]. Любая цепь множеств [math]\displaystyle{ \{M_{\alpha}\} }[/math] имеет верхнюю грань — ей является множество [math]\displaystyle{ \bigcup M_{\alpha} }[/math], которое по предположению принадлежит системе [math]\displaystyle{ \mathfrak{M} }[/math]. В силу [math]\displaystyle{ \mathcal{ZL}_2 }[/math] в семействе есть максимальный элемент, то есть максимальное по включению множество.
- [math]\displaystyle{ III.\;\mathcal{ZL}_3 {\Rightarrow} \mathcal{HM}_2 }[/math]
Пусть [math]\displaystyle{ M }[/math] — частично упорядоченное множество, [math]\displaystyle{ C_0 }[/math] — цепь в [math]\displaystyle{ M }[/math], [math]\displaystyle{ \mathfrak{M} }[/math] — множество всех цепей в [math]\displaystyle{ M }[/math], содержащих [math]\displaystyle{ C_0 }[/math], упорядоченных по отношению включения. Существование максимальной цепи, содержащей [math]\displaystyle{ C_0 }[/math] теперь вытекает из [math]\displaystyle{ \mathcal{ZL}_3 }[/math], применительно к [math]\displaystyle{ \mathfrak{M} }[/math], и того факта, что объединение всех множеств цепи в [math]\displaystyle{ \mathfrak{M} }[/math] («цепи цепей»), снова есть множество из [math]\displaystyle{ \mathfrak{M} }[/math].
- [math]\displaystyle{ IV.\;\mathcal{HM}_2 {\Rightarrow} \mathcal{HM}_1 }[/math]
Очевидно. [math]\displaystyle{ \mathcal{HM}_1 }[/math] — частный случай [math]\displaystyle{ \mathcal{HM}_2 }[/math], когда исходная цепь — пустое множество [math]\displaystyle{ \varnothing }[/math].
- [math]\displaystyle{ V.\;\mathcal{HM}_1 {\Rightarrow} \mathcal{ZL}_1 }[/math]
Пусть [math]\displaystyle{ M }[/math] — частично упорядоченное множество в условии [math]\displaystyle{ \mathcal{ZL}_1 }[/math]. Рассмотрим максимальную цепь [math]\displaystyle{ C }[/math] в [math]\displaystyle{ M }[/math], существование которой вытекает из [math]\displaystyle{ \mathcal{HM}_1 }[/math]. По условию эта цепь имеет верхнюю грань [math]\displaystyle{ \overline{a} }[/math]. Тогда [math]\displaystyle{ \overline{a} }[/math] является максимальным элементом [math]\displaystyle{ M }[/math], и кроме того, принадлежит цепи. Предположив противное, мы придем к противоречию с условием максимальности [math]\displaystyle{ C }[/math].
Эти рассуждения доказывают эквивалентность принципа максимума Хаусдорфа и леммы Цорна.
Теорема Цермело
Формулировка теоремы Цермело (англ. Well Ordering Principle)
[math]\displaystyle{ \mathcal{WO}. }[/math] Любое множество можно вполне упорядочить.
- [math]\displaystyle{ \mathcal{ZL}_1 \Rightarrow \mathcal{WO} }[/math]
Пусть [math]\displaystyle{ M }[/math] — произвольное данное множество. Покажем, что его можно вполне упорядочить.
Рассмотрим совокупность [math]\displaystyle{ \mathfrak{M} }[/math] всех пар [math]\displaystyle{ \langle A, \leqslant_A \rangle }[/math], где [math]\displaystyle{ A \subseteq M }[/math], а [math]\displaystyle{ \leqslant_A }[/math] — отношение полного порядка на [math]\displaystyle{ A }[/math]. На множестве [math]\displaystyle{ \mathfrak{M} }[/math] введем естественное отношение порядка: [math]\displaystyle{ \langle B, \leqslant_B \rangle }[/math] следует за [math]\displaystyle{ \langle A, \leqslant_A \rangle }[/math], если [math]\displaystyle{ \langle A, \leqslant_A \rangle }[/math] есть начальный отрезок [math]\displaystyle{ \langle B, \leqslant_B \rangle }[/math], то есть если [math]\displaystyle{ A = \{ a \in B: a \lt b\} }[/math] для некоторого [math]\displaystyle{ b \in B }[/math] и на множестве [math]\displaystyle{ A }[/math] отношения [math]\displaystyle{ \leqslant_B }[/math] совпадает с [math]\displaystyle{ \leqslant_A }[/math].
Далее докажем два утверждения.
I. В [math]\displaystyle{ \mathfrak{M} }[/math] существует максимальный элемент. Это следует из [math]\displaystyle{ \mathcal{ZL}_1 }[/math] и того факта, что если [math]\displaystyle{ \mathfrak{C} }[/math] — цепь в [math]\displaystyle{ \mathfrak{M} }[/math], то объединение всех элементов [math]\displaystyle{ C \in \mathfrak{C} }[/math] есть также элемент [math]\displaystyle{ \mathfrak{M} }[/math], который является верхней гранью цепи [math]\displaystyle{ \mathfrak{C} }[/math].
II. Если [math]\displaystyle{ \langle A, \leqslant_A \rangle }[/math] — максимальный элемент, то [math]\displaystyle{ A=M }[/math]. Если бы [math]\displaystyle{ M \setminus A }[/math] было непусто, то взяв какой-нибудь элемент [math]\displaystyle{ b \in M \setminus A }[/math], и положив [math]\displaystyle{ b\gt a }[/math] для любого [math]\displaystyle{ a \in A }[/math], мы получили бы вполне упорядоченное множество [math]\displaystyle{ A \cup \{ b \} }[/math], начальным отрезком которого является [math]\displaystyle{ A }[/math]. Это противоречит предположению о максимальности [math]\displaystyle{ \langle A, \leqslant_A \rangle }[/math].
Таким образом, мы имеем вполне упорядоченное множество [math]\displaystyle{ \langle M, \leqslant_M \rangle }[/math]. Что и требовалось доказать.
- [math]\displaystyle{ \mathcal{WO} \Rightarrow \mathcal{HM}_1 }[/math]
Пусть [math]\displaystyle{ \langle M, \preceq \rangle }[/math] — частично упорядоченное множество. В силу теоремы Цермело множество [math]\displaystyle{ M }[/math] можно вполне упорядочить. Пусть [math]\displaystyle{ \leqslant }[/math] — отношение вполнеупорядочивания на [math]\displaystyle{ M }[/math].
Определим разбиение множества [math]\displaystyle{ M }[/math] на два подмножества [math]\displaystyle{ C }[/math] и [math]\displaystyle{ \overline{C} }[/math] индукцией по вполне упорядоченному множеству [math]\displaystyle{ \langle M, \leqslant \rangle }[/math] (такой способ также называется трансфинитной рекурсией).
Пусть [math]\displaystyle{ a \in M }[/math] и все элементы [math]\displaystyle{ b \lt a }[/math] уже отнесены либо к [math]\displaystyle{ C }[/math], либо к [math]\displaystyle{ \overline{C} }[/math]. Отнесем [math]\displaystyle{ a }[/math] к [math]\displaystyle{ C }[/math], если он сравним со всеми элементами [math]\displaystyle{ C }[/math]; в противном случае отнесем его к [math]\displaystyle{ \overline{C} }[/math].
Проводя таким образом индуктивное построение по вполне упорядоченному множеству [math]\displaystyle{ \langle M, \leqslant \rangle }[/math] мы получим множества [math]\displaystyle{ C }[/math] и [math]\displaystyle{ \overline{C} }[/math]. Как видно из построения [math]\displaystyle{ C }[/math] — цепь в [math]\displaystyle{ \langle M, \preceq \rangle }[/math]. Кроме того ясно что она является максимальной. Таким образом, мы доказали принцип максимума Хаусдорфа.
Аксиома выбора
Формулировка аксиомы выбора (англ. Axiom of Сhoice).
[math]\displaystyle{ \mathcal{AC}. }[/math] Для всякого семейства непустых множеств [math]\displaystyle{ \{ S_{\alpha}\}, \alpha \in A }[/math] существует функция выбора [math]\displaystyle{ f }[/math], то есть [math]\displaystyle{ \forall \alpha \; f(\alpha) \in S_{\alpha} }[/math]
Достаточно доказать, эквивалентность [math]\displaystyle{ \mathcal{AC} }[/math] одному из предложений [math]\displaystyle{ \mathcal{ZL}, \mathcal{HM}, \mathcal{WO} }[/math]. Однако ниже приведены несколько доказательств.
[math]\displaystyle{ \mathcal{AC} \Rightarrow \mathcal{WO} }[/math]
См. книгу Хаусдорфа, или Куроша
[math]\displaystyle{ \mathcal{AC} \Rightarrow \mathcal{HM} }[/math]
Рассуждение аналогичное тому, что использовалось при доказательстве [math]\displaystyle{ \mathcal{AC} \Rightarrow \mathcal{WO} }[/math].
[math]\displaystyle{ \mathcal{WO} \Rightarrow \mathcal{AC} }[/math]
Упорядочим каждое [math]\displaystyle{ \{ S_{\alpha}\} }[/math], и затем определим функцию выбора как минимальный элемент множества:
- [math]\displaystyle{ f(\alpha) = \min S_{\alpha} }[/math]
[math]\displaystyle{ \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.