Is Set B of Functions from Natural Numbers to {0,1} Countable?

[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

 

[HallsofIvy]

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.

 

[BustedBreaks]

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.

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?

 

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

 

[HallsofIvy]

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!