Countability of Functions from {0,1}: Finding a 1-1 Correspondence

[kathrynag]

Homework Statement

Is the set of all functions from {0,1} countable or uncountable? Provide a 1-1 correspondence with a set of know cardinality.

Homework Equations

The Attempt at a Solution

I say it is countable, but my problem is I don't really know how to provide a 1-1 correspondence.

 

[Office_Shredder]

The set of all functions from {0,1} to where?

 

[kathrynag]

oops sorry to the natural numbers. My book has another question asking the same thing but from the natural numbers to that set. I'm just trying to get the whole idea of this down.

 

[Office_Shredder]

A function from the set {0,1} to the natural numbers is a set of ordered pairs {(0,m),(1,n)} where m and n are natural numbers. Do you see how to biject this with something?

 

[kathrynag]

Not really.
f:(0, a), (1, b)

 

[Office_Shredder]

If f is the function corresponding to {(0,m),(1,n)} maybe we could label it f_m,n. Then each function f:{0,1}--> N is f_m,n for some choices of m and n, and all f_m,n are distinct

 

[kathrynag]

So is that basically for the set going to the natural numbers. If I want the natural numbers to {0,1}, I have {(m,n)} to {0,1} and each choice is not distinct. Uncountable.

 

[Office_Shredder]

Just because the choice is not distinct doesn't mean that it's uncountable

 

[kathrynag]

It's not onto, so uncountable?