I 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!

 

[JeffJo]

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

Hey, it's much easier to enumerate vulgar fractions. It's even how I choose to do it in an antagonistic "discussion," because there's a simple formula for it. But I call them pairs of integers (m,n) instead of "vulgar fractions." That sounds so, well, vulgar. And while I wouldn't use them in an engineering paper, they can be useful when using a tape measure that is marked off in sixteenths of an inch.

The point is, we can use whatever objects work for the specific purpose at hand. And we can even choose what works more easily, if we want. In diagonalization, it is important to be able to prove that two elements of the candidate set are different. It is a lot easier to show this with strings, and it prevents the use of certain irrelevant arguments.

 

[Flo Tur]

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.

In your logic, replace Q with R. Then, r is not in R?

 

[Flo Tur]

In my opinion, the flaw is here: "Trivially, $d$ is not in $S$". Cantor proved only that for every digit n, the diagonal number is not yet on the list. This is an excelent algoritm to create new numbers, but has noting to do with count-ability. If you count the ordered natural numbers, for every n you reached I can prove that n+1 is not on your list. And I can do this forever, not because N is uncountable, but because is infinite.

 

[stevendaryl]

In your logic, replace Q with R. Then, r is not in R?

The argument starts off: "Let Q be the set of rational numbers in. It can be put into a list."

If you replace Q by R, then the second sentence isn't true, so the rest doesn't follow. Cantor's proof shows that the second sentence isn't true with Q replaced by R.

 

[stevendaryl]

In my opinion, the flaw is here: "Trivially, $d$ is not in $S$". Cantor proved only that for every digit n, the diagonal number is not yet on the list. This is an excelent algoritm to create new numbers, but has noting to do with count-ability.

It is the definition of countability. A set is countable if there is a list that contains every element.

If you count the ordered natural numbers, for every n you reached I can prove that n+1 is not on your list. And I can do this forever, not because N is uncountable, but because is infinite.

The claim is this: If $L$ is a function from natural numbers to reals (that is, for every $n$, $L(n)$ returns a real number), then there is a real number $r$ that is not on the list. Mathematically, that is formalized as follows:

$\forall L\ \exists r\ \forall n\ : r \neq L(n)$

(the quantifiers should actually be restricted quantifiers: forall L of type list of reals, exists r of type real, forall n of type natural, ...)

Your claim about natural numbers is completely different. You're saying for every list of natural numbers, and for every natural number $n$, there exists another natural number, $n'$ such that $n'$ is unequal to every natural number up to index $n$. That's a much more complex statement, which can be formalized as follows:

$\forall L\ \forall i\ \exists n'\ \forall j \leq i : n' \neq L(j)$

These are very different statements.

Here's a way to understand logical statements with alternations of quantifiers. In terms of a two-player game. We have a logical statement of the form:

$\forall L\ \exists r\ \forall n\ : r \neq L(n)$

(The general form is: some number of $\forall$ quantifiers, then some number of $\exists$ quantifiers, then more $\forall$ quantifiers, etc, until you get to the statement at the end, which has no quantifiers)

The first player is trying to make the statement false. We'll call him the falsifier. The second player is trying to make it true. We'll call him the verifier. They take turns playing.

The falsifier picks some list $L$. The verifier gets to inspect $L$ and picks, based on $L$, a real number $r$. The falsifier then picks a number $n$. Then we evaluate the expression $r \neq L(n)$. If it's true, then the verifier wins. If it's false, then the falsifier wins.

We say that a formula is "valid" if there is a strategy such that the verifier can always win, following this strategy. If there is no such strategy, then the formula is invalid.

A simplest case is "For every number, there is a larger number". That can be formalized as:

$\forall n\ \exists n' : n' > n$

Here's the winning strategy: Whatever number $n$ the falsifier picks, the verifier picks a number one higher: $n' = n+1$.

The verifier always wins with this strategy. So it's a valid formula. Similarly, the verifier always wins Cantor's formula:

$\forall L\ \exists r\ \forall n\ : r \neq L(n)$

If you want to show that Cantor's formula is invalid, then you have to play the falsifier, and show that you have a strategy, a way of playing, such that you can beat Cantor's verifier strategy.

 

[stevendaryl]

So in terms of games, the winning strategy for the verifier that "Every list of real numbers omits at least one real number" is Cantor's diagonal strategy.

The statement is $\forall L\ \exists r\ \forall n\ : r \neq L(n)$
(where $L$ is restricted to a function from naturals to reals, $r$ is restricted to be a real, $n$ is restricted to be a natural)
The game plays out by the falsifier picking $L$, the verifier picking $r$, the falsifier picking $n$, then checking whether $r \neq L(n)$.

• The falsifier picks any list $L$. Let $L(m)[n]$ be the $n^{th}$ decimal in the expansion of real number $m$ in the list $L$.
• The verifier picks a number $r$ such that the decimal expansion of $r$ has as its $n^{th}$ decimal: $r[n] = L(n)[n] +1$ (unless $L(n)[n] = 9$, in which case $r[n] = 0$)
• Then whatever natural number $n$ is chosen by the falsifier, the verifier shows that $r[n] \neq L(n)[n]$. That shows that $r \neq L(n)$.

In contrast, how would the game "Every list of natural numbers omits at least one natural number" play out?

The statement is $\forall L\ \exists n\ \forall n'\ : n \neq L(n')$
(where $L$ is restricted to a function from naturals to naturals, $n$ and $n'$ are restricted to be naturals)

The game plays out by the falsifier picking $L$, then the verifier picks $n$, then the falsifier picks $n'$ then checking whether $n \neq L(n')$.

• The falsifier picks the list $L$ where $L(n) = n$.
• The verifier picks a natural number $n$.
• The falsifier picks $n' = n$
• We check if $n \neq L(n')$. That's false. So verifier loses.

 

[Demystifier]

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.

In this way you produce only rational numbers. Your list does not have any single irrational number. The numbers like $\pi$ and $e$ are not on your list.

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.

Congratulations, you just proved that the set of rational numbers is countable! But this says nothing about the set of real numbers.

 

[SSequence]

Yes, that's a good idea. If we just add one further initial step in the construction (which would basically be modifying the original list L to make a list L' so that L' is guaranteed to contain every rational number) ... then in that case every "digit diagonalisation" would always be guaranteed to work.

=================

Though there are some further subtleties one can consider. Given a certain amount of basic assumptions, the argument certainly shows that we somehow can't "squeeze" ℝ to make a 1-1 correspondence function from ℕ to ℝ.

But if some collection C is too big to be "squeezed" to make a 1-1 correspondence function from ℕ to C, then it does raise the question that shouldn't we distinguish between "surveyable" and "non-surveyable" collections?

 

[JeffJo]

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.

In your logic, replace Q with R. Then, r is not in R?

It doesn't further your point when you ignore some steps. It only suggests that you have already reached a conclusion, and are trying to twist the logic to support it. But recall that my "valid strings" use, for example, 0.5000... instead of 0.4999... . And my "valid diagonalization technique" will never use the digit "9":

• Let $R1$ be the set of rational numbers in [0,1). We don't know if it can, or can't, be put into a list. So assume we have an arbitrary list that may or may not be complete. Call the set that is listed $T$.
  
• Let $S$ be the set of strings that represent the elements of $T$. 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$, that is in $R1$.
  
• Since each number has exactly one representation, and $d$ is not in $S$, we know that $r$ is not in $T$.
• But all real numbers are in $T$. So $T$ is not all of $R$.

In my opinion, the flaw is here: "Trivially, $d$ is not in $S$". Cantor proved only that for every digit n, the diagonal number is not yet on the list

You are falling into the trap favored by all Cantor doubters. The trap of confusing how a 9th-grade teacher will demonstrate the comparison on the blackboard for beginning students, with the comparison process that is being demonstrated.

The comparison process is not a sequential one. Since any element of $T$ corresponds to an $n$ in the FULL list (not $n$'s taken in sequence), it necessarily differs from $d$ in position $n$. There are no elements of $TT$ that this statement does not apply to.

This is an excelent algoritm to create new numbers, but has noting to do with count-ability.

Directly? Of course not. That is just one line of the proof.

But look at the first and list lines of that proof. They say "If we have a list of members of $R1$ ... then that list does not include all of $R1$." Since by definition, "countability" means "the entire set can be put into a list," and this proof demonstrates unequivocally that $R1$ can't, it is uncountable.

If you count the ordered natural numbers, for every n you reached I can prove that n+1 is not on your list. And I can do this forever, not because N is uncountable, but because is infinite.

And if the dog hadn't stopped to pee, he'd have caught the rabbit. In other words, inserting a step that is not in the proof (stopping after you "reach" a finite-numbered line in the list) says nothing about the proof itself.

 

[JeffJo]

There was a typo in my last reply, that I can't correct. The part in blue is the correction.

• Let $R1$ be the set of rational numbers in [0,1). We don't know if it can, or can't, be put into a list. So assume we have an arbitrary list that may or may not be complete. Call the set that is listed $T$.
  
• Let $S$ be the set of strings that represent the elements of $T$. 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$, that is in $R1$.
  
• Since each number has exactly one representation, and $d$ is not in $S$, we know that $r$ is not in $T$.
• But all real numbers are in $R$. So $T$ is not all of $R$.

 

[Periwinkle]

If I understood what was said, it was agreed that Cantor's diagonal argument would not work if the real numbers were expressed as dual (or also called binary) fractions. However, I looked at Abraham A. Fraenkel's Abstract set theory, North-Holland Pub. Co., 1961, p. 54, writes A. Fraenkel that the method can be applied to the base 2 with minor modifications. The method itself is not described, but at the end of the section, exercise 2 contains this question with a hint.
.................................

Each real number in the interval $(0,1]$ can be on way written as an infinite dual fraction of type $0, c_1c_2c_3…,$ which cannot be such that after some $c_i$ digit only 0 follows. So it can't end with an infinite number of 0s. (The correct way to write the real number.)

We omit $0$ because it cannot be written in this form.

Thus, the finite dual fraction $0.1011$ is represented as an infinite fraction of $0.10101111….$ And here are the other infinite fractions that cannot be written in a finite form. This theorem is explained by mathematical analysis.
.................................

It must be proved that the numbers of the interval $(0,1]$ cannot be listed in a countable sequence. Suppose that it is possible.

$$r_\rm{1} = 0.a_\rm{1,1}, a_\rm{1,2}, a_\rm{1,3}, a_\rm{1,4},…
\\r_\rm{2} = 0.a_\rm{2,1}, a_\rm{2,2}, a_\rm{2,3}, a_\rm{2,4},…
\\r_\rm{3} = 0.a_\rm{3,1}, a_\rm{3,2}, a_\rm{3,3}, a_\rm{3,4}, ...
\\r_\rm{4} = 0.a_\rm{4,1}, a_\rm{4,2}, a_\rm{4,3}, a_\rm{4,4},…
\\......$$
All dual fraction digits in the table are $0$ or $1$. With the diagonal method we take the opposite of the numbers $a_\rm{1,1}, a_\rm{2,2}, a_\rm{3,3},…$. $1$ instead of $0$, but $0$ instead of $1$. In this diagonal number $d$,

$$d = 0.a_\rm{1,1}'a_\rm{2,2}'a_\rm{3,3}'a_\rm{4,4} '...$$
the digits will be different from at least one place (at the diagonal location) of each of the $r_1, r_2, r_3,…$ numbers listed.
.................................

However, it has not yet been shown that the number $d$ is different from each of the numbers $r_1, r_2, r_3,….$ There is no guarantee that this $d$ diagonal number would be represented in the correct way of writing. In this case, despite that, it differs in at least one binary digit from every $r_1, r_2, r_3,…$ number, it would be the same.

The number $d$ would not be written correctly if it would appear as $0, 1011000 ...$ with infinite number $0$ at the end. If this is avoided, the proof is ready.

Let's take the $n_1, n_2, n_3,…,$ infinitely growing sequence of natural numbers. Let's look at the diagonal element of $r_{n_1}$. If the diagonal element of $r_{n_1}$ is $0$, then nothing has to be done with $n_1$, because it is secured on its part the $1$ digit in the diagonal fraction $d$. However, if $r_{n_1}$ has a diagonal element of $1$, then we proceed as follows:

The assumption is that the $r_1, r_2, r_3,…$ sequence contains all the numbers in the interval $(0,1]$. It should therefore also include the number $r$ which is precisely the same as $r_{n_1}$, except that the $n_1$ digit in the fraction is not $1$ but $0$. Therefore, in the above table, the $n_1$ digit of $r_{n_1}$ is replaced by $0$, while $n_1$ of $r$ is replaced by $1$. This secures that the $n_1$ digit of the $d$ diagonal number is $1$.

The above steps are continued for the infinitely growing sequence of $n_1, n_2, n_3,...$ It is achieved that the $d$ diagonal number should not of $0.110100000…$ type, with infinite number $0$ at the end. So it is correctly written, but differs from all the numbers in the table, so we have contradicted the assumption that we would have listed all real numbers in the interval $(0, 1]$.

 

[JeffJo]

If I understood what was said, it was agreed that Cantor's diagonal argument would not work if the real numbers were expressed as dual (or also called binary) fractions.

This diagonalization method:

1. Express every real number in [0,1) as a binary string, with the single restriction that all rational numbers whose denominator is a power of two are represented by your choice of either a terminating string followed by infinite 0's, or as a non-terminating string ending with infinite 1's.
2. Make a list s1, s2, s3, ... of these strings.
3. Extract the diagonal string d.
4. Create a new string by switching 1's for 0's, and vice-versa.

... will not work in Cantor's Diagonalization method. The reason being that you can't prove that the new string satisfies the restriction. But it is entirely possible that one could devise a second restriction that allows such a proof, and I never said otherwise.

I didn't look closely at it, but that appears to be what Fraenkel suggests. Whether or not that is so, it is entirely irrelevant. The elegance of Cantor's Argument is that such machinations are not needed when it is applied to strings, and not numbers.

 

[FactChecker]

The elegance of Cantor's Argument is that such machinations are not needed when it is applied to strings, and not numbers.

I agree. And although different representations of the real numbers might present some technical problems, they are all solvable. The fact remains that, given a reasonable representation of the reals, the proof can be made solid.
"The reals by any other representation would be as numerous." -- Shakespeare

 

[Periwinkle]

\begin{array}{|c|c|c|c|c|c|c|c|}
\hline & a & b & c & d & e & f & g & h & i & .\\
\hline a & \mathbf {*} & & & &X & X & X & & X &. \\
\hline b & & \mathbf {X} & & & & & X & &. \\
\hline c & & & \mathbf {X} & X & & & & & X &. \\
\hline d & & & & \mathbf {X} & & & & & &. \\
\hline e & & &X &X & \mathbf {X} &X & & & &. \\
\hline f & &X & X &X & & \mathbf {*} & & & &. \\
\hline g & & & X &X & X & & \mathbf {*} & & &. \\
\hline h &X & & & & & X &X &\mathbf {*} & &. \\
\hline i & &X &X &X & & & & & \mathbf {X} &. \\
\hline . & . & . & . & . & . & . & . & . & . & .\\
\hline
\end{array}

The diagonal argument in its general form.​

We want to prove that if $A = {a, b, c, d, ...}$ is an infinite set, then it has more subset than the number of elements. Suppose that this is not the case so we would be able to equate $a, b, c, d, ...$ with all its subset exhaustively (illustrated in the rows of the above table, each subset would occur). However, take the elements $A = {a, b, c, d, ...}$ that are not included in the subset corresponding to it. This is the $A^*$ set. (Illustrated where there is no $X$ in the diagonal of the above table.)

..................................
This is definitely a subset of the set $A$, at most the empty set.

The question is, is this $A^*$ set assigned to one of $a, b, c, ...$?

• If it were assigned to an $x^*$ element that is not in the assigned subset, then we get a contradiction because we chose the elements of $A^*$ by taking the elements that are not in the subset that is associated with it. (In the table, if there was no $X$ in the diagonal, we had the item.) However, the assignment shows that $x^*$ should be in $A^*$.
• If $A^*$ were assigned to an $x^*$ element that is included in the assigned subset, then we also get a contradiction because we chose the elements of $A^*$ to exclude the elements that are in the subset assigned to it. (In the table, if the diagonal was a letter $X$, we didn't need the item.) However, due to the assignment, $x^*$ could not be in $A^*$ .

 

[JeffJo]

I'm not sure if the OP is even following this anymore, but the points people want to make seem to be becoming muddled and not addressing the question.

Here is an outline of how Cantor's Diagonal Argument works. Note that only addresses how there must be a cardinality greater than Aleph0. Cantor's Theorem, which seems to be what Periwinkle addressed, is more general.

1. For an appropriate, infinite set T.
2. Let S be any subset, proper or improper, of T that can be put into an infinite sequence S1, S2, S3, ...
3. Define a "diagonalizing algorithm" on set T to be an algortihm such that:
   • The object produced, d, is a member of T.
   • Guarantees that d is different from Sn for every n.
4. If we can define T and a diagonalizing algorithm on T, then T cannot be put into a sequence.
   • Because every possible sequence S necessarily omits a member of T.

Here is the original question:

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.

Like most treatments, this inserts steps into the argument, that the author thinks are trivial and/or transparent. The set T in this passage is not the set of reals in [0,1], which I call R1. It is a set of strings that can be interpreted as members of R1. But numbers are not the same mathematical objects, and the translation between the two sets is not as transparent as some would believe. And it is the translation process that causes the "error" that FLO TUR alleges.

All this accomplishes, is obfuscation of the proof. FLO TUR showed only that inappropriate choices for T and/or the diagonalizing algorithm may not prove the result. That doesn't mean that there aren't appropriate choices that do. They are easiest to show using the choices Cantor actually used: T is teh set of all possible, infinite-length, binary strings. The algorithm selects the diagonal character in each string of the sequence, and inverts it.

 

[TeethWhitener]

Why not start with binary, but subtly do your operations in base 4? Just change two bits at a time such that they don't get changed to 11. So break up
$$a = 0.01110100101011 $$
into pairs of bits, like so
$$a = 0.\text{ } 01\text{ } 11\text{ } 01\text{ } 00 \text{ }10\text{ } 10\text{ } 11$$
and change each pair of bits for a pair from the set $\{00, 01, 10\}$, such that if $a$ is in the first position on your list, you get (e.g.,)
$$a_1 = 0.\text{ } \color{red}{\mathbf{10}}\text{ } 11\text{ } 01\text{ } 00\text{ } 10\text{ } 10\text{ } 11$$
If $a$ is in the second position, you get (e.g.,)
$$a_2 = 0. \text{ } 01\text{ } \color{red}{\mathbf{00}}\text{ } 01\text{ } 00\text{ } 10\text{ } 10\text{ } 11$$
etc. You're still in a binary representation, but you're basically doing operations as if you were in base 4.

 

[JeffJo]

Why not start with binary, but subtly do your operations in base 4?

Why apply it to real numbers at all? Cantor didn't.

It's an elegant proof. Burdening it with unnecessary details diminishes that.

 

[stevendaryl]

Why apply it to real numbers at all? Cantor didn't.

It's an elegant proof. Burdening it with unnecessary details diminishes that.

Well, the point is that the set that people are most interested in is the reals, not the infinite binary strings. They are only interested in the latter because they can be used to represent reals.

But of course, it's pretty simple to see that the cardinality of the reals is equal to that of the infinite binary strings.

 

[TeethWhitener]

Why apply it to real numbers at all? Cantor didn't.

Because that’s what the OP asked about?

 

[FactChecker]

But of course, it's pretty simple to see that the cardinality of the reals is equal to that of the infinite binary strings.

But isn't it critical to show that the example which the diagonal process comes up with is a real number which is not on the list in another form?