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).
- For each \(m\in\mathbb N\), choose an enumeration
\[
A_m = \{\,a_{m,1},\,a_{m,2},\,a_{m,3},\dots\}.
\]
- 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)).
\]
- Define a new sequence \((c_k)_{k=1}^\infty\) by
\[
c_k \;=\; a_{\,m(k),\,n(k)}.
\]
- 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:
- 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
\]
- 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.
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:
-
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.
-
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.
