Finite Subsets of N: Proving Countability

[kingtaf]

Prove that the collection F(N) of all finite subsets of N (natural numbers) is countable.

 

[hochs]

Countable union of countable sets is countable.
For each n > 0, the number of subsets having cardinality n is countable. There's the empty set for n = 0 also.

 

[Outlined]

you have to look at the maximal element in an S in F(N). After that consider there are 2^{max(S) - 1} sets in F(N) which have max(S) as a maximum. Hope this helps.

 

[willem2]

It's easy to construct a bijection from this set to N, by mapping the set to a string of 1's and 0's and so construct a binary number.