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 \ne \mathbb{N}$ , then $B:=\mathbb{N}-S\ne \varnothing$ , so $B$ has a least element $r$ . As a result, none of $i\in \seg{r-1}$ is in $B$ , and $\seg{r-1}\subseteq s$ . If some $m \ge r$ is in $s$ , then there is an initial segment $\seg{n} \in S$ with $m\in \seg{n}$ , so that $r\in \seg{m} \subseteq \seg{n} \subseteq s$ , contradicting $r\in B$ .

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 \dom{R}$ such that $f(n) R f(n+1)$ .

Let $P$ be the set of all partial functions $f:\mathbb{N}\Rightarrow \dom{R}$ such that $\dom{f}$ is either an initial segment of $\mathbb{N}$ , or $\mathbb{N}$ itself, such that $f(n) R f(n+1)$ , whenever $n,n+1\in \dom{f}$ . Since $R\ne \varnothing$ , some $(a,b)\in R$ . Additionally, $b\in \ran{R}\subseteq \dom{R}$ . Define function $g:\lbrace 1,2\rbrace \to \dom{R}$ by $g(1)=a$ and $g(2)=b$ . Then $g(1) R g(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 $\dom{h}$ is the union of initial segments or $\mathbb{N}$ , $\dom{h}$ itself is either an initial segment or $\mathbb{N}$ by Lemma 1.

Now, suppose $m,m+1\in \dom{h}$ , then $m+1\in \dom{s}$ for some $s\in C$ , so $m\in \dom{s}$ as well. Therefore $s(m) R s(m+1)$ . Since $h(i) = s(i)$ for any $i\in \dom{s}$ , we see that $h(m) R h(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 $\dom{f}=\lbrace 1,\ldots, n\rbrace$ for some $n$ . Since $f(n)\in \dom{R}$ , there is some $d\in \ran{R}$ such that $f(n) R d$ . Define a partial function $g: \mathbb{N}\Rightarrow \dom{R}$ such that $\dom{g}=\lbrace 1,\ldots, n+1\rbrace$ , and $g(i)=f(i)$ for all $i=1,\ldots, n$ , and $g(n+1)=b$ . So $g\ne 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=\lbrace A_i\mid i\in \mathbb{N}\rbrace$ . 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: $a R b$ iff there is an $i\in \mathbb{N}$ such that $a \in A_i$ and $b\in A_{i+1}$ . Since each $A_i\ne \varnothing$ , $R\ne \varnothing$ . Furthermore, if $b\in \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}\ne \varnothing$ ), so that $b R c$ , and therefore $b\in \dom{R}$ . This shows that $\ran{R}\subseteq \dom{R}$ .

By DC, there is a function $g:\mathbb{N}\to \dom{R}$ such that $g(i) R g(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 \seg{j-1}$ , pick $a_i\in A_i$ and set $h(i):=a_i$ (this can be done by induction), and for $i\ge 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.