 #1
 93
 1
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:
[tex] f:(a_1, a_2, a_3, a_4, a_5) = \left\{ a_1, a_2, a_3, a_4, a_5 \right\} [/tex]
The set of lists is given by: [tex] \mathbb{N} \times \mathbb{N} \times \mathbb{N} \times \mathbb{N} \times \mathbb{N}.[/tex]
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.
Last edited: