Cantor's diagonal number

  • #1
16
0

Main Question or Discussion Point

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.
 

Answers and Replies

  • #2
PeroK
Science Advisor
Homework Helper
Insights Author
Gold Member
13,422
5,936
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:
  • Like
Likes WWGD and FactChecker
  • #3
PeroK
Science Advisor
Homework Helper
Insights Author
Gold Member
13,422
5,936
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.
 
  • Like
Likes Dale and pbuk
  • #4
16
0
How long should I wait?
If you change a single 1 with 0 you obtain a rational number.
 
  • #5
PeroK
Science Advisor
Homework Helper
Insights Author
Gold Member
13,422
5,936
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.
 
  • #6
pbuk
Science Advisor
Gold Member
1,431
414
Or alternatively, go down a different diagonal.
 
  • Like
Likes mfb
  • #7
13,084
9,855
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\,.##
 
  • #8
16
0
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.
 
  • #9
13,084
9,855
So, for numbers in binary system , reals could be countable?
No. Even if you allow all doubles the argument still works.
 
  • #10
PeroK
Science Advisor
Homework Helper
Insights Author
Gold Member
13,422
5,936
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.
 
  • #11
PeroK
Science Advisor
Homework Helper
Insights Author
Gold Member
13,422
5,936
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.
 
  • Like
Likes Dale
  • #12
16
0
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.
 
  • Sad
Likes Dale
  • #13
stevendaryl
Staff Emeritus
Science Advisor
Insights Author
8,401
2,580
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:
  • #14
stevendaryl
Staff Emeritus
Science Advisor
Insights Author
8,401
2,580
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.
 
  • #15
110
15
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.
 
  • Informative
  • Like
Likes Dale and FactChecker
  • #16
FactChecker
Science Advisor
Gold Member
5,583
2,060
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.
 
  • #17
16
0
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.
 
  • #18
110
15
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.
 
  • #19
16
0
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
FactChecker
Science Advisor
Gold Member
5,583
2,060
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.
 
  • #21
jbriggs444
Science Advisor
Homework Helper
2019 Award
8,770
3,529
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.
That challenge is incomplete. You have not specified whether the provided list of rationals is complete. Nor have you nailed down a specific diagonalization process. Or radix.

If you provide a complete list of rationals and if we use base 4 and an algorithm of switching all 0's and 1's to 2's and all 2's and 3's to 1's on the main diagonal then the resulting main diagonal is guaranteed to be irrational.

[We can agree not to worry about dealing with negative numbers and rational numbers greater than one so that there are no difficulties with stuff off to the left of our grid of digits]
 
  • #22
16
0
That challenge is incomplete. You have not specified whether the provided list of rationals is complete. Nor have you nailed down a specific diagonalization process. Or radix.

If you provide a complete list of rationals and if we use base 4 and an algorithm of switching all 0's and 1's to 2's and all 2's and 3's to 1's on the main diagonal then the resulting main diagonal is guaranteed to be irrational.
Any diagonal number must be irrationnal.
 
  • #23
jbriggs444
Science Advisor
Homework Helper
2019 Award
8,770
3,529
Any diagonal number must be irrationnal.
That depends on what precise conditions are specified for the list and for the construction of the diagonal.

If I have the list (0, 0, 0, ... ) and use base 4 and an algorithm of "0's and 1's become 2's while 2's and 3's become 1's" then the resulting diagonal is 0.222... (base 4) which is rational.
 
  • #24
FactChecker
Science Advisor
Gold Member
5,583
2,060
Any diagonal number must be irrationnal.
You can assume that the list contains all the rationals since that is easy to do. But the list has not been actually constructed, so the nature of the digit patterns is unknown. You can still easily construct a number that is not on the list but you would have no idea what its pattern of digits is. You can say that it is not rational because of your initial assumption.
 
  • #25
110
15
OK, no binary.
Sup(p)ose I have the list of rationals.
Can you prove that any diagonal number is irrational?
No matter how I order my list.
Um, yeah? The result you describe is the reason the proof works?

First aside: let me reiterate that Cantor's intent was to use Diagonalization on strings, and specifically not on numbers. His first proof of the proposition that there are uncountable sets did use numbers. But it made some debatable assumptions about sets of numbers. So he devised a second proof, because (and this is a direct quote from that link) "there is a proof of this proposition that is much simpler, and which does not depend on considering the irrational numbers."

If used on strings, your question is irrelevant; a string is not "rational" or "irrational." The argument can be used on numbers, but only with the additional step of converting them to strings.

Second aside: "0.25" is not a number. It is a string used to represent a number; in this case, the number we name "one fourth". I know it sounds pedantic to point out the difference, but the property of numbers that you are trying to utilize depends on it. Some rational numbers have two such representations. And I'll point out that since you are relying on two such representations, and only rational numbers have two, the answer to your question should already be obvious.

To get a "diagonal number" as you call it, there are steps that Cantor didn't need that become necessary. There technically is no such thing - diagonlaization applies to strings. So you mean the number associated with the diagonal string. And to get it, we need to guarantee that any number, rational or irrational, has only one valid string. So we need these requirements in any base B:
  • If the number to be converted is rational with a denominator whose prime factors are all prime factors of the base B, then express it as terminating string and append an infinite string of "0"s to it.
  • If there is a prime factor of the denominator that is not a prime factor of B, then the representation eventually becomes a repeating string of characters that are not all "B-1".
  • If the number is irrational, there is no repetition.
Now we need to make sure that diagonalization will produce a string meeting the same requirements (i.e., not ending with repeating "B-1")s:
  • One way (there are many) is to replace each character "C", that isn't an "B-1", with "C+1". And replace "B-1" with "0".
  • None of the many similar methods works in binary, so you need a more complicated scheme like stevendaryl's. He was a little terse in explaining the string for every number, even the ones he seemed to skip over, are included in his list. It's not that I think you don't, but I need to ask you if you understand why.
So now the proof you asked for is:
  • Let ##Q## be the set of rational numbers in [0,1). It can be put into a list. Assume we have an arbitrary one.
  • Let ##S## be the set of strings that represent the elements of ##Q##. It can be put into a parallel list.
  • Apply the valid diagonlaization technique to the list of ##S##. Call the result a "diagonal string", and name it ##d##.
  • Trivially, ##d## is not in ##S##.
  • But ##d## does fulfill the restrictions for our strings. So it can be converted back to a number, ##r##.
  • Since each number has exactly one representation, and ##d## is not in ##S##, we know that ##r## is not in ##Q##.
  • But all rational numbers are in ##Q##. So ##r## is not a rational number.
 
Last edited by a moderator:
  • Like
Likes FactChecker

Related Threads on Cantor's diagonal number

  • Last Post
Replies
17
Views
779
  • Last Post
2
Replies
49
Views
9K
  • Last Post
Replies
4
Views
1K
  • Last Post
Replies
2
Views
2K
  • Last Post
Replies
1
Views
1K
  • Last Post
Replies
2
Views
2K
  • Last Post
2
Replies
38
Views
9K
  • Last Post
4
Replies
86
Views
4K
Top