I don't see the significance of Cantor's diagonal argument

Jun 2014
56
2
Alberta
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.
 

v8archie

Math Team
Dec 2013
7,709
2,677
Colombia
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:
  • Like
Reactions: 2 people

SDK

Sep 2016
708
476
USA
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.
 
  • Like
Reactions: 1 person
Jun 2014
56
2
Alberta
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.
 

greg1313

Forum Staff
Oct 2008
8,008
1,174
London, Ontario, Canada - The Forest City
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.
 
  • Like
Reactions: 2 people
Aug 2012
2,466
764
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/Fundamental_theorem_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:
  • Like
Reactions: 2 people

v8archie

Math Team
Dec 2013
7,709
2,677
Colombia
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:
  • Like
Reactions: 1 person
Jun 2014
56
2
Alberta
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:

v8archie

Math Team
Dec 2013
7,709
2,677
Colombia
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.
 
Jun 2014
56
2
Alberta
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?