set theory | (parentheses)

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.

(parentheses)

ramblings and thought on Haskell, programming and logic

Tag Archives: set theory

Union of countable sets is countable.