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.

Advertisements

2 thoughts on “Union of countable sets is countable.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s