Exercise 1561Logic, sets and proofs › Countability and cardinalityM1Added 3 Nov 2026

Finite subsets of $\mathbb{N}$

#finite subsets#countable#naturals

Statement

Show that the set of finite subsets of $\mathbb{N}$ is countable.

Hint

Each finite subset is contained in some $\{0,1,\ldots,n-1\}$ .

Show solutionHide solution

Union. Let $\mathcal{F}_n=\{S\subseteq\mathbb{N}:\max S<n\text{ or }S=\emptyset\}$ . Each $\mathcal{F}_n$ is finite (of size $2^n$ ).

Union. The set of finite subsets is $\bigcup_n\mathcal{F}_n$ , a countable union of finite sets.

Conclusion. The set of finite subsets of $\mathbb{N}$ is countable.