Аксиома зависимого выбора
Аксиома зависимого выбора — одно из ослаблений аксиомы выбора. Обычно обозначается как [math]\displaystyle{ \mathbf{DC} }[/math]. Аксиома зависимого выбора следует из полной аксиомы выбора и влечёт за собой аксиому счётного выбора, таким образом, в [math]\displaystyle{ \mathbf{ZF} }[/math] [math]\displaystyle{ \mathbf{AC}_{\omega} \lt \mathbf{DC} \lt \mathbf{AC} }[/math].
Формулировка: если задано произвольное непустое множество [math]\displaystyle{ X }[/math] с полным слева отношением [math]\displaystyle{ R }[/math] (отношение [math]\displaystyle{ R }[/math] называется полным слева, если для любого [math]\displaystyle{ x }[/math] существует [math]\displaystyle{ y }[/math], что [math]\displaystyle{ xRy }[/math]), то существует такая последовательность [math]\displaystyle{ x_n }[/math] элементов [math]\displaystyle{ X }[/math], что[1]:
- [math]\displaystyle{ \forall n \in \mathbb{N} \colon x_nRx_{n+1} }[/math].
Следующие утверждения эквивалентны в [math]\displaystyle{ \mathbf{ZF} }[/math] аксиоме зависимого выбора: теорема Бэра о категориях[2]; теорема Лёвенгейма — Скулема[3][4]; лемма Цорна для конечных цепей. У леммы Цорна для конечных цепей есть две эквивалентных формулировки:
- если в частично упорядоченном множестве все цепи конечны, то множество имеет максимальный элемент.[1];
- если в частично упорядоченном множестве все вполне-упорядоченные цепи конечны, то множество имеет максимальный элемент.[5]
(Несмотря на то, что вторая формулировка сильнее, чем первая, они эквивалентны в [math]\displaystyle{ \mathbf{ZF} }[/math].)
Обобщения
Аксиома зависимого выбора для трансфинитных последовательностей: если в формулировке аксиомы зависимого выбора допустить не только счётные последовательности, но и трансфинитные, можно получить усиление этой аксиомы.
Пусть [math]\displaystyle{ \gamma }[/math] — некоторый ординал. Функция [math]\displaystyle{ x_{\alpha} \colon \gamma \to X }[/math] называется трансфинитной последовательностью типа [math]\displaystyle{ \gamma }[/math]. Обозначим за [math]\displaystyle{ S_\gamma }[/math] множество всех последовательностей типа меньше [math]\displaystyle{ \gamma }[/math]. Аксиома зависимого выбора для трансфинитных последовательностей формулируется для определённого начального ординала [math]\displaystyle{ \lambda }[/math] и обозначается как [math]\displaystyle{ \mathbf{DC}_\lambda }[/math].
Пусть задано непустое множество [math]\displaystyle{ X }[/math] и полное слева бинарное отношение [math]\displaystyle{ R\subset S_\gamma \times X }[/math]. Тогда [math]\displaystyle{ \mathbf{DC}_\lambda }[/math] утверждает, что существует трансфинитная последовательность [math]\displaystyle{ \{a_n\}_{n\in\lambda} }[/math] типа [math]\displaystyle{ \lambda }[/math] такая, что [math]\displaystyle{ \forall \mu \lt \lambda \colon \{a_n\}_{n\in\mu} R a_\mu }[/math][5].
Аксиома [math]\displaystyle{ \mathbf{DC}_\omega }[/math] эквивалентна [math]\displaystyle{ \mathbf{DC} }[/math]. Обобщения же для больших ординалов строго сильнее её, но слабее полной аксиомы выбора: [math]\displaystyle{ \mathbf{DC} \lt \mathbf{DC}_{\omega_1} \lt \mathbf{DC}_{\omega_2} \lt \ldots \lt \mathbf{AC} }[/math]. Выполнение же [math]\displaystyle{ \mathbf{DC}_\lambda }[/math] для любых начальных ординалов эквивалентно полной аксиоме выбора: [math]\displaystyle{ (\forall\lambda\colon\mathbf{DC}_\lambda)\Leftrightarrow\mathbf{AC} }[/math][6].
Для аксиом [math]\displaystyle{ \mathbf{DC}_\lambda }[/math] есть соответствующие им эквивалентные ослабления леммы Цорна:
- если в частично упорядоченном множестве все цепи вполне упорядочены, имеют порядковый тип меньше [math]\displaystyle{ \lambda }[/math] и имеют верхнюю грань, то в множестве есть максимальный элемент[5];
- если в частично упорядоченном множестве каждая вполне упорядоченная цепь имеет порядковый тип меньше [math]\displaystyle{ \lambda }[/math] и имеет верхнюю грань, то в множестве есть максимальный элемент[5].
Примечания
- ↑ 1,0 1,1 Wolk, 1983, с. 365.
- ↑ Blair, 1977.
- ↑ Moore, 1982, с. 325.
- ↑ Boolos, 1989, с. 155.
- ↑ 5,0 5,1 5,2 5,3 Wolk, 1983, с. 366.
- ↑ Wolk, 1983, с. 367.
Литература
- Wolk Elliot S. On the principle of dependent choices and some forms of Zorn's lemma (англ.) // Canadian Mathematical Bulletin : журнал. — 1983. — Vol. 26, no. 3. — P. 365–367. — doi:10.4153/CMB-1983-062-5.
- Blair Charles E. The Baire category theorem implies the principle of dependent choices // Bull. Acad. Polon. Sci. Sér. Sci. Math. Astron. Phys. : журнал. — 1977. — Т. 25, № 10. — С. 933–934.
- Moore Gregory H. Zermelo's Axiom of Choice: Its origins, development, and influence. — Springer, 1982. — ISBN 0-387-90670-3.
- Boolos George S., Jeffrey Richard C. Computability and Logic. — 3rd. — Cambridge University Press, 1989. — ISBN 0-521-38026-X.