My Math Forum  

Go Back   My Math Forum > Math Forums > Math

Math General Math Forum - For general math related discussion and news


Thanks Tree15Thanks
Reply
 
LinkBack Thread Tools Display Modes
January 10th, 2017, 04:11 PM   #1
Member
 
Joined: Jun 2014
From: Alberta

Posts: 55
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.
Mathbound is offline  
 
January 10th, 2017, 04:32 PM   #2
Math Team
 
Joined: Dec 2013
From: Colombia

Posts: 6,778
Thanks: 2195

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.
Thanks from Mathbound and SDK

Last edited by v8archie; January 10th, 2017 at 04:35 PM.
v8archie is offline  
January 10th, 2017, 05:35 PM   #3
SDK
Senior Member
 
Joined: Sep 2016
From: USA

Posts: 114
Thanks: 44

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.
Thanks from Mathbound
SDK is offline  
January 10th, 2017, 06:04 PM   #4
Member
 
Joined: Jun 2014
From: Alberta

Posts: 55
Thanks: 2

Quote:
Originally Posted by v8archie View Post
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.
But I can show the exact same thing when listing the rationals. I can use the same kind of rule so that at least one rational is not listed.
Mathbound is offline  
January 10th, 2017, 06:49 PM   #5
Global Moderator
 
greg1313's Avatar
 
Joined: Oct 2008
From: London, Ontario, Canada - The Forest City

Posts: 7,488
Thanks: 887

Math Focus: Elementary mathematics and beyond
Quote:
Originally Posted by Mathbound View Post
But I can show the exact same thing when listing the rationals. I can use the same kind of rule so that at least one rational is not listed.
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.
Thanks from topsquark and Mathbound
greg1313 is offline  
January 10th, 2017, 08:02 PM   #6
Senior Member
 
Joined: Aug 2012

Posts: 1,371
Thanks: 321

Quote:
Originally Posted by Mathbound View Post
But I can show the exact same thing when listing the rationals. I can use the same kind of rule so that at least one rational is not listed.
Here's a cool little way to fit all the rationals inside the natural numbers, with plenty of natural numbers left over.

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 one-to-one, 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.
Thanks from topsquark and Mathbound

Last edited by Maschke; January 10th, 2017 at 08:23 PM.
Maschke is offline  
January 10th, 2017, 08:51 PM   #7
Math Team
 
Joined: Dec 2013
From: Colombia

Posts: 6,778
Thanks: 2195

Math Focus: Mainly analysis and algebra
Quote:
Originally Posted by Mathbound View Post
But I can show the exact same thing when listing the rationals. I can use the same kind of rule so that at least one rational is not listed.
You can't show that for every listing of rationals.

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.
Thanks from Mathbound

Last edited by v8archie; January 10th, 2017 at 09:49 PM.
v8archie is offline  
January 10th, 2017, 10:23 PM   #8
Member
 
Joined: Jun 2014
From: Alberta

Posts: 55
Thanks: 2

Quote:
Originally Posted by v8archie View Post
You can't show that for every listing of rationals.

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.
Thanks, but I just watched a video from a university lecture, and a student had a similar issue. The professor said that reals can be infinitely long decimals. So I suppose you could never exhaust an irrational like pi with n still as a natural number.

Is that what the argument is essentially about?

Last edited by Mathbound; January 10th, 2017 at 10:27 PM.
Mathbound is offline  
January 10th, 2017, 10:33 PM   #9
Math Team
 
Joined: Dec 2013
From: Colombia

Posts: 6,778
Thanks: 2195

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.
v8archie is offline  
January 10th, 2017, 11:11 PM   #10
Member
 
Joined: Jun 2014
From: Alberta

Posts: 55
Thanks: 2

Quote:
Originally Posted by v8archie View Post
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.
But you could guarantee it to be a rational depending on the rule, right?
Mathbound is offline  
Reply

  My Math Forum > Math Forums > Math

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 07:13 AM
Cantor's Diagonal Argument Reconsidered zylo Topology 12 March 24th, 2016 09: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 07:22 AM
Cantorīs diagonal argument netzweltler Applied Math 191 November 7th, 2010 02:39 PM





Copyright © 2017 My Math Forum. All rights reserved.