# Countable set of elements chosen from Countable collection

Let $$U$$ be a countable collection of subsets of $$X$$. Then there exists a countable set which consists of elements of the elements in $$U$$.

Proof: As $$U$$ is a countable collection of subsets of $$X$$, it follows that the elements in $$U$$ can be indexed by the natural numbers. Furthermore, by the axiom of choice we can choose an element from each element of $$U$$ and form a new set $$C$$ which consists of elements of each element in $$U$$. So $$C = \{ x_n : x_n \in U_n\}$$ so we can define a map $$f$$ from $$C$$ to $$U$$ by $$f(x_n)=U_n$$ then it suffices to show that the map is injective, thus making $$C$$ countable. Suppose $$f(x_n)=f(x_m) = U_n =U_m$$: as $$U$$ is countable, $$n=m$$ hence $$x_n=x_m$$ so the map is injective and therefore $$C$$ is countable.

Is the proof correct? How could I improve it?

Your proof is mostly correct. It however needs correction on these two points:

$$\boxed{\textit{Firstly:}}$$ the axiom of choice is used on collections of non-empty sets and you never forbade your collection $$U$$ from containing $$\emptyset$$ as that is still a valid subset of $$X$$.

Hence you want to eliminate the empty set from your collection first before using the axiom of choice on it. That is you want proceed in your proof with $$U' = U - \{\emptyset\}$$ instead or say something to the effect of "without loss of generality, assume that $$U$$ does not contain $$\emptyset$$; otherwise just replace $$U$$ with $$U - \{\emptyset\}$$".

$$\boxed{\textit{Secondly:}}$$ this map you are defining from $$C$$ to $$U$$:

So $$C = \{ x_n : x_n \in U_n\}$$ so we can define a map $$f$$ from $$C$$ to $$U$$ by $$f(x_n)=U_n$$

may not be well-defined. For instance, if $$x_{1,2} \in C$$ were a common element of $$U_1$$ and $$U_2$$, then do you define $$f(x_{1,2})$$ as $$U_1$$ or $$U_2$$? And your hypotheses never mentioned that $$U$$ is a collection of disjoint subsets of $$X$$. Hence it is totally possible for $$U_1$$ and $$U_2$$ to have non-empty intersection.

The correct way to go about it is this. Simply define a map from $$C$$ to $$\Bbb N$$ directly like so (there is no need to map into $$U$$):

For each $$x \in C$$, certainly $$x \in U_k$$ for some $$k \in \Bbb N$$. So the set $$C_x \subseteq \Bbb N$$ of all $$n \in \Bbb N$$ such that $$x \in U_n$$ is non-empty (as $$n = k$$ is in there). Thus the well-ordering of $$\Bbb N$$ says that the least element of $$C_x$$ must exist; so we can define $$f(x) = \min C_x \in \Bbb N$$.

You can check that this gives an injective map from $$C$$ into $$\Bbb N$$ due to the uniqueness of minimums. And you can now conclude that $$C$$ is countable (where I am assuming finiteness is a possibility when I say "countable").

• Thanks! Can I make an argument for countability which does not require maps? – topologicalmagician Aug 11 at 9:14
• Definitions of countability itself involves maps! One such definition is: a set $S$ is countable (where finiteness is included as a possibility) iff $\exists$ an injection $f : S \to \Bbb N$. So at some level you will have to use maps or a theorem that itself uses maps to conclude countability. – 0XLR Aug 11 at 9:17
• @topologicalmagician By the way, if my answer is satisfactory consider accepting it. – 0XLR Aug 11 at 10:39