Cardinality of a uncountable set.

  • Thread starter R.P.F.
  • Start date
  • #1
212
0

Homework Statement



Let S be the set consisting of all sequences of 0's and 1's.

S = {(a_1, a_2, a_3,...):a_n = 0 or 1 }

Show that S is uncountable.

Homework Equations





The Attempt at a Solution



I'm not sure where to start. I think I should either assume that S~N and use proof by contradiction. Or maybe I could show that S has the same cardinality with R which means there is a bijective map between those two. Both of them don't seem easy.
I would really appreciate it if anyone could show me where to start.
 

Answers and Replies

  • #2
193
2

Homework Statement



Let S be the set consisting of all sequences of 0's and 1's.

S = {(a_1, a_2, a_3,...):a_n = 0 or 1 }

Show that S is uncountable.

Homework Equations





The Attempt at a Solution



I'm not sure where to start. I think I should either assume that S~N and use proof by contradiction. Or maybe I could show that S has the same cardinality with R which means there is a bijective map between those two. Both of them don't seem easy.
I would really appreciate it if anyone could show me where to start.
We can use the same classic approach as the one used for proving that the set of all real numbers is uncountable, namely, Cantor's diagonal argument. BWOC, suppose the set is countable. List all these sequences in some order. Then generate a sequence of your own by a method that excludes it from this list, thus arriving at a contradiction, i.e., proving S is uncountable.
 
  • #3
193
2
Here, I even found a decent explanation of this method. However, before you click the following link, please try and think of such a method by yourself. Just imagine how great you'll feel afterwards if you get it all by yourself!!

http://en.wikipedia.org/wiki/Cantor's_diagonal_argument[/SPOILER] [Broken]
 
Last edited by a moderator:
  • #4
212
0
Thanks a lot! I know how to do this now! :)
 

Related Threads on Cardinality of a uncountable set.

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