# Help with function mapping

1. Jul 5, 2009

### AnthonyAcc

Let B={s|s is a function mapping the set of natural numbers to {0,1}}. Is B a countable set-that is, is it possible to find a function $$\Phi$$() mapping the set of natural numbers onto B-?

I know that it has to do with infinite binary sequences, but the countability part confuses me. Can someone explain that and give me a first step to answering this?

Thanks

2. Jul 5, 2009

### HallsofIvy

Staff Emeritus
Every mapping in B is an infinite binary sequence (sequences of 0 and 1), as you say, and so, if we put a "." in front of it, represents a real number, written in base 2, in the interval (0,1). But the set of real numbers in that interval is not countable.

3. Jul 5, 2009

### BustedBreaks

That's interesting. Does saying that putting a "." in front of the sequences written in base 2 is in the interval (0,1) mean anything? If the question was if B={s|s is a function mapping the set of natural numbers to {1,2}} putting a period in front of the sequences would make them less than 1 which would make them not in the interval (1,2), but the logic of them being real numbers and that real numbers aren't countable is still solid. Correct?

4. Jul 5, 2009

### Dick

Halls is suggesting a shortcut. No, putting a 'dot' in front really doesn't prove anything unless you understand the shortcut. But you can always use the Cantor diagonal argument directly. I'd suggest you look that up and understand it, since it's fundamental to the proof that there are uncountable sets.

5. Jul 6, 2009

### HallsofIvy

Staff Emeritus
My point is this: suppose one such sequence is "11001010010101100...". "Putting a '.' in front of it" means writing .11001010010101100..., a number between 0 and 1, written in binary. Further, any real number, between 0 and 1, is such a sequence so there is a one-to-one correspondence. Every such sequence corresponds to a number between 0 and 1.

You ask about "if B={s|s is a function mapping the set of natural numbers to {1,2}} putting a period in front of the sequences would make them less than 1 which would make them not in the interval (1,2)". Why would you want it in (1, 2)? The notation {1, 2} means every value must be either 1 or 2 and does not have anything to do with the interval (1, 2). Frankly, if I were given the problem of showing that the set of all functions from the natural numbers to {1, 2} were uncountable, I would immediately observe that there is an obvious correspondence between {1, 2} and {0,1} and start talking about binary numerals again!