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: Showing that Increasing sequences of natural numbers is uncountable

  1. Dec 12, 2011 #1
    1. The problem statement, all variables and given/known data
    Show that A, the set of all increasing sequences of natural numbers is uncountable


    2. Relevant equations
    I know that the natural numbers themselves are countable.


    3. The attempt at a solution
    I am thinking of using some sort of diagonal argument to prove this.
     
  2. jcsd
  3. Dec 12, 2011 #2
    Well take the example:

    Let R denote the reals. Let R′ denote the set of real numbers, between 0 and 1, having decimal expansions that only involve 3s and 7s. s. (This set R′ is an example of what is called a Cantor set. ) There is a bijection between R′ and the set S of infinite binary sequences. For instance, the sequence 0101001.. is mapped to .3737337.... Hence R′ is uncountable. Hope this gives you a clue on how to start.
     
    Last edited: Dec 12, 2011
  4. Dec 12, 2011 #3

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    You probably know how to show that the set of all infinite sequences of 0's and 1's is uncountable by a diagonal argument. Can you think of a bijection between infinite sequences of increasing natural numbers and infinite sequences of 0's and 1's?
     
  5. Dec 12, 2011 #4

    That's kind of what I was trying to tell him.
     
  6. Dec 12, 2011 #5

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    Yes, I see that it was. Sorry to be redundant.
     
  7. Dec 12, 2011 #6
    Not a problem he's here for our help.
     
  8. Dec 12, 2011 #7
    That helps a lot! Thank you to the both of you.
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook