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: Sets of all functions. Countable and Uncountable sets.

  1. Oct 9, 2012 #1
    I have some confidence that this is the right idea. But whenever I have the slightest shred of doubt, I turn to the experts! :tongue:Thus, before I write up my proof in my notes, does this look somewhat coherent?

    The problem states:
    “Determine whether the set of all functions from {0,1} to Z+ is countable or uncountable.”

    First, I took a look at what a few functions looked like. For instance, {(0,5),(1,7)} would constitute a function. In general, the set of all functions in this case would be the collection of all {(0,n),(1,m)}, where n and m are positive integers. It then hit me that I can construct a bijective correspondence between the set of functions from {0,1} to Z+ and {0} X Z+ X {1} X Z+ by the mapping
    ((0,n),(1,m)) <-> (0,n,1,m).​
    The latter set is a finite product of countable sets, and therefore countable. The desired result will follow.

    Any input would be great! Thanks so much! =)
  2. jcsd
  3. Oct 9, 2012 #2


    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    Yes, this proof is fine. Note that there is also a simpler bijection with the set [itex]Z_+ \times Z_+[/itex], namely {(0,n), (1,m)} <-> (n,m).
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook