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

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