You are here
Homeaxiom of dependent choices
Primary tabs
axiom of dependent choices
The axiom of dependent choices (DC), or the principle of dependent choices, is the following statement:
given a set $A$ and a binary relation $R\neq\varnothing$ on $A$ such that $\operatorname{ran}(R)\subseteq\operatorname{dom}(R)$, then there is a sequence $(a_{n})_{{n\in\mathbb{N}}}$ in $A$ such that $a_{n}Ra_{{n+1}}$.
Here, $\mathbb{N}$ is the set of all natural numbers.
The relation between DC, AC (axiom of choice), and CC (axiom of countable choice) are the following:
Proposition 1.
ZF+AC implies ZF+DC.
We prove this by using one of the equivalents of AC: Zorn’s lemma. For this proof, we define $\operatorname{seg}(n):=\{m\in\mathbb{N}\mid m\leq n\}$, the initial segment of $\mathbb{N}$ with the greatest element $n$. Before starting the proof, we need a fact about initial segments:
Lemma 1.
The union of initial segments of $\mathbb{N}$ is either $\mathbb{N}$ or an initial segment.
Proof.
Let $S$ be a set of initial segments of $\mathbb{N}$. If $s:=\bigcup S\neq\mathbb{N}$, then $B:=\mathbb{N}S\neq\varnothing$, so $B$ has a least element $r$. As a result, none of $i\in\operatorname{seg}(r1)$ is in $B$, and $\operatorname{seg}(r1)\subseteq s$. If some $m\geq r$ is in $s$, then there is an initial segment $\operatorname{seg}(n)\in S$ with $m\in\operatorname{seg}(n)$, so that $r\in\operatorname{seg}(m)\subseteq\operatorname{seg}(n)\subseteq s$, contradicting $r\in B$. ∎
Remark. The fact that $B$ in the proof above has a least element is a direct result of ZF, so the wellordering principle (and hence AC) is not needed.
We are now ready for the proof of proposition 1.
Proof.
Let $R$ be a nonempty binary relation on a set $A$ (of course nonempty). We want to find a function $f:\mathbb{N}\to\operatorname{dom}(R)$ such that $f(n)Rf(n+1)$.
Let $P$ be the set of all partial functions $f:\mathbb{N}\Rightarrow\operatorname{dom}(R)$ such that $\operatorname{dom}(f)$ is either an initial segment of $\mathbb{N}$, or $\mathbb{N}$ itself, such that $f(n)Rf(n+1)$, whenever $n,n+1\in\operatorname{dom}(f)$. Since $R\neq\varnothing$, some $(a,b)\in R$. Additionally, $b\in\operatorname{ran}(R)\subseteq\operatorname{dom}(R)$. Define function $g:\{1,2\}\to\operatorname{dom}(R)$ by $g(1)=a$ and $g(2)=b$. Then $g(1)Rg(2)$, so that $g\in P$, or $P$ is nonempty.
Partial order $P$ by inclusion so it is a poset. Let $C$ be a chain in $P$, then $h:=\bigcup C$ is a partial function from $\mathbb{N}$ to $A$. Since $\operatorname{dom}(h)$ is the union of initial segments or $\mathbb{N}$, $\operatorname{dom}(h)$ itself is either an initial segment or $\mathbb{N}$ by Lemma 1.
Now, suppose $m,m+1\in\operatorname{dom}(h)$, then $m+1\in\operatorname{dom}(s)$ for some $s\in C$, so $m\in\operatorname{dom}(s)$ as well. Therefore $s(m)Rs(m+1)$. Since $h(i)=s(i)$ for any $i\in\operatorname{dom}(s)$, we see that $h(m)Rh(m+1)$. This shows that $h\in P$, or that $C$ has an upper bound in $P$.
By Zorn’s lemma, $P$ has a maximal element $f$. We claim that $f$ is a total function. If not, then $\operatorname{dom}(f)=\{1,\ldots,n\}$ for some $n$. Since $f(n)\in\operatorname{dom}(R)$, there is some $d\in\operatorname{ran}(R)$ such that $f(n)Rd$. Define a partial function $g:\mathbb{N}\Rightarrow\operatorname{dom}(R)$ such that $\operatorname{dom}(g)=\{1,\ldots,n+1\}$, and $g(i)=f(i)$ for all $i=1,\ldots,n$, and $g(n+1)=b$. So $g\neq f$ extends $f$, contradicting the maximality of $f$. Hence, $f$ is a total function, and we are done. ∎
Proposition 2.
ZF+DC implies ZF+CC.
Proof.
Let $C$ be a countable set of nonempty sets. We assume that $C$ is countably infinite, for the finite case can be proved using ZF alone, and is left for the reader.
Since there is a bijection $\phi:C\to\mathbb{N}$, index each element in $C$ by its image in $\mathbb{N}$, so that $C=\{A_{i}\mid i\in\mathbb{N}\}$. Let $A:=\bigcup C$. We want to find a function $f:C\to A$ such that $f(A_{i})\in A_{i}$ for every $i\in\mathbb{N}$.
Define a binary relation $R$ on $A$ as follows: $aRb$ iff there is an $i\in\mathbb{N}$ such that $a\in A_{i}$ and $b\in A_{{i+1}}$. Since each $A_{i}\neq\varnothing$, $R\neq\varnothing$. Furthermore, if $b\in\operatorname{ran}(R)$, then $b\in A_{{i+1}}$ for some $i\in\mathbb{N}$. Pick any $c\in A_{{i+2}}$ (since $A_{{i+2}}\neq\varnothing$), so that $bRc$, and therefore $b\in\operatorname{dom}(R)$. This shows that $\operatorname{ran}(R)\subseteq\operatorname{dom}(R)$.
By DC, there is a function $g:\mathbb{N}\to\operatorname{dom}(R)$ such that $g(i)Rg(i+1)$ for every $i\in\mathbb{N}$. Now, $g(1)\in A_{j}$ for some $j\in\mathbb{N}$. Define a function $h:\mathbb{N}\to A$ as follows, for each $i\in\operatorname{seg}(j1)$, pick $a_{i}\in A_{i}$ and set $h(i):=a_{i}$ (this can be done by induction), and for $i\geq j$, set $h(i):=g(ji+1)$ (arithmetic of finite cardinals is possible in ZF). Then $h(i)\in A_{i}$ for all $i\in\mathbb{N}$.
However, the converses of both of these implications are false. Jensen proved the independence of DC from ZF+CC, and Mostowski and Jech proved the independence of AC from ZF+DC. In fact, it was shown that the weaker version of AC, which states that every set with cardinality at most $\aleph_{1}$ has a choice function, is independent from ZF+DC.
Remark. DC is related to Baire spaces in pointset topology. It can be shown that DC is equivalent to each of the following statements in ZF:

Any complete pseudometric space is Baire under the topology induced by the pseudometric.

Any product of compact Hausdorff spaces is Baire under the product topology.
References
 1 T. Jech, Interdependence of weakened forms of the axiom of choice, Comment. Math. Univ. Carolinae 7, pp. 359371, (1966).
 2 R. B. Jensen Independence of the axiom of dependent choices from the countable axiom of choice (abstract), Jour. Symbolic Logic 31, 294, (1966).
 3 A. Levy, Basic Set Theory, Dover Publications Inc., (2002).
 4 A. Mostowski On the principle of dependent choices, Fund. Math. 35, pp 127130 (1948).
Mathematics Subject Classification
03E25 no label found Forums
 Planetary Bugs
 HS/Secondary
 University/Tertiary
 Graduate/Advanced
 Industry/Practice
 Research Topics
 LaTeX help
 Math Comptetitions
 Math History
 Math Humor
 PlanetMath Comments
 PlanetMath System Updates and News
 PlanetMath help
 PlanetMath.ORG
 Strategic Communications Development
 The Math Pub
 Testing messages (ignore)
 Other useful stuff
 Corrections