I Cantor's diagonal number

Tags:
1. Jan 11, 2019

Flo Tur

Let me consider the reals between [0;1] and work in binary numeration system.
I order the list like this: first number is 1, second is 0.0, third is 0.10. For the next numbers, the rule is that all the diagonal decimal digits are 0's. Cantor's diagonal number will then be 0.111111....=0.(1)=1. So, he failed to produce a number which is not on my list.

2. Jan 11, 2019

PeroK

There is a subtlety in the diagonal argument that the decimal expansion of a number is not unique. To stay in base 10, any terminating decimal has two expansions. E.g.

$0.1234$

Can also be written as:

$0.123999 \dots$

So, you need two further statements:

First, where the decimal expansion is ambiguous, you choose the terminating one. I.e. $0.1234$ appears on the list once as $0.1234$. And not as $0.123999 \dots$

Second, for the diagonal number you must avoid ending up with an infinite sequence of 9's. There are many ways to do this. One simple way is never to change a digit to a 9. You've always eight other digits to choose from.

Your binary problem is quite nice. You need to ensure that the final number is not $0.111 \dots$. One way round it would be wait until you get a non-terminating decimal - which must be a mixture of 0's and 1's - and jump to the next digit that is 1 and change that to 0.

Last edited: Jan 11, 2019
3. Jan 11, 2019

PeroK

Actually, to make a further point.

Let's say that Cantor's diagonal argument uses numbers in base 10. Then, that constitutes a proof. That proof may not work directly if you change to binary. But, it doesn't have to. You have a valid proof. In particular, any difficulties (or even an impossiblity) of transferring a specific proof to binary representation makes no difference to the original proof.

In different circumstances, you may switch to binary and produce a very nice proof (of something) exploiting the simplicity of binary numbers. But, the fact that your (binary) proof may not be directly transferable to base 10 wouldn't invalidate your binary proof. In fact, many mathematical proofs hinge on presenting the problem in a certain way.

You can prove something using base 10, or you could prove something using binary, but you don't have to do both.

4. Jan 11, 2019

Flo Tur

How long should I wait?
If you change a single 1 with 0 you obtain a rational number.

5. Jan 11, 2019

PeroK

The simplest argument is that it doesn't matter. Let's assume, for the sake of argument, that Cantor's diagonal proof doesn't work in binary representation. Let's assume that it needs at least 3 digits to work properly. Then the proof is still valid.

6. Jan 11, 2019

pbuk

Or alternatively, go down a different diagonal.

7. Jan 11, 2019

Staff: Mentor

Don't we have the same phenomenon in any basis? Binary $0.111\ldots = 1\,.$

8. Jan 11, 2019

Flo Tur

So, for numbers in binary system , reals could be countable?
Proof it in binary. Countability cannot depend on the system used.

9. Jan 11, 2019

Staff: Mentor

No. Even if you allow all doubles the argument still works.

10. Jan 11, 2019

PeroK

No. At worst you would need a different proof. If a proof doesn't work, all that means is that that proof is no good. It doesn't mean that the opposite is automatically true.

In any case, it's the same list whether the numbers are expressed in base 10, binary or Roman numerals. The list is either complete or not. The diagonal proof (using base 10 representation) proves the reals are uncountable.

11. Jan 11, 2019

PeroK

Exactly, you don't have to prove it using only binary. If you list the reals in binary, convert them to base 10 and apply Cantor's argument. That's it proved.

Otherwise, you could argue that most of number theory is not proved, because no one has proved it using Roman numerals! You could argue that $25 \times 7 = 175$ may not be true until you have checked it in Roman numerals, or in binary, or in hexadecimal.

In mathematics, one proof is enough. It might be nice to come up with another proof that the reals are uncountable. For example, not using the diagonal argument or applying some other constraint to make it harder. But, that doesn't affect the proof you already have.

Otherwise, nothing would ever be proved. You could always say: prove it again, not using base 10 or not using the Zeta function or not using complex numbers, or whatever.

A proof is a proof.

12. Jan 12, 2019

Flo Tur

Let's stay in binary and consider some rational's with periodic part (10). I arrange my list so that on diagonal is a succesion of 01's. Cantor's diagonal number will then be 0.(10). Because 0.(10) is missing from my initial list, it means this set is uncountable.

13. Jan 13, 2019

stevendaryl

Staff Emeritus
Strictly, speaking, what the diagonal argument proves is that there can be no countable list containing all representations of the real numbers in [0,1]. A representation being an infinite decimal (or binary) expansion. So the representation 0.01 and the representation 0.001111... are different representations, but they represent the same number.

Of course, it's also true that there is no countable list containing every real number in [0,1]. The proof is a little bit messier, but not much.

Note that the only reals that have double representations are ones that end in all 0s or all 1s in the binary expansion. So modify the diagonal argument so that it never produces one of those.

Here's one way to do that: Start with your original list. Let $f(n)$ be the $n^{th}$ real on your list. Now define a new list $\overline{f}(n)$ as follows:
• If $n$ is a multiple of 3, then $g(n) = f(n/3)$
• If $n+1$ is a multiple of 3, then $g(n) = 0.000...$
• If $n+2$ is a multiple of 3, then $g(n) = 0.1111...$
Now, diagonalize the new list $g$. You're guaranteed to get a representation that does not appear anywhere on $g$. If it's not on the list $g$, then it is not on the list $f$, either. And furthermore, you can prove that this number cannot end with all 0s or all 1s.

Last edited: Jan 13, 2019
14. Jan 13, 2019

stevendaryl

Staff Emeritus
I'm not sure I understand what you're saying. But Cantor's argument goes like this:
1. If a set $S$ is countable, then (by definition), there is an infinite list $s_1, s_2, ...$ that contains every element of $S$.
2. There is no list that contains every element of the reals.
3. So, the reals are not countable.
The rationals are countable. So you can produce a list that contains every rational number. If you use Cantor's trick to produce a real that is not on that list, then that diagonal number is guaranteed to be irrational.

15. Jan 13, 2019

JeffJo

Cantor's Diagonalization Argument is one of the most elegantly simple proofs of a complex concept in all of mathematics. Unfortunately, it gets simplified even further to teach it to beginners. And almost all of the objections to it, that you will find, arise from these simplifications.

Cantor wanted to prove that there can be sets that could not be counted. To do so, all he had to do was demonstrate one. And the one he used was not the set of real numbers. Let me repeat that: Cantor did NOT use diagonalization on any set of real numbers. He used the set of all possible binary strings. While "1.000..." and "0.1111..." may represent the same number in binary, "1000..." and "0111..." are still different strings. What you found was a string that was not in the set of strings that you counted, establishing that there was a string you didn't count exactly as Cantor intended.

+++++

• The only infinite strings that most beginners will be familiar with, are the decimal representations of either irrational numbers or repeating rational numbers. It's easier to teach with familiar tools, then to define new ones. Unfortunately, it isn's as accurate.
• Decimal representations of real numbers work fine in the proof, if care is taken to not use the digit "9" in a way where it could repeat indefinitely. It's simplest to just not use it at all.
• The same caveat applies to any base B; to make the argument work with the real numbers, just don't use the character for B-1. But this isn't possible with binary representation.
• You found a clever way to demonstrate why it isn't possible. Still, all you did was find a schema where the argument fails - that doesn't means it has to fail, just that you can't use that schema.
• There's another simplification that tricks a lot of beginners. It isn't really a proof by contradiction. What the argument shows, is that (A) if there is a way to count a set $S$ of binary strings, (B) then that counting process can be used to show there is a binary string that is not in $S$. Notice that I never claimed that $S$ included all such strings. Cantor didn't either.

16. Jan 13, 2019

FactChecker

That is a very good point. One thing I like about the application to the reals in decimal form is that it gives some intuitive idea of how much greater the unlisted numbers are than any countable subset. Every decimal place gives a multiplier of 9 to the set of unlisted numbers. I think this makes one more easily accept that the rational numbers form a dense set of measure zero.

17. Jan 13, 2019

Flo Tur

0.(10) is rationa
Diagonal 0.(10) is rational and is not on my initial list of rational's with period 10.

18. Jan 14, 2019

JeffJo

To clarify what I said, the diagonal method with straight replacement of characters does not work on a set of real numbers when expressed in binary. It does work on the same set of real numbers if expressed in a base B>2, but only if care is taken to not use the character B-1. Or with a more complicated schema to change the characters. What stevendaryl said is true in decimal notation, or his modified method in binary. I'm sure he was thinking of that.

19. Jan 15, 2019

Flo Tur

OK, no binary.
Supose I have the list of rationals.
Can you prove that any diagonal number is irrational?
No matter how I order my list.

20. Jan 15, 2019

FactChecker

If you have the list of all rationals (assumed for a proof by contradiction) then any number not on the list must be irrational.

The proofs that I have seen that a number is irrational have been specialized for that number. I don't know if there is a general method of proof that could be applied.