Regarding Cantor's Diagonal Argument

[ryan]

Here it is to recall or understand, https://www.youtube.com/watch?v=mEEM_dLWY0g .

So the argument says that there will be an object/number that is not in the list of "matching" natural numbers.

Now here is my counter argument. If I have a bag full of natural numbers in my left hand and a bag full of natural numbers in my right hand, it can be said that I have an infinite number of objects in each hand. And it would also mean that there is a one-to-one correspondence for each object in one bag to each object in the other bag.

What if I throw an apple in one of the bags? I have an object that is not one-to-one with the naturals because it's something else; apple is not an element of N. Yet I still only have an infinite number of objects in each bag.

 

[beero1000]

Here it is to recall or understand, https://www.youtube.com/watch?v=mEEM_dLWY0g .

So the argument says that there will be an object/number that is not in the list of "matching" natural numbers.

Now here is my counter argument. If I have a bag full of natural numbers in my left hand and a bag full of natural numbers in my right hand, it can be said that I have an infinite number of objects in each hand. And it would also mean that there is a one-to-one correspondence for each object in one bag to each object in the other bag.

What if I throw an apple in one of the bags? I have an object that is not one-to-one with the naturals because it's something else; apple is not an element of N. Yet I still only have an infinite number of objects in each bag.

One-to-one correspondences are functions from one set to another so it does not matter what is in the bags, just how many. Adding one element to a countable set still yields a countable set, as we can simply shift the correspondence appropriately.

 

[ryan]

Here it is to recall or understand, https://www.youtube.com/watch?v=mEEM_dLWY0g .

So the argument says that there will be an object/number that is not in the list of "matching" natural numbers.

Now here is my counter argument. If I have a bag full of natural numbers in my left hand and a bag full of natural numbers in my right hand, it can be said that I have an infinite number of objects in each hand. And it would also mean that there is a one-to-one correspondence for each object in one bag to each object in the other bag.

What if I throw an apple in one of the bags? I have an object that is not one-to-one with the naturals because it's something else; apple is not an element of N. Yet I still only have an infinite number of objects in each bag.

One-to-one correspondences are functions from one set to another so it does not matter what is in the bags, just how many. Adding one to a countable set still yields a countable set, as we can simply shift the correspondence appropriately.

But the argument shows there being only one object left remaining that is not matching a natural number. The apple does not match a natural number either.

The argument leaves one object out. Why can't we just add it to the infinity of N cardinality, aleph-null.

 

[beero1000]

One-to-one correspondences are functions from one set to another so it does not matter what is in the bags, just how many. Adding one to a countable set still yields a countable set, as we can simply shift the correspondence appropriately.

But the argument shows there being only one object left remaining that is not matching a natural number. The apple does not match a natural number either.

The diagonal argument shows that EVERY potential assignment of the integers to the reals necessarily excludes some reals. Your example just shows that ONE assignment doesn't work. If we shift the correspondence, it is easy to find alternative matchings from one bag to the other that do work.

 

[ryan]

But the argument shows there being only one object left remaining that is not matching a natural number. The apple does not match a natural number either.

The diagonal argument shows that EVERY potential assignment of the integers to the reals necessarily excludes some reals. Your example just shows that ONE assignment doesn't work. If we shift the correspondence, it is easy to find alternative matchings from one bag to the other that do work.

Similar to the argument, I can say that for every object in one bag that is not an apple, there will be a corresponding object in the other bag that is not an apple. In the end, the naturals are used up, and I am left with the apple in the other bag. I don't see the difference to my analogy.

 

[beero1000]

The diagonal argument shows that EVERY potential assignment of the integers to the reals necessarily excludes some reals. Your example just shows that ONE assignment doesn't work. If we shift the correspondence, it is easy to find alternative matchings from one bag to the other that do work.

Similar to the argument, I can say that for every object in one bag that is not an apple, there will be a corresponding object in the other bag that is not an apple. In the end, the naturals are used up, and I am left with the apple in the other bag. I don't see the difference to my analogy.

Your second sentence does not follow from your first. A countably infinite set cannot be 'used up' in that way.

The proof is in the pudding, here is a correspondence between {apple, 1, 2, 3, ...} and {1, 2, 3,....}:

f(apple) = 1
For every natural n, f = n+1

Every element of the first set is matched uniquely to an element of the second. If your argument was correct, no such matching could exist.

 

[ryan]

Similar to the argument, I can say that for every object in one bag that is not an apple, there will be a corresponding object in the other bag that is not an apple. In the end, the naturals are used up, and I am left with the apple in the other bag. I don't see the difference to my analogy.

Your second sentence does not follow from your first. A countably infinite set cannot be 'used up' in that way.

The proof is in the pudding, here is a correspondence between {apple, 1, 2, 3, ...} and {1, 2, 3,....}:

f(apple) = 1
For every natural n, f = n+1

Every element of the first set is matched uniquely to an element of the second. If your argument was correct, no such matching could exist.

But similar to the proof, why don't we just use every element that is not an apple?

 

[beero1000]

Your second sentence does not follow from your first. A countably infinite set cannot be 'used up' in that way.

The proof is in the pudding, here is a correspondence between {apple, 1, 2, 3, ...} and {1, 2, 3,....}:

f(apple) = 1
For every natural n, f = n+1

Every element of the first set is matched uniquely to an element of the second. If your argument was correct, no such matching could exist.

But similar to the proof, why don't we just use every element that is not an apple?

There are many wrong choices - the key here is that there is at least one that works.

 

[ryan]

I am not sure what you mean.

Instead of an apple, let me use -1 as the extra element. So let's match each N number in one bag to each N number in the other bag that is not -1. -1 will never be used either.

But as we know integers are suppose to have the same cardinality as the naturals.

 

[beero1000]

I am not sure what you mean.

Instead of an apple, let me use -1 as the extra element. So let's match each N number in one bag to each N number in the other bag that is not -1. -1 will never be used either.

But as we know integers are suppose to have the same cardinality as the naturals.

I don't really know any simpler way to say it. No one is required to use that correspondence. All that is necessary is that a correspondence between the two sets exist.

Being in one-to-one correspondence with some of your proper subsets is a defining attribute of infinite sets. In no way does that negate the one-to-one correspondence from a set to itself.

 

[ryan]

I am not sure what you mean.

Instead of an apple, let me use -1 as the extra element. So let's match each N number in one bag to each N number in the other bag that is not -1. -1 will never be used either.

But as we know integers are suppose to have the same cardinality as the naturals.

I don't really know any simpler way to say it. No one is required to use that correspondence. All that is necessary is that a correspondence between the two sets exist.

Being in one-to-one correspondence with some of your proper subsets is a defining attribute of infinite sets. In no way does that negate the one-to-one correspondence from a set to itself.

What is different between a -1 that gets left out of the of the set and the number that gets left out of the set in Cantor's argument?

 

[beero1000]

I don't really know any simpler way to say it. No one is required to use that correspondence. All that is necessary is that a correspondence between the two sets exist.

Being in one-to-one correspondence with some of your proper subsets is a defining attribute of infinite sets. In no way does that negate the one-to-one correspondence from a set to itself.

What is different between a -1 that gets left out of the of the set and the number that gets left out of the set in Cantor's argument?

Please go back and read post #4 in this thread.

 

[ryan]

But the argument shows there being only one object left remaining that is not matching a natural number. The apple does not match a natural number either.

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

So then why don't we just keep shifting the correspondence to each real that is excluded?

 

[beero1000]

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

So then why don't we just keep shifting the correspondence to each real that is excluded?

You absolutely can, but for any correspondence you propose you will necessarily continue to exclude real numbers.

There cannot exist a one-to-one correspondence between the reals and the integers. No amount of fiddling with correspondences that don't work will ever find one that does...

 

[Angra Mainyu]

ryan:

beero1000 already explained it, but maybe you'll see it in the following way (readers: yes, it's not elegant, but it might work...).

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(n,n)=h for all n. But that is contradictory, 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]

To twist the knife a little more:

If I match every integer to a real, I necessarily miss some real numbers. So I again match each integer to a new real, and still miss real numbers. If I continue matching integers to reals forever, I will still never match all of the reals. This is true even if I drop the requirement that I match all the reals with one matching. Even if I include every real that was ever matched in my infinite sequence of matchings each of an infinite number of reals (even if I never repeat a real the entire time!) I will still miss real numbers.

There are A LOT of real numbers...

 

[ryan]

ryan:

beero1000 already explained it, but maybe you'll see it in the following way (readers: yes, it's not elegant, but it might work...).

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(n,n)=h for all n. But that is contradictory, 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.

Thanks for trying.

 

[ryan]

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?

 

[beero1000]

You keep asking the same question - it's been answered already, multiple times. Here is post #4 again:

But the argument shows there being only one object left remaining that is not matching a natural number. The apple does not match a natural number either.

The diagonal argument shows that EVERY potential assignment of the integers to the reals necessarily excludes some reals. Your example just shows that ONE assignment doesn't work. If we shift the correspondence, it is easy to find alternative matchings from one bag to the other that do work.

Take some time and really think about it.

 

[Angra Mainyu]

ryan:

beero1000 already explained it, but maybe you'll see it in the following way (readers: yes, it's not elegant, but it might work...).

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(n,n)=h for all n. But that is contradictory, 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.

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?