# Axiom of Choice Implies Axiom of Dependent Choice

## Theorem

The axiom of choice implies the axiom of dependent choice.

## Proof

Let $\mathcal R$ be a binary endorelation on a non-empty set $S$ such that:

$\forall a \in S: \exists b \in S: a \mathrel{\mathcal R} b$

For an element $x \in S$, define:

$R \left({x}\right) = \left\{{y \in S: x \mathrel{\mathcal R} y}\right\}$

By assumption, $R \left({x}\right)$ is non-empty for all $x \in S$.

Now, consider the indexed family of sets:

$\left\langle{R \left({x}\right)}\right\rangle_{x \mathop \in S}$

Using the axiom of choice, there exists a mapping $f: S \to S$ such that:

$\forall x \in S: f \left({x}\right) \in R \left({x}\right)$

That is:

$x \mathrel{\mathcal R} f \left({x}\right)$

So, for any $x \in S$, the sequence:

$\left\langle{x_n}\right\rangle_{n \mathop \in \N} = \left\langle{f^n \left({x}\right)}\right\rangle_{n \mathop \in \N}$

where $f^n$ denotes the composition of $f$ with itself $n$ times, is a sequence such that:

$x_n \mathrel{\mathcal R} x_{n+1}$

for all $n \in \N$, as desired.

$\blacksquare$