January 10th, 2017, 04:11 PM  #1 
Member Joined: Jun 2014 From: Alberta Posts: 56 Thanks: 2  I don't see the significance of Cantor's diagonal argument
I know it shows that we can exhaust all of the naturals leaving out a real number by implementing a rule. But we can do the same thing with matching the naturals with rationals. For example, we can exhaust all elements of N by just matching each of them to each element in the infinite set of rationals, {0.3, 0.33, 0.333 ... 1/3} while leaving out an infinite number of other rationals. I just can't see how leaving out one real number or leaving out a set of 1's and 0's (which ever version of the argument you prefer) demonstrates that the reals tally to a larger infinity. 
January 10th, 2017, 04:32 PM  #2 
Math Team Joined: Dec 2013 From: Colombia Posts: 7,598 Thanks: 2583 Math Focus: Mainly analysis and algebra 
The point of the proof is that there exist no orderings of the real numbers that permit a bijection to the natural numbers. Such orderings do exist for the rational numbers and even for the algebraic numbers. The demonstration is that whatever list of reals you have, there is at least one real number that is not in that list. In fact there are uncountably many real numbers that are not in the list, not just one. Last edited by v8archie; January 10th, 2017 at 04:35 PM. 
January 10th, 2017, 05:35 PM  #3 
Senior Member Joined: Sep 2016 From: USA Posts: 555 Thanks: 319 Math Focus: Dynamical systems, analytic function theory, numerics 
You are exhibiting that there exists a mapping of the natural numbers to rationals which is not a surjection. This doesn't prove that there doesn't exist a mapping which is a surjection. In fact, it is easy to prove that there is. Cantor's proof does something different. He doesn't show that there is a mapping from the naturals to the reals which is not a surjection. He shows that every such mapping to the reals is not a surjection implying no bijection exists. 
January 10th, 2017, 06:04 PM  #4  
Member Joined: Jun 2014 From: Alberta Posts: 56 Thanks: 2  Quote:
 
January 10th, 2017, 06:49 PM  #5 
Global Moderator Joined: Oct 2008 From: London, Ontario, Canada  The Forest City Posts: 7,912 Thanks: 1110 Math Focus: Elementary mathematics and beyond  Then do that here, so folks can analyse your work and give feedback that would be accurate in terms of addressing any misunderstandings you may have.

January 10th, 2017, 08:02 PM  #6  
Senior Member Joined: Aug 2012 Posts: 2,156 Thanks: 630  Quote:
I'll do this first for the positive fractions, which are all the expressions of the form $\frac{n}{m}$ where $n$ and $m$ are nonnegative integers ($0, 1, 2, 3, \dots$) and $m$ isn't zero. The positive rational numbers, just to clarify this distinction, are all the unique equivalence classes of fractions; where we say that the fractions $\frac{1}{2}$, $\frac{2}{4}$, $\frac{3}{6}$, etc. all represent the same rational number. There are at least as many fractions as rational numbers, so if I can squeeze the fractions into the naturals I'll be done. Now given a fraction $\frac{n}{m}$, I can calculate the natural number $2^n \times 3^m$, which is some natural number. By the Fundamental Theorem of Arithmetic (FTA), which says that every natural number has a unique factorization into prime powers, we know that no combination of $m$ and $n$ can possibly calculate out to the same number as any other one. https://en.wikipedia.org/wiki/Fundam..._of_arithmetic So the function $f(n, m) = 2^n \times 3^m$ is onetoone, or injective, meaning that different pairs go to different natural numbers. It maps pairs of natural numbers to single natural numbers in such a way that different pairs go to different natural numbers. But there are plenty of natural numbers that don't get hit by $f$. For example there's no way to hit $5$. So we can map pairs of natural numbers comfortably inside the set of natural numbers with plenty of natural numbers left over. Another way to think about this is that perhaps I have to send a secret spy message of vital importance consisting of two natural numbers. But I am only allowed to send out one number, not two. Maybe the spies on the other side can't detect one number, but if I send two they'll be able to capture me. So I encode my two numbers into one using the above trick; and the receiver of my message simply calculates the prime power factorization of my number and recovers the original pair. So we see that if we want, we can make the set of rational numbers appear no larger than the set of whole numbers. We can map the rationals into a proper subset of the naturals. This is a typical cardinality argument. Intuition isn't always reliable. The point in this case is that although SOME mappings from the rationals to the naturals leave out some rationals; other mappings exhaust all the rationals without using up all the naturals! In fact that furnishes a proof that the rationals and the naturals have the same cardinality; that there are injections going both ways. But as others have mentioned, there is no injective mapping from the reals to the naturals. Every attempt will result in reals left over. The injection only goes one way. Last edited by Maschke; January 10th, 2017 at 08:23 PM.  
January 10th, 2017, 08:51 PM  #7  
Math Team Joined: Dec 2013 From: Colombia Posts: 7,598 Thanks: 2583 Math Focus: Mainly analysis and algebra  Quote:
You may be trying to say that exactly the same construction works. The problem with this though is that the new number that we construct is not guaranteed to be a rational number. This is where the argument fails for the rationals, as it must because we can demonstrate orderings that suffice. Last edited by v8archie; January 10th, 2017 at 09:49 PM.  
January 10th, 2017, 10:23 PM  #8  
Member Joined: Jun 2014 From: Alberta Posts: 56 Thanks: 2  Quote:
Is that what the argument is essentially about? Last edited by Mathbound; January 10th, 2017 at 10:27 PM.  
January 10th, 2017, 10:33 PM  #9 
Math Team Joined: Dec 2013 From: Colombia Posts: 7,598 Thanks: 2583 Math Focus: Mainly analysis and algebra 
Having an infinitely long decimal representation for each of the reals is necessary to the argument. Of course, rationals also have an infinitely long decimal representation, but not every infinitely long decimal is a rational number. Thus the number we construct under Cantor's scheme is guaranteed to be a real number, but is not guaranteed to be a rational number.

January 10th, 2017, 11:11 PM  #10  
Member Joined: Jun 2014 From: Alberta Posts: 56 Thanks: 2  Quote:
 

Tags 
argument, cantor, diagonal, significance 
Thread Tools  
Display Modes  

Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Cantor's Diagonal Argument and Infinity  zylo  Topology  59  May 21st, 2016 08:13 AM 
Cantor's Diagonal Argument Reconsidered  zylo  Topology  12  March 24th, 2016 10:53 AM 
Cantor's Diagonal Argument  zylo  Math  22  January 26th, 2016 09:05 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 