My Math Forum Question about Cantor's Diagonal Proof

 Topology Topology Math Forum

August 15th, 2016, 02:34 PM   #11
Senior Member

Joined: Aug 2012

Posts: 1,886
Thanks: 522

Quote:
 Originally Posted by JeffM1 Do you have a proof for that assertion?
Do I need one?

JeffJo sketched out the proof the other day via bisecting intervals. Formal proofs can be found by Googling. As far as how anyone knew anything before Google, that's unknown. Back in those days you had to rely on vigorous handwaving.

August 15th, 2016, 04:57 PM   #12
Math Team

Joined: Dec 2013
From: Colombia

Posts: 7,305
Thanks: 2443

Math Focus: Mainly analysis and algebra
Quote:
 Originally Posted by JeffM1 I have learned to be suspicious of the "obvious" when it comes to real numbers and the infinite. I agree that it is very hard to conceive how that proposition can be false, but absent citation to a proof, I shall continue to be agnostic.
It's good to be suspicious of "obvious", but think you can take some things (in the mainstream) as read - at least until you find the proof.

Anyhow, the proof that Maschke has alluded too is perfectly serviceable. In particular, since the real numbers are a complete, ordered field under addition and multiplication we have all that we require for the proof to work. The only possible problem being that we may have taken two different definitions of the real numbers to get the two results. But again you should be able to find a proof that the two definitions are equal.

August 15th, 2016, 05:39 PM   #13
Senior Member

Joined: May 2016
From: USA

Posts: 1,027
Thanks: 419

Do you mean this post?

Quote:
 Originally Posted by JeffJo Say X(0) is a real number between 0 and 1.If X(0)>=1/2, then B(1)=1; otherwise, B(1)=0. Then, let X(1)=(X(0)-B(1))*2 If X(1)>=1/2, then B(2)=1; otherwise, B(2)=0. Then, let X(2)=(X(1)-B(2))*2 In general, If X(N-1)>=1/2, then B(N)=1; otherwise, B(N)=0. Then, let X(N)=(X(N-1)-B(N))*2 Finding a closed-form way to evaluate each inequality may become problematic- like if X(0) is non-algebraic - but the cardinality of the set of the algorithms defined as I just did is the same as the cardinality of the set real numbers between 0 and 1. But this is all I meant. An abstract definition. The next most prevalent misconception about Cantor's proof, is confusing the abstract with the physical.
Is this the post you are discussing? It is more of a sketch of a sketch than a proof and did not seem to persuade anyone at the time.

However, you are correct. Google is a friend, and I too can now see what JeffJo was sketching.

This I think is what I was looking for initially.

Can every real number be represented by a (possibly infinite) decimal? - Mathematics Stack Exchange

So that proposition can be proved. Good

But I still think it is interesting that the proposition is totally unnecessary to show that the reals have a higher cardinality than the natural numbers.

Anyway, my thanks are sincere for following through on this.

August 15th, 2016, 05:53 PM   #14
Math Team

Joined: Dec 2013
From: Colombia

Posts: 7,305
Thanks: 2443

Math Focus: Mainly analysis and algebra
Quote:
 Originally Posted by JeffM1 Anyway, my thanks are sincere for following through on this.
No problem. It's always a pleasure to (try to) help somebody who asks for assistance to understand something.

It's people who don't understand but don't attempt to learn that irritate me.

August 15th, 2016, 06:37 PM   #15
Senior Member

Joined: Aug 2012

Posts: 1,886
Thanks: 522

Quote:
 Originally Posted by JeffM1 Do you mean this post?
Yes.

Quote:
 Originally Posted by JeffM1 Is this the post you are discussing? It is more of a sketch of a sketch than a proof and did not seem to persuade anyone at the time.
I glazed over the first time and went off on a tangent (interesting as it was) about algorithms. The second time I realized it's a sketch of a sketch of a proof that every real number is defined by a bitstring. It so captures the core concept that it might as well be a proof.

You know when Perelman solved the PoincarĂ© conjecture and turned down both the Fields medal AND his million dollar Millennium prize, his proof was seen as correct yet hugely missing in detail. He gave a sketch of a sketch but he got credit. A Chinese team later filled in the details and did not get the credit. In fact they got accused of stealing Perelman's ideas. No good deed goes unpunished.

There is no general agreement on how much detail a proof must have. JeffFo's argument snapped my brain into alignment on this issue. The bisection idea is the key. The rest of the proof is technique. A lot of it.

Quote:
 Originally Posted by JeffM1 So that proposition can be proved. Good
I started to look at online proofs then stopped myself, thinking I might take a run at it. I see right away thati t will be a tedious amount of detailed work. I may or may not do it. It's character building but I'm not sure I want that much character!

Quote:
 Originally Posted by JeffM1 But I still think it is interesting that the proposition is totally unnecessary to show that the reals have a higher cardinality than the natural numbers.
You've mentioned that a couple of times. I don't think I understand what you mean. If you know that the bitstrings are uncountable you have to prove that the reals are equinumerous with the bitstrings. And to do that I think you have to go through the binary expansion. Or perhaps not? Maybe you're right.

Quote:
 Originally Posted by JeffM1 Anyway, my thanks are sincere for following through on this.
This is the coolest stuff IMO.

I wanted to make a remark about approaching this proof.

Suppose we want to prove that every real number has a binary expression. But wait! What is a real number? Every student has heard that a real number is an "infinite binary expression like $.333\dots$ or $\pi$" and that's the last time they ever gave the matter any thought.

Now instead of defining a real number as an infinite decimal; we have to define a real number as something else and then show that the thing we've defined has a decimal expression. To get started we have to make philosophical and pedagogical choices and map out a proof strategy. So this is not the typical "plug and chug" from definitions. We have to work out our own definitions and figure out what we're trying to say.

For example v8archie said:

Quote:
 Originally Posted by v8archie $\mathbb R$ can be defined as the completion of $\mathbb Q$ with respect to the metric $|x-y|$
This gets full marks in real analysis class; but does not (in my opinion) fully satisfy the expositional problem of convincing our naive doubter. It's close though. I think at some point we're going to have to tell people that every real is the limit of a sequence of rationals. That fact will be enough to make all this go through. Hmmm. I see that we are going to need the fact that every real is the limit of a sequence of dyadic rationals. Those are the terminating binary expressions, or finite sums of negative integer powers of $2$. If we can arbitrarily approximate a real number with a terminating binary expression we'll be able to get our proof in both directions. Every bitstring gives a real; and ever real has a bitstring.

Last edited by Maschke; August 15th, 2016 at 07:13 PM.

August 15th, 2016, 07:08 PM   #16
Senior Member

Joined: May 2016
From: USA

Posts: 1,027
Thanks: 419

Quote:
 Originally Posted by Maschke You've mentioned that a couple of times. I don't think I understand what you mean. If you know that the bitstrings are uncountable you have to prove that the reals are equinumerous with the bitstrings. And to do that I think you have to go through the binary expansion. Or perhaps not? Maybe you're right.
I'll try to sketch what I mean again, particularly now that see that I scrambled my own notation the first time around. This may be a sketch of a sketch of a sketch.

(1) We start with T as the set of all infinite bit strings. We do the diagonal algorithm and show that T has greater cardinality than N, the set of natural numbers. I agree with you and JeffJo that this is a very intuitive and clear way to show that there is cardinality greater than N.

(2) We then follow Archie and interpret the bit strings as reals between (0, 1). Still following Archie, we split T into two exhaustive but mutually exclusive sets. A contains exactly one of each pair of dual representations, and B contains everything else. It is almost trivial to show that A can be put into 1-1 correspondence with N. Therefore B cannot be put into such a correspondence because T has no such correspondence, and A + B is T. In other words B has a cardinality greater than N.

(3) Now, B is clearly a subset of R. Therefore R has either the same cardinality as B or greater cardinality than B. In either case, R has greater cardinality than N.

If that argument is correct (and if it is flawed, I'd sincerely like to know), the issue of proving that B is R is irrelevant to proving that R has greater cardinality than N.

August 15th, 2016, 07:46 PM   #17
Senior Member

Joined: Aug 2012

Posts: 1,886
Thanks: 522

Quote:
 Originally Posted by JeffM1 (2) We then follow Archie and interpret the bit strings as reals between (0, 1).
How? Given a bitstring $(b_i)_{i \in \mathbb Z^+}$ (I hope that notation is clear) we need to show that the infinite series $\sum_{i=1}^\infty \frac{b_i}{2^i}$ represents some real number. To do that we have to know that the sum of a series is the limit of the partial sums; and then we need to know what is the limit of a sequence. We are going to have to show our naive doubter some real analysis.

Otherwise for all we know those infinite series fly into space and don't represent real numbers at all. For example if we tried to do the same proof with the rational numbers we would find that most of the bitstrings don't hit rationals. We need the concept that the reals are complete; that there are no "holes" in them where a binary series might fall off the world.

I envision our doubter as tough but fair. We have a logic gap here that requires knowledge of limits and the completeness of the reals.

Going the other way, we need to show that every real has a bitstring ... but perhaps you are saying we don't need this direction. [Jumping ahead -- yes we DON'T need this! Now I understand your point].

Quote:
 Originally Posted by JeffM1 Still following Archie, we split T into two exhaustive but mutually exclusive sets. A contains exactly one of each pair of dual representations
Ok we have to show that not only does each bitstring converge to a real number, but that all but countably many bitstrings converge to distinct numbers; and that the exceptions fall into classes of 2 bitstrings per single real number. You see the snakepit of drilling this down for our naive doubter. I don't think any of this is trivial if you never thought about it before.

Perhaps doing this with decimals is easier! You don't have to do the real analysis if you start by assuming a real number IS an infinite decimal. We may have to revise our opinion as to which is the better approach. The leap from bitstrings to decimals requires knowledge of limits. Starting with decimals doesn't, since students are already predisposed to think of real numbers as decimals.

Quote:
 Originally Posted by JeffM1 and B contains everything else. It is almost trivial to show that A can be put into 1-1 correspondence with N.
Doesn't look trivial to me at all. "Almost" trivial, well maybe

Quote:
 Originally Posted by JeffM1 Therefore B cannot be put into such a correspondence because T has no such correspondence, and A + B is T. In other words B has a cardinality greater than N.
I now see your diabolical point. Once we know that every bitstring gives a real; and that there's an uncountable set of bitstrings each of which gives a distinct real; we are done. We do not care if we have perhaps missed a lot of reals, because the reals are a superset of our bitstring targets and are therefore uncountable.

We do not need to go back the other way and show that every real has a bitstring. Yes you convinced me!

Quote:
 Originally Posted by JeffM1 (3) Now, B is clearly a subset of R. Therefore R has either the same cardinality as B or greater cardinality than B. In either case, R has greater cardinality than N.
Right. For all we know we barely scratched the surface of the reals by hitting them with bitstrings. There are more reals than bitstrings and there are uncountably many bitstrings so we're done.

Quote:
 Originally Posted by JeffM1 If that argument is correct (and if it is flawed, I'd sincerely like to know), the issue of proving that B is R is irrelevant to proving that R has greater cardinality than N.
Yes you've got it. But the transition from bitstrings to reals involves limits and the completeness of the reals; and perhaps that's too much for our naive doubter. I no longer think bitstrings are simpler unless your doubter is willing to believe the infinite binary sums converge.

In fact the bitstring approach serves to demonstrate that there is SOME uncountable set; after which the standard decimal-based diagonal argument might be more believable. The conversion from bitstrings to real numbers is harder than it looks.

You can really begin to see why so many people DO doubt the diagonal proof. Cantor and his contemporaries well understood basic real analysis, which had been developed by Cauchy and Dedekind and Weirstrass earlier. But these are very sophisticated ideas about the real numbers that are not available to our naive doubters.

Last edited by Maschke; August 15th, 2016 at 08:06 PM.

 August 16th, 2016, 05:32 AM #18 Senior Member   Joined: May 2016 From: USA Posts: 1,027 Thanks: 419 Couple of thoughts before this thread is wrapped up. First, this was fun. Thanks Maschke and Archie for going along. Second, some admissions. I found real analysis so ugly that I dropped it within days and never took another math class at Columbia. So I know more analysis than my dog, but not by much. When I was in graduate school (not at Columbia), I decided I needed to know more math and took more courses, but nothing to do with calculus or the nature of real numbers. Moreover, I never taught a course in anything. I have tutored online and at the local public library since I retired. This has taught me some things about teaching, but not en masse. And I don't touch analysis; in fact I scarcely ever touch integral calculus because I have forgotten 90% of it. Third. What the bit string approach does is to provide an intuitive proof that, if you accept infinity at all, there are different levels of infinity, however we label them. I am very grateful to you two and JeffJo for opening up my eyes to that approach. But it is, I suspect, the very idea of different levels of infinity that sets some people's teeth on edge and causes them to doubt Cantor's proof. They do not care emotionally about the nature of real numbers. The guy who wanted to use only one symbol to represent the real numbers actually said that what he objected to was the idea of different cardinalities of infinity. In other words, all the twists and turns about representing real numbers from Zylo et al. never get to what is fundamentally bothering most of them. If the hurdle of different cardinalities of infinity can be jumped over using the bit strings approach, my follow up question about extending the argument to the cardinalities of the real numbers is not likely to come up. If the question does come up, I doubt that it is any harder to deal with the reals through binary notation than through decimal notation, but people are a lot more familiar with decimal fractions than binary ones. By the way, if we do take the route of bit strings to binary representations, we have to define the interval as [0, 1] because T as the set of all infinite bit strings includes the strings of all zeroes and all ones.

 Tags cantor, diagonal, proof, question

 Thread Tools Display Modes Linear Mode

 Similar Threads Thread Thread Starter Forum Replies Last Post zylo Topology 8 March 31st, 2016 02:00 PM mjcguest Applied Math 9 July 25th, 2013 07:22 AM netzweltler Applied Math 191 November 7th, 2010 01:39 PM ch00blet Applied Math 3 January 12th, 2010 11:50 AM Barbarel Number Theory 2 April 10th, 2009 02:59 PM

 Contact - Home - Forums - Cryptocurrency Forum - Top