I Question about Cantor's Diagonal Proof

[thinkandmull]

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

 

[RPinPA]

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?

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.

 

[thinkandmull]

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.

 

[RPinPA]

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.

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.

 

[jedishrfu]

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

 

[Mark44]

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."

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.

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:

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.

 

[thinkandmull]

Hilbert's Hotel suggests that having members outside a set doesn't make the set any different in cardinality

 

[fresh_42]

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.

 

[RPinPA]

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.

 

[thinkandmull]

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.

 

[fresh_42]

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.

 

[jedishrfu]

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.

 

[RPinPA]

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$.

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.

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.

 

[thinkandmull]

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).

 

[RPinPA]

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?

 

[thinkandmull]

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

 

[Mark44]

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.

 

[thinkandmull]

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

 

[PeroK]

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$.

 

[jbriggs444]

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.

 

[Jon Richfield]

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.

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

Think about it and mull a bit

 

[PeroK]

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!

 

[Rap]

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.