# How to use the AC to extract a countable subset from an infinite set.

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.

• I suppose one could rephrase the argument to be the creation of a function from $\mathbb{N}$ to $X$ by at each step $n$ looking at elements of $P(X)$ that do not contain the range up to that point.
– Alan
Aug 22, 2021 at 5:14
• You don't need the full AC, just Axiom of (Countable) Dependent Choice(DC). See this question. Aug 22, 2021 at 5:14
• @user10354138 Thank you. This is plausible to me. Though I wonder why in this situation the AC seems can't be applied, while a weak form of it can be applied. Aug 22, 2021 at 5:20
• You can dress it up as pure AC + replacement + union if you want, or mimick part of the proof of the equivalence of AC, WO and Zorn. Aug 22, 2021 at 5:53
• This is practically a duplicate. Aug 22, 2021 at 9:05

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.