Prove that the set of all finite subsets of N is countableSo

Prove that the set of all finite subsets of N is countable.

Solution

Let S_k be the set of subsets of N consisting of k elements.

Then S = _k=1 S_k.

Let fk : Sk N k be constructed as follows.

Given a set of k natural numbers A = {x1 < x2 < . . . < xk} define fk(A) = (x1, x2, . . . , xk).

By construction, fk is 1-1.

Thus |Sk| |N k | = |N|.

By the theorem from class, |S| |N| also. It’s obvious that |S| |S1| = |N.

By Shroeder-Berenstein Theorem this implies that |S| = |N|.