# Prove that Axiom of Dependent Choice implies Axiom of Countable Choice

Please have a look at below proof! Thank you for your help so much

1. Axiom of Dependent Choice

Let $$T \neq\varnothing$$ and $$\mathcal{R} \subseteq T^2$$ such that $$\forall a \in T, \exists b \in T: a\mathcal{R}b$$. Then there exists $$(x_n \mid n \in \mathbb N)$$ such that $$x_n \mathcal{R} x_{n+1}$$.

1. Axiom of Countable Choice

Let $$(A_n \mid n \in \mathbb N)$$ be a sequence of non-empty sets and $$X=\bigcup_{n \in \mathbb N} A_n$$. Then there exists a mapping $$f: \mathbb N \to X$$ such that $$f(n) \in A_n$$.

My proof that Axiom of Dependent Choice implies Axiom of Countable Choice:

Let $$\mathcal{R}=\{(a,b) \in X^2 \mid \exists n \in \mathbb N, a \in A_n \text{ and } b \in A_{n+1}\}$$.

$$\mathcal{R}$$ satisfies the requirement of Axiom of Dependent Choice. Hence there exists a sequence $$(x_i \mid i \in \mathbb N)$$ such that $$x_i \mathcal{R} x_{i+1}$$ where for some $$n$$, $$x_i \in A_{i+n}$$ for all $$i \in \mathbb N$$.

Let $$f:\mathbb N \to X$$ such that $$f(i) \in A(i)$$ for all $$i and $$f(i)=x_{i-n}$$ for all $$i \geq n$$.

Defining $$f$$ in this way, we get a function as desired.

PS: From @spaceisdarkgreen's answer,I fixed $$\mathcal{R}$$ as follows

Let $$Y=\{(a,i) \mid a \in A_i\}$$ and $$\mathcal{R}=\{((a,m),(b,n)) \in Y^2 \mid n=m+1\}$$.

• Would probably be best to edit below your original rather than replacing if you want to ask about your revised proof. Otherwise my answer to the previous question will be confusing. – spaceisdarkgreen Apr 24 '18 at 4:10
• I got it @spaceisdarkgreen. Let me restore the original :) – LE Anh Dung Apr 24 '18 at 4:12
• Hi @spaceisdarkgreen, I have added two proofs to my post at math.stackexchange.com/questions/2750388/…. People seem not to take notice of the detail of the proofs, could you please have a check on these proofs for me? – LE Anh Dung Apr 24 '18 at 5:28

The problem is your relation does not preclude the possibility that, say $x_1\in A_{52}$ and $x_2\in A_{53},$ but also $x_2\in A_{103}$ and $x_3\in A_{104},$ all while $x_3\notin A_{54}.$ So it is not necessarily true that there is an $n$ such that $x_i\in A_{i+n}$ for all $i.$
One trick for fixing it is would be to start by rigging the $A_i$ to be disjoint by replacing the elements $a\in A_i$ with tagged elements $\langle i,a\rangle.$
• say $x_1 \in A_{52} \implies x_2 \in A_{53} \implies x_3 \in A_{54}$. We know that, in this sequence, $x_i \mathcal{R} x_{i+1}$ for all $i \in \mathbb N$, so how can $x_1 \in A_{52}$ and $x_2 \in A_{103}$? and how can $x_2$ simultaneously belongs to $A_{53}$ and $A_{103}$? – LE Anh Dung Apr 24 '18 at 2:52
• $x_2$ can be in both since $A_{52}$ and $A_{103}$ may not be disjoint. The point is if we have $x_1\in A_{52},$ $x_2\in A_{52},$ $x_2\in A_{103},$ $x_3\in A_{104}$ and $x_3\notin A_{53},$ then by your definition, we have $x_1\mathcal R x_2$ and $x_2\mathcal R x_3.$ So the start of (or some segment of) the sequence whose existence is guaranteed by DC could be $x_1,x_2,x_3.$ But this doesn't have the property you claim/want. We can't just say $x_1\in A_{52}\to x_2\in A_{53}\to x_3\in A_{54}$... we need to make a definition of $\mathcal R$ for which the DC sequence is guaranteed this property. – spaceisdarkgreen Apr 24 '18 at 3:28