Question about Cantor's Diagonal Proof

  • I
  • Thread starter thinkandmull
  • Start date
  • Tags
    Proof
In summary, Cantor's diagonal proof demonstrates that it is impossible to create a one-to-one correspondence between the set of natural numbers and the set of real numbers. This is because for every finite value of n, there exists a real number that cannot be matched with any natural number. This disproves the notion that all infinite sets have the same size and shows that infinite sets behave differently than finite sets.
  • #1
thinkandmull
51
0
Dear friends, I was wondering if someone can explain how Cantors diagonal proof works.

This is my problem with it. He says that through it he finds members of an infinite set that are not in another. However, 2 and 4 are not odd numbers, but all the odd numbers equal all the whole numbers.

If one to one correspondence works such that you can line up all the odd numbers and start with all the whole numbers and say "they start at the same place, and they go to infinity so they are equal", why can't we do this same trick with the "bigger infinities". If they are made up of members, the members can be lined up and "set off" into infinity, and the result would be that all infinities are equal.

Where am I going wrong with this? Thanks
 
Last edited by a moderator:
Mathematics news on Phys.org
  • #2
A mistake a lot of people make is thinking that somewhere you plug "infinity" into an equation. That never happens.

All the natural numbers are finite. They don't end, but everything on that unending list is finite.

Cantor considers a set S to have the same cardinality (size) as the natural numbers N if you can set up a bijection (the technical term) between N and the members of that set. That means that for every FINITE n there is a unique element of S that n is mapped to, and that every element of S gets mapped to some n.

OK so far?

thinkandmull said:
If one to one correspondence works such that you can line up all the odd numbers and start with all the whole numbers and say "they start at the same place, and they go to infinity so they are equal",

Not quite. What we say is that for the set S = {1, 3, 5, ...}, we can write these as 2n - 1, n = 1, 2, 3, ...

What that means is that for every FINITE n, there is an associated element 2n-1 of S. And for every element of S, which are ALL FINITE, it can be written in the form 2n - 1 for some FINITE n. This mapping exists for all the elements of N. WHICH ARE ALL FINITE. We could label the elements of S with their associated n. That is, this bijection is giving us a list S1, S2, S3, ... for every finite n, and we are guaranteed that every element of S is on that list. For some finite n.

At no point do we say "they go to infinity". We just say "all the finite natural numbers are mapped".

Now, what happens with an uncountable set like the real numbers from 0 to 1? Cantor shows that every mapping is incomplete. As simple as that. If you have mapped all the numbers n to numbers in S = [0, 1], then he guarantees there's a number not on the list. And shows how to construct it.

Therefore it's impossible to make a bijection between n and [0, 1].

Again, nobody just waves their hands and says "they go off to infinity". The thing we're checking is what happens at every finite value of n. And what happens in Cantor's proof is that he ensures he's constructed a number which is not the n-th number in the list. FOR EVERY FINITE n. If we have a list of numbers S1, S2, S3, ... in [0, 1], Cantor has proved that there's a real number not in that list. It is not associated with any finite n. It's not equal to S1, it's not equal to S2, etc. It's not equal to Sn for any finite n.

That's the heart of the proof if you want to summarize it. I give you a list S1, S2, S3, ... of numbers from [0, 1]. You can construct a number which is not equal to Sn for any n. Period.
 
  • #3
Thanks for your reply. I guess I don't understand yet how all the odd numbers can be equal to all the odd plus even numbers. You have to distort how they naturally fall on the number line in order to make them have a one to one correspondence, which led me to think that there might be a way to distort or use an equation on the diagonal proof and get a one to one correspondence.
 
  • #4
thinkandmull said:
I guess I don't understand yet how all the odd numbers can be equal to all the odd plus even numbers.

Your use of the word "equal" is bugging me. But I guess you're saying "can be put into one-to-one-correspondence with".

That's just one of the properties of an infinite set in Cantor's structure, that it can be put into bijection with a proper subset of itself. A simpler example: The numbers in {1, 2, 3, ...} can be put into bijection with the numbers { 2, 3, ...} despite our experience with finite sets. We dropped an element but there are still just as many elements, in a sense, in the resulting set.

This stuff can be a little hard to get used to. But it is rigorous and self-consistent.

thinkandmull said:
You have to distort how they naturally fall on the number line in order to make them have a one to one correspondence,

And again you're using a word in a way I don't understand. Nothing is being distorted here. The odd numbers and the natural numbers in the mapping ##n \rightarrow 2n - 1## are both in their natural order.
 
  • Like
Likes FactChecker
  • #5
Working with infinite sets is conceptually different from finite sets. Cantors ideas were initially rejected by many mathematicians of the day.

He was even viciously attacked by his own teacher Kronecker for such absurd ideas and yet we are today embracing them.

If an infinite set be mapped to the natural numbers then it said to be countably infinite. There are schemes to map the set of even numbers and of odd numbers and integers to the natural numbers so we know the sets are the infinite size.

Same goes for rational numbers but reals are much denser than the natural as we can't construct a mapping that associate a real with a natural number.

There are some numberphile videos on youtube that describe cantors ideas better what i said here.



And this one from mathloger

 
Last edited:
  • Like
Likes pinball1970
  • #6
thinkandmull said:
However, 2 and 4 are not odd numbers, but all the odd numbers equal all the whole numbers.
Like @RPinPA, I'm also bothered by this language. Corrected, this would be "the cardinality of the set of odd integers is equal to the cardinality of the set of all integers."
thinkandmull said:
If they are made up of members, the members can be lined up and "set off" into infinity, and the result would be that all infinities are equal.
Which is not true. The cardinality of the positive integers is less than the cardinality of the real numbers in the interval [0, 1]. Both sets have an infinite number of members, but there are different sizes of infinity. We say that the positive integers are countably infinite, while the real numbers are uncountably infinite.

thinkandmull said:
I guess I don't understand yet how all the odd numbers can be equal to all the odd plus even numbers. You have to distort how they naturally fall on the number line in order to make them have a one to one correspondence, which led me to think that there might be a way to distort or use an equation on the diagonal proof and get a one to one correspondence.
We're not "distorting" anything. We're pairing numbers from one set with numbers in the other set. The pairing goes like this:
Code:
I = 1 2 3 4 5 6 ...   n    n + 1 ...
O = 1 3 5 7 9 11 ... 2n-1 2n + 1 ...
You tell me a number in set I, and I'll tell you its counterpart in set O. Or you can tell me a number in set O, and I'll tell you its counterpart in set I. That's the one-to-one pairing, or map, between the two sets.
 
  • Like
Likes Klystron, fresh_42 and jedishrfu
  • #7
Hilbert's Hotel suggests that having members outside a set doesn't make the set any different in cardinality
 
  • #8
thinkandmull said:
Hilbert's Hotel suggests that having members outside a set doesn't make the set any different in cardinality
Depends on the number of members outside. As stated it is wrong.
 
  • #9
thinkandmull said:
Hilbert's Hotel suggests that having members outside a set doesn't make the set any different in cardinality

Removing a finite number of members from an infinite set does not change its cardinality.

Removing an infinite subset may or may not change the cardinality. For instance you can remove all the even numbers from N and the cardinality is unchanged.

But if you remove all the integers > 100 from N, leaving a finite set, you've definitely changed its cardinality.

This stuff is tricky, and you have to be very precise in your language and your reasoning. Vagueness doesn't mix well with mathematics.
 
  • #10
Is it true that Cantor would say the cardinality of parts of Earth is the same as the cardinality of parts of a football? You would never reach the end of parts (points) in either, so aren't they equal in their uncountable infinities? But it seems to me that something has to account for the Earth being larger in size.
 
  • #11
You cannot argue with real world particles, since they will always break down to a finite number of atoms. It is true that ##\lim_{n\to \infty} |[-n,n]| \neq |[0,1]|## and ##\operatorname{card (\mathbb{R})} = \operatorname{card}([0,1])##. So cardinality and length are two different concepts. You cannot measure how long you have to count the number of elements in an infinite set.
 
  • #12
That’s the point cardinality doesn’t map to size as we understand it as in comparing natural numbers vs rational numbers on a number line.

Rational numbers appear to be denser than natural numbers but both are countably infinite and are considered the same “size”. That’s why we use the word cardinality.
 
  • #13
thinkandmull said:
Is it true that Cantor would say the cardinality of parts of Earth is the same as the cardinality of parts of a football?

The cardinality of the points in a solid sphere are the same, whether that is a sphere of radius 1 or radius 1000.

To be clear, I'm not talking about a physical sphere measured in meters, but all the points ##(x,y,z)## that satisfy ##x^2+y^2+z^2 \leq r^2## for some real number ##r##.

thinkandmull said:
You would never reach the end of parts (points) in either, so aren't they equal in their uncountable infinities?

You keep going back to this "you never reach the end", but that's not a phrase that appears anywhere in this theory. It's a test of your own creation. You can use it in an informal way to explain what we mean by an infinite set, but it has nothing to do with the formal idea of set cardinality.

The test of cardinality is whether you can line up the elements of one set one-to-one with another. Period.

And you can most definitely do such a one-to-one lineup with the points in two different spheres, so yes they have the same cardinality.

thinkandmull said:
But it seems to me that something has to account for the Earth being larger in size.

Sure. Two spheres of different sizes have different values of ##r## in the definition of "sphere of radius ##r##" as "all the points ##(x,y,z)## that satisfy ##x^2+y^2+z^2 \leq r^2##.

But cardinality is not required to account for that. Cardinality is a different thing, that only has to do with matching up set elements one-to-one.
 
  • Like
Likes FactChecker and jedishrfu
  • #14
I think I understand this better now. I hope my final question is a good one: considering Cantor's proofs, are all the odd numbers a part of all the whole numbers in the sense way that a half circle is part of a circle (a circle having uncountable points, as does the half circle).
 
  • #15
thinkandmull said:
I think I understand this better now. I hope my final question is a good one: considering Cantor's proofs, are all the odd numbers a part of all the whole numbers in the sense way that a half circle is part of a circle (a circle having uncountable points, as does the half circle).

Again just to be precise (sorry if it seems fussy, but you really do need precision in language to do rigorous mathematics), by "whole numbers" do you mean all the integers, positive and negative? The set ##\{0, \pm1, \pm2, ...\}##? If so then the set of odd numbers ##\{\pm1, \pm3, \pm5, ... \}## is a proper subset of ("part of" in your terminology) the set of whole numbers.

Also true if by "whole numbers" you just meant the positive ones ##\{1, 2, 3, ...\}## and by "odd numbers" you just meant the set of positive odd numbers ##\{1, 3, 5, ... \}##

It's a subset because every odd number is a member of the set of whole numbers.

It's a proper subset because there are whole numbers that aren't in the set of odd numbers. The set of odd numbers doesn't include every whole number.

But that's not really connected to Cantor's proofs. Except for the fact that an infinite set has the property that it can be put in one-to-one correspondence with a proper subset. Or put in Cantor's terms, that an infinite set has proper subsets with the same cardinality. What I mean about "not really connected" is you don't have to invoke anything from Cantor's proofs to point out that the odd numbers are a proper subset of the whole numbers, or that the interval from 0 to 1 is a proper subset of the interval from 0 to 2.

That seems like a lot of words to answer what you probably thought was a simple question. Did I answer it?
 
  • #16
Ye, you answered it well. In philosophy it was assumed for centuries that a part cannot be equal to a whole. But when we add infinities to the situation, a subset can equal a set. VERY interesting. Thanks everyone
 
  • #17
thinkandmull said:
But when we add infinities to the situation, a subset can equal a set.
In general, a subset does not "equal" a set, whether or not we're talking about infinite sets.

Throughout this thread, the people responding have taken pains to talk about the cardinality of one set versus another. Loosely speaking, this is about the number of elements of each set. The set of positive integers ##\mathbb Z^+## = {1, 2, 3, ..., n, n + 1, ...} has the same cardinality as the set of even integers E = {2, 4, 6, 8, ..., 2n, 2n+2, ...}, but the two sets are not equal.
 
Last edited:
  • Like
Likes fresh_42
  • #18
I don't know what a set has to define it besides cardinality. But thanks to everyone for trying to help to understand a bit more. These are probably questions a lot of people wrestle with
 
  • #19
thinkandmull said:
I don't know what a set has to define it besides cardinality.

A set is defined by its members; not by its cardinality.

The set ##\{ you \}## is not the same as the set ##\{ me \}##. But both sets have cardinality of ##1##.
 
  • Like
Likes sysprog
  • #20
thinkandmull said:
I don't know what a set has to define it besides cardinality.
If you are concerned with the "size" of a set, there are notions other than cardinality that can be used. For instance, one can define a measure. Roughly speaking, cardinality deals with "how many" while measure theory deals with "how much".

Cardinality jars one's intuition because the whole can have the same cardinality as a part.
Measure theory may leave one unsatisfied because not all sets are measurable.

A typical measure would fit with one's intuition: the measure of a hemisphere would normally be half the measure of the whole sphere.

If one is concerned with subsets of the positive integers (for instance, the odd positive integers), there is a notion that can be useful: asymptotic density. Unless I am mistaken, asymptotic density is an example of a measure on the set of positive integers. As alluded to above, not all subsets of the positive integers have an asymptotic density. But the odd positive integers have an asymptotic density of 0.5, just as one would expect.
 
Last edited:
  • Like
Likes PeroK and jedishrfu
  • #21
The folks gave you some nice replies, so these are just comments. Whether you find them interesting, much less helpful, is up to you.

Firstly, about that triangle. Notice that it generally is seen as a triangle of decimal digits. But every decimal representation can be uniquely and precisely represented by any other radix but 0 and 1 (actually, in some bases they can be represented in more than 1 way, even in decimal, but Cantor ducked that one by replacing every string terminating in zeroes, with a slightly different one terminating in 9s. Amounts to the same thing of course, so no problem, and you can always do that or something similar to the other bases as well by choosing a suitable convention).

But OK, so what about binary, as compared to decimal? At each digit on the decimal diagonal you have the option of choosing any of 9 other digit values, so that there are 9^aleph-null possible diagonal values, which it is trivial to prove to be equal to aleph-1, the next infinity in the sequence. Same for base 16 (15 options per digit) and ternary (2 options per digit); they all give you aleph-1. (OK?)

But binary (whether positive or negative) gives you precisely 1 option, and aleph null +1 gives you aleph-null, not aleph-1.

I could give you the catch easily, but see whether you can work it out yourself first. It is simpler than you might think; a quickie, if you like.

Another thing, far more important, that you need to get into your mind, and bear it in mind, is that the concept of existence in maths, or in fact any other formal system, is in some ways radically different from the concept of existence of apples or atoms or stars etc. Even the concept of finite numbers existing or not, is horribly treacherous. In fact to my mind the idea of finity is more interesting and in some ways more challenging than anything I have yet seen in dealing with infinities.

When we axiomatise anything to do with numbers or infinities, we say in effect: "suppose we accept the following statement as true (meaningfully or not) then it follows that...". We don't say "It is true because my axioms prove it and you can go down to the nearest store and buy half a dozen of them, or if you are conjecturing what you want, placing it on back-order." Some of the theorems we come up with have useful correspondences with aspects of our empirical world, and some don't, not obviously anyway, but that has nothing to do with anything.

Remember, not only are there NO, repeat NO physical infinities on our observable universe but there are hardly any finite numbers either. Right? (And outside our observable universe it is arguable there cannot be any more.) Consider the largest finite number you can express physically say, 7^2^3^4^... using one subatomic particle for each digit, till you have filled each nook of space solid up to our redshift horizon, no room for atoms or stars or space. Big enough for you?

Well, with negligible exceptions, every finite integer is larger than that number. Call it S. Never mind aleph-null, which is not a number at all in our ordinary sense of the word. ALeph-null's "existence" is based on different axioms from those from which we derive ordinary integers!

But does that number S exist? And if it does, what does it mean to say it exists? We don't even know, and never will know, most of its digits, nor even what power of 7 we have achieved. Try calculating it and display the result. :oops:

All of which might seem totally pointless, but there are important implications.

Think about it and mull a bit :wink:
 
  • #22
jbriggs444 said:
Measure theory may leave one unsatisfied because not all sets are measurable.

Although, if you want to you can drop the Axiom of Choice and instead assume that all sets of real numbers are measurable.

I don't know if that would satisfy you!
 
  • #23
RPinPA said:
Removing a finite number of members from an infinite set does not change its cardinality.

In the words of the hymn "Amazing Grace" (written 1779):

When we've been here ten thousand years,
Bright, shining as the sun,
We've no less days to sing God's praise,
Than when we've first begun.
 
Last edited:

1. What is Cantor's Diagonal Proof?

Cantor's Diagonal Proof is a mathematical proof developed by Georg Cantor in the late 19th century. It is used to show that there are different levels of infinity, and that some infinities are larger than others.

2. How does Cantor's Diagonal Proof work?

Cantor's Diagonal Proof works by constructing a list of all the possible infinite sequences of numbers, and then using a diagonal argument to show that there must be numbers missing from the list. This demonstrates that there are more numbers than can be listed, and therefore there are different levels of infinity.

3. What is the significance of Cantor's Diagonal Proof?

Cantor's Diagonal Proof is significant because it revolutionized the way mathematicians think about infinity. It showed that there are different sizes of infinity, and that some infinities are uncountable. This has had a profound impact on many areas of mathematics, including set theory and analysis.

4. What are some real-world applications of Cantor's Diagonal Proof?

Cantor's Diagonal Proof has been applied in various fields, including computer science and cryptography. It has also been used to develop new mathematical concepts, such as fractals and the theory of chaos.

5. Are there any criticisms of Cantor's Diagonal Proof?

While Cantor's Diagonal Proof is widely accepted by mathematicians, there have been some criticisms of its assumptions and implications. Some argue that it relies on the assumption that infinity is a well-defined concept, while others question the validity of using a diagonal argument in mathematical proofs. However, these criticisms have not diminished the significance and impact of Cantor's Diagonal Proof in mathematics.

Similar threads

  • General Math
Replies
19
Views
1K
Replies
9
Views
2K
Replies
4
Views
492
  • General Math
Replies
1
Views
1K
  • Set Theory, Logic, Probability, Statistics
2
Replies
55
Views
4K
  • General Math
Replies
20
Views
2K
  • General Math
Replies
9
Views
2K
Replies
9
Views
10K
  • Set Theory, Logic, Probability, Statistics
3
Replies
86
Views
7K
  • General Math
Replies
32
Views
2K
Back
Top