My Math Forum > Math I don't see the significance of Cantor's diagonal argument

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

 January 10th, 2017, 03: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, 03:32 PM #2 Math Team   Joined: Dec 2013 From: Colombia Posts: 7,635 Thanks: 2620 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 03:35 PM.
 January 10th, 2017, 04:35 PM #3 Senior Member   Joined: Sep 2016 From: USA Posts: 598 Thanks: 366 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
January 10th, 2017, 05:04 PM   #4
Member

Joined: Jun 2014
From: Alberta

Posts: 56
Thanks: 2

Quote:
 Originally Posted by v8archie 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.

January 10th, 2017, 05:49 PM   #5
Global Moderator

Joined: Oct 2008
From: London, Ontario, Canada - The Forest City

Posts: 7,929
Thanks: 1124

Math Focus: Elementary mathematics and beyond
Quote:
 Originally Posted by Mathbound 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.

January 10th, 2017, 07:02 PM   #6
Senior Member

Joined: Aug 2012

Posts: 2,258
Thanks: 682

Quote:
 Originally Posted by Mathbound 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.

Last edited by Maschke; January 10th, 2017 at 07:23 PM.

January 10th, 2017, 07:51 PM   #7
Math Team

Joined: Dec 2013
From: Colombia

Posts: 7,635
Thanks: 2620

Math Focus: Mainly analysis and algebra
Quote:
 Originally Posted by Mathbound 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.

Last edited by v8archie; January 10th, 2017 at 08:49 PM.

January 10th, 2017, 09:23 PM   #8
Member

Joined: Jun 2014
From: Alberta

Posts: 56
Thanks: 2

Quote:
 Originally Posted by v8archie 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 09:27 PM.

 January 10th, 2017, 09:33 PM #9 Math Team   Joined: Dec 2013 From: Colombia Posts: 7,635 Thanks: 2620 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, 10:11 PM   #10
Member

Joined: Jun 2014
From: Alberta

Posts: 56
Thanks: 2

Quote:
 Originally Posted by v8archie 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?

 Tags argument, cantor, diagonal, significance

 Thread Tools Display Modes Linear Mode

 Similar Threads Thread Thread Starter Forum Replies Last Post zylo Topology 59 May 21st, 2016 07:13 AM zylo Topology 12 March 24th, 2016 09:53 AM zylo Math 22 January 26th, 2016 08:05 PM mjcguest Applied Math 9 July 25th, 2013 07:22 AM netzweltler Applied Math 191 November 7th, 2010 01:39 PM

 Contact - Home - Forums - Cryptocurrency Forum - Top