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

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

 

[stevendaryl]

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?

No, my argument is this:

1. Cantor's diagonal argument proves that there are uncountably many infinite binary strings. The binary string "0.01111.." is a different string than "0.1000..."
2. The cardinality of the reals in $[0,1]$ is the same as the cardinality of the infinite binary strings.
3. Therefore, there are uncountably many reals in $[0,1]$

 

[TeethWhitener]

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

Echoing @FactChecker , it's simple to see that the cardinality of the infinite binary strings is equal to the cardinality of the powerset of the natural numbers. I'm not sure it's so easy to see that the cardinality of the reals is equal to this as well.

 

[stevendaryl]

Echoing @FactChecker , it's simple to see that the cardinality of the infinite binary strings is equal to the cardinality of the powerset of the natural numbers. I'm not sure it's so easy to see that the cardinality of the reals is equal to this as well.

Well, we can split up the infinite binary strings into three sets:

1. $A$ = Those with only finitely many 0s
2. $B$ = Those with only finitely many 1s
3. $C$ = Those with infinitely many 0s and infinitely many 1s

Since sets $A$ and $B$ are countable, and the union $A \cup B \cup C$ is uncountable, it follows that $C$ must be uncountable. But $C$ has a one-to-one correspondence with a subset of the reals in $[0,1]$. So that subset must be uncountable, as well.

 

[jbriggs444]

Or go with Schroeder-Bernstein.

There is an injection⁽¹⁾ from the reals in [0,1) to the binary strings. Just take the canonical decimal expansion of each real.

There is an injection from the binary strings to the reals. Rewrite each 0 as 01, each 1 as 10 and interpret the resulting string as a binary decimal expansion of a real number. By construction, it cannot end in all zeroes or in all ones.

By the Schroeder-Bernstein theorem, it follows that there is a bijection between the reals and the binary strings. QED.

(1): An injection or a "one to one" function maps distinct elements in the domain to distinct elements in the range. No element in the range is re-used.

 

[JeffJo]

Because that’s what the OP asked about?

Oh? Where? The start of the thread was not a question. It was the claim to have found a counterexample to the proof. A counterexample that was based on a misunderstanding that can exist only when the proof is applied to the real numbers.

So, a good reason to not use the real numbers is that these misunderstanding would not arise. I still see no reason to use them. Not even...

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.

Which came first, the chicken or the egg?

Similarly, which came first, the interest in whether the reals were uncountable, or applying the proof to them because they seem to be a more recognizable set?

Cantor's interest was never about what sets had what cardinalities, it was that he could order the cardinalities of infinite sets.

 

[TeethWhitener]

Well, we can split up the infinite binary strings into three sets:

1. $A$ = Those with only finitely many 0s
2. $B$ = Those with only finitely many 1s
3. $C$ = Those with infinitely many 0s and infinitely many 1s

Since sets $A$ and $B$ are countable, and the union $A \cup B \cup C$ is uncountable, it follows that $C$ must be uncountable. But $C$ has a one-to-one correspondence with a subset of the reals in $[0,1]$. So that subset must be uncountable, as well.

Minor point: this says that the cardinality of the reals is greater than or equal to the cardinality of $C$, not strictly equal. If you're concerned about showing that the cardinality of the reals is greater than the cardinality of the naturals, it's sufficient.

I still see no reason to use them.

Given post #46, I see no reason not to use them.

 

[FactChecker]

The cardinality of the reals in $[0,1]$ is the same as the cardinality of the infinite binary strings.

I agree, but since there are multiple binary strings for some reals, something more must be said to rigorously conclude this. There are simple ways to avoid this issue.

 

[JeffJo]

Circular logic, applied to excepts, doesn't help:

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

Given post #46, I see no reason not to use them.

Post #46:

Why not start with binary, but subtly do your operations in base 4? ...[valid demonstration omitted]...

Post #47:

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

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

[Emphasis added.]

So let me repeat:

1. Cantor's second proof, which is the subject of this thread, was intended to be a proof of "the proposition that there is an infinite manifold, which cannot be put into a one-one correlation with the totality of all finite whole numbers." That's a quote.
   1. All that is needed to prove this is an example set.
   2. Cantor specifically chose to use an example set that wasn't the real numbers. He chose strings.
   3. It is a remarkably elegant proof.
2. It can be applied to the reals in [0,1].
   1. To do so requires transforming the reals into strings, and the strings into reals.
   2. There are complications in doing so that are often not recognized.
   3. So it is less elegant.
3. Nearly every attempt to "disprove" the proof involves those complications.
   1. Using strings as the example invalidates those attempts.
   2. Continuing to use the real numbers allows the authors of those attempts to believe they are right.
   3. AND THIS THREAD IS AN EXAMPLE OF EXACTLY THAT.
4. Still, the complications are surmountable.
   1. Doing so as the initial presentation of the proof adds unnecessary steps that add to the confusion of beginning students (and sometimes students who think they are quite advanced).
   2. But it can done as an addendum once the proof is understood.
   3. As an addendum, it on;ly needs to be done once. It is both more understandable, and easier, to do it in base 10. The students will recognize the applicability, and the diagonalization method is straight forward.

Do you disagree with any of this? Which part?

 

[FactChecker]

I think that there are benefits to using the set of real numbers as an example. The application of the proof to such a familiar object as the real numbers has some appeal. By using the decimal representation of the reals, it is also possible to point out that there are unimaginably more reals than there are natural numbers (and rational, if one wants to show how to count them). It makes it very natural to anticipate the rational numbers having Lebesgue measure zero while the reals have measure 1.

 

[JeffJo]

I think that there are benefits to using the set of real numbers as an example. The application of the proof to such a familiar object as the real numbers has some appeal.

And that application can be pointed out after the proof is understood (see point #4.2). Until then, it gets in the way (see point #3). Evidence: search the internet for people who claim to have disproved it. Start with post #1 of this thread. How many of these claims are based on the parts added to the proof to make it apply to real numbers?

All I am asking, is that you you compare the benefits and detriments.

By using the decimal representation of the reals, it is also possible to point out that there are unimaginably more reals than there are natural numbers (and rational, if one wants to show how to count them). It makes it very natural to anticipate the rational numbers having Lebesgue measure zero while the reals have measure 1.

I really do think this is a chicken v. egg point you make. Experienced people want to see it applied to real numbers because it was first presented to them that way. Not because it helps the inexperienced to understand it. And as I keep pointing out, it gets in the way.

 

[FactChecker]

One can use the decimal representation of the real numbers that everyone is familiar with since 4th grade and avoid the 999... issue simply by never allowing the infinite 9 representation in the list and never using 9 on the diagonal. That is concrete and familiar and does not require any abstraction to infinite lists. IMO, abstraction to the general list is easier to motivate after seeing a concrete example.

 

[TeethWhitener]

Do you disagree with any of this?

Nope. You win.

 

[Mark44]

One can use the decimal representation of the real numbers that everyone is familiar with since 4th grade and avoid the 999... issue simply by never allowing the infinite 9 representation in the list and never using 9 on the diagonal. That is concrete and familiar and does not require any abstraction to infinite lists. IMO, abstraction to the general list is easier to motivate after seeing a concrete example.

Sounds eminently reasonable to me.