# 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  .

###### Proposition 1.

ZF+AC implies ZF+DC.

###### 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}(r-1)$ is in $B$, and $\operatorname{seg}(r-1)\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 well-ordering principle (and hence AC) is not needed.

###### Proof.

Let $R$ be a non-empty binary relation on a set $A$ (of course non-empty). 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 non-empty.

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 non-empty 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}(j-1)$, 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(j-i+1)$ (arithmetic of finite cardinals is possible in ZF). Then $h(i)\in A_{i}$ for all $i\in\mathbb{N}$.

Finally, define $f:C\to A$ as follows: for each $A_{i}\in C$, set $f(A_{i}):=h(i)$. Then $f$ has the desired property $f(A_{i})\in A_{i}$, and the proof is complete     . ∎

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.

## References

• 1 T. Jech, Interdependence of weakened forms of the axiom of choice, Comment. Math. Univ. Carolinae 7, pp. 359-371, (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 127-130 (1948).
Title axiom of dependent choices AxiomOfDependentChoices 2013-03-22 18:46:39 2013-03-22 18:46:39 CWoo (3771) CWoo (3771) 7 CWoo (3771) Definition msc 03E25