August 15th, 2016, 03:34 PM  #11 
Senior Member Joined: Aug 2012 Posts: 1,661 Thanks: 427  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, 05:57 PM  #12  
Math Team Joined: Dec 2013 From: Colombia Posts: 7,091 Thanks: 2360 Math Focus: Mainly analysis and algebra  Quote:
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, 06:39 PM  #13  
Senior Member Joined: May 2016 From: USA Posts: 857 Thanks: 348 
Do you mean this post? Quote:
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, 06:53 PM  #14 
Math Team Joined: Dec 2013 From: Colombia Posts: 7,091 Thanks: 2360 Math Focus: Mainly analysis and algebra  
August 15th, 2016, 07:37 PM  #15  
Senior Member Joined: Aug 2012 Posts: 1,661 Thanks: 427  Yes. Quote:
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. 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:
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: 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 08:13 PM.  
August 15th, 2016, 08:08 PM  #16  
Senior Member Joined: May 2016 From: USA Posts: 857 Thanks: 348  Quote:
(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 11 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, 08:46 PM  #17  
Senior Member Joined: Aug 2012 Posts: 1,661 Thanks: 427  Quote:
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:
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:
Quote:
We do not need to go back the other way and show that every real has a bitstring. Yes you convinced me! Quote:
Quote:
In fact the bitstring approach serves to demonstrate that there is SOME uncountable set; after which the standard decimalbased 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 09:06 PM.  
August 16th, 2016, 06:32 AM  #18 
Senior Member Joined: May 2016 From: USA Posts: 857 Thanks: 348 
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  

Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Cantor's diagonal proof and the real numbers  zylo  Topology  8  March 31st, 2016 03:00 PM 
Help! Cantor's Diagonal Argument  mjcguest  Applied Math  9  July 25th, 2013 08:22 AM 
Cantor´s diagonal argument  netzweltler  Applied Math  191  November 7th, 2010 02:39 PM 
Counting the reals: Cantor's Diagonal Proof  ch00blet  Applied Math  3  January 12th, 2010 12:50 PM 
Cantor diagonal functions  Barbarel  Number Theory  2  April 10th, 2009 03:59 PM 