Regarding Cantor's Diagonal Argument

[ryan]

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?

Oh, I really did think that I could do that. I want to know what the positive and negative integers minus the natural numbers equals.

 

[beero1000]

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?

Oh, I really did think that I could do that. I want to know what the positive and negative integers minus the natural numbers equals.

aannnndddd, I'm out.

 

[Angra Mainyu]

I'll try a bit more since I made a mistake earlier:

Oh, I really did think that I could do that. I want to know what the positive and negative integers minus the natural numbers equals.

That doesn't clarify what you mean, but if you mean what is left if you remove the natural numbers from the set of positive and negative integers (i.e., all of the integers except for zero), then what is left is the set of negative integers, which has the same cardinality as the set of natural numbers (i.e., it's a denumerable set, i.e., a countably infinite set).

But in any case, have you considered the corrected version of the argument I gave earlier?
The argument proves there is no bijection between N and R.
Then, given that there is a bijection between N and any infinite subset of N, it follows there is no bijection between R and any infinite subset of N (proper or not9.
Since clearly there is no bijection between R and a finite subset of N, it follows that for any subset S of N, there is no bijection between R and S. Hence, R is not countable.

 

[ryan]

Note to self: don't be wrong around mathematicians.

The point is that the naturals are not enough to cancel out all integers, but they can somehow be matched to every integer as long as it is a one-to-one correspondence.

 

[Angra Mainyu]

Note to self: don't be wrong around mathematicians.

The point is that the naturals are not enough to cancel out all integers, but they can somehow be matched to every integer as long as it is a one-to-one correspondence.

ryan,

Sorry if I offended you, but if you want help, you need to try to read carefully the questions you're being asked.
For example, I can help if you tell me what it is you don't understand about the argument I gave.

Let me try by identifying different parts:

Part I:

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.

Part II:

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

Part III:

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


Part IV:

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.

Part V:

That is contradictory, because if we take j=n0, then 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.)

Part VI:

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

Hence, there is no bijection between N and R.

Let's begin with Part I. Do you understand Part I, or is there something about it that you don't understand?

 

[ryan]

Note to self: don't be wrong around mathematicians.

The point is that the naturals are not enough to cancel out all integers, but they can somehow be matched to every integer as long as it is a one-to-one correspondence.

ryan,

Sorry if I offended you, but if you want help, you need to try to read carefully the questions you're being asked.
For example, I can help if you tell me what it is you don't understand about the argument I gave.

Let me try by identifying different parts:

Part I:

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.

Part II:

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

Part III:

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


Part IV:

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.

Part V:

That is contradictory, because if we take j=n0, then 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.)

Part VI:

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

Hence, there is no bijection between N and R.

Let's begin with Part I. Do you understand Part I, or is there something about it that you don't understand?

My last post was meant for beero1000.

I am too rusty to be clear about this proof. However, I will take your word for it because I know that it is true.

That doesn't clarify what you mean, but if you mean what is left if you remove the natural numbers from the set of positive and negative integers (i.e., all of the integers except for zero), then what is left is the set of negative integers, which has the same cardinality as the set of natural numbers (i.e., it's a denumerable set, i.e., a countably infinite set).

Okay, so don't you think it is a paradox that the naturals are not enough to cancel out all integers, but they can somehow be matched to every integer as long as it is in a one-to-one correspondence?

 

[beero1000]

Note to self: don't be wrong around mathematicians.

The point is that the naturals are not enough to cancel out all integers, but they can somehow be matched to every integer as long as it is a one-to-one correspondence.

At some point, I just have to give up and assume you're simply trolling me, intentionally or otherwise. Since it doesn't seem like you're making any effort at all to understand or respond to any of the replies to your posts, I've reached that point.

It's not about being wrong. It's about not making an effort to be right.

 

[ryan]

Note to self: don't be wrong around mathematicians.

The point is that the naturals are not enough to cancel out all integers, but they can somehow be matched to every integer as long as it is a one-to-one correspondence.

At some point, I just have to give up and assume you're simply trolling me, intentionally or otherwise. Since it doesn't seem like you're making any effort at all to understand or respond to any of the replies to your posts, I've reached that point.

It's not about being wrong. It's about not making an effort to be right.

You had mentioned "set difference", so I looked it up here, http://www.basic-mathematics.com/difference-of-sets.html .

It says that you can get the difference of two sets just by subtracting. So instead of symbols I used words to explain. Jeez, this shouldn't be a show stopper.

 

[beero1000]

At some point, I just have to give up and assume you're simply trolling me, intentionally or otherwise. Since it doesn't seem like you're making any effort at all to understand or respond to any of the replies to your posts, I've reached that point.

It's not about being wrong. It's about not making an effort to be right.

You had mentioned "set difference", so I looked it up here, http://www.basic-mathematics.com/difference-of-sets.html .

It says that you can get the difference of two sets just by subtracting. So instead of symbols I used words to explain. Jeez, this shouldn't be a show stopper.

Yes, *I* mentioned set difference as one possibility of what you could have meant by "minus". I mentioned a few others too. *You* just said "minus", and continued to repeat it after I told you that it was ambiguous and asked you to clarify.

Set difference is by no means the only possibility, as the usual notation for set difference is A \ B instead of A - B for the very reason that it is ambiguous, and in particular A - B usually means the Minkowski difference or sumset difference.

So you keep using vague ideas and ambiguous terminology and make no effort to clarify what you meant when asked. Why should I bother continuing to try and help you? This thread has been going on for 50 posts, and what progress has been made?

You can keep googling and youtubing, but you're still going to have a lot of trouble unless you learn how to think carefully about these things. It can't just be big claims, intuition, handwaving and vague ambiguous terms. There is no royal road with math, you actually have to think hard and specify exactly what you mean. If you do that, I'll be happy to help. Until then, you're going to remain too sloppy of a thinker to grasp the distinctions between the ideas you're attempting.

 

[Angra Mainyu]

My last post was meant for beero1000.

Ok, I see.
I misunderstood because your post came directly after mine, and didn't identify the poster - you did say "mathematicians" and I'm not one, but that given the plural, I thought it was either directed at both of us, or at me, thinking for some reason that I was a mathematician (in any case, even if you were right about this particular case, it is too small a sample to make a probable generalization about mathematicians. Also, it's not about being wrong, though. Right or wrong, beero1000 thinks you're not trying seriously, and I have to concede, I did get that impression too).

I am too rusty to be clear about this proof. However, I will take your word for it because I know that it is true.

Thanks, but I was trying to explain it to you. I thought maybe step by step might work (e.g. Part I, then Part II, etc.)

Okay, so don't you think it is a paradox that the naturals are not enough to cancel out all integers, but they can somehow be matched to every integer as long as it is in a one-to-one correspondence?

If I understand what you mean by "cancel out", then no, that's not a paradox (if I also understand what you mean by "paradox")
For example, consider N and N0:=(N U {0}) (i.e., the naturals, and the naturals adding the number zero), and the following function F:N0->N
F(k)=k+1

Then, F is a bijection, but if you remove N from N0 (that's what you mean by "cancel out"), you still get a nonempty set (namely, {0}).
That seems natural to me, and in any case, no contradiction follows.

 

[ryan]

Okay, so don't you think it is a paradox that the naturals are not enough to cancel out all integers, but they can somehow be matched to every integer as long as it is in a one-to-one correspondence?

If I understand what you mean by "cancel out", then no, that's not a paradox (if I also understand what you mean by "paradox")
For example, consider N and N0:=(N U {0}) (i.e., the naturals, and the naturals adding the number zero), and the following function F:N0->N
F(k)=k+1

Then, F is a bijection, but if you remove N from N0 (that's what you mean by "cancel out"), you still get a nonempty set (namely, {0}).
That seems natural to me, and in any case, no contradiction follows.

But there is something paradoxical (or at least inconsistent) about the fact that we can correlate a natural number to all natural numbers and negative integers in the set Z. But, when we remove every natural number from the set Z, we are left with the rest of the negative integers. If all of the natural numbers can match up to all of the integers, why then are negative integers left when all natural numbers are removed?

Please answer this question because it sums up everything that troubles me about Cantor's argument.

 

[Angra Mainyu]

But there is something paradoxical (or at least inconsistent) about the fact that we can correlate a natural number to all natural numbers and negative integers in the set Z. But, when we remove every natural number from the set Z, we are left with the rest of the negative integers. If all of the natural numbers can match up to all of the integers, why then are negative integers left when all natural numbers are removed?

Because the matching is not the identity, and clearly if you remove the natural numbers from the integers, then the negative integers plus zero are left.
Similarly, if you remove the natural numbers from the nonnegative integers, then zero is still left. But that does not change the fact that there is a bijection between the nonnegative integers and the natural numbers; one such bijection is the function F that I gave above.

If by "inconsistent" you mean it leads to a contradiction, then it doesn't (try to derive one, if you don't believe me). If you mean something else, what do you mean? (the same for "paradoxical").

Please answer this question because it sums up everything that troubles me about Cantor's argument.

Maybe, but the impression I get from reading your posts is that it doesn't. I think either addressing beero1000's requests for clarity or trying to understand the argument I gave step by step would be more likely to help you understand Cantor's argument. Your choice, of course.

 

[ryan]

Because the matching is not the identity, and clearly if you remove the natural numbers from the integers, then the negative integers plus zero are left.
Similarly, if you remove the natural numbers from the nonnegative integers, then zero is still left. But that does not change the fact that there is a bijection between the nonnegative integers and the natural numbers; one such bijection is the function F that I gave above.

I do not understand your answer to my question. Don't you think it's perplexing that we can match each element but we can't subtract each element, from my example?

I promise that the smoke will clear because this is the heart of my issue.

 

[Angra Mainyu]

I don't find it perplexing, I'm afraid, and it's not that we can't substract every element. We can substract anything we want, but if we substract N, there are integers left.
As for my answer, well I was trying to explain it in a way that is intuitive to you, and that addresses what you're trying to say, because if the matching were the identity, then those would be the same sets, so by removing the elements of one of the sets from the other, there would be nothing left, and because I thought you were confusing a matching with an identity (though my attempts at mind reading aren't working).
Then again (I need some sleep), even if it weren't the identity, there might be nothing left, so the answer isn't right. I should have said because N is a subset of Z, and the matching cannot be the identity (i.e., it's a proper subset).

I can try another way: since there are integers that aren't naturals, of course, clearly, obviously, if you remove the naturals from the integers, you will still have some integers left!
The fact that there is a matching doesn't affect that at all.

We can do it even with finite sets, as long as one is not a subset of the other.

For example:
A:={1, 2, 3}
B:={1, 2, 0}

g:A->B
g(1)=1
g(2)=2
g(3)=0

Clearly, we can match each element of A to each element of B through the bijection g.
But now, consider the set C:=A \ B.
Then, C is the set {3}, so even though we can match every element, if we remove every element of B from A (every element that is in A, of course), we still have an element left. With infinite sets, you can do the same with a proper subset of a set (whereas B is not a subset of A). But there is no problem.

In any case, I think it would be much better if you tried to understand my argument step by step, since your line of questions isn't productive.

 

[Angra Mainyu]

I promise that the smoke will clear because this is the heart of my issue.

I don't think so. In fact, your issue isn't at this point even about Cantor's argument, but maybe about infinite sets, or not even that (I'm not sure; again, my attempts at my reading aren't working, but I can still tell from what you say that this isn't about Cantor's argument, even if I can't tell exactly what it is about).

 

[ryan]

Go to sleep we will pick it up tomorrow.

 

[EricK]

ryan, I think your problem is that you have many intuitions about how sets work based on your knowledge of finite sets, and you are carrying all of them over when you think about infinite sets, but only some of them apply.

So, consider the two finite sets {2,4,6} and {1,2,3}. These are the same size because we can form a correspondence between the elements of each set: 2->1, 4->2, 6->3. But that's not the only we we can form a correspondence. We could have done 2->2, 4->3, 6->1. And in fact, however we had tried to form the correspondence it would have worked. Conversely, with the sets {2,4,6} and {1,2}, however we try to form a correspondence we will fail - there will always be one element from the first set left over.

But when we look at infinite sets, things aren't so simple. Consider the sets {2,4,6,8,....) and {1,2,3,4,...}. i.e. the positive even numbers and the positive numbers. We can easily enough form a correspondence between them so that all elements of each set are used up: 2->1, 4->2, 6->3 etc. So they appear to be the same size. But, of course we can also try to form a correspondence and fail to match them up: 2->2, 4->4, 6->6 etc leaves all the odd numbers (i.e. an infinite number of elements) unmatched from the second set. Or we could try to match 2->2, 4->3, 6->4, 8->5 etc and leave just one element in the second set unmatched.

So here is the major difference - given two finite sets, you will either always succeed, however you try to match them, or never succeed however you try (depending on whether they are the same size or not). But with two infinite sets, even if some attempts at a correspondence fail, there still might be some which succeed. And we say two infinite sets are the same size if there exists some way to match them up, even if other ways to try to match them fail.

So the key thing with infinite sets is not whether some attempt to match them fails (because we will always be able to do that!), but whether there is any possible attempt which succeeds. So when you say:

But there is something paradoxical (or at least inconsistent) about the fact that we can correlate a natural number to all natural numbers and negative integers in the set Z. But, when we remove every natural number from the set Z, we are left with the rest of the negative integers. If all of the natural numbers can match up to all of the integers, why then are negative integers left when all natural numbers are removed?

, this is the point you are missing. You are looking at one of many possible failed attempts to form a correspondence (matching the positive integers with the positive integers, and not matching anything with the negative integers). But that's really irrelevant to the fact that some other correspondence does work.

In the case above, I explicitly demonstrated a correspondence which works. Given any number in either set, I could tell you the corresponding number in the other set. Cantor's diagonal argument is a standard proof by contradiction. It assumes you have made an attempt at a correspondence between the Real numbers in the interval (0,1) and the counting numbers {1,2,3...}, and then shows how, for that attempt, you can find a real number which doesn't correspond to any counting number. It's not showing that one particular correspondence will fail (because as we have seen, with infinite finding attempted correspondence which fail is always easy), it's showing why every attempted correspondence is bound to fail.

 

[ryan]

I don't find it perplexing, I'm afraid, and it's not that we can't substract every element. We can substract anything we want, but if we substract N, there are integers left.
As for my answer, well I was trying to explain it in a way that is intuitive to you, and that addresses what you're trying to say, because if the matching were the identity, then those would be the same sets, so by removing the elements of one of the sets from the other, there would be nothing left, and because I thought you were confusing a matching with an identity (though my attempts at mind reading aren't working).
Then again (I need some sleep), even if it weren't the identity, there might be nothing left, so the answer isn't right. I should have said because N is a subset of Z, and the matching cannot be the identity (i.e., it's a proper subset).

I can try another way: since there are integers that aren't naturals, of course, clearly, obviously, if you remove the naturals from the integers, you will still have some integers left!
The fact that there is a matching doesn't affect that at all.

We can do it even with finite sets, as long as one is not a subset of the other.

For example:
A:={1, 2, 3}
B:={1, 2, 0}

g:A->B
g(1)=1
g(2)=2
g(3)=0

Clearly, we can match each element of A to each element of B through the bijection g.
But now, consider the set C:=A \ B.
Then, C is the set {3}, so even though we can match every element, if we remove every element of B from A (every element that is in A, of course), we still have an element left. With infinite sets, you can do the same with a proper subset of a set (whereas B is not a subset of A). But there is no problem.

Okay, I see. I spent a lot of time today trying to find another problem, but I might be out of concerns.

And thanks, because I think that I did make some progress. Even though I am not totally comfortable with this, I am much more comfortable than when I posted the OP.

- - - Updated - - -

ryan, I think your problem is that you have many intuitions about how sets work based on your knowledge of finite sets, and you are carrying all of them over when you think about infinite sets, but only some of them apply.

So, consider the two finite sets {2,4,6} and {1,2,3}. These are the same size because we can form a correspondence between the elements of each set: 2->1, 4->2, 6->3. But that's not the only we we can form a correspondence. We could have done 2->2, 4->3, 6->1. And in fact, however we had tried to form the correspondence it would have worked. Conversely, with the sets {2,4,6} and {1,2}, however we try to form a correspondence we will fail - there will always be one element from the first set left over.

But when we look at infinite sets, things aren't so simple. Consider the sets {2,4,6,8,....) and {1,2,3,4,...}. i.e. the positive even numbers and the positive numbers. We can easily enough form a correspondence between them so that all elements of each set are used up: 2->1, 4->2, 6->3 etc. So they appear to be the same size. But, of course we can also try to form a correspondence and fail to match them up: 2->2, 4->4, 6->6 etc leaves all the odd numbers (i.e. an infinite number of elements) unmatched from the second set. Or we could try to match 2->2, 4->3, 6->4, 8->5 etc and leave just one element in the second set unmatched.

So here is the major difference - given two finite sets, you will either always succeed, however you try to match them, or never succeed however you try (depending on whether they are the same size or not). But with two infinite sets, even if some attempts at a correspondence fail, there still might be some which succeed. And we say two infinite sets are the same size if there exists some way to match them up, even if other ways to try to match them fail.

So the key thing with infinite sets is not whether some attempt to match them fails (because we will always be able to do that!), but whether there is any possible attempt which succeeds. So when you say:

But there is something paradoxical (or at least inconsistent) about the fact that we can correlate a natural number to all natural numbers and negative integers in the set Z. But, when we remove every natural number from the set Z, we are left with the rest of the negative integers. If all of the natural numbers can match up to all of the integers, why then are negative integers left when all natural numbers are removed?

, this is the point you are missing. You are looking at one of many possible failed attempts to form a correspondence (matching the positive integers with the positive integers, and not matching anything with the negative integers). But that's really irrelevant to the fact that some other correspondence does work.

In the case above, I explicitly demonstrated a correspondence which works. Given any number in either set, I could tell you the corresponding number in the other set. Cantor's diagonal argument is a standard proof by contradiction. It assumes you have made an attempt at a correspondence between the Real numbers in the interval (0,1) and the counting numbers {1,2,3...}, and then shows how, for that attempt, you can find a real number which doesn't correspond to any counting number. It's not showing that one particular correspondence will fail (because as we have seen, with infinite finding attempted correspondence which fail is always easy), it's showing why every attempted correspondence is bound to fail.

Thanks, I don't fully understand the entirety of the diagonal argument, but I am going to have to accept it for now.

 

[ryan]

Another question, what happens if we do the exact same thing as with Cantor's argument. But instead of building a decimal number that doesn't show up for any nth row, we build a very large natural that doesn't show up for any nth row. Each number will take the position left of the next number from the ones position then to the tens position then to the hundreds position ect. It looks very similar to Cantors argument where x is also any number from 0 to 9.

----1 2 3 4 5 . . .

--1 x x x x x . . .

--2 x x x x x . . .

--3 x x x x x . . .

--4 x x x x x . . .

--5 x x x x x . . .
.
.
.


. . . not x(3,3) not x(2,2) not x(1,1)

Won't this natural number be left out like in Cantor's argument?

 

[EricK]

Can you clarify what two sets you are assuming a correspondence between?