Denumerability of Subsets

Given an enumeration $a_1,a_2,\dots ,a_n,\dots$ of a denumerable set $A$, and an enumeration $b_1,b_2,\dots ,b_n,\dots$ of a denumerable set $B$, we can enumerate $A\cup B$ in the order $a_1,b_1,a_2,b_2,\dots ,a_n,b_n,\dots$. Write a more general version of this statement for the union of arbitrarily many denumerable sets.

More generally, one shows:

Theorem.
If $\{A_m{\}}_{m\in \mathbb{N}}$ is a countable family of countable (denumerable) sets, then
$$\bigcup _{m=1}^{\mathrm{\infty }}{A}_m$$ is itself countable.

Proof sketch (by explicit enumeration).

1. For each $m\in \mathbb{N}$, choose an enumeration

$$A_m=\{a_{m,1},a_{m,2},a_{m,3},\dots \}.$$

2. Recall that $\mathbb{N}\times \mathbb{N}$ is countable. Fix any bijection

$$\pi :\mathbb{N}⟶\mathbb{N}\times \mathbb{N},\pi (k)=(m(k),n(k)).$$

3. Define a new sequence $(c_k{)}_{k=1}^{\mathrm{\infty }}$ by

$$c_k=a_{m(k),n(k)}.$$

4. Then $\{c_1,c_2,c_3,\dots \}$ lists every element of $\bigcup _m{A}_m$

(possibly with repetitions), showing that $\bigcup _m{A}_m$ is countable.

---

Equivalently, if you prefer a “diagonal” style ordering without naming a particular pairing function, you can say:

1. List all pairs $(m,n)\in \mathbb{N}\times \mathbb{N}$ in a single sequence, for example by moving along the diagonals

$$(1,1),(1,2),(2,1),(1,3),(2,2),(3,1),\dots$$

2. Whenever $(m,n)$ appears in that list, write down the $n$-th element of $A_m$, namely $a_{m,n}$.

Because every pair $(m,n)$ will eventually appear, every element of every $A_m$ will be listed. Hence a countable union of countable sets is countable.

The set of all infinite subsets of $\mathbb{N}$ cannot be denumerable; show this by showing that the set of all finite subsets of $\mathbb{N}$ is denumerable, and then applying the above theorem.

First, partition the collection of all finite subsets of $\mathbb{N}$ by their cardinality. For each $k\in \mathbb{N}$, let $${\mathcal{F}}_k=\{F\subseteq \mathbb{N}:|F|=k\}$$ be the family of all $k$-element subsets of $\mathbb{N}$. Then:

1. Each ${\mathcal{F}}_k$ is denumerable.
   An easy way to see this is to observe that any $k$-element subset can be written uniquely as an increasing $k$-tuple $$(n_1,n_2,\dots ,n_k)\text{with}{n}_1<n_2<\cdots <n_k,n_i\in \mathbb{N}.$$ The set of all such increasing $k$-tuples is a subset of ${\mathbb{N}}^k$, and ${\mathbb{N}}^k$ is denumerable (e.g.\ by the diagonal‐pairing argument). Hence each ${\mathcal{F}}_k$ is denumerable.

2. The set of all finite subsets is a countable union of the ${\mathcal{F}}_k$.
   $$\mathcal{F}=\{F\subseteq \mathbb{N}:|F|<\mathrm{\infty }\}=\bigcup _{k=0}^{\mathrm{\infty }}{\mathcal{F}}_k.$$ By the theorem you just proved, a countable union of denumerable sets is denumerable. Therefore $\mathcal{F}$ is denumerable.

---

Now let $$\mathcal{I}=\{X\subseteq \mathbb{N}:|X|=\mathrm{\infty }\}$$ be the collection of infinite subsets of $\mathbb{N}$. Notice that every subset of $\mathbb{N}$ is either finite or infinite, so $$\mathcal{P}(\mathbb{N})=\mathcal{F}\cup \mathcal{I}.$$ Suppose, for the sake of contradiction, that $\mathcal{I}$ were denumerable. Then $\mathcal{F}$ is denumerable (as shown above), so by the union theorem again, $$\mathcal{P}(\mathbb{N})=\mathcal{F}\cup \mathcal{I}$$ would be a union of two denumerable sets, hence itself denumerable. But this contradicts Cantor’s theorem that $\mathcal{P}(\mathbb{N})$ is uncountable. Therefore our assumption was false, and $\mathcal{I}$ cannot be denumerable. In other words, the family of all infinite subsets of $\mathbb{N}$ is uncountable.