1. PF Contest - Win "Conquering the Physics GRE" book! Click Here to Enter
    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!

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).
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook