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").

  • $\begingroup$ Thanks! Can I make an argument for countability which does not require maps? $\endgroup$ – topologicalmagician Aug 11 '19 at 9:14
  • $\begingroup$ 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. $\endgroup$ – 0XLR Aug 11 '19 at 9:17
  • $\begingroup$ @topologicalmagician By the way, if my answer is satisfactory consider accepting it. $\endgroup$ – 0XLR Aug 11 '19 at 10:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.