Аксиома зависимого выбора - Axiom of dependent choice

В математика, то аксиома зависимого выбора, обозначаемый ${\displaystyle {\mathsf {DC}}}$, является слабой формой аксиома выбора (${\displaystyle {\mathsf {AC}}}$), которого все еще достаточно для разработки большинства реальный анализ. Он был представлен Пол Бернейс в статье 1942 года, в которой исследуется, какие теоретико-множественный аксиомы необходимы для развития анализа.^[а]

Официальное заявление

А бинарное отношение ${\displaystyle R}$ на ${\displaystyle X}$ называется весь если для каждого ${\displaystyle a\in X}$, есть некоторые ${\displaystyle b\in X}$ такой, что ${\displaystyle a\,R~b}$ правда.

Аксиому зависимого выбора можно сформулировать следующим образом: для любого непустого набор ${\displaystyle X}$ и каждое полное бинарное отношение ${\displaystyle R}$ на ${\displaystyle X,}$ существует последовательность ${\displaystyle (x_{n})_{n\in \mathbb {N} }}$ в ${\displaystyle X}$ такой, что

${\displaystyle x_{n}\,R~x_{n+1}}$ для всех ${\displaystyle n\in \mathbb {N} .}$

Если набор ${\displaystyle X}$ выше ограничено набором всех действительные числа, то полученная аксиома обозначается через ${\displaystyle {\mathsf {DC}}_{\mathbb {R} }.}$

Использовать

Даже без такой аксиомы для любого ${\displaystyle n}$, можно использовать обычную математическую индукцию для формирования первого ${\displaystyle n}$ аксиома зависимого выбора гласит, что таким образом мы можем образовать целую (счетно бесконечную) последовательность.

Аксиома ${\displaystyle {\mathsf {DC}}}$ это фрагмент ${\displaystyle {\mathsf {AC}}}$ что требуется для доказательства существования последовательности, построенной трансфинитная рекурсия из счетный length, если необходимо делать выбор на каждом этапе, и если некоторые из этих выборов не могут быть сделаны независимо от предыдущих выборов.

Эквивалентные заявления

Над Теория множеств Цермело – Френкеля ${\displaystyle {\mathsf {ZF}}}$, ${\displaystyle {\mathsf {DC}}}$ эквивалентен Теорема Бэра о категории для полных метрических пространств.^[1]

Это также эквивалентно ${\displaystyle {\mathsf {ZF}}}$ к Теорема Левенгейма – Сколема.^[b][2]

${\displaystyle {\mathsf {DC}}}$ также эквивалентен ${\displaystyle {\mathsf {ZF}}}$ к заявлению, что каждый обрезанное дерево с ${\displaystyle \omega }$ уровни имеет ответвляться (доказательство ниже).

Доказательство того, что ${\displaystyle \,{\mathsf {DC}}\iff }$ Каждое обрезанное дерево с ω уровнями имеет ветвь

${\displaystyle (\,\Longleftarrow \,)}$ Позволять ${\displaystyle R}$ быть полным бинарным отношением на ${\displaystyle X}$. Стратегия состоит в том, чтобы определить дерево ${\displaystyle T}$ на ${\displaystyle X}$ конечных последовательностей, соседние элементы которых удовлетворяют ${\displaystyle R.}$ Затем ветвь через ${\displaystyle T}$ бесконечная последовательность, соседние элементы которой удовлетворяют ${\displaystyle R.}$ Начнем с определения ${\displaystyle \langle x_{0},\dots ,x_{n}\rangle \in T}$ если ${\displaystyle x_{k}R\,x_{k+1}}$ за ${\displaystyle 0\leq k<n.}$ С ${\displaystyle R}$ целая, ${\displaystyle T}$ это обрезанное дерево с ${\displaystyle \omega }$ уровни. Таким образом, ${\displaystyle T}$ есть филиал ${\displaystyle \langle x_{0},\dots ,x_{n},\dots \rangle .}$ Итак, для всех ${\displaystyle n\geq 0\!:}$ ${\displaystyle \langle x_{0},\dots ,x_{n},x_{n+1}\rangle \in T,}$ что подразумевает ${\displaystyle x_{n}R\,x_{n+1}.}$ Следовательно, ${\displaystyle {\mathsf {DC}}}$ правда. ${\displaystyle (\,\Longrightarrow \,)}$ Позволять ${\displaystyle T}$ быть обрезанным деревом на ${\displaystyle X}$ с ${\displaystyle \omega }$ уровни. Стратегия состоит в том, чтобы определить бинарное отношение ${\displaystyle R}$ на ${\displaystyle T}$ так что ${\displaystyle {\mathsf {DC}}}$ производит последовательность ${\displaystyle t_{n}=\langle x_{0},\dots ,x_{f(n)}\rangle }$ куда ${\displaystyle t_{n}R\,t_{n+1}}$ и ${\displaystyle f(n)}$ это строго возрастающий функция. Тогда бесконечная последовательность ${\displaystyle \langle x_{0},\dots ,x_{k},\dots \rangle }$ это филиал. (Это доказательство должно доказать это только для ${\displaystyle f(n)=m+n.}$) Начнем с определения ${\displaystyle u\,R\,v}$ если ${\displaystyle u}$ является начальной подпоследовательностью ${\displaystyle v,\operatorname {length} (u)>0,\,}$ и ${\displaystyle \operatorname {length} (v)=}$ ${\displaystyle \operatorname {length} (u)+1.}$ С ${\displaystyle T}$ это обрезанное дерево с ${\displaystyle \omega }$ уровни ${\displaystyle R}$ целая. Следовательно, ${\displaystyle {\mathsf {DC}}}$ означает, что существует бесконечная последовательность ${\displaystyle t_{n}}$ такой, что ${\displaystyle t_{n}\,R\,t_{n+1}.}$ Сейчас же ${\displaystyle t_{0}=\langle x_{0},\dots ,x_{m}\rangle }$ для некоторых ${\displaystyle m\geq 0.}$ Позволять ${\displaystyle x_{m+n}}$ быть последним элементом ${\displaystyle t_{n}.}$ потом ${\displaystyle t_{n}=\langle x_{0},\dots ,x_{m},\dots ,x_{m+n}\rangle .}$ Для всех ${\displaystyle k\geq 0,}$ последовательность ${\displaystyle \langle x_{0},\dots ,x_{k}\rangle }$ принадлежит ${\displaystyle T}$ потому что это начальная подпоследовательность ${\displaystyle t_{0}\,(k\leq m)}$ или это ${\displaystyle t_{n}\,(k\geq m).}$ Следовательно, ${\displaystyle \langle x_{0},\dots ,x_{k},\dots \rangle }$ это филиал.

Связь с другими аксиомами

В отличие от полного ${\displaystyle {\mathsf {AC}}}$, ${\displaystyle {\mathsf {DC}}}$ недостаточно для доказательства (учитывая ${\displaystyle {\mathsf {ZF}}}$) что существует неизмеримый набор действительных чисел, или что существует набор действительных чисел без собственность Бэра или без идеальный набор собственности. Это следует потому, что Модель Соловея удовлетворяет ${\displaystyle {\mathsf {ZF}}+{\mathsf {DC}}}$, и каждый набор действительных чисел в этой модели измерим по Лебегу, обладает свойством Бэра и имеет свойство идеального множества.

Из аксиомы зависимого выбора следует аксиома счетного выбора и строго сильнее.^[3][4]

Примечания

1. «Основание анализа не требует полной общности теории множеств, но может быть достигнуто в более узких рамках». Бернейс, Пол (1942). «Часть III. Бесконечность и перечислимость. Анализ» (PDF). Журнал символической логики. Система аксиоматической теории множеств. 7 (2): 65–89. Дои:10.2307/2266303. JSTOR  2266303. МИСТЕР  0006333. Аксиома зависимого выбора изложена на с. 86.
2. Мур утверждает, что «Принцип зависимого выбора ${\displaystyle \Rightarrow }$ Теорема Левенхайма – Сколема », т. Е. ${\displaystyle {\mathsf {DC}}}$ следует теорема Левенгейма – Сколема. Видеть стол Мур, Грегори Х. (1982). Аксиома выбора Цермело: ее происхождение, развитие и влияние. Springer. п. 325. ISBN  0-387-90670-3.

Рекомендации

1. «Теорема Бэра о категории подразумевает принцип зависимого выбора». Блэр, Чарльз Э. (1977). «Теорема Бэра о категории подразумевает принцип зависимого выбора». Бык. Акад. Полон. Sci. Сэр. Sci. Математика. Астроном. Phys. 25 (10): 933–934.
2. В разговаривать доказано в Булос, Джордж С.; Джеффри, Ричард С. (1989). Вычислимость и логика (3-е изд.). Издательство Кембриджского университета. стр.155–156. ISBN  0-521-38026-X.
3. Бернейс доказал, что из аксиомы зависимого выбора следует аксиома счетного выбора См. Особенно п. 86 дюйм Бернейс, Пол (1942). «Часть III. Бесконечность и перечислимость. Анализ» (PDF). Журнал символической логики. Система аксиоматической теории множеств. 7 (2): 65–89. Дои:10.2307/2266303. JSTOR  2266303. МИСТЕР  0006333.
4. Для доказательства того, что из аксиомы счетного выбора не следует аксиома зависимого выбора видеть Jech, Thomas (1973), Аксиома выбора, Северная Голландия, стр. 130–131, ISBN  978-0-486-46624-8

• Jech, Томас (2003). Теория множеств (Третье тысячелетие изд.). Springer-Verlag. ISBN  3-540-44085-2. OCLC  174929965. Zbl  1007.03002.