# Sets of all functions. Countable and Uncountable sets.

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! =)

Related Calculus and Beyond Homework Help News on Phys.org
jbunniii
Homework Helper
Gold Member
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! =)
Yes, this proof is fine. Note that there is also a simpler bijection with the set $Z_+ \times Z_+$, namely {(0,n), (1,m)} <-> (n,m).