Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

you can do a mapping between binary decimal numbers and integers like this

1 -> 0.110100111
2 -> 0.101010110
3 -> 0.010001000
4 -> 0.101011111

n -> 0.011100010

Now with cantor's diagonal argument we can prove that there is a decimal binary number not in the list

and thereby prove that binary numbers in decimal representation is uncountable right ?

share|improve this question
I don't understand the first sentence of your statement. What does "you can do a mapping between binary decimal numbers and integers" meant to be? If you are asking "Can one apply Cantor's diagonal argument to the binary decimals to show that the binary decimals are uncountable?" the answer is "yes, but you have to be a bit careful with the issue of dual representation." If the first sentence means something else... well, it depends on what your first sentence is supposed to mean. –  Arturo Magidin Feb 10 '12 at 4:06
binary (fractional) numbers are all part of $\mathbb{R}$ just as all decimal fractional numbers are (there is a 1-1 binding between them) –  ratchet freak Feb 10 '12 at 4:07
To get around the issue of double representation, work with blocks of 2 digits instead of single digits; given blocks 00, 01, or 11, select 10; given the block 10, select the block 01. This will give you a number in binary expansion with a unique expansion that is not on the given list. –  Arturo Magidin Feb 10 '12 at 4:12
"binary" means base-2; "decimal" means base-10. What does "binary decimal" mean?? –  Michael Hardy Feb 10 '12 at 4:14
@Michael: It means I need to get some sleep, at any rate... –  Arturo Magidin Feb 10 '12 at 4:17
show 4 more comments

2 Answers

up vote 3 down vote accepted

Yes, you can use (a variant of) Cantor's diagonal argument to prove that the real numbers $x$ with $0\le x\lt1$, as given in binary, are uncountable. I say "a variant of" because one must exercise a little more care when the numbers are given in binary than when they are given in decimal, but it is still essentially Cantor's argument - and of course it gives the same conclusion, since the reals are the reals, whether you represent them to base 2 or to base 10 or as continued fractions or....

share|improve this answer
add comment

First, binary fraction is perhaps a better phrase than binary decimals. Second your mapping is not exactly clear. If I give you an integer, let's say 77777077777, then how do you decide which binary fraction it belongs to?

Third, are you trying to prove that the set of all binary fractions is uncountable? If yes, then why are you mapping the natural numbers to binary fractions? The natural numbers are countable. You should map the binary fractions to some uncountable set (how Gerry said x between zero and one). This map must be one-to-one and onto and then conclude, "since [0,1) is uncountable, the set of all binary fractions is also uncountable".

share|improve this answer
Have you ever seen the diagonal argument before? It proves that for any $f:\mathbb N\to\mathbb R$ there is a real number not in its range. The OP was just attempting to tell show how he imagined a generic mapping $f:\mathbb N\to\mathbb R$ might look when the function values are represented as binary fractions. The argument he was envisioning did not apply to one particular such map, but to all possible maps. –  Henning Makholm Oct 16 '12 at 18:30
add comment

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.