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: Countability calculation help

  1. Sep 23, 2010 #1
    1. The problem statement, all variables and given/known data
    Is the set of all functions from {0,1} countable or uncountable? Provide a 1-1 correspondence with a set of know cardinality.



    2. Relevant equations



    3. The attempt at a solution
    I say it is countable, but my problem is I don't really know how to provide a 1-1 correspondence.
     
  2. jcsd
  3. Sep 23, 2010 #2

    Office_Shredder

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Re: Countability

    The set of all functions from {0,1} to where?
     
  4. Sep 23, 2010 #3
    Re: Countability

    oops sorry to the natural numbers. My book has another question asking the same thing but from the natural numbers to that set. I'm just trying to get the whole idea of this down.
     
  5. Sep 23, 2010 #4

    Office_Shredder

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Re: Countability

    A function from the set {0,1} to the natural numbers is a set of ordered pairs {(0,m),(1,n)} where m and n are natural numbers. Do you see how to biject this with something?
     
  6. Sep 23, 2010 #5
    Re: Countability

    Not really.
    f:(0, a), (1, b)
     
  7. Sep 23, 2010 #6

    Office_Shredder

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Re: Countability

    If f is the function corresponding to {(0,m),(1,n)} maybe we could label it fm,n. Then each function f:{0,1}--> N is fm,n for some choices of m and n, and all fm,n are distinct
     
  8. Sep 23, 2010 #7
    Re: Countability

    So is that basically for the set going to the natural numbers. If I want the natural numbers to {0,1}, I have {(m,n)} to {0,1} and each choice is not distinct. Uncountable.
     
  9. Sep 23, 2010 #8

    Office_Shredder

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Re: Countability

    Just because the choice is not distinct doesn't mean that it's uncountable
     
  10. Sep 23, 2010 #9
    Re: Countability

    It's not onto, so uncountable?
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook