Аксиома зависимого выбора

Аксиома зависимого выбора — одно из ослаблений аксиомы выбора. Обычно обозначается как $\mathbf{D}\mathbf{C}$$\mathbf {DC}$. Аксиома зависимого выбора следует из полной аксиомы выбора и влечёт за собой аксиому счётного выбора, таким образом, в $\mathbf{Z}\mathbf{F}$$\mathbf {ZF}$ $\mathbf {AC} _{\omega }<\mathbf {DC} <\mathbf {AC}$.

Формулировка: если задано произвольное непустое множество $X$$X$ с полным слева отношением $R$$R$ (отношение $R$$R$ называется полным слева, если для любого $x$$x$ существует $y$$y$, что $xRy$$xRy$), то существует такая последовательность $x_n$$x_{n}$ элементов $X$$X$, что:

$\mathrm{\forall <!--\; \forall \; -->}n\in <!--\; \in \; -->\mathbb{N}:<!--\; :\; -->x_{n}R{x}_{n+1}$$\forall n\in \mathbb {N} \colon x_{n}Rx_{n+1}$.

Следующие утверждения эквивалентны в $\mathbf{Z}\mathbf{F}$$\mathbf {ZF}$ аксиоме зависимого выбора: теорема Бэра о категориях; теорема Лёвенгейма — Скулема; лемма Цорна для конечных цепей. У леммы Цорна для конечных цепей есть две эквивалентных формулировки:

• если в частично упорядоченном множестве все цепи конечны, то множество имеет максимальный элемент.;
• если в частично упорядоченном множестве все вполне-упорядоченные цепи конечны, то множество имеет максимальный элемент.

(Несмотря на то, что вторая формулировка сильнее, чем первая, они эквивалентны в $\mathbf{Z}\mathbf{F}$$\mathbf {ZF}$.)

ОбобщенияПравить

Аксиома зависимого выбора для трансфинитных последовательностей: если в формулировке аксиомы зависимого выбора допустить не только счётные последовательности, но и трансфинитные, можно получить усиление этой аксиомы.

Пусть $\mathrm{\gamma <!--\; \gamma \; -->}$$\gamma$  — некоторый ординал. Функция $x_{\mathrm{\alpha <!--\; \alpha \; -->}}:<!--\; :\; -->\mathrm{\gamma <!--\; \gamma \; -->}\to <!--\; \to \; -->X$$x_{\alpha }\colon \gamma \to X$  называется трансфинитной последовательностью типа $\mathrm{\gamma <!--\; \gamma \; -->}$$\gamma$ . Обозначим за $S_{\mathrm{\gamma <!--\; \gamma \; -->}}$$S_{\gamma }$  множество всех последовательностей типа меньше $\mathrm{\gamma <!--\; \gamma \; -->}$$\gamma$ . Аксиома зависимого выбора для трансфинитных последовательностей формулируется для определённого начального ординала $\mathrm{\lambda <!--\; \lambda \; -->}$$\lambda$  и обозначается как ${\mathbf{D}\mathbf{C}}_{\mathrm{\lambda <!--\; \lambda \; -->}}$$\mathbf {DC} _{\lambda }$ .

Пусть задано непустое множество $X$$X$  и полное слева бинарное отношение $R\subset <!--\; \subset \; -->S_{\mathrm{\gamma <!--\; \gamma \; -->}}\times <!--\; \times \; -->X$$R\subset S_{\gamma }\times X$ . Тогда ${\mathbf{D}\mathbf{C}}_{\mathrm{\lambda <!--\; \lambda \; -->}}$$\mathbf {DC} _{\lambda }$  утверждает, что существует трансфинитная последовательность $\{a_n{\}}_{n\in <!--\; \in \; -->\mathrm{\lambda <!--\; \lambda \; -->}}$$\{a_{n}\}_{n\in \lambda }$  типа $\mathrm{\lambda <!--\; \lambda \; -->}$$\lambda$  такая, что $\forall \mu <\lambda \colon \{a_{n}\}_{n\in \mu }Ra_{\mu }$ .

Аксиома ${\mathbf{D}\mathbf{C}}_{\mathrm{\omega <!--\; \omega \; -->}}$$\mathbf {DC} _{\omega }$  эквивалентна $\mathbf{D}\mathbf{C}$$\mathbf {DC}$ . Обобщения же для больших ординалов строго сильнее её, но слабее полной аксиомы выбора: $\mathbf {DC} <\mathbf {DC} _{\omega _{1}}<\mathbf {DC} _{\omega _{2}}<\ldots <\mathbf {AC}$ . Выполнение же ${\mathbf{D}\mathbf{C}}_{\mathrm{\lambda <!--\; \lambda \; -->}}$$\mathbf {DC} _{\lambda }$  для любых начальных ординалов эквивалентно полной аксиоме выбора: $(\mathrm{\forall <!--\; \forall \; -->}\mathrm{\lambda <!--\; \lambda \; -->}:<!--\; :\; -->{\mathbf{D}\mathbf{C}}_{\mathrm{\lambda <!--\; \lambda \; -->}})\iff <!--\; \iff \; -->\mathbf{A}\mathbf{C}$$(\forall \lambda \colon \mathbf {DC} _{\lambda })\Leftrightarrow \mathbf {AC}$ .

Для аксиом ${\mathbf{D}\mathbf{C}}_{\mathrm{\lambda <!--\; \lambda \; -->}}$$\mathbf {DC} _{\lambda }$  есть соответствующие им эквивалентные ослабления леммы Цорна:

• если в частично упорядоченном множестве все цепи вполне упорядочены, имеют порядковый тип меньше $\mathrm{\lambda <!--\; \lambda \; -->}$$\lambda$  и имеют верхнюю грань, то в множестве есть максимальный элемент;
• если в частично упорядоченном множестве каждая вполне упорядоченная цепь имеет порядковый тип меньше $\mathrm{\lambda <!--\; \lambda \; -->}$$\lambda$  и имеет верхнюю грань, то в множестве есть максимальный элемент.

ЛитератураПравить

• 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.