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: Prove that {0,1}^N is uncountable.

  1. Nov 23, 2011 #1
    1. The problem statement, all variables and given/known data
    Prove that {0,1}N is uncountable.

    (N = positive integers)


    2. Relevant equations
    f: N -> {0,1}


    3. The attempt at a solution
    f(n) = 0 or 1 for every n is an element of N.
    I should treat n as the nth term of an infinitely long sequence of 0's and 1's.
     
  2. jcsd
  3. Nov 23, 2011 #2

    LCKurtz

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    Are you familiar with Cantor's diagonal argument which shows the reals are uncountable?
     
  4. Nov 23, 2011 #3
    Yes, we discussed that today in class, but I'm a bit confused on Cantor's argument. We also discussed possibly proving the statement through contradiction, assuming that it is countable.
     
  5. Nov 23, 2011 #4

    HallsofIvy

    User Avatar
    Science Advisor

    Every real number, between 0 and 1, can be written in binary notation as a list of "0"s and "1"s so your set is equivalent to the set of all real numbers between 0 and 1.
     
  6. Nov 23, 2011 #5

    LCKurtz

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    Sounds like a good plan. Kind'a like Cantor's argument...
     
  7. Nov 23, 2011 #6
    Can you explain to me what Cantor's argument is though?
     
  8. Nov 23, 2011 #7

    LCKurtz

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    You can read about it here:
    http://planetmath.org/encyclopedia/CantorsDiagonalArgument.html [Broken]
     
    Last edited by a moderator: May 5, 2017
  9. Nov 23, 2011 #8
    alright, thank you for your help!
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook