Denumerability of Subsets

Given an enumeration \( a_1, a_2, \ldots, a_n, \ldots \) of a denumerable set \( A \), and an enumeration \( b_1, b_2, \ldots, b_n, \ldots \) of a denumerable set \( B \), we can enumerate \( A \cup B \) in the order \( a_1, b_1, a_2, b_2, \ldots, a_n, b_n, \ldots \). 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}^\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\colon \mathbb N \;\longrightarrow\;\mathbb N\times\mathbb N, \quad \pi(k) = (m(k),\,n(k)). \]

3. Define a new sequence \((c_k)_{k=1}^\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 = \bigl\{\,F\subseteq\mathbb{N}:\lvert F\rvert = k\bigr\} \] 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) \quad\text{with}\quad n_1<n_2<\cdots<n_k,\quad 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 \;=\; \bigl\{\,F\subseteq\mathbb{N}:\lvert F\rvert<\infty\bigr\} = \bigcup_{k=0}^\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 = \bigl\{\,X\subseteq\mathbb{N}:\lvert X\rvert=\infty\bigr\} \] 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.