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<n$ 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\}$.

  • $\begingroup$ 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. $\endgroup$ Apr 24, 2018 at 4:10
  • $\begingroup$ I got it @spaceisdarkgreen. Let me restore the original :) $\endgroup$
    – Akira
    Apr 24, 2018 at 4:12
  • $\begingroup$ 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? $\endgroup$
    – Akira
    Apr 24, 2018 at 5:28

1 Answer 1


This is on the right track, but there is an error.

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

  • $\begingroup$ 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}$? $\endgroup$
    – Akira
    Apr 24, 2018 at 2:52
  • $\begingroup$ $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. $\endgroup$ Apr 24, 2018 at 3:28
  • $\begingroup$ @DungLe see the proof here, which uses a similar approach to yours but gets out of this problem with the tagged element trick proofwiki.org/wiki/… $\endgroup$ Apr 24, 2018 at 3:32

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .