Tag Archives: set theory

Union of countable sets is countable.

Let’s say we have a possibly infinite countable collection of countable sets A_1, A_2, \cdots, A_n, \cdots, prove that \bigcup A_i is countable too. We are going to do this using Axiom of Choice.

Since every set A_i is countable, there is a set of injections from N to A_i, let’s call it M_i. Using the axiom of choice we can create a set of maps \{g_1, g_2, \cdots\} from N to A_i. Now, we are going to create an injection from (N, N) to \bigcup A_i. If x_k is an element of \bigcup A_i then it’s also an element of some set A_m. Therefore we can construct f(z, m) = x_k where x_k = g_m(z). And since we know that (N, N) is countable, we can map N to \bigcup A_i. QED.