Cardinality of sets

  • Thread starter A_B
  • Start date
  • #1
A_B
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:

Answers and Replies

  • #2
Dick
Science Advisor
Homework Helper
26,260
619
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 \}.
 
  • #3
A_B
93
1
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 [tex] \mathbb{N} \times \mathbb{N} [/tex] is countably infinite. Is this correct?

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

Thanks Dick!
 
  • #4
Dick
Science Advisor
Homework Helper
26,260
619
Sure. A countable union of countable sets is countable. And it's very much the same argument as showing NxN is countable.
 

Related Threads on Cardinality of sets

  • Last Post
Replies
6
Views
1K
  • Last Post
Replies
2
Views
4K
  • Last Post
Replies
13
Views
2K
  • Last Post
Replies
5
Views
1K
  • Last Post
Replies
4
Views
2K
  • Last Post
Replies
4
Views
2K
Replies
5
Views
1K
  • Last Post
Replies
3
Views
3K
Replies
3
Views
1K
Top