Regarding Cantor's Diagonal Argument

[Angra Mainyu]

Okay, in the video, he tries to list all of the numbers exclusively between 0 and 1. He shows that there will be some numbers left out of the list such as 0. not a, not b, not c ... Now why can't I start a new matching for each of the "unlistable" numbers and match them to, say, another column of naturals?

You can start, but no matter how you do it, there is no full matching (i.e., a bijection) between N and R, or between N and (0,1); beero1000 has already proven that, but if you don't understand it, how about this: there is no bijection between if one assumes there is one, a contradiction follows.

 

[Angra Mainyu]

Okay, in the video, he tries to list all of the numbers exclusively between 0 and 1. He shows that there will be some numbers left out of the list such as 0. not a, not b, not c ... Now why can't I start a new matching for each of the "unlistable" numbers and match them to, say, another column of naturals?

You can start, but no matter how you do it, there is no full matching (i.e., a bijection) between N and R, or between N and (0,1); beero1000 has already proven that, but if you don't understand it, how about this: there is no bijection between if one assumes there is one, a contradiction follows.

 

[ryan]

The diagonal argument shows that EVERY potential assignment of the integers to the reals necessarily excludes some reals.

Why then are we allowed to exclude, say, all even natural numbers and still have a set the size of the natural numbers, but we are not allowed to exclude some real numbers?

Here is my argument:

My rule is that we will exclude every 2nd row starting at row 2. We will fill the set {2n+1} as n goes to infinity.

1, 2, 3, 4, 5, ...
2
3
4
5
.
.
.

There, I have a set with a cardinality of aleph 0, and the number 2n just never showed up in the list just like certain real numbers didn't show up in Cantor's argument.

But, we can still just add the elements in the two sets {2n+1} + {2n} = aleph 0, and finally aleph 0 = {2n+1} = {2n}.

So my question is why can't we put every real that does not show up in the list and have {extra reals} + {N} = aleph 0.

 

[beero1000]

The diagonal argument shows that EVERY potential assignment of the integers to the reals necessarily excludes some reals.

Why then are we allowed to exclude, say, all even natural numbers and still have a set the size of the natural numbers, but we are not allowed to exclude some real numbers?

Here is my argument:

My rule is that we will exclude every 2nd row starting at row 2. We will fill the set {2n+1} as n goes to infinity.

1, 2, 3, 4, 5, ...
2
3
4
5
.
.
.

There, I have a set with a cardinality of aleph 0, and the number 2n just never showed up in the list just like certain real numbers didn't show up in Cantor's argument.

But, we can still just add the elements in the two sets {2n+1} + {2n} = aleph 0, and finally aleph 0 = {2n+1} = {2n}.

So my question is why can't we put every real that does not show up in the list and have {extra reals} + {N} = aleph 0.

Because putting the remaining reals "in the list" is implicitly assuming that the reals are countable. Because there are uncountably many 'extra reals'. Because even if you combined countably many countably infinite sets of reals, you still would not have all of them. Because if you could do that, then there would be a bijection between the reals and the integers and that is exactly what Cantor proved to be impossible.

I'm not sure how else to say it.

 

[ryan]

Thanks for trying.

You're welcome.
I see it did not work.
However, considered this: I assumed that there was a bijection between N and R, and from that assumption, I reached a contradiction. Therefore, it is not the case that there is a bijection between N and R.
What part of that do you not understand?

There are two problems I have:

I don't see why the diagonal argument ensures that there can't be some better argument that somehow injects the unlisted reals into a set with aleph 0 size. And I don't see why there needs to be a bijection in the first place. We are allowed to add other elements to an infinite set and still have the same size of infinite set. It seems more consistent just do that and have one infinity.

 

[ryan]

Why then are we allowed to exclude, say, all even natural numbers and still have a set the size of the natural numbers, but we are not allowed to exclude some real numbers?

Here is my argument:

My rule is that we will exclude every 2nd row starting at row 2. We will fill the set {2n+1} as n goes to infinity.

1, 2, 3, 4, 5, ...
2
3
4
5
.
.
.

There, I have a set with a cardinality of aleph 0, and the number 2n just never showed up in the list just like certain real numbers didn't show up in Cantor's argument.

But, we can still just add the elements in the two sets {2n+1} + {2n} = aleph 0, and finally aleph 0 = {2n+1} = {2n}.

So my question is why can't we put every real that does not show up in the list and have {extra reals} + {N} = aleph 0.

Because putting the remaining reals "in the list" is implicitly assuming that the reals are countable. Because there are uncountably many 'extra reals'.

Aren't the reals uncountable because that is what the diagonal argument shows? Or is there some deeper meaning to countably/uncountably infinity.

Because even if you combined countably many countably infinite sets of reals, you still would not have all of them. Because if you could do that, then there would be a bijection between the reals and the integers and that is exactly what Cantor proved to be impossible.

Yes, he shows this by assuming that this is the way it is. Sorry, but that's where I am at with all of this.

 

[Angra Mainyu]

You're welcome.
I see it did not work.
However, considered this: I assumed that there was a bijection between N and R, and from that assumption, I reached a contradiction. Therefore, it is not the case that there is a bijection between N and R.
What part of that do you not understand?

There are two problems I have:

I don't see why the diagonal argument ensures that there can't be some better argument that somehow injects the unlisted reals into a set with aleph 0 size. And I don't see why there needs to be a bijection in the first place. We are allowed to add other elements to an infinite set and still have the same size of infinite set. It seems more consistent just do that and have one infinity.

I will address why there would have to be a bijection if addressing it might help. So, I would like to ask:
Do you understand the argument I gave above, as a proof that there is no bijection between N and R? Or is there something in that argument that you haven't been able to understand?

 

[ryan]

There are two problems I have:

I don't see why the diagonal argument ensures that there can't be some better argument that somehow injects the unlisted reals into a set with aleph 0 size. And I don't see why there needs to be a bijection in the first place. We are allowed to add other elements to an infinite set and still have the same size of infinite set. It seems more consistent just do that and have one infinity.

I will address why there would have to be a bijection if addressing it might help. So, I would like to ask:
Do you understand the argument I gave above, as a proof that there is no bijection between N and R? Or is there something in that argument that you haven't been able to understand?

I do not understand how the diagonal argument shows that there can't be a bijection between R and N even though I can clearly see how some real numbers get left out as n rows go to infinity. BUT, I also see how filling the naturals in an infinite set leaves out negative integers.

 

[Angra Mainyu]

I will address why there would have to be a bijection if addressing it might help. So, I would like to ask:
Do you understand the argument I gave above, as a proof that there is no bijection between N and R? Or is there something in that argument that you haven't been able to understand?

I do not understand how the diagonal argument shows that there can't be a bijection between R and N even though I can clearly see how some real numbers get left out as n rows go to infinity. BUT, I also see how filling the naturals in an infinite set leaves out negative integers.

Do you understand how the argument I wrote in post#15 proves that there can't be a bijection between R and N?

 

[ryan]

I do not understand how the diagonal argument shows that there can't be a bijection between R and N even though I can clearly see how some real numbers get left out as n rows go to infinity. BUT, I also see how filling the naturals in an infinite set leaves out negative integers.

Do you understand how the argument I wrote in post#15 proves that there can't be a bijection between R and N?

No, because the format leaves too much ambiguity.

 

[Angra Mainyu]

Do you understand how the argument I wrote in post#15 proves that there can't be a bijection between R and N?

No, because the format leaves too much ambiguity.

Actually, there is no ambiguity.
But given that you don't understand that argument or main arguments in beero1000's posts, in my assessment I don't have the means to explain this to you in a reasonable amount of time, so I'm afraid I'm giving up. I hope you'll eventually understand why Cantor's diagonal argument (in any of its many variants) succeeds.

 

[beero1000]

Which statements do you disagree with or not understand?

1. The set of natural numbers N is countably infinite.
2. If the cardinality of a set A is strictly larger than the cardinality of the natural numbers N then the set A is uncountably infinite.
3. A function f : A -> B is onto if and only if for every b in B there exists an a in A such that b = f(a).
4. The cardinality of a set B is strictly larger than the cardinality of a set A if and only if there does not exist a function f : A -> B that is onto.
5. (Cantor's argument) If f : N -> R is a function from the natural numbers to the real numbers, then the function f is not onto.
6. There does not exist a function f : N -> R that is onto.
7. The real numbers R are strictly larger in cardinality than the natural numbers N.
8. The real numbers R are uncountably infinite.

 

[ryan]

No, because the format leaves too much ambiguity.

Actually, there is no ambiguity.
But given that you don't understand that argument or main arguments in beero1000's posts, in my assessment I don't have the means to explain this to you in a reasonable amount of time, so I'm afraid I'm giving up. I hope you'll eventually understand why Cantor's diagonal argument (in any of its many variants) succeeds.

Okay, maybe not, I just don't know why the j turned into an n, and the rest didn't seem to help me understand anything about the issues I have.

 

[ryan]

Which statements do you disagree with or not understand?

2. If the cardinality of a set A is strictly larger than the cardinality of the natural numbers N then the set A is uncountably infinite.

I think I may get somewhere now. Here are two important parts about what part of this that I am trying to understand.

1. Assuming the converse for #2 on your list is necessary, why would something uncountable have to have a larger infinity than something countable? Before answering, please see the next part.

2. If the answer to the above question is something like "there are many numbers that get left out when correlating countable elements to uncountable elements", then my response is that there are also many countable numbers that get left out when correlating every natural number to every second rational number.

Similarly, we don't say that aleph 0 + 5 is greater than aleph 0, so then why do we say that 2^(aleph 0) is larger than aleph 0?

 

[Angra Mainyu]

Okay, maybe not, I just don't know why the j turned into an n, and the rest didn't seem to help me understand anything about the issues I have.

Ha, good catch. I just botched that (I rewrote the argument after I writing it, in order to make it more clear, but forgot to rewrite another part, and also added an "n" in the wrong place, where it was supposed to be a "j"); the contradiction does follow using that function, but I explained it wrong.

So, my apologies. Here's the corrected version:

Let's assume there is a bijection g:N->R.
Given n in N, let's say (in decimal notation) that g=k.x(n,1)x(n,2)x(n,3))...., where (x(n,j)) is an integer in {0,1,...,9} for every natural number j, and k is an integer.

Let h:N->{2,3} be the following function:
h=2 iff x(n,n)=/=2.
h=3 iff x(n,n)=2

Consider now the following real number:
x0:=0.h(1)h(2)h(3)...

Let n0 be g(-1)(x0) (i.e., apply the inverse of g to x0). Then g(n0)=x0.

That entails that k(n0).x(n0,1)x(n0,2)x(n0,3)....=0.h(1)h(2)h(3)...

Since h(j) = 2 or 3 for all j, the only way this can happen is that x(n0,j)=h(j) for all j. But that is contradictory, because when j=n0, x(n0,n0)=/=h(n0) (this is because if x(n0,n0)=2, then h(n0)=3, and if x(n0,n0) =/=2, then h(n0) = 2.)

In other words, this proves that assuming that there is a bijection between N and R entails a contradiction.

On the other hand, if you try to derive a contradiction from the assumption that there is a bijection between N and N U {-1}, you will not succeed.

 

[beero1000]

Which statements do you disagree with or not understand?

2. If the cardinality of a set A is strictly larger than the cardinality of the natural numbers N then the set A is uncountably infinite.

I think I may get somewhere now. Here are two important parts about what part of this that I am trying to understand.

1. Assuming the converse for #2 on your list is necessary, why would something uncountable have to have a larger infinity than something countable? Before answering, please see the next part.

2. If the answer to the above question is something like "there are many numbers that get left out when correlating countable elements to uncountable elements", then my response is that there are also many countable numbers that get left out when correlating every natural number to every second rational number.

Similarly, we don't say that aleph 0 + 5 is greater than aleph 0, so then why do we say that 2^(aleph 0) is larger than aleph 0?

Not being in correspondence with the some subset of the integers is the DEFINITION of being uncountable. All sets with cardinality less than or equal to the cardinality of N are countable (again, by definition), so the uncountable sets are exactly the sets whose cardinality is strictly greater than the cardinality of N.

 

[ryan]

First of all, the idea that we could somehow figure out a way to jam in some irrational numbers that don't seem to ever have a match to a natural number is no less crazy than any of the other paradoxes that arise out of infinity.

But I will not say that just because I don't understand it it can't be true.

Now let me just reluctantly swallow this pill and aasume it is true so that I can get to my other problem.

Now I have the issue of what I think is a clear paradox.

What does {Z} - {N} equal?

 

[beero1000]

First of all, the idea that we could somehow figure out a way to jam in some irrational numbers that don't seem to ever have a match to a natural number is no less crazy than any of the other paradoxes that arise out of infinity.

But I will not say that just because I don't understand it it can't be true.

Now let me just reluctantly swallow this pill and aasume it is true so that I can get to my other problem.

Now I have the issue of what I think is a clear paradox.

What does {Z} - {N} equal?

Do us all a favor and take the time to learn the basics before you start proclaiming 'paradox'. Paradoxes are not just crazy-seeming ideas, and Cantor's arguments are about as low level as you can get when talking about infinities.

Also, {Z} - {N} is gibberish until you define what you intend those symbols to mean...

 

[ryan]

The set of all integers minus the set of all naturals

 

[beero1000]

The set of all integers minus the set of all naturals

That is the completely unhelpful clarification that I was worried you'd say.

Do you know that the standard operation of subtraction denoted by " - " is not generally defined for sets? Do you mean set difference? Symmetric difference? Subtraction sumset? Are you trying to subtract cardinalities? Something else?

Do you know what curly braces mean when it comes to set theory? If Z is the set of integers then {Z} is the set containing the set of integers as an element, which is very different.

Which definition of equality are you using? Elemental equality? Bijective equivalence? Something else?

Sloppiness is a very, very bad habit to get into when dealing with mathematics. You need to learn how to think carefully if you're going to get anywhere at all and part of that is learning the language with which to precisely convey mathematical ideas. The symbols and their proper usage MATTER. I suspect that not knowing the grammar of the language of mathematics is a major contributor to your confusion.

So, with that said, can you CAREFULLY ask your question again?