Sets of all functions. Countable and Uncountable sets.

[jmjlt88]

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

 

[jbunniii]

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).