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

Аксио́ма зави́симого вы́бора — одно из ослаблений аксиомы выбора. Обычно обозначается как $𝐃𝐂$. Аксиома зависимого выбора следует из полной аксиомы выбора ($𝐀𝐂$) и влечёт за собой аксиому счётного выбора (${𝐀𝐂}_{\omega }$), таким образом, в $𝐙𝐅$ (аксиоматике Цермело — Френкеля) ${𝐀𝐂}_{\omega }<𝐃𝐂<𝐀𝐂$.

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

$\mathrm{\forall }n\in \mathbb{N}:x_{n}R{x}_{n+1}$.

Следующие утверждения эквивалентны в $𝐙𝐅$ аксиоме зависимого выбора: теорема Бэра о категорияхШаблон:Sfn; теорема Лёвенгейма — Скулема (в сильном варианте для счётных или конечных сигнатур)Шаблон:SfnШаблон:Sfn; лемма Цорна для конечных цепей. У леммы Цорна для конечных цепей есть две эквивалентных формулировки:

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

(Несмотря на то, что вторая формулировка сильнее, чем первая, они эквивалентны в $𝐙𝐅$.)

Обобщения

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

Пусть $\gamma$ — некоторый ординал. Обозначим за $X^{<\gamma }$ множество всех трансфинитных последовательностей длины меньше $\gamma$. Аксиома зависимого выбора для трансфинитных последовательностей формулируется для определённого начального ординала $\lambda$ и обозначается как ${𝐃𝐂}_{\lambda }$.

Пусть задано непустое множество $X$ и полное слева бинарное отношение $R\subset X^{<\gamma }\times X$. Тогда ${𝐃𝐂}_{\lambda }$ утверждает, что существует трансфинитная последовательность $\{a_n{\}}_{n<\lambda }$ длины $\lambda$ такая, что $\mathrm{\forall }\mu <\lambda :\{a_n{\}}_{n<\mu }R{a}_{\mu }$Шаблон:Sfn.

Аксиома ${𝐃𝐂}_{\omega }$ эквивалентна $𝐃𝐂$. Обобщения же для больших ординалов строго сильнее её, но слабее полной аксиомы выбора: $𝐃𝐂<{𝐃𝐂}_{{\omega }_1}<{𝐃𝐂}_{{\omega }_2}<\dots <𝐀𝐂$. Выполнение же ${𝐃𝐂}_{\lambda }$ для любых начальных ординалов эквивалентно полной аксиоме выбора: $(\mathrm{\forall }\lambda :{𝐃𝐂}_{\lambda })\iff 𝐀𝐂$Шаблон:Sfn.

Для аксиом ${𝐃𝐂}_{\lambda }$ есть соответствующие им эквивалентные ослабления леммы Цорна:

• если в частично упорядоченном множестве все цепи вполне упорядочены, имеют порядковый тип меньше $\lambda$ и имеют верхнюю грань, то в множестве есть максимальный элементШаблон:Sfn;
• если в частично упорядоченном множестве каждая вполне упорядоченная цепь имеет порядковый тип меньше $\lambda$ и имеет верхнюю грань, то в множестве есть максимальный элементШаблон:Sfn.

Литература

• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Книга
• Шаблон:Книга