1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Cardinality of a uncountable set.

  1. Jul 11, 2010 #1
    1. The problem statement, all variables and given/known data

    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.

    2. Relevant equations

    3. 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.
  2. jcsd
  3. Jul 11, 2010 #2
    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.
  4. Jul 11, 2010 #3
    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: May 4, 2017
  5. Jul 11, 2010 #4
    Thanks a lot! I know how to do this now! :)
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook