I have done some searches on this site before I wrote this question. There were similar posts regarding this problem to some extent, but none of them was exactly what I want to ask, and none of them solved my problem (They only showed the requirement of AC).
This proposition is well known:
Every infinite set has a countable subset.
I have this proof for it:
Let $X$ be an infinite set. Since it's not empty, we have a element
$x_0 \in X$. Now we define recursively $$\begin{align*}X_0 &:= X \\
\exists x_n &\in X_n \\ X_{n+1} &:= X_n\setminus\{x_n\}\end{align*}$$
And thus we have an infinite sequence $\{x_n\}$, which gives a
countable subset of $X$.
I understand why the AC is required, as we are selecting infinitely from sets of indistinguishable elements. However, I don't know how to apply it.
In my understanding, we can only use AC when the entire collection of sets is known. In this problem, that requires us to know the entire $\{X_n\}$. But as we can see, each definition of $X_n$ is built on the previous one.
We may use finite choice and induction to show that for every $n$, $\forall m \le n, X_n \text{ is well-defined}$. But without the axiom of choice, we cannot show that all $X_n$ are well-defined. Therefore, we cannot make the whole collection of $X_n$ known without the axiom of choice. However, in order to use the axiom of choice, we must know the entire collection. This seems to be a contradiction.
So after some thoughts, I even begin to doubt if the AC can really be used in this problem.
Thank you for reading my problem.
Best Answer
The trick is that you don't actually need to know the set $\{X_n\}_{n\in\mathbb{N}}$ in order to apply AC to get the choice function you want: you just need to know some set which you can be sure will contain every $X_n$, since there's no harm in using a choice function with a larger domain than you need. So you can just take a choice function defined on the set of all nonempty subsets of $X$, and use that choice function to pick an element $x_n$ from $X_n$ in each step of your recursive definition.