Axiom of dependent choice

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

${\displaystyle R}$

${\displaystyle X}$

${\displaystyle T}$

${\displaystyle X}$

${\displaystyle R.}$

${\displaystyle T}$

${\displaystyle R.}$

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

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

${\displaystyle 0\leq k<n.}$

${\displaystyle R}$

${\displaystyle T}$

${\displaystyle \omega }$

${\displaystyle T}$

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

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

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

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

${\displaystyle {\mathsf {DC}}}$

${\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.