Countability calculation help

1. Sep 23, 2010

kathrynag

1. The problem statement, all variables and given/known data
Is the set of all functions from {0,1} countable or uncountable? Provide a 1-1 correspondence with a set of know cardinality.

2. Relevant equations

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

2. Sep 23, 2010

Office_Shredder

Staff Emeritus
Re: Countability

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

3. Sep 23, 2010

kathrynag

Re: Countability

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.

4. Sep 23, 2010

Office_Shredder

Staff Emeritus
Re: Countability

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?

5. Sep 23, 2010

kathrynag

Re: Countability

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

6. Sep 23, 2010

Office_Shredder

Staff Emeritus
Re: Countability

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

7. Sep 23, 2010

kathrynag

Re: Countability

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.

8. Sep 23, 2010

Office_Shredder

Staff Emeritus
Re: Countability

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

9. Sep 23, 2010

kathrynag

Re: Countability

It's not onto, so uncountable?