Sets of all functions. Countable and Uncountable sets.

  • Thread starter jmjlt88
  • Start date
  • #1
96
0
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! =)
 

Answers and Replies

  • #2
jbunniii
Science Advisor
Homework Helper
Insights Author
Gold Member
3,394
180
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 [itex]Z_+ \times Z_+[/itex], namely {(0,n), (1,m)} <-> (n,m).
 

Related Threads on Sets of all functions. Countable and Uncountable sets.

  • Last Post
Replies
1
Views
2K
  • Last Post
Replies
5
Views
2K
Replies
3
Views
2K
  • Last Post
Replies
2
Views
3K
  • Last Post
Replies
3
Views
3K
  • Last Post
Replies
2
Views
1K
  • Last Post
Replies
4
Views
3K
  • Last Post
Replies
3
Views
1K
  • Last Post
Replies
1
Views
2K
Top