Cardinality of Sets Homework: Find Subsets of Natural Numbers

[A_B]

Homework Statement

The problems are to find the cardinality of several sets, a proof is not required, but there must be a decent argument.
a) What is the cardinality of the set of all subsets of the natural numbers that contain up to 5 elements?
b) What is the cardinality of the set of all finite subsets of the natural numbers?

Homework Equations

-

The Attempt at a Solution

a) I define a surjection from the lists of 5 natural numbers to a set of natural numbers as follows:
f:(a_1, a_2, a_3, a_4, a_5) = \left\{ a_1, a_2, a_3, a_4, a_5 \right\}
The set of lists is given by: \mathbb{N} \times \mathbb{N} \times \mathbb{N} \times \mathbb{N} \times \mathbb{N}.
Because the cartesian product of countable sets is itself countable, the set of lists of 5 natural numbers is also countable. Because the function above is surjective, the cardinality of the set of all subsets of the natural numbers is smaller then or equal to the cardinality of the set of lists. Because the cardinality of the set of subsets... is obviously infinite, it is countably infinite.

b) ?

PS. I can't get the curly brackets in LaTeX to work.

 

[Dick]

You've proved the set of all subsets with 5 elements is countable. So are the sets of elements with 0,1,2,3,... elements. Form a union. { is a special TeX character. Try \{ and \}.

 

[A_B]

Ha, I think I get it, a union of a countably infinite amount of countably infinite sets is itself countably infinite because of roughly the same argument the shows that \mathbb{N} \times \mathbb{N} is countably infinite. Is this correct?

I got the curly brackets to show using \left\{ and \right\}

Thanks Dick!

 

[Dick]

Sure. A countable union of countable sets is countable. And it's very much the same argument as showing NxN is countable.