I Cantor's diagonal number (1 Viewer)

Users Who Are Viewing This Thread (Users: 0, Guests: 1)

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.
 

PeroK

Science Advisor
Homework Helper
Insights Author
Gold Member
2018 Award
8,626
3,086
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.
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:

PeroK

Science Advisor
Homework Helper
Insights Author
Gold Member
2018 Award
8,626
3,086
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.
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.
 
How long should I wait?
If you change a single 1 with 0 you obtain a rational number.
 

PeroK

Science Advisor
Homework Helper
Insights Author
Gold Member
2018 Award
8,626
3,086
How long should I wait?
If you change a single 1 with 0 you obtain a rational number.
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.
 
993
145
Or alternatively, go down a different diagonal.
 

fresh_42

Mentor
Insights Author
2018 Award
8,991
6,277
There is a subtlety in the diagonal argument that the decimal expansion of a number is not unique.
Don't we have the same phenomenon in any basis? Binary ##0.111\ldots = 1\,.##
 
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.
So, for numbers in binary system , reals could be countable?
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.
Proof it in binary. Countability cannot depend on the system used.
 

PeroK

Science Advisor
Homework Helper
Insights Author
Gold Member
2018 Award
8,626
3,086
So, for numbers in binary system , reals could be countable?
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.
 

PeroK

Science Advisor
Homework Helper
Insights Author
Gold Member
2018 Award
8,626
3,086
Countability cannot depend on the system used.
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.
 
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.
 

stevendaryl

Staff Emeritus
Science Advisor
Insights Author
8,111
2,388
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.
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:

stevendaryl

Staff Emeritus
Science Advisor
Insights Author
8,111
2,388
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.
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.
 
104
13
Let me consider the reals between [0;1] and work in binary numeration system. ... So, he failed to produce a number which is not on my list.
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.

+++++

Some comments:
  • 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.
 

FactChecker

Science Advisor
Gold Member
2018 Award
4,608
1,565
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.
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.
 
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.
0.(10) is rationa
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.
Diagonal 0.(10) is rational and is not on my initial list of rational's with period 10.
 
104
13
0.(10) is rationa(l)

Diagonal 0.(10) is rational and is not on my initial list of rational's with period 10.
  • 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.
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.
 
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.
 

FactChecker

Science Advisor
Gold Member
2018 Award
4,608
1,565
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.
 

The Physics Forums Way

We Value Quality
• Topics based on mainstream science
• Proper English grammar and spelling
We Value Civility
• Positive and compassionate attitudes
• Patience while debating
We Value Productivity
• Disciplined to remain on-topic
• Recognition of own weaknesses
• Solo and co-op problem solving
Top