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

редактировать

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

Содержание

1 Формально оператор
2 Использование
3 Эквивалентные утверждения
4 Связь с другими аксиомами
5 Примечания
6 Ссылки

Формальный оператор

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

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

xn R xn + 1 {\ displaystyle x_ {n} \, R ~ x_ {n + 1}}

{\ displaystyle x_ {n} \, R ~ x_ {n + 1}}

для всех

n ∈ N. {\ displaystyle n \ in \ mathbb {N}.}

n \ in \ mathbb {N}.

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

Используйте

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

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

Эквивалентные утверждения

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

Он также эквивалентен $ZF {\ displaystyle {\ mathsf {ZF}}}$ ${\ displaystyle {\ mathsf {ZF}}}$ к теореме Лёвенгейма – Сколема.

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

Доказательство того, что $DC ⟺ {\ displaystyle \, {\ mathsf {DC}} \ iff}$ ${\ displaystyle \, {\ mathsf {DC}} \ iff }$ Каждое обрезанное дерево с ω-уровнями имеет ветвь
$(⟸) {\ displaystyle ( \, \ Longleftarrow \,)}$ ${\ displaystyle (\, \ Longleftarrow \,)}$ Пусть $R {\ displaystyle R}$ $R$ будет целым двоичным отношением на $X {\ displaystyle X}$ $X$ . Стратегия состоит в том, чтобы определить дерево $T {\ displaystyle T}$ $T$ на $X {\ displaystyle X}$ $X$ конечных последовательностей, соседние элементы которых удовлетворяют $R. {\ displaystyle R.}$ $R.$ Тогда ветвь через $T {\ displaystyle T}$ $T$ представляет собой бесконечную последовательность, соседние элементы которой удовлетворяют $R. {\ displaystyle R.}$ $R.$ Начнем с определения $⟨x 0,…, xn⟩ ∈ T {\ displaystyle \ langle x_ {0}, \ dots, x_ {n} \ rangle \ in T }$ ${\ displaystyle \ langle x_ {0}, \ dots, x_ {n} \ rangle \ in T}$ если $xk R xk + 1 {\ displaystyle x_ {k} R \, x_ {k + 1}}$ ${\ displaystyle x_ {k} R \, x_ {k + 1}}$ для $0 ≤ k < n. {\displaystyle 0\leq k$ ${\ displaystyle 0 \ leq k <n.}$ Поскольку $R {\ displaystyle R}$ $R$ является целым, $T {\ displaystyle T}$ $T$ является обрезанным деревом с $ω {\ displaystyle \ omega }$ $\ omega$ уровней. Таким образом, $T {\ displaystyle T}$ $T$ имеет ветвь $⟨x 0,…, x n,…⟩. {\ displaystyle \ langle x_ {0}, \ dots, x_ {n}, \ dots \ rangle.}$ ${\ displaystyle \ langle x_ { 0}, \ dots, x_ {n}, \ dots \ rangle.}$ Итак, для всех $n ≥ 0: {\ displaystyle n \ geq 0 \! :}$ ${\ displaystyle n \ geq 0 \ !:}$ $⟨x 0,…, xn, xn + 1⟩ ∈ T, {\ displaystyle \ langle x_ {0}, \ dots, x_ {n}, x_ {n + 1} \ rangle \ in T, }$ ${\ displaystyle \ langle x_ {0}, \ dots, x_ {n}, x_ {n + 1} \ rangle \ in T,}$ что подразумевает $xn R xn + 1. {\ displaystyle x_ {n} R \, x_ {n + 1}.}$ ${\ displaystyle x_ {n} R \, x_ {n + 1}.}$ Следовательно, $D C {\ displaystyle {\ mathsf {DC}}}$ ${\ displaystyle {\ mathsf {DC}}}$ верно. $(⟹) {\ displaystyle (\, \ Longrightarrow \,)}$ ${\ displaystyle (\, \ Longrightarrow \,)}$ Пусть $T {\ displaystyle T}$ $T$ будет обрезанным деревом на $X {\ displaystyle X}$ $X$ с $ω {\ displaystyle \ omega}$ $\ omega$ уровнями. Стратегия состоит в том, чтобы определить бинарное отношение $R {\ displaystyle R}$ $R$ на $T {\ displaystyle T}$ $T$ так, чтобы $DC {\ displaystyle {\ mathsf {DC}}}$ ${\ displaystyle {\ mathsf {DC}}}$ производит последовательность $tn = ⟨x 0,…, xf (n)⟩ {\ displaystyle t_ {n} = \ langle x_ {0}, \ dots, x_ {f (n)} \ rangle}$ ${\ displaystyle t_ {n} = \ langle x_ {0}, \ dots, x_ {f (n)} \ rangle}$ где $tn R tn + 1 {\ displaystyle t_ {n} R \, t_ {n + 1}}$ ${\ displaystyle t_ {n} R \, t_ { п + 1}}$ и $f (n) {\ displaystyle f (n)}$ $f (n)$ - это строго возрастающая функция. Тогда бесконечная последовательность $⟨x 0,…, x k,…⟩ {\ displaystyle \ langle x_ {0}, \ dots, x_ {k}, \ dots \ rangle}$ ${\ displaystyle \ langle x_ {0}, \ dots, x_ {k}, \ dots \ rangle}$ является ветвью. (Это доказательство необходимо только для $f (n) = m + n. {\ Displaystyle f (n) = m + n.}$ ${\ displaystyle f (n) = m + n.}$ ) Начните с определения $u R v {\ displaystyle u \, R \, v}$ ${\ displaystyle u \, R \, v}$ , если $u {\ displaystyle u}$ $u$ является начальной подпоследовательностью $v, длина ⁡ (u)>0, {\ displaystyle v, \ operatorname {length} (u)>0, \,}$ $v,\operatorname {length} (u)>0, \,$ и $длина ⁡ (v) = {\ displaystyle \ operatorname {length} (v) =}$ ${\ displaystyle \ operatorname {length} ( v) =}$ $length ⁡ (u) + 1. {\ displaystyle \ operatorname {length} (u) +1.}$ ${\ displaystyle \ operatorname {length} (u) +1.}$ Поскольку $T {\ displaystyle T}$ $T$ является обрезанным деревом с $ω {\ displaystyle \ omega}$ $\ omega$ levels, $R {\ displaystyle R}$ $R$ - целое. Следовательно, $DC {\ displaystyle {\ mathsf {DC}} }$ ${\ displaystyle {\ mathsf {DC}}}$ подразумевает, что существует бесконечная последовательность $tn {\ displaystyle t_ {n}}$ $t_ {n}$ такая, что $tn R tn + 1. {\ Displaystyle t_ {n} \, R \, t_ {n + 1}.}$ ${\ displaystyle t_ {n} \, R \, t_ {n + 1}.}$ N ow $t 0 = ⟨x 0,…, xm⟩ {\ displaystyle t_ {0} = \ langle x_ {0}, \ dots, x_ {m} \ rangle}$ ${\ displaystyle t_ {0 } = \ langle x_ {0}, \ dots, x_ {m} \ rangle}$ для некоторых $m ≥ 0. {\ displaystyle m \ geq 0.}$ ${\ displaystyle m \ geq 0.}$ Пусть $xm + n {\ displaystyle x_ {m + n}}$ ${\ displaystyle x_ {m + n}}$ будет последним элементом $тн. {\ displaystyle t_ {n}.}$ ${\ displaystyle t_ {n}.}$ Тогда $t n = ⟨x 0,…, x m,…, x m + n⟩. {\ displaystyle t_ {n} = \ langle x_ {0}, \ dots, x_ {m}, \ dots, x_ {m + n} \ rangle.}$ ${\ displaystyle t_ {n} = \ langle x_ {0}, \ dots, x_ {m}, \ точки, x_ {m + n} \ rangle.}$ Для всех $k ≥ 0, {\ displaystyle k \ geq 0,}$ ${\ displaystyle k \ geq 0,}$ последовательность $⟨x 0,…, xk⟩ {\ displaystyle \ langle x_ {0}, \ dots, x_ {k} \ rangle}$ ${\ displaystyle \ langle x_ {0}, \ dots, x_ {k} \ rangle}$ принадлежит $T {\ displaystyle T}$ $T$ , потому что это начальная подпоследовательность $t 0 (k ≤ m) {\ displaystyle t_ {0} \, (k \ leq m)}$ ${\ displaystyle t_ {0} \, (k \ leq m)}$ или это $tn (k ≥ m). {\ displaystyle t_ {n} \, (k \ geq m).}$ ${\ displaystyle t_ {n} \, (k \ geq m).}$ Следовательно, $⟨x 0,…, xk,…⟩ {\ displaystyle \ langle x_ {0}, \ dots, x_ {k}, \ dots \ rangle}$ ${\ displaystyle \ langle x_ {0}, \ dots, x_ {k}, \ dots \ rangle}$ - ветвь.

Доказательство того, что

DC ⟺ {\ displaystyle \, {\ mathsf {DC}} \ iff}

{\ displaystyle \, {\ mathsf {DC}} \ iff }

Каждое обрезанное дерево с ω-уровнями имеет ветвь

(⟸) {\ displaystyle ( \, \ Longleftarrow \,)}

{\ displaystyle (\, \ Longleftarrow \,)}

Пусть

R {\ displaystyle R}

R

будет целым двоичным отношением на

X {\ displaystyle X}

X

. Стратегия состоит в том, чтобы определить дерево

T {\ displaystyle T}

T

на

X {\ displaystyle X}

X

конечных последовательностей, соседние элементы которых удовлетворяют

R. {\ displaystyle R.}

R.

Тогда ветвь через

T {\ displaystyle T}

T

представляет собой бесконечную последовательность, соседние элементы которой удовлетворяют

R. {\ displaystyle R.}

R.

Начнем с определения

⟨x 0,…, xn⟩ ∈ T {\ displaystyle \ langle x_ {0}, \ dots, x_ {n} \ rangle \ in T }

{\ displaystyle \ langle x_ {0}, \ dots, x_ {n} \ rangle \ in T}

если

xk R xk + 1 {\ displaystyle x_ {k} R \, x_ {k + 1}}

{\ displaystyle x_ {k} R \, x_ {k + 1}}

для

0 ≤ k < n. {\displaystyle 0\leq k

{\ displaystyle 0 \ leq k <n.}

Поскольку

R {\ displaystyle R}

R

является целым,

T {\ displaystyle T}

T

является обрезанным деревом с

ω {\ displaystyle \ omega }

\ omega

уровней. Таким образом,

T {\ displaystyle T}

T

имеет ветвь

⟨x 0,…, x n,…⟩. {\ displaystyle \ langle x_ {0}, \ dots, x_ {n}, \ dots \ rangle.}

{\ displaystyle \ langle x_ { 0}, \ dots, x_ {n}, \ dots \ rangle.}

Итак, для всех

n ≥ 0: {\ displaystyle n \ geq 0 \! :}

{\ displaystyle n \ geq 0 \ !:}

⟨x 0,…, xn, xn + 1⟩ ∈ T, {\ displaystyle \ langle x_ {0}, \ dots, x_ {n}, x_ {n + 1} \ rangle \ in T, }

{\ displaystyle \ langle x_ {0}, \ dots, x_ {n}, x_ {n + 1} \ rangle \ in T,}

что подразумевает

xn R xn + 1. {\ displaystyle x_ {n} R \, x_ {n + 1}.}

{\ displaystyle x_ {n} R \, x_ {n + 1}.}

Следовательно,

D C {\ displaystyle {\ mathsf {DC}}}

{\ displaystyle {\ mathsf {DC}}}

верно.

$(⟹) {\ displaystyle (\, \ Longrightarrow \,)}$ ${\ displaystyle (\, \ Longrightarrow \,)}$ Пусть $T {\ displaystyle T}$ $T$ будет обрезанным деревом на $X {\ displaystyle X}$ $X$ с $ω {\ displaystyle \ omega}$ $\ omega$ уровнями. Стратегия состоит в том, чтобы определить бинарное отношение $R {\ displaystyle R}$ $R$ на $T {\ displaystyle T}$ $T$ так, чтобы $DC {\ displaystyle {\ mathsf {DC}}}$ ${\ displaystyle {\ mathsf {DC}}}$ производит последовательность $tn = ⟨x 0,…, xf (n)⟩ {\ displaystyle t_ {n} = \ langle x_ {0}, \ dots, x_ {f (n)} \ rangle}$ ${\ displaystyle t_ {n} = \ langle x_ {0}, \ dots, x_ {f (n)} \ rangle}$ где $tn R tn + 1 {\ displaystyle t_ {n} R \, t_ {n + 1}}$ ${\ displaystyle t_ {n} R \, t_ { п + 1}}$ и $f (n) {\ displaystyle f (n)}$ $f (n)$ - это строго возрастающая функция. Тогда бесконечная последовательность $⟨x 0,…, x k,…⟩ {\ displaystyle \ langle x_ {0}, \ dots, x_ {k}, \ dots \ rangle}$ ${\ displaystyle \ langle x_ {0}, \ dots, x_ {k}, \ dots \ rangle}$ является ветвью. (Это доказательство необходимо только для $f (n) = m + n. {\ Displaystyle f (n) = m + n.}$ ${\ displaystyle f (n) = m + n.}$ ) Начните с определения $u R v {\ displaystyle u \, R \, v}$ ${\ displaystyle u \, R \, v}$ , если $u {\ displaystyle u}$ $u$ является начальной подпоследовательностью $v, длина ⁡ (u)>0, {\ displaystyle v, \ operatorname {length} (u)>0, \,}$ $v,\operatorname {length} (u)>0, \,$ и $длина ⁡ (v) = {\ displaystyle \ operatorname {length} (v) =}$ ${\ displaystyle \ operatorname {length} ( v) =}$ $length ⁡ (u) + 1. {\ displaystyle \ operatorname {length} (u) +1.}$ ${\ displaystyle \ operatorname {length} (u) +1.}$ Поскольку $T {\ displaystyle T}$ $T$ является обрезанным деревом с $ω {\ displaystyle \ omega}$ $\ omega$ levels, $R {\ displaystyle R}$ $R$ - целое. Следовательно, $DC {\ displaystyle {\ mathsf {DC}} }$ ${\ displaystyle {\ mathsf {DC}}}$ подразумевает, что существует бесконечная последовательность $tn {\ displaystyle t_ {n}}$ $t_ {n}$ такая, что $tn R tn + 1. {\ Displaystyle t_ {n} \, R \, t_ {n + 1}.}$ ${\ displaystyle t_ {n} \, R \, t_ {n + 1}.}$ N ow $t 0 = ⟨x 0,…, xm⟩ {\ displaystyle t_ {0} = \ langle x_ {0}, \ dots, x_ {m} \ rangle}$ ${\ displaystyle t_ {0 } = \ langle x_ {0}, \ dots, x_ {m} \ rangle}$ для некоторых $m ≥ 0. {\ displaystyle m \ geq 0.}$ ${\ displaystyle m \ geq 0.}$ Пусть $xm + n {\ displaystyle x_ {m + n}}$ ${\ displaystyle x_ {m + n}}$ будет последним элементом $тн. {\ displaystyle t_ {n}.}$ ${\ displaystyle t_ {n}.}$ Тогда $t n = ⟨x 0,…, x m,…, x m + n⟩. {\ displaystyle t_ {n} = \ langle x_ {0}, \ dots, x_ {m}, \ dots, x_ {m + n} \ rangle.}$ ${\ displaystyle t_ {n} = \ langle x_ {0}, \ dots, x_ {m}, \ точки, x_ {m + n} \ rangle.}$ Для всех $k ≥ 0, {\ displaystyle k \ geq 0,}$ ${\ displaystyle k \ geq 0,}$ последовательность $⟨x 0,…, xk⟩ {\ displaystyle \ langle x_ {0}, \ dots, x_ {k} \ rangle}$ ${\ displaystyle \ langle x_ {0}, \ dots, x_ {k} \ rangle}$ принадлежит $T {\ displaystyle T}$ $T$ , потому что это начальная подпоследовательность $t 0 (k ≤ m) {\ displaystyle t_ {0} \, (k \ leq m)}$ ${\ displaystyle t_ {0} \, (k \ leq m)}$ или это $tn (k ≥ m). {\ displaystyle t_ {n} \, (k \ geq m).}$ ${\ displaystyle t_ {n} \, (k \ geq m).}$ Следовательно, $⟨x 0,…, xk,…⟩ {\ displaystyle \ langle x_ {0}, \ dots, x_ {k}, \ dots \ rangle}$ ${\ displaystyle \ langle x_ {0}, \ dots, x_ {k}, \ dots \ rangle}$ - ветвь.

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

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

Аксиома зависимого выбора подразумевает аксиому счетного выбора и является строго более сильной.

Примечания

Ссылки

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