Axiom of dependent choice

In mathematics, the axiom of dependent choice, denoted by ${\displaystyle {\mathsf {DC}}}$, is a weak form of the axiom of choice (${\displaystyle {\mathsf {AC}}}$) that is still sufficient to develop much of

A homogeneous relation ${\displaystyle R}$ on ${\displaystyle X}$ is called a total relation if for every ${\displaystyle a\in X,}$ there exists some ${\displaystyle b\in X}$ such that ${\displaystyle a\,R~b}$ is true.

The axiom of dependent choice can be stated as follows: For every nonempty set ${\displaystyle X}$ and every total relation ${\displaystyle R}$ on ${\displaystyle X,}$ there exists a sequence ${\displaystyle (x_{n})_{n\in \mathbb {N} }}$ in ${\displaystyle X}$ such that

${\displaystyle x_{n}\,R~x_{n+1}}$ for all ${\displaystyle n\in \mathbb {N} .}$

In fact, x₀ may be taken to be any desired element of X. (To see this, apply the axiom as stated above to the set of finite sequences that start with x₀ and in which subsequent terms are in relation ${\displaystyle R}$, together with the total relation on this set of the second sequence being obtained from the first by appending a single term.)

If the set ${\displaystyle X}$ above is restricted to be the set of all real numbers, then the resulting axiom is denoted by ${\displaystyle {\mathsf {DC}}_{\mathbb {R} }.}$

Use

Even without such an axiom, for any ${\displaystyle n}$, one can use ordinary mathematical induction to form the first ${\displaystyle n}$ terms of such a sequence. The axiom of dependent choice says that we can form a whole (

The axiom ${\displaystyle {\mathsf {DC}}}$ is the fragment of ${\displaystyle {\mathsf {AC}}}$ that is required to show the existence of a sequence constructed by

Over ${\displaystyle {\mathsf {ZF}}}$ (Zermelo–Fraenkel set theory without the axiom of choice), ${\displaystyle {\mathsf {DC}}}$ is equivalent to the Baire category theorem for complete metric spaces.^[1]

It is also equivalent over ${\displaystyle {\mathsf {ZF}}}$ to the

${\displaystyle {\mathsf {DC}}}$ is also equivalent over ${\displaystyle {\mathsf {ZF}}}$ to the statement that every

pruned tree

with ${\displaystyle \omega }$ levels has a

branch

(proof below).

Furthermore, ${\displaystyle {\mathsf {DC}}}$ is equivalent to a weakened form of Zorn's lemma; specifically ${\displaystyle {\mathsf {DC}}}$ is equivalent to the statement that any

Proof that ${\displaystyle \,{\mathsf {DC}}\iff }$ Every pruned tree with ω levels has a branch

${\displaystyle (\,\Longleftarrow \,)}$ Let ${\displaystyle R}$ be an entire binary relation on ${\displaystyle X}$. The strategy is to define a tree ${\displaystyle T}$ on ${\displaystyle X}$ of finite sequences whose neighboring elements satisfy ${\displaystyle R.}$ Then a branch through ${\displaystyle T}$ is an infinite sequence whose neighboring elements satisfy ${\displaystyle R.}$ Start by defining ${\displaystyle \langle x_{0},\dots ,x_{n}\rangle \in T}$ if ${\displaystyle x_{k}R\,x_{k+1}}$ for ${\displaystyle 0\leq k<n.}$ Since ${\displaystyle R}$ is entire, ${\displaystyle T}$ is a pruned tree with ${\displaystyle \omega }$ levels. Thus, ${\displaystyle T}$ has a branch ${\displaystyle \langle x_{0},\dots ,x_{n},\dots \rangle .}$ So, for all ${\displaystyle n\geq 0\!:}$ ${\displaystyle \langle x_{0},\dots ,x_{n},x_{n+1}\rangle \in T,}$ which implies ${\displaystyle x_{n}R\,x_{n+1}.}$ Therefore, ${\displaystyle {\mathsf {DC}}}$ is true. ${\displaystyle (\,\Longrightarrow \,)}$ Let ${\displaystyle T}$ be a pruned tree on ${\displaystyle X}$ with ${\displaystyle \omega }$ levels. The strategy is to define a binary relation ${\displaystyle R}$ on ${\displaystyle T}$ so that ${\displaystyle {\mathsf {DC}}}$ produces a sequence ${\displaystyle t_{n}=\langle x_{0},\dots ,x_{f(n)}\rangle }$ where ${\displaystyle t_{n}R\,t_{n+1}}$ and ${\displaystyle f(n)}$ is a strictly increasing function. Then the infinite sequence ${\displaystyle \langle x_{0},\dots ,x_{k},\dots \rangle }$ is a branch. (This proof only needs to prove this for ${\displaystyle f(n)=m+n.}$) Start by defining ${\displaystyle u\,R\,v}$ if ${\displaystyle u}$ is an initial subsequence of ${\displaystyle v,\operatorname {length} (u)>0,\,}$ and ${\displaystyle \operatorname {length} (v)=}$ ${\displaystyle \operatorname {length} (u)+1.}$ Since ${\displaystyle T}$ is a pruned tree with ${\displaystyle \omega }$ levels, ${\displaystyle R}$ is entire. Therefore, ${\displaystyle {\mathsf {DC}}}$ implies that there is an infinite sequence ${\displaystyle t_{n}}$ such that ${\displaystyle t_{n}\,R\,t_{n+1}.}$ Now ${\displaystyle t_{0}=\langle x_{0},\dots ,x_{m}\rangle }$ for some ${\displaystyle m\geq 0.}$ Let ${\displaystyle x_{m+n}}$ be the last element of ${\displaystyle t_{n}.}$ Then ${\displaystyle t_{n}=\langle x_{0},\dots ,x_{m},\dots ,x_{m+n}\rangle .}$ For all ${\displaystyle k\geq 0,}$ the sequence ${\displaystyle \langle x_{0},\dots ,x_{k}\rangle }$ belongs to ${\displaystyle T}$ because it is an initial subsequence of ${\displaystyle t_{0}\,(k\leq m)}$ or it is a ${\displaystyle t_{n}\,(k\geq m).}$ Therefore, ${\displaystyle \langle x_{0},\dots ,x_{k},\dots \rangle }$ is a branch.

Relation with other axioms

Unlike full ${\displaystyle {\mathsf {AC}}}$, ${\displaystyle {\mathsf {DC}}}$ is insufficient to prove (given ${\displaystyle {\mathsf {ZF}}}$) that there is a

satisfies ${\displaystyle {\mathsf {ZF}}+{\mathsf {DC}}}$, and every set of real numbers in this model is

Lebesgue measurable

, has the Baire property and has the perfect set property.

The axiom of dependent choice implies the axiom of countable choice and is strictly stronger.^[4][5]

It is possible to generalize the axiom to produce transfinite sequences. If these are allowed to be arbitrarily long, then it becomes equivalent to the full axiom of choice.

Notes