Regarding Cantor's Diagonal Argument

[ryan]

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

The naturals to the naturals, and each row is a reflected natural number. So column 1 takes the place of the ones, column 2 takes place of the tens, etc.

 

[EricK]

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

The naturals to the naturals, and each row is a reflected natural number. So column 1 takes the place of the ones, column 2 takes place of the tens, etc.

That's what I suspected. The issue here, is that the "number" you get when you try to apply the diagonal method isn't a natural number. Every natural number has a finite number of digits - a first digit, a second digit etc, however what you will end up with is an infinite string of digits with no beginning.

Cantor's diagonal argument for the Reals works because a real number is an infinite string of digits with no end, and the construction produces such a number.

 

[ryan]

The naturals to the naturals, and each row is a reflected natural number. So column 1 takes the place of the ones, column 2 takes place of the tens, etc.

That's what I suspected. The issue here, is that the "number" you get when you try to apply the diagonal method isn't a natural number. Every natural number has a finite number of digits - a first digit, a second digit etc, however what you will end up with is an infinite string of digits with no beginning.

I can either have a beginning with no end or an end with no beginning. I chose to have it begin in the ones position. Just reflect the rows and they will start in the ones position.

Cantor's diagonal argument for the Reals works because a real number is an infinite string of digits with no end, and the construction produces such a number.

But the nth row and nth column can only ever be natural numbers too. So the rows will only ever have an n number of digits.

 

[EricK]

That's what I suspected. The issue here, is that the "number" you get when you try to apply the diagonal method isn't a natural number. Every natural number has a finite number of digits - a first digit, a second digit etc, however what you will end up with is an infinite string of digits with no beginning.

I can either have a beginning with no end or an end with no beginning. I chose to have it begin in the ones position. Just reflect the rows and they will start in the ones position.

But you are still constructing a "number" without a finite number of digits i.e. not a natural number at all.

Cantor's diagonal argument for the Reals works because a real number is an infinite string of digits with no end, and the construction produces such a number.

But the nth row and nth column can only ever be natural numbers too. So the rows will only ever have an n number of digits.

Not sure what you are saying here. If you restrict yourself to an n x n grid, then you can construct an n digit number which is not in the grid, but thereby you are just showing that there are more than n n-digit numbers.

 

[ryan]

I can either have a beginning with no end or an end with no beginning. I chose to have it begin in the ones position. Just reflect the rows and they will start in the ones position.

But you are still constructing a "number" without a finite number of digits i.e. not a natural number at all.

Cantor's diagonal argument for the Reals works because a real number is an infinite string of digits with no end, and the construction produces such a number.

But the nth row and nth column can only ever be natural numbers too. So the rows will only ever have an n number of digits.

Not sure what you are saying here. If you restrict yourself to an n x n grid, then you can construct an n digit number which is not in the grid, but thereby you are just showing that there are more than n n-digit numbers.

Okay then I have an underlying issue with the relationship between natural numbers and aleph 0.

A sequence of natural numbers would mean that there are at least n elements for any n. For example, if n = 6 in a sequence of natural numbers then we know that there are at least 6 elements in some set. So then how can we get an infinite number of elements while n can only ever equal a natural number? Wouldn't all of the natural numbers have to mean that there must be a number where n = infinity (aleph 0)?

 

[EricK]

But you are still constructing a "number" without a finite number of digits i.e. not a natural number at all.

Cantor's diagonal argument for the Reals works because a real number is an infinite string of digits with no end, and the construction produces such a number.

But the nth row and nth column can only ever be natural numbers too. So the rows will only ever have an n number of digits.

Not sure what you are saying here. If you restrict yourself to an n x n grid, then you can construct an n digit number which is not in the grid, but thereby you are just showing that there are more than n n-digit numbers.

Okay then I have an underlying issue with the relationship between natural numbers and aleph 0.

A sequence of natural numbers would mean that there are at least n elements for any n. For example, if n = 6 in a sequence of natural numbers then we know that there are at least 6 elements in some set. So then how can we get an infinite number of elements while n can only ever equal a natural number? Wouldn't all of the natural numbers have to mean that there must be a number where n = infinity (aleph 0)?

Infinity is not a number. 'Infinite' is the word used to describe the size of the set of all natural numbers (and any larger sets). It is easy to see that this can not be any natural number. eg we know it is not the number 1,000 because the set {1,2,3,...,999,1000,1001} is larger than 1,000 and the size of the set of all numbers will be larger still. And we knoe it is not 1,000,000 because the set {1,2,..., 1000001} is larger. And by the same argument we can show that the size of the set of natural numbers, whatever it is, is not a natural number.

Again, this might be a situation where you are relying on your intuition about numbers, rather than just looking at the logical arguments and see where they lead.

 

[Speakpigeon]

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.

I think it's Russell who said that if you don't understand logic nobody will be able to explain it to you.
EB

 

[ryan]

Okay then I have an underlying issue with the relationship between natural numbers and aleph 0.

A sequence of natural numbers would mean that there are at least n elements for any n. For example, if n = 6 in a sequence of natural numbers then we know that there are at least 6 elements in some set. So then how can we get an infinite number of elements while n can only ever equal a natural number? Wouldn't all of the natural numbers have to mean that there must be a number where n = infinity (aleph 0)?

Infinity is not a number. 'Infinite' is the word used to describe the size of the set of all natural numbers (and any larger sets). It is easy to see that this can not be any natural number. eg we know it is not the number 1,000 because the set {1,2,3,...,999,1000,1001} is larger than 1,000 and the size of the set of all numbers will be larger still. And we knoe it is not 1,000,000 because the set {1,2,..., 1000001} is larger. And by the same argument we can show that the size of the set of natural numbers, whatever it is, is not a natural number.

Again, this might be a situation where you are relying on your intuition about numbers, rather than just looking at the logical arguments and see where they lead.

I definitely see your logical argument, but what about my logical argument?

The set of all natural numbers can only have natural numbers in it, and each natural number represents at least that many elements. An infinite number of numbers would have to mean that a natural number would represent at least that many elements.

Clearly there is no possible natural number that can represent an infinite number of elements.

 

[EricK]

Infinity is not a number. 'Infinite' is the word used to describe the size of the set of all natural numbers (and any larger sets). It is easy to see that this can not be any natural number. eg we know it is not the number 1,000 because the set {1,2,3,...,999,1000,1001} is larger than 1,000 and the size of the set of all numbers will be larger still. And we knoe it is not 1,000,000 because the set {1,2,..., 1000001} is larger. And by the same argument we can show that the size of the set of natural numbers, whatever it is, is not a natural number.

Again, this might be a situation where you are relying on your intuition about numbers, rather than just looking at the logical arguments and see where they lead.

I definitely see your logical argument, but what about my logical argument?

The set of all natural numbers can only have natural numbers in it, and each natural number represents at least that many elements. An infinite number of numbers would have to mean that a natural number would represent at least that many elements.

Clearly there is no possible natural number that can represent an infinite number of elements.

I'm sorry. I don't understand what it is you are trying to show here.

 

[ryan]

I definitely see your logical argument, but what about my logical argument?

The set of all natural numbers can only have natural numbers in it, and each natural number represents at least that many elements. An infinite number of numbers would have to mean that a natural number would represent at least that many elements.

Clearly there is no possible natural number that can represent an infinite number of elements.

I'm sorry. I don't understand what it is you are trying to show here.

Let's simply try to match each number of elements m to ordered sets of n natural numbers starting from 1.

n as a function of m

m = 1 element, then n = 1; m = 2 elements, then n = 2; m = aleph 0 elements, then n = aleph 0

Now, I must have done something wrong here for this argument to be false or not make sense. What is wrong with this argument?

 

[EricK]

I'm sorry. I don't understand what it is you are trying to show here.

Let's simply try to match each number of elements m to ordered sets of n natural numbers starting from 1.

n as a function of m

m = 1 element, then n = 1; m = 2 elements, then n = 2; m = aleph 0 elements, then n = aleph 0

Now, I must have done something wrong here for this argument to be false or not make sense. What is wrong with this argument?

You can say that every natural number, n, is matched to the finite set {1,2,3...,n}. But there is no reason to assume that therefore there must be a natural number which matches to the infinite set {1,2,3...}. In fact there can't be, because we have matched each natural number to a finite set.

 

[ryan]

Let's simply try to match each number of elements m to ordered sets of n natural numbers starting from 1.

n as a function of m

m = 1 element, then n = 1; m = 2 elements, then n = 2; m = aleph 0 elements, then n = aleph 0

Now, I must have done something wrong here for this argument to be false or not make sense. What is wrong with this argument?

You can say that every natural number, n, is matched to the finite set {1,2,3...,n}. But there is no reason to assume that therefore there must be a natural number which matches to the infinite set {1,2,3...}. In fact there can't be, because we have matched each natural number to a finite set.

Unless I am misunderstanding something here, it seems like you are agreeing with me.

 

[EricK]

You can say that every natural number, n, is matched to the finite set {1,2,3...,n}. But there is no reason to assume that therefore there must be a natural number which matches to the infinite set {1,2,3...}. In fact there can't be, because we have matched each natural number to a finite set.

Unless I am misunderstanding something here, it seems like you are agreeing with me.

Possibly. But I'm still not sure what you are ultimately trying to show here.

Cantor's diagonal argument is (in fairly non-mathematical lingo) a proof that there are more real numbers between 0 and 1 than there are integers. i.e. it is impossible to form a 1-1 correspondence between those two sets. And, given an attempt to form such a correspondence, it shows you how to find a real number which isn't matched to any integer.

Can you say, in similar sort of language, what it is you are trying to show?

 

[ryan]

Unless I am misunderstanding something here, it seems like you are agreeing with me.

Possibly. But I'm still not sure what you are ultimately trying to show here.

Cantor's diagonal argument is (in fairly non-mathematical lingo) a proof that there are more real numbers between 0 and 1 than there are integers. i.e. it is impossible to form a 1-1 correspondence between those two sets. And, given an attempt to form such a correspondence, it shows you how to find a real number which isn't matched to any integer.

Can you say, in similar sort of language, what it is you are trying to show?

If what I am saying about the naturals is true, then the set of all naturals does not have an infinite number of elements. For the same reasons, the reals wouldn't be infinite either. This would all ultimately mean that the reals just have more elements than the naturals, which is obviously true.

 

[EricK]

Possibly. But I'm still not sure what you are ultimately trying to show here.

Cantor's diagonal argument is (in fairly non-mathematical lingo) a proof that there are more real numbers between 0 and 1 than there are integers. i.e. it is impossible to form a 1-1 correspondence between those two sets. And, given an attempt to form such a correspondence, it shows you how to find a real number which isn't matched to any integer.

Can you say, in similar sort of language, what it is you are trying to show?

If what I am saying about the naturals is true, then the set of all naturals does not have an infinite number of elements. For the same reasons, the reals wouldn't be infinite either. This would all ultimately mean that the reals just have more elements than the naturals, which is obviously true.

But the naturals do not have a finite number of elements - and I don't see how what you are saying shows that to be false.

Suppose the naturals did have a finite number of elements: Then the set of all naturals could be put into a 1-1 correspondence with the set {1,2,3,..., N} for some number N (that is, after, all, what it means for a set to be finite). So imagine such a correspondence. The first N+1 elements of the naturals are in a 1-1 correspondence with some subset of {1,2,3,...N} ie there are fewer than N of them. That is clearly false, hence no such correspondence can exist.

 

[ryan]

If what I am saying about the naturals is true, then the set of all naturals does not have an infinite number of elements. For the same reasons, the reals wouldn't be infinite either. This would all ultimately mean that the reals just have more elements than the naturals, which is obviously true.

But the naturals do not have a finite number of elements - and I don't see how what you are saying shows that to be false.

Suppose the naturals did have a finite number of elements: Then the set of all naturals could be put into a 1-1 correspondence with the set {1,2,3,..., N} for some number N (that is, after, all, what it means for a set to be finite). So imagine such a correspondence. The first N+1 elements of the naturals are in a 1-1 correspondence with some subset of {1,2,3,...N} ie there are fewer than N of them. That is clearly false, hence no such correspondence can exist.

I do not mean a finite set; I mean any of all N. Any nth number is at least the number of elements that the set has. An infinite number of elements would have to mean that at some point n = aleph 0.

 

[EricK]

I do not mean a finite set; I mean any of all N.

I don't understand what you are trying to say here.

Any nth number is at least the number of elements that the set has.

Nor here. Any nth number is less than the number of elements the set of Natural numbers has.

An infinite number of elements would have to mean that at some point n = aleph 0.

At some point in what? Aleph 0 is not a natural number, so n can never equal Aleph 0. Consider the sets {1}, {1,2}, {1,2,3} etc.If you stop at any point, {1,2,3,...,N}, you have a finite set of size N. If you never stop, you have an infinite set of size Aleph 0. These are two distinct situations so Aleph 0 does not equal N for any N.

 

[ryan]

I don't understand what you are trying to say here.

Any nth number is at least the number of elements that the set has.

Nor here. Any nth number is less than the number of elements the set of Natural numbers has.

An infinite number of elements would have to mean that at some point n = aleph 0.

At some point in what? Aleph 0 is not a natural number, so n can never equal Aleph 0. Consider the sets {1}, {1,2}, {1,2,3} etc.If you stop at any point, {1,2,3,...,N}, you have a finite set of size N. If you never stop, you have an infinite set of size Aleph 0. These are two distinct situations so Aleph 0 does not equal N for any N.

Sorry, I wasn't being clear.

Let's just take a subset of sequential natural numbers starting at 1, {1, 2, 3, 4}. In this kind of set, there are 4 natural numbers where n = 4. We can also say that n = # of elements. But then what about the set of all naturals; n cannot equal aleph 0.

 

[EricK]

I don't understand what you are trying to say here.


Nor here. Any nth number is less than the number of elements the set of Natural numbers has.

An infinite number of elements would have to mean that at some point n = aleph 0.

At some point in what? Aleph 0 is not a natural number, so n can never equal Aleph 0. Consider the sets {1}, {1,2}, {1,2,3} etc.If you stop at any point, {1,2,3,...,N}, you have a finite set of size N. If you never stop, you have an infinite set of size Aleph 0. These are two distinct situations so Aleph 0 does not equal N for any N.

Sorry, I wasn't being clear.

Let's just take a subset of sequential natural numbers starting at 1, {1, 2, 3, 4}. In this kind of set, there are 4 natural numbers where n = 4. We can also say that n = # of elements. But then what about the set of all naturals; n cannot equal aleph 0.

In the first cases, n is the natural number which is the highest number in the set. In the last case that definition no longer holds (as there isn't a highest number) but you haven't defined what n is.

 

[ryan]

Sorry, I wasn't being clear.

Let's just take a subset of sequential natural numbers starting at 1, {1, 2, 3, 4}. In this kind of set, there are 4 natural numbers where n = 4. We can also say that n = # of elements. But then what about the set of all naturals; n cannot equal aleph 0.

In the first cases, n is the natural number which is the highest number in the set. In the last case that definition no longer holds (as there isn't a highest number) but you haven't defined what n is.

I found an equivalence to what n is. See what I put in bold: n is also the number of elements. The number of elements in the set of the naturals is aleph 0. n Cannot equal aleph 0.