Trouble with Understanding Cantor's Diagonal Argument

[Mates]

Yes, in that case, we would have shown that the set of rational numbers is "uncountable". Since you are the one claiming that you could apply Cantor's argument to the rational numbers, and get the same result, you would have to show that it is possible for this process to result in a rational number.

(Actually, since we have a completely separate proof that the set of rationals is countable, the number you arrive at cannot be rational!)

Okay, I couldn't quite see the difference between applying the argument to the rationals vs irrationals, but I now see what the difference is.


Thank-you very very much!

 

[Mates]

Forgive me if I am dead wrong, but I really think I have found a contradiction.


I will attempt to list all real numbers between 0.1 and 1 in the following fashion.


1) 0.10000 ...
2) 0.20000 ...
3) 0.30000 ...
.
.
.


After the first decimal place becomes 9, the second decimal place and the first will then make all possible combinations between 1 and 9 of the first and second decimal places, which is 9^2. Then we do the same for n decimal places (columns), 9^n possible combinations.


My rule in an attempt to leave out a rational will be that any number not 3 becomes 3, and any 3 becomes, say, 8.


Clearly the number that will be left out is going to be the rational number 0.333...


I take from this that one of 2 problems occurs here. Either we can never construct a nonterminating decimal number for all N elements, or that we think we are omitting a number that is actually there (that which n has not "caught up to" yet).


Also, in my list, or a list like mine, couldn't I find pi given an infinite amount of time and space? Shouldn't the infinite number of decimal places be exhausted for pi the same way they would be exhausted for 1/3?

 

[HallsofIvy]

You are dead wrong and I forgive you.

First, your list contains only those rational numbers that have terminating decimal representations. And it is easy to show that those are only the rational numbers that, written as a fraction, have only powers of 2 and 5 in the denominator so your list is not all rational numbers from its definition. Starting with a list that only contains some rational numbers says nothing about the countability of the set of rational numbers.

Second, no, you could not find "\(\displaystyle \pi\)" in this list. \(\displaystyle \pi\) is not rational and your list contains only a small subset of the rationals.

 

[Mates]

You are dead wrong and I forgive you.

First, your list contains only those rational numbers that have terminating decimal representations. And it is easy to show that those are only the rational numbers that, written as a fraction, have only powers of 2 and 5 in the denominator so your list is not all rational numbers from its definition. Starting with a list that only contains some rational numbers says nothing about the countability of the set of rational numbers.

Second, no, you could not find "\(\displaystyle \pi\)" in this list. \(\displaystyle \pi\) is not rational and your list contains only a small subset of the rationals.

But wouldn't an infinite number of natural elements exhaust an infinite number of decimal places?

 

[HallsofIvy]

But wouldn't an infinite number of natural elements exhaust an infinite number of decimal places?

No, it wouldn't. Suppose you were to make a list of all integers. That would be an infinite list but every number on it would be finite. Similarly, although you have an infinite list of numbers here, every number on it "terminates" at some finite number of digits (has only "0" beyond that point) and so is a rational number which, expressed as a fraction, has only powers of 2 and 5 in the denominator. That is, as I said, only a small subset of the set of all rational numbers.

 

[Mates]

No, it wouldn't. Suppose you were to make a list of all integers. That would be an infinite list but every number on it would be finite. Similarly, although you have an infinite list of numbers here, every number on it "terminates" at some finite number of digits (has only "0" beyond that point) and so is a rational number which, expressed as a fraction, has only powers of 2 and 5 in the denominator. That is, as I said, only a small subset of the set of all rational numbers.

Suppose the list was just :



1) 0.3
2) 0.33
3) 0.333
.
.
.


Since n rows = n decimal places with 3, would this infinite list eventually have 1/3, using all elements of N?

 

[JeffM]

Suppose the list was just :



1) 0.3
2) 0.33
3) 0.333
.
.
.


Since n rows = n decimal places with 3, would this infinite list eventually have 1/3, using all elements of N?

No.

You must not think that \(\displaystyle \aleph_0\) is a natural number.

The number of elements in a set of numbers is independent of the numbers in the set. There are

5 elements in the set {6, 7, 8, 9, 10), but 5 is not in the set, and although 6 is in the set, it is not the number of elements in the set.

The number of elements in the set of natural numbers is \(\displaystyle \aleph_0\), which is not itself a natural number.

Your list implicitly assumes that the last element in your list is infinity. The whole point is that there is no last element in the list.

It is easier I think to consider symbols like \(\displaystyle +\) and \(\displaystyle -\).

So we have

1 +------... forever
2 -+-----... forever
And so on forever.

The list is endless, and each string of symbols is endless.

We intuitively suppose that this endless list will contain every possible endless string. (Assuming that "endless" is meaningful, which you do not have to accept. Cantor's whole idea is based on accepting that "endless" is meaningful.)

But Cantor shows that if such a list is possible, it will not contain every possible string. We can construct a new one by flipping the nth symbol in the nth row. So an infinitely denumerable list of infinitely denumerable strings of just two symbols is incomplete. It is counter-intuitive because we experience only the finite. The infinite is quite weird.

What happens is that Cantor's very simple argument gets bogged down in comprehending the irrational numbers.

 

[Mates]

No.

You must not think that \(\displaystyle \aleph_0\) is a natural number.

The number of elements in a set of numbers is independent of the numbers in the set. There are

5 elements in the set {6, 7, 8, 9, 10), but 5 is not in the set, and although 6 is in the set, it is not the number of elements in the set.

The number of elements in the set of natural numbers is \(\displaystyle \aleph_0\), which is not itself a natural number.

Your list implicitly assumes that the last element in your list is infinity. The whole point is that there is no last element in the list.

It is easier I think to consider symbols like \(\displaystyle +\) and \(\displaystyle -\).

So we have

1 +------... forever
2 -+-----... forever
And so on forever.

The list is endless, and each string of symbols is endless.

We intuitively suppose that this endless list will contain every possible endless string. (Assuming that "endless" is meaningful, which you do not have to accept. Cantor's whole idea is based on accepting that "endless" is meaningful.)

But Cantor shows that if such a list is possible, it will not contain every possible string. We can construct a new one by flipping the nth symbol in the nth row. So an infinitely denumerable list of infinitely denumerable strings of just two symbols is incomplete. It is counter-intuitive because we experience only the finite. The infinite is quite weird.

What happens is that Cantor's very simple argument gets bogged down in comprehending the irrational numbers.

But doesn't 1/3 have an infinite but countable number of 3's behind the zero? If so, that would match the aleph 0 numberl of rows. Similarly sum of 1/(3*10^(n-1)) as n goes to infinity.

 

[JeffM]

That is exactly my point. You never get to the line numbered \(\displaystyle \aleph_0.\) The list goes on forever. You get to n, and then you have n + 1,
but n + 1 is still a natural number, not a transfinite number. So your algorithm will never get you to a decimal expansion of 1/3.

But wait you say. Did not Cantor find a way to put rationals into 1-to-1 correspondence with integers? Yes, he did, but he did not say that 1/3 was last on the list because there is no last on the list.

 

[Mates]

That is exactly my point. You never get to the line numbered \(\displaystyle \aleph_0.\) The list goes on forever. You get to n, and then you have n + 1,
but n + 1 is still a natural number, not a transfinite number. So your algorithm will never get you to a decimal expansion of 1/3.

Then doesn't that mean that there is only a finite number of rows, when there is suppose to be an infinite number of rows for all natural numbers?

But wait you say. Did not Cantor find a way to put rationals into 1-to-1 correspondence with integers? Yes, he did, but he did not say that 1/3 was last on the list because there is no last on the list.

If the diagonal argument must leave out all nonterminating decimal numbers, then the argument seems to only be saying that a finite number of rows will never match an infinite number of columns. Is that all there is to this?

 

[JeffM]

Then doesn't that mean that there is only a finite number of rows, when there is suppose to be an infinite number of rows for all natural numbers?

Not at all. Write down a list of natural numbers increasing by 1 each time. Can you get to the end? No. Is one of them \(\displaystyle \aleph_0\)? No, because that is not a natural number. The way you are thinking your first row has 1 digit, the second has 2 digits, etc. Your algorithm never gets to an infinite number of digits because your algorithm never ends.

In Cantor's list, no algorithm is specified. We just assume that an infinite list of numbers each with an infinite number of digits exists. You can deny the assumption if you wish. In that case, Cantor's argument is irrelevant, but you also cannot talk about infinity at all and cannot deal with Zeno's paradox.

If the diagonal argument must leave out all nonterminating decimal numbers, then the argument seems to only be saying that a finite number of rows will never match an infinite number of columns. Is that all there is to this?

I did not say (and did not mean to imply) that it is impossible (given Cantor's assumption about the existence of transfinite numbers) for an infinite list of numbers with an infinite number of digits to include non-terminating decimals.

I said before that it greatly complicates the argument to worry about rational and irrational numbers.

The argument can proceed in two steps.

Imagine a list where (1) each row in the list contains an infinite string of symbols of two or more types (plus and minus signs will do), (2) each string in the list is unique (no double counting), (3) no string consists solely of one symbol, and (4) there is a unique row associated with each natural number. There are an infinite number of rows and an infinite number of columns. We have said nothing about what the symbols mean.

All that the diagonal argument itself proves is that this infinite list cannot contain all the possible infinite strings that can be constructed (assuming you can do such a thing).

Now the argument proceeds to numbers. Every real number greater than 0 and less than 1 can be written as an infinite string of digits. If you can put a list of such strings in 1-to-1 correspondence with the natural numbers, the list will not contain all possible such strings (from part 1 of the proof). Therefore there are more real numbers between 0 and 1 than there are natural numbers.

The proof says nothing about what numbers are in the list and what numbers are not in the list.

In a completely separate proof, Cantor showed that the rational numbers (including 1/3) can be put into 1-to-1 correspondence with the natural numbers. So all the irrational numbers cannot be put into 1-to-1 correspondence with the natural numbers. However, it is possible to construct a list consisting solely of irrational numbers that can be put into 1-to-1 correspondence with the natural numbers, e.g. \(\displaystyle \pi^n\). We can list all of the rational numbers or some of the irrational numbers, but not all rationals and all irrationals.

It is best (if you really want to understand Cantor) to accept for purposes of argument the existence of the transfinite and forget about imagining any process for generating such a list. The argument becomes very simple when you forget all about generating such a list and worrying about how to represent numbers.

 

[Mates]

Not at all. Write down a list of natural numbers increasing by 1 each time. Can you get to the end? No. Is one of them \(\displaystyle \aleph_0\)? No, because that is not a natural number. The way you are thinking your first row has 1 digit, the second has 2 digits, etc. Your algorithm never gets to an infinite number of digits because your algorithm never ends.

In Cantor's list, no algorithm is specified. We just assume that an infinite list of numbers each with an infinite number of digits exists. You can deny the assumption if you wish. In that case, Cantor's argument is irrelevant, but you also cannot talk about infinity at all and cannot deal with Zeno's paradox.



I did not say (and did not mean to imply) that it is impossible (given Cantor's assumption about the existence of transfinite numbers) for an infinite list of numbers with an infinite number of digits to include non-terminating decimals.

I said before that it greatly complicates the argument to worry about rational and irrational numbers.

The argument can proceed in two steps.

Imagine a list where (1) each row in the list contains an infinite string of symbols of two or more types (plus and minus signs will do), (2) each string in the list is unique (no double counting), (3) no string consists solely of one symbol, and (4) there is a unique row associated with each natural number. There are an infinite number of rows and an infinite number of columns. We have said nothing about what the symbols mean.

All that the diagonal argument itself proves is that this infinite list cannot contain all the possible infinite strings that can be constructed (assuming you can do such a thing).

Now the argument proceeds to numbers. Every real number greater than 0 and less than 1 can be written as an infinite string of digits. If you can put a list of such strings in 1-to-1 correspondence with the natural numbers, the list will not contain all possible such strings (from part 1 of the proof). Therefore there are more real numbers between 0 and 1 than there are natural numbers.

The proof says nothing about what numbers are in the list and what numbers are not in the list.

In a completely separate proof, Cantor showed that the rational numbers (including 1/3) can be put into 1-to-1 correspondence with the natural numbers. So all the irrational numbers cannot be put into 1-to-1 correspondence with the natural numbers. However, it is possible to construct a list consisting solely of irrational numbers that can be put into 1-to-1 correspondence with the natural numbers, e.g. \(\displaystyle \pi^n\). We can list all of the rational numbers or some of the irrational numbers, but not all rationals and all irrationals.

It is best (if you really want to understand Cantor) to accept for purposes of argument the existence of the transfinite and forget about imagining any process for generating such a list. The argument becomes very simple when you forget all about generating such a list and worrying about how to represent numbers.

This has helped me a lot. But because the diagonal argument does not work for matching N to all terminating and repeating decimal numbers combined, how does the argument show that there is not a function out there that can't match N to R.


So if we never found a way to match the naturals to the rationals, wouldn't the diagonal argument appear to rule out a match between them, the same way it does for the all R? In which case, the diagonal argument would be wrong because it is incomplete.

 

[JeffM]

This has helped me a lot. But because the diagonal argument does not work for matching N to all terminating and repeating decimal numbers combined, how does the argument show that there is not a function out there that can't match N to R.


So if we never found a way to match the naturals to the rationals, wouldn't the diagonal argument appear to rule out a match between them, the same way it does for the all R? In which case, the diagonal argument would be wrong because it is incomplete.

OK. Maybe we are closing in.

The diagonal argument works with any proposed list of infinite strings. You can state it as:

Assume that there are any number of lists of all reals (they could differ only in their order), but at least one such list. Choose any one of them. The diagonal argument will give us a real number not in the list. Therefore that list does not match to ALL the reals. Contradiction: because we assumed that the list did include all the reals. So the assumption that one or more lists of all the reals exists must be false. Therefore no list of all the reals exists.

Got that. Very simple. Very neat.

Now you go on to a clever subtlety. It took me a bit to figure it out.

Let's see whether that argument holds up for the rational numbers.

Assume that there are any number of lists of all rationals, but at least one. Choose any one of them. The diagonal argument will give us a real number not on that list. BUT WE DO NOT CARE. We never said that this list contained all the reals. You have to show that the diagonal argument applied to an arbitrary rational number results in a rational number. And that you cannot do because, in a completely different proof, Cantor showed that you can construct (given infinite time) a list of all rationals. So we do not get a contradiction.

 

[Mates]

OK. Maybe we are closing in.

The diagonal argument works with any proposed list of infinite strings. You can state it as:

Assume that there are any number of lists of all reals (they could differ only in their order), but at least one such list. Choose any one of them. The diagonal argument will give us a real number not in the list. Therefore that list does not match to ALL the reals. Contradiction: because we assumed that the list did include all the reals. So the assumption that one or more lists of all the reals exists must be false. Therefore no list of all the reals exists.

Got that. Very simple. Very neat.

Now you go on to a clever subtlety. It took me a bit to figure it out.

Let's see whether that argument holds up for the rational numbers.

Assume that there are any number of lists of all rationals, but at least one. Choose any one of them. The diagonal argument will give us a real number not on that list. BUT WE DO NOT CARE. We never said that this list contained all the reals. You have to show that the diagonal argument applied to an arbitrary rational number results in a rational number. And that you cannot do because, in a completely different proof, Cantor showed that you can construct (given infinite time) a list of all rationals. So we do not get a contradiction.

My concern is that if it incorrectly shows uncountability for repeating decimals when mixed in with all other reals, how can we trust that it is correctly demonstrating uncountability for the irrationals? How do we know that there is not some function N -> R that can be found like what was found for the rationals?

 

[JeffM]

My concern is that if it incorrectly shows uncountability for repeating decimals when mixed in with all other reals, how can we trust that it is correctly demonstrating uncountability for the irrationals? How do we know that there is not some function N -> R that can be found like what was found for the rationals?

I either do not understand you, or you do not understand me.

Why do you say that the diagonal argument shows the uncountability of repeating decimals? It does no such thing.

The diagonal argument shows that you can construct a countably infinite string that differs from any countably infinite string in a countably infinite list of such strings. It does not show that the number so constructed is a repeating decimal.

The point of Cantor's proof is that every real number in (0, 1) can be represented by an infinite string. So if you can construct such a string not in the list, that is a real number not in the list.

It is true that every rational number in (0, 1) can be represented by an infinite string. You are correct that you can construct a string not in that list. But unless that number is a rational number, you have not shown a contradiction. And by the method of construction, the constructed number cannot be a rational number because it is not repeating.

 

[Mates]

I either do not understand you, or you do not understand me.

Why do you say that the diagonal argument shows the uncountability of repeating decimals? It does no such thing.

The diagonal argument shows that you can construct a countably infinite string that differs from any countably infinite string in a countably infinite list of such strings. It does not show that the number so constructed is a repeating decimal.

The point of Cantor's proof is that every real number in (0, 1) can be represented by an infinite string. So if you can construct such a string not in the list, that is a real number not in the list.

It is true that every rational number in (0, 1) can be represented by an infinite string. You are correct that you can construct a string not in that list. But unless that number is a rational number, you have not shown a contradiction. And by the method of construction, the constructed number cannot be a rational number because it is not repeating.

Because, if any n will only "match" to a terminating decimal, doesn't this mean that we have left out all nonterminating numbers? In which case we must have left out all nonterminating decimal numbers, including all repeating decimal numbers.

 

[JeffM]

Because, if any n will only "match" to a terminating decimal, doesn't this mean that we have left out all nonterminating numbers? In which case we must have left out all nonterminating decimal numbers, including all repeating decimal numbers.

No one has said that n will match only to a "terminating decimal. In fact, in the logic of the diagonal argument, there is no such thing as a "terminating" decimals, only repeating decimals, which are rational numbers, and non-repeating decimals, which are irrational numbers. Every string has an infinite number of digits.

So \(\displaystyle \dfrac{1}{3} = 0. \bar 3\ and\ \dfrac{1}{2} = 0.5 \bar 0\ and\ \dfrac{1}{7} = 0. \bar 1 \bar4 \bar2 \bar 8 \bar 5 \bar 7.\)

 

[Mates]

No one has said that n will match only to a "terminating decimal. In fact, in the logic of the diagonal argument, there is no such thing as a "terminating" decimals, only repeating decimals, which are rational numbers, and non-repeating decimals, which are irrational numbers. Every string has an infinite number of digits.

So \(\displaystyle \dfrac{1}{3} = 0. \bar 3\ and\ \dfrac{1}{2} = 0.5 \bar 0\ and\ \dfrac{1}{7} = 0. \bar 1 \bar4 \bar2 \bar 8 \bar 5 \bar 7.\)

Okay, thanks, I think it has all sunk in now!