Question

Show that the set of all finite subsets of the set of positive integers is a countable set.

Short answer

The set of all finite subsets of the set of positive integers is a countable set.

Step-by-step solution

Step: 1

Proposition: the set of all finite subsets of N is countable.

Define a set$X=\left\{A\subseteq N/Aisfinite\right\}$

Step: 2

We can have a function$g_n:N\to A_n$ for each subset such that the function is surjective ( by fundamental theorem of arithmetic). Hence each subset An is countable.

Step: 3

Union of countable sets is countable, therefore X is countable.