Undergrad Can Cantor's diagonal number solve the issue of infinite lists?

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

 

[PeroK]

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.

 

[PeroK]

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.

 

[Flo Tur]

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

 

[PeroK]

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.

 

[pbuk]

Or alternatively, go down a different diagonal.

 

[fresh_42]

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\,.$

 

[Flo Tur]

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.

 

[fresh_42]

So, for numbers in binary system , reals could be countable?

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

 

[PeroK]

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]

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.

 

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

 

[stevendaryl]

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.

 

[stevendaryl]

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.

 

[JeffJo]

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]

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.

 

[Flo Tur]

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.

 

[JeffJo]

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.

 

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

 

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

 

[jbriggs444]

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]

 

[Flo Tur]

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.

 

[jbriggs444]

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.

 

[FactChecker]

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.

 

[JeffJo]

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.

 

[FactChecker]

First aside: let me reiterate that Cantor's intent was to use Diagonalization on strings, and specifically not on numbers.​

Of course, it is also trivial to have the list include both representations of the listed number, both 0.1 and 0.099999... Then his method would avoid both of those with no trouble.

 

[JeffJo]

Of course, it is also trivial to have the list include both representations of the listed number, both 0.1 and 0.099999... Then his method would avoid both of those with no trouble.

Which is exactly what is accomplished by using strings, instead of numbers, in the first place. :)

But it points out another improperly-taught simplification of the proof. There are several - "strings" v. "numbers" is another - that I claim cause more harm than good.

When presented as a proof by contradiction:

• It starts by assuming a bijection between $N$ and the example set $T$.
• It then uses diagonalization to find an element of $T$ that is not mapped by this bijection.
• The alleged contradiction is that there can't be an element that is not mapped by a bijection, so the assumption must be false.
• But this is not the outline of a valid proof by contradition. It doesn't actually use the part of that assumption that says you have a surjection; it just claims that it is contradicted.
• So, it is actually a direct proof that you can't have a surjection.

The harm that I claim, is that many people will correctly object to assuming the thing that gets contradicted this way. So they feel the proof must be wrong, when all that really happened was that it was explained poorly.
A similar fact that you use, is that diagonalization does not need to assume an injection, either. What it proves is "If $f(n)$ is a function whose range is $N$ and whose co-domain is the set of all binary strings $T$, then there is a binary string in $T$ that is not mapped by $f(n)$." This proves that $T$ is uncountable.

 

[PeroK]

Which is exactly what is accomplished by using strings, instead of numbers, in the first place.

There's no sense in which "numbers" and "strings" are fundamentally different things. That's a bit like saying "using n-tuples instead of vectors".

 

[JeffJo]

There's no sense in which "numbers" and "strings" are fundamentally different things. That's a bit like saying "using n-tuples instead of vectors".

I suggest you look up the definition of numbers. Strings represent numbers, but are mathematically different objects.

Trivial example: "0.4999..." and "0.5000..." are quite different - in the same sense that Cantor uses - strings, but represent the same number in decimal.

 

[PeroK]

I suggest you look up the definition of numbers. Strings represent numbers, but are mathematically different objects.

Trivial example: "0.4999..." and "0.5000..." are quite different - in the same sense that Cantor uses - strings, but represent the same number in decimal.

And $1/2$ and $2/4$ represent the same number. But, you don't say: let's use vulgar fractions instead of numbers!