Regarding Cantor's diagonal proof

[ATAUD]

I am very open minded and I would fully trust in Cantor's diagonal proof yet this question is the one that keeps holding me back. My question is the following:

In any given infinite set, there exist a certain cardinality within that set, this cardinality can be holded as a list. When you change the value of the diagonal within that list, you obtain a new number that is not in infinity, here is my problem, now that if inf + 1 = infinity, why would doing that to the diagonal be any different from simply adding or subtracting from infinity.

Perhaps the new number has a value different from the list yet if adding or subtracting from an infinite sequence gives you infinity regardless, why would it be any different doing it to a certain number within that sequence, the way I see it, the new number is not outside of infinity, yet is instead outside of the cardinality of an infinite sequence therefore isn't really greater than infinity, just different from infinity and just by cardinality, not naturally.

 

[FactChecker]

It proves that there can be no counting of the real numbers. What is more, it is clear from the proof that you can make up many more missing numbers than there are on the list. So the "infinity" of the real numbers ($\aleph$₁) is a level above the infinity of the counting numbers ($\aleph$₀) . So $\aleph$₁ > $\aleph$₀.

 

[haruspex]

there exist a certain cardinality within that set, this cardinality can be holded as a list.

In he standard proof, we assume the entire set can be written as an infinite list.

When you change the value of the diagonal within that list,

The diagonal is not changed. An element of the set is constructed by taking a copy of the diagonal and modifying every term.

you obtain a new number that is not in infinity

It is not in the list.

why would doing that to the diagonal

Nothing is done to the diagonal. It doesn't change.

The significance of the newly constructed element is that we assumed the list contained all the elements, but this new element proves it did not.

 

[willem2]

Your question contains a lot of statements that make no sense.\

In any given infinite set, there exist a certain cardinality within that set,

Do you mean, every infinite set has a subset with a certain cardinality?

this cardinality can be holded as a list.

Do you mean this subset is countable, So you can make a list of this subset? (by producing a 1-1 correspondence with the integers)

When you change the value of the diagonal within that list,

Do you mean: when you change the values of of all the numbers on the diagonal?
This also means you're looking at a set of numbers with an unlimited decimal expansion.
Probably easier to name the real numbers up front.

you obtain a new number that is not in infinity,

I have no idea what that means. The diagonal will be a number that is not on the list.

here is my problem, now that if inf + 1 = infinity, why would doing that to the diagonal be any different from simply adding or subtracting from infinity.

The diagonal is not infinity, but a real number, so none of this makes sense.
Most versions of the proof produce a number between 0 and 1. Changing all the numbers on the diagonal is nothing like adding 1 to the diagonal.

 

[ATAUD]

The diagonal is a real number that tends to infinity, that's why I assumed it would be treated the same as infinity.
Yes when I was talking about the cardinality I was referring to 1-1 correspondance.
The diagonal is not changed, instead it was copied and changed, therefore it was changed.

My point was, if the list is an infinite sequence of numbers and we add 1 to the diagonal, then wouldn't the sequence reach that 1 we added? because the way I see it, it's the same thing as inf + 1 = infinity.

"The diagonal is not infinity, but a real number, so none of this makes sense.
Most versions of the proof produce a number between 0 and 1. Changing all the numbers on the diagonal is nothing like adding 1 to the diagonal."

The diagonal is a real number with tendance to infinity, why would it be different from an infinite number or an infinite sequence? And when I say add 1 to the diagonal I'm only referring to the change of the values in that diagonal.

And the diagonal being a real number or not doesn't matter in my point.
If we say inf + 1 = infinity, why would adding 1 to the diagonal of an infinite list not equal infinity, in other words, why would the new number be any different from the meaning of infinity on the list, the new number looks different from the ones on the list, yet only because of 1-1 correspondance, which is the order of the list, why would it be any different from the meaning of infinity and why would it be greater than infinity? I'm suggesting that the infinity on the list is absolute and that the new number is different from the numbers on the list, yet just because of 1 - 1 correspondance not because it's any different from an infinite number.

 

[Khashishi]

When I was in middle school I didn't accept the Cantor diagonal proof because I thought math had to be grounded in reality. Numbers only existed because they referred to actual measurements we could make in the universe. The problem I had with Cantor's proof is that it claims that the number constructed by taking the diagonal entries and modifying each digit is different from every other number. But as you go down the list, you find that the constructed number might differ by smaller and smaller amounts from a number on the list. And extending to infinity, we are claiming that the number only disagrees with a number on the list by an infinitesimal amount. We already claim that 0.9999... = 1.0000, so why are we saying that two numbers that disagree by an infinitesimal amount are different numbers? We can't physically measure the difference.

Well, as I got older, I realized that math is not just a tool for describing reality, but it is a creature of our mind, which happens to be very useful. In math we can talk about infinities and such, which we can't really measure. As long as it's consistent, it's all fine.

Anyways, it's not mathematically valid to say inf + 1 = infinity. And it's not a problem of just a single number that we can't match up into a 1-1 correspondence. Any single number we can easily accommodate into the list by shifting the entries down one. The problem is that no matter how many numbers we shift in, there are always more numbers we haven't added yet.

 

[FactChecker]

My point was, if the list is an infinite sequence of numbers and we add 1 to the diagonal, then wouldn't the sequence reach that 1 we added? because the way I see it, it's the same thing as inf + 1 = infinity.

But the original assumption was that the list included ALL of the reals. You are thinking that there is only 1 new one to add. (In fact there are many more omitted from the list than on it, since for every diagonal digit, there are 9 other digits that could be there, making numbers that were omitted.) Saying that it was not in the original list violates the original assumption. So the reals can not be counted in a list and there are more of them than there are natural numbers. The "infinity" of the reals ( $\aleph$₁ ) is greater than the "infinity" of the natural numbers ( $\aleph$₀ ).

 

[haruspex]

The diagonal is a real number that tends to infinity

No, you seem to have misunderstood the process completely. Consider this example.
Suppose our infinite list happens to look like thsi:
.2
.32
.312
.3142
.31412
.314152
.3141592
...
(I think you can see how it goes.)
Now we construct a real number by copying the diagonal:
.222222222...
then adding 1 to each digit:
.3333333333...
I.e. 1/3. This number is a perfectly good real number, not infinite, but definitely not in the list.

 

[FactChecker]

When I was in middle school I didn't accept the Cantor diagonal proof because I thought math had to be grounded in reality. Numbers only existed because they referred to actual measurements we could make in the universe. The problem I had with Cantor's proof is that it claims that the number constructed by taking the diagonal entries and modifying each digit is different from every other number. But as you go down the list, you find that the constructed number might differ by smaller and smaller amounts from a number on the list. And extending to infinity, we are claiming that the number only disagrees with a number on the list by an infinitesimal amount.

But the number created by the diagonalization method is significantly different from every number on the list. There is nothing infinitesimal about each difference. The difference from each number on the list is "grounded in reality". All you are saying is that it is possible to have a countable set of numbers that is dense in the real line. The rational numbers are such a set. That is not a weakness in the proof and it does not prevent it from being grounded in reality.

 

[SSequence]

I think there is a point in the following sense (not a significant one but it came to my mind while reading this thread):
Suppose the number constructed by taking elements from the diagonal was:
0.1999999...

If our rule for changing digits was:
0 to 1
1 to 2
2 to 3
...
9 to 0

then the above number would be changed to:
0.200000...

But that is again equal to the previous number (without changing digits). And hence this number may very well be on the original list.

Of course it could easily be shown that this doesn't affect the actual result. Or alternatively we could just choose a slightly different rule for altering digits.

 

[FactChecker]

I think there is a point in the following sense (not a significant one but it came to my mind while reading this thread):
Suppose the number constructed by taking elements from the diagonal was:
0.1999999...

If our rule for changing digits was:
0 to 1
1 to 2
2 to 3
...
9 to 0

then the above number would be changed to:
0.200000...

But that is again equal to the previous number (without changing digits). And hence this number may very well be on the original list.

Of course it could easily be shown that this doesn't affect the actual result. Or alternatively we could just choose a slightly different rule for altering digits.

Since there are 9 available choices for each digit of the generated number, it is easy to avoid any problem pattern.

 

[SSequence]

Yes you are right. Even if one didn't do that it would be very easy to show that this is not an issue as far as countability or uncountability related issues are concerned.

Certainly this isn't the source of OP's confusion (which might just be a matter of seeing enough concrete exampes).

 

[ATAUD]

Correct me if I'm wrong, but what I understood with your arguments is that the diagonal has a next number, the next number has 9 different possibilites or 10 if we include zero, no matter the list, the number that goes after that number can't fullfill those 9 possibilites at the same time. Yet I still don't know why this would mean it's greater than infinity and not simply a different kind of infinity. Now that if we change the diagonal by adding 2 to each number, it would still only fullfill one possibility, 1/9.

 

[haruspex]

it's greater than infinity

What is "it" here?

 

[ATAUD]

What is "it" here?

Pehaps infinity doesn't have a value whatsoever, yet if that's the case I don't know why omega would play in the game before ever reaching absolute infinity without it being an assumption of the order of infinity.

If there exist 9 different possibilites after a number in the sequence, uncountable would start at saying there exist 2 out of 9 possibilites or 3 out of 9 possibilites at the same time, and you could even say it's possible to have 9/9 possibilites even though it's impossible to actually see something like that, but this only makes me believe in uncountable numbers and absolute infinity, yet not in omega, I see omega and omega + 1 as an assumption of the order of absolute infinity, why isn't it?

 

[haruspex]

If there exist 9 different possibilites after a number in the sequence

You still have not grasped the reductio ad absurdum nature of the proof. We are not adding one or 2 or 9 entries to the list to make a longer one.

1. If the reals are countable then the reals between 0 and 1 can be arranged in a list. That is, there exists a list which contains every real in that range.
2. Suppose we had such a list. We construct from it a real in the range which is missing from the list.
3. Therefore no such list can exist.

 

[FactChecker]

Correct me if I'm wrong, but what I understood with your arguments is that the diagonal has a next number, the next number has 9 different possibilites or 10 if we include zero, no matter the list, the number that goes after that number can't fullfill those 9 possibilites at the same time. Yet I still don't know why this would mean it's greater than infinity and not simply a different kind of infinity.

Exactly. It is a different kind of infinity. Countably infinite, like the natural numbers is indicated by $\aleph$₀. The larger infinity of the real numbers is indicated by $\aleph$₁. There are larger and larger types of infinity, $\aleph$₂, $\aleph$₃, ... etc. There is no limit.

Now that if we change the diagonal by adding 2 to each number, it would still only fullfill one possibility, 1/9.

There is no reason to stick to a pattern like adding 2. You can pick any number you like that is not the current diagonal digit of the listed number. If that diagonal digit is 3, then you can generate 9 example numbers by putting 0,1,2,4,5,6,7,8,9 there. If the next diagonal number is 8, pick any of 0,1,2,3,4,5,6,7,9. You don't have to follow any pattern. There are so many real numbers that are not in the list that they are MUCH more numerous than the numbers in the list.

 

[ATAUD]

Exactly. It is a different kind of infinity. Countably infinite, like the natural numbers is indicated by $\aleph$₀. The larger infinity of the real numbers is indicated by $\aleph$₁. There are larger and larger types of infinity, $\aleph$₂, $\aleph$₃, ... etc. There is no limit.There is no reason to stick to a pattern like adding 2. You can pick any number you like that is not the current diagonal digit of the listed number. If that diagonal digit is 3, then you can generate 9 example numbers by putting 0,1,2,4,5,6,7,8,9 there. If the next diagonal number is 8, pick any of 0,1,2,3,4,5,6,7,9. You don't have to follow any pattern. There are so many real numbers that are not in the list that they are MUCH more numerous than the numbers in the list.

So basically you can make an infinite amount of different lists of reals, and you can always get a real which wouldn't be on the list, which is aleph null, and therefore it's sensical to think that all the aleph nulls could be arranged in an order by using a graph, reasonable!
But hang on a second, omega is basically a reprentation of the order of uncountable sets, why does it come in play before reaching absolute infinity without simply being an assumption of the order of infinity, I can't seem to find the true purpose of ordinals. And also, aleph null represents the uncountable real numers, yet regardless of that, the order of aleph null is made still made by only 1/10 possibilites of the different numbers you could have chosen, what about 2/10 numbers you could choose at the same time, it's impossible to see it or represent it, but wouldn't it still exist?

 

[Jarvis323]

I have a related question which I posted here http://math.stackexchange.com/quest...f-infinite-sets-and-infinite-sets-as-whole-ob . Since it looks like that isn't going to get much attention, I figure I might as well contribute to this thread and ask your advice since my question is highly related.

My difficulty with feeling certain about the diagnonalization proof, explained in more detail on math exchange, is that picking an element s that differs at one digit by all of the elements in an infinite set seams like an undoable thing, there is no base case. We can write a rule for trying that seams like it would work if applied without bound, but actually completing the action (it needs to be applied infinitely)? Then selecting s seams a little bit like saying let n' be the largest natural number (which we know doesn't exist).

 

[haruspex]

I have a related question which I posted here http://math.stackexchange.com/quest...f-infinite-sets-and-infinite-sets-as-whole-ob . Since it looks like that isn't going to get much attention, I figure I might as well contribute to this thread and ask your advice since my question is highly related.

My difficulty with feeling certain about the diagnonalization proof, explained in more detail on math exchange, is that picking an element s that differs at one digit by all of the elements in an infinite set seams like an undoable thing, there is no base case. We can write a rule for trying that seams like it would work if applied without bound, but actually completing the action (it needs to be applied infinitely)? Then selecting s seams a little bit like saying let n' be the largest natural number (which we know doesn't exist).

There is no difficulty as long as the number is defined by a finite rule. You are happy with the existence of a number we call pi. If you need to know what any given digit is, you have a rule for finding it that will terminate in a finite number of steps.
Moreover, we have theorems that show the rule converges, and by the axioms for the reals it converges to a real number. The same is not true of the "largest natural number" analogy.

 

[Jarvis323]

That's a good point. I think my natural number analogy maybe a bad one though. Nevertheless I see mathematically why it works I guess. At least without this power mathematics would be a little boring. I still need to resolve some things conceptually, but I'm getting closer.

 

[SSequence]

Note that the purpose of any candidate list is to include more and more decimal representations (and hence, generally speaking, also more reals).

But you will note that as soon as the candidate list includes all computable decimal representations, it will be no longer be possible to generate such a list using a rule. It is fairly easy to see this (think of such a list*** as a total function from N² to digits 0-9).
Note though that inclusion of all computable decimal representations is a sufficient (but not necessary) condition to make such a list impossible to generate using a rule. At any rate, we can see that the "rule" (just using the word rule as synonymous to intuitively calculable) part is over pretty quick as soon as we try to include more and more decimal representations. Once again this is assuming CT(Church Thesis).

So, assuming the above, it seems to be more about the list being "well-defined". As far as that is concerned, there is also the subject of more and more complex classes of sub-sets of natural numbers. Unfortunately I don't know anything about it (beyond just single definitions for arithmetic and hyperarithmetic hierarchies -- without any details of their underlying structure).

However, people who do have knowledge of the more complex classifications of the sub-sets of N (and probably also more detailed working of set theory in addition) probably might also have a better understanding (or at least awareness) of the more subtle issues that pertain to this topic (that's my guess).

*** Note that with this kind of convention you will have to write 0.385 as 0.385000... -- you can choose somewhat different convention(s) but the end result will be the same.

 

[FactChecker]

I have a related question which I posted here http://math.stackexchange.com/quest...f-infinite-sets-and-infinite-sets-as-whole-ob . Since it looks like that isn't going to get much attention, I figure I might as well contribute to this thread and ask your advice since my question is highly related.

My difficulty with feeling certain about the diagnonalization proof, explained in more detail on math exchange, is that picking an element s that differs at one digit by all of the elements in an infinite set seams like an undoable thing, there is no base case. We can write a rule for trying that seams like it would work if applied without bound, but actually completing the action (it needs to be applied infinitely)?

Not really. The number existed before we began. We instantly see that there is a number (in fact many, many numbers) that are not on the list. There is no "completing the action" or "applying infinitely". The number itself is not changing but rather, we see one-by-one that the number is different from every number on the list.

 

[ATAUD]

I have been thinking about aleph null for some time.
Especially about the probability of the diagonal only fulfilling 1/10 different possibilities.
I came to the conclusion that this is true yet only for the way we quantify.

.12814823842197512941...
.16549821975219849124...
.14784982144829419248...
.14923124812784272178...
.13928198239812492148...

If we take the diagonal and change it by any number we obtain "28947..." by what we discussed earlier we said that the position of the next number in that diagonal could only fulfill 1/10 different possibilities.
But the position is just limited by the representation of the number yet if I were to say (28 = L, 94 = D, 47 = A ...)
I could then say:

.12814823842197512941...
.16549821975219849124...
.14784982144829419248...
.14923124812784272178...
.13928198239812492148...

Before "28947..." Now "LDA..."

The argument still works because it indeed only fulfills one specific value whether of a number greater than 9 or not at a time yet the total wouldn't be 10, it would be infinite, now that numerically the next number has 0 to 9 different possibilities, because those are the ones capable of only fulfilling one space at a time, yet why would that be universal?
If cantor's diagonal proof works for any given sequence then it must also work for sequences that have single values above 9, hence should work with
(L = 28, D = 94, A = 47 ... ) the "..."
refers to any type of representation any sequence of finite values.

Which is why I believe the next number in the diagonal doesn't have 1/10 different possibilities yet instead has 1/inf different possibilities.
This is my conceptual view on aleph null, if I am wrong, I would gladly take some corrections.

 

[FactChecker]

For the first digit, we could have 9 others that are not on the list. So that is 1/10. For the first and second digits combined, we could have 99 others. So that is 1/100. For the first, second, and third digits combined, we could have 999 others. So that is 1/1000. For the ... This goes on forever.

So you see that the set of numbers on the numbered list must be an unbelievably small fraction of the entire set of reals. That is why $\aleph$₀ is so much smaller than $\aleph$₁. There are even larger infinite cardinal values than $\aleph$₁.
When a person talks about "infinity", that is not specific enough. There are so many different sizes of "infinity". $\aleph$₀ is the infinite size of the natural numbers (and the rational numbers). $\aleph$₁ is the infinite size of the real numbers. There are progressively larger infinite sizes, $\aleph$₂, $\aleph$₃, ...

 

[SSequence]

Nearly the same idea works for showing collection of all functions of the following form as uncountable:
f : N → {0,1}
f : N → {0,1,2,3,4,5,6,7,8,9}
f : N → N
=====

If cantor's diagonal proof works for any given sequence then it must also work for sequences that have single values above 9, hence should work with
(L = 28, D = 94, A = 47 ... ) the "..."
refers to any type of representation any sequence of finite values.

The set of all finite lists of natural numbers is counted very easily (computer programs routinely make use of such structures). Following are some examples of such finite lists:
(0,10,5) -- 3 elements
(15,30,20,25) -- 4 elements
(2,2,2,2,2) -- 5 elements
etc.
This is true even though the number of such lists with a given number of elements (say 5) isn't finite.

The detail of how is this is done isn't particularly difficult. It can be done easily with encoding. However, I couldn't find a very friendly and easy to understand source describing it.
Another way, apart from direct encoding, is to see that one could create (in a fairly easy manner) 1-1 correspondence of all such finite lists (of natural numbers/integers) with ω^ω.

 

[pwsnafu]

$\aleph$₁ is the infinite size of the real numbers.

No, $\aleph_1$ is the cardinality of all countable infinite ordinals. The cardinality of real numbers is $2^{\aleph_0}$. These are equal only if the continuum hypothesis is true.

 

[FactChecker]

No, $\aleph_1$ is the cardinality of all countable infinite ordinals. The cardinality of real numbers is $2^{\aleph_0}$. These are equal only if the continuum hypothesis is true.

Ok. $\aleph$₀ is the smallest transfinite cardinal number, "countably infinite". $\aleph$₁ is the cardinality of the real numbers (assuming the continuum hypothesis). (see https://en.wikipedia.org/wiki/Cardinal_number, http://mathworld.wolfram.com/Aleph-0.html, and http://mathworld.wolfram.com/Aleph-1.html )

PS. I am assuming that questions about the continuum hypothesis are beyond what the OP wants.

 

[FactChecker]

Just for fun: Proof some infinities are bigger than other infinities by Vi Hart

 

[JeffJo]

When taught to teenagers, Cantor Diagonalization is almost always taught incorrectly. The problem is, we tend to remember what were were taught first. And every objection I've ever seen to it, is grounded in what was taught incorrectly.

For the following, I'll refer to this translation of the paper where Cantor described the process:

1. The proposition Cantor wanted to prove was "There exists an infinite set that cannot be counted." His first proof of this proposition, published 27 years earlier, used the real numbers as an example only. There were some issues with assumptions he made about the set, so he created this second proof specifically to not use the real numbers as the example.
2. He used infinite-length strings that use only two characters. He used "m" and "w." I'll use "0" and "1" like Wikipedia does. I call them Cantor Strings, and the set of all Cantor Strings is called T.
   
   • Each of my Cantor Strings can be interpreted as the binary representation of a unique real number in [0,1]. But some real numbers in that range have two Cantor Strings in T that correspond to them. There is an easy fix to this problem, but it is unnecessary since Cantor used the strings themselves.
3. Cantor never assumed you could enumerate every element in T. He only assumed that can be an enumeration of a subset of T. Such an enumeration is easy to demonstrate, just let every element of a string be a "0" except the nth, which is a "1."
4. My point #3 is an important distinction, because Diagonalization is not a proof by contradiction.
   • To be a valid proof by contradiction, you must assume the negation of your premise and prove that a contradiction follows logically from it.
   • The alleged contradiction in Diagonalization is the existence of a string that is not in the enumeration. Its existence does not follow logically from an assumption that all strings in T are enumerated, just that some are.
   • Yes, Wikipedia seems to say otherwise. It teaches the interpretation meant for teenagers.
5. But it is a very similar form of proof, called Contraposition, that is easily mistaken for proof by contradiction. Contraposition relies on the fact that "If A, then B" and "If not B, then not A" are logically equivalent statements. So you can prove "If S is a subset of T that contains every member of T, then S cannot be enumerated" by proving "If S is a subset of T that can be enumerated, then S does not contain every member of T."
   • Cantor's assertion, near the end of the paper, that "otherwise we would have the contradiction" does not say that Diagonalization is a proof by contradiction. It is merely pointing out how proving that there is a Cantor String that is not in S, is proving that S is not all of T.

Rough outline of Cantor's Proof:

1. Assume the set T exists, that contains every possible Cantor String.
2. Assume there is a subset S of T that can be enumerated.
3. This enumeration provides the definition of a Cantor String that cannot be in S. But since it is a Cantor String, it is T.
4. So, if S is a subset of T that can be enumerated, then S does not contain every member of T.
   
5. QED, by contraposition.