2 Questions about Cantor's Diagonal Argument

[Mates]

I am trying to understand the significance of Cantor's diagonal argument. Here are 2 questions just to give an example of my confusion.

From what I understand so far about the diagonal argument, it finds a real number that cannot be listed in any nth row, as n (from the set of natural numbers) goes to infinity. It does this by listing real numbers and making a rule that its nth column cannot have a digit in the corresponding nth row. This produces a real number that cannot be listed using the countably infinite (aleph null) set of rows. It is said that the reason this number can be created and not listed is because the reals are a set that is even larger than the aleph null set.

If any of that is wrong please let me know.

Here are the parts that I do not understand. I do not understand why we can't just make the same argument using the rationals instead of reals.

Question 1: I know the rationals have a one-to-one correlation with the naturals and thus the same cardinality, wouldn't the diagonal argument work the same way that it does for the reals?

For example, since we can make 1/3 be the number not "listable" (by choosing not 3 in the diagonal direction after the decimal point) doesn't this mean that we falsely proved that the set of rationals is larger than the set of the naturals?

Question 2: Instead of listing all of the naturals to a list of reals, couldn't we just list every 2nd n or n^2 so that there are always more naturals left to correlate to any reals that can't be correlated in the original list?

I am really confused and curious how the diagonal argument handles questions like these.

 

[topsquark]

I am trying to understand the significance of Cantor's diagonal argument. Here are 2 questions just to give an example of my confusion.

From what I understand so far about the diagonal argument, it finds a real number that cannot be listed in any nth row, as n (from the set of natural numbers) goes to infinity. It does this by listing real numbers and making a rule that its nth column cannot have a digit in the corresponding nth row. This produces a real number that cannot be listed using the countably infinite (aleph null) set of rows. It is said that the reason this number can be created and not listed is because the reals are a set that is even larger than the aleph null set.

If any of that is wrong please let me know.

Here are the parts that I do not understand. I do not understand why we can't just make the same argument using the rationals instead of reals.

Question 1: I know the rationals have a one-to-one correlation with the naturals and thus the same cardinality, wouldn't the diagonal argument work the same way that it does for the reals?

For example, since we can make 1/3 be the number not "listable" (by choosing not 3 in the diagonal direction after the decimal point) doesn't this mean that we falsely proved that the set of rationals is larger than the set of the naturals?

Question 2: Instead of listing all of the naturals to a list of reals, couldn't we just list every 2nd n or n^2 so that there are always more naturals left to correlate to any reals that can't be correlated in the original list?

I am really confused and curious how the diagonal argument handles questions like these.

Question 1. Cantor's argument will not work for this. It is pretty much (so far as I know) designed to deal only with the cardinality of the reals.

Question 2. You could, but then you'd end up in a situation where you couldn't compare the cardinalities of the sets. In order to make the argument work you need to be able to pair all of the natural numbers with a real.

-Dan

 

[NotJeffM]

You do not seem to have the argument in perspective.

Yes, you can (CONCEPTUALLY) take the complete list of rational numbers and (CONCEPTUALLY) do the diagonalization procedure. You are perfectly right about that. Now we have conceptualized a number that is not in the list of rational numbers. So what? We already listed the rational numbers in a 1-1 correspondence with the natural numbers. You have merely created a number not in that list. Therefore, you have created an irrational number, maybe [imath]\sqrt[5]{\dfrac{7}{\pi^{\pi}}}[/imath].

It is important to realize that Cantor did not hypothesize a way to put the rationals and natural numbers into 1-1 correspondence. He specified conceptually how to do it.

The cleverness of Cantor’s diagonalization with respect to the real numbers is this. He assumes (for purposes of contradiction) that it is possible to list ALL the real numbers between 0 and 1 in a 1-1 correspondence with the natural numbers and then gives a conceptual procedure to construct a real number between 0 and 1 that is not in that list. Contradiction. Thus, there can be no such list.

EDIT: It is difficult for most of us (at least for me) to grasp Cantor’s work because we have no physical correlates to irrational numbers or infinite sets. We are dealing with a world created by the human imagination limited only by logic. I struggled with Cantor’s proof for days before I fully grasped it (if indeed I fully grasp it yet).

 

[NotJeffM]

As for your second question, you are making the assumption that your proper subsets of the natural numbers have fewer members than the natural numbers. You must demonstrate that is true. Cantor shows in another proof that it is not necessarily true for infinite subsets to have smaller cardinality than their parent sets. That is true of finite sets but not infinite sets. For example, it is fairly easy to put the subset of all even natural numbers into 1-1 correspondence with the set of natural numbers. For your suggestion to work, you would have to construct an infinite subset of natural numbers and show that it cannot be put into 1-1 correspondence with the natural numbers. Good luck.

By the way, these are intelligent questions about a weird branch of mathematics.

 

[JeffJo]

Question 1: I know the rationals have a one-to-one correlation with the naturals and thus the same cardinality, wouldn't the diagonal argument work the same way that it does for the reals?

For example, since we can make 1/3 be the number not "listable" (by choosing not 3 in the diagonal direction after the decimal point) doesn't this mean that we falsely proved that the set of rationals is larger than the set of the naturals?

Cantor's Diagonal Argument is almost always taught incorrectly. It is very close to correct, but includes several picky little differences that not only confuse students who first learn them, but can be considered to make it wrong. (Don't worry, the correct proof is right.)

As an example of one difference that really doesn't matter, it was not about real numbers. Cantor even wrote in the introduction "here is a proof of this proposition that doesn't rely on the properties of irrational numbers." What he actually used, were infinite-length strings. It still works, because the decimal representations of the real numbers are such strings. If you stop and think about what you were taught, it really only manipulates strings. There are two extra steps needed if you call them numbers.

Anyway, here is a rough outline of the actual proof. The symbology follows what is published in Wikipedia.

Part 1:

1. A Cantor String is an infinite-length sequence of the characters '0' and '1'. (You can think of these as the binary representations of real numbers in [0,1]).
2. Let T be the set of all Cantor Strings.
3. Let S be any subset of T that has the additional property that it can be listed s1, s2, s3, ..., sn, ... .
   1. Technically, an example has to be shown. So let sn be a string that is all 0s except a 1 in position n.
4. Create a new string, s, by taking the nth character of sn, for all n, and inverting it.
   1. This s is an infinite-length sequence of the characters '0' and '1', so it is a Cantor String in T.
   2. This s is not in S because it differs from each sn in at least one place.
5. This proves the lemma "If S is a set of Cantor Strings that can listed, then there is a Cantor String s that is not in S.

Note that this is a direct proof, not a proof-by-contradiction. Note also that it does not assume that S is, or is not, equal to T.

Part 2:

1. Suppose that the entire set T can be put into such a list.
2. By the lemma, there is a Cantor String s that is not in T.
3. By the definition of T, the Cantor String s is in T.
4. This contradiction disproves the assumption in step 1 here.
5. The entire set T cannot be put into such a list.

Note that the contradiction is not about the set, it is about the string s.

Now to address your question. If you try to do his with rational numbers, you cant prove that the diagonal you construct in Part 1, step 4 is also a rational number. SO step 4.1 fails.

Question 2: Instead of listing all of the naturals to a list of reals, couldn't we just list every 2nd n or n^2 so that there are always more naturals left to correlate to any reals that can't be correlated in the original list?

I am really confused and curious how the diagonal argument handles questions like these.

That is what is accomplished by using the correct, two-part proof. It doesn't matter what subset you use, you must find a string (or real) that is not in any list that can be made. So you can't make a list of all.

 

[Mates]

Question 1. Cantor's argument will not work for this. It is pretty much (so far as I know) designed to deal only with the cardinality of the reals.

This is where I am foggy. I don't understand why this type of proof cannot be used in other ways. I guess a way to find out what the difference is is to ask what if Cantor came out with his argument showing that the rationals had a larger cardinality than the naturals instead of the actual argument. I suppose there would be a peer review to explain why the argument fails.

Question 2. You could, but then you'd end up in a situation where you couldn't compare the cardinalities of the sets. In order to make the argument work you need to be able to pair all of the natural numbers with a real.

But let's pretend that I am a peer reviewing the proof and I make attempt to critique it with the argument in my second question. I wonder what the response would be.


I hope I am not putting you on the spot with all these questions. I don't know a better way to understand this.

 

[Mates]

You do not seem to have the argument in perspective.

Yes, you can (CONCEPTUALLY) take the complete list of rational numbers and (CONCEPTUALLY) do the diagonalization procedure. You are perfectly right about that. Now we have conceptualized a number that is not in the list of rational numbers. So what? We already listed the rational numbers in a 1-1 correspondence with the natural numbers. You have merely created a number not in that list. Therefore, you have created an irrational number, maybe [imath]\sqrt[5]{\dfrac{7}{\pi^{\pi}}}[/imath].

I was hoping to consider my example in the OP. The example created a rational number that the natural numbers would seemingly not be able to list, even though we know now that they should. Trying to figure out why the diagonal argument cannot be applied in certain ways is basically my way of trying to understand the diagonal argument in general. I am just trying to feel my way through the darkness.

The cleverness of Cantor’s diagonalization with respect to the real numbers is this. He assumes (for purposes of contradiction) that it is possible to list ALL the real numbers between 0 and 1 in a 1-1 correspondence with the natural numbers and then gives a conceptual procedure to construct a real number between 0 and 1 that is not in that list. Contradiction. Thus, there can be no such list.

EDIT: It is difficult for most of us (at least for me) to grasp Cantor’s work because we have no physical correlates to irrational numbers or infinite sets. We are dealing with a world created by the human imagination limited only by logic. I struggled with Cantor’s proof for days before I fully grasped it (if indeed I fully grasp it yet).

When I first learnt about the diagonal argument, it seemed quite clear, and I never really gave the DA a second thought. But a few years ago I started trying to understand more about infinity, set theory etc. Then the diagonal argument became less clear some how, lol. I guess I have misunderstood something somewhere along the way.

 

[pka]

From your OP, it seems to me as if you are just confused about countable and uncountable sets.
It is often put that a countable set is either finite or denumerable. The later meaning that the set can put into a one-to-one correspondence with the set of all infinite sequences of zeros and ones. Then any set is either countable or it is un-countable. Cantor's diagonal argument was developed to prove that certain sets are not countable, such as the set of all infinite sequences of zeros and ones.

 

[Mates]

As for your second question, you are making the assumption that your proper subsets of the natural numbers have fewer members than the natural numbers. You must demonstrate that is true. Cantor shows in another proof that it is not necessarily true for infinite subsets to have smaller cardinality than their parent sets. That is true of finite sets but not infinite sets. For example, it is fairly easy to put the subset of all even natural numbers into 1-1 correspondence with the set of natural numbers. For your suggestion to work, you would have to construct an infinite subset of natural numbers and show that it cannot be put into 1-1 correspondence with the natural numbers. Good luck.

I did not mean to make that assumption. I was only trying to understand the diagonal argument better by "testing" it in a different situation. I thought that I was trying to show that as n goes to infinity, there will always be more n left over to list to the unlistable number/s that the rules produce.

This of course should not work (unless I disproved the diagonal argument which is highly unlikey), but I don't know why it shouldn't.

By the way, these are intelligent questions about a weird branch of mathematics.

Thanks, I appreciate that. I have been fascinated with this topic for many years. But unfortunately I am only an armchair student, so my understanding is quite shaky.

 

[NotJeffM]

I was hoping to consider my example in the OP. The example created a rational number that the natural numbers would seemingly not be able to list, even though we know now that they should. Trying to figure out why the diagonal argument cannot be applied in certain ways is basically my way of trying to understand the diagonal argument in general. I am just trying to feel my way through the darkness.


When I first learnt about the diagonal argument, it seemed quite clear, and I never really gave the DA a second thought. But a few years ago I started trying to understand more about infinity, set theory etc. Then the diagonal argument became less clear some how, lol. I guess I have misunderstood something somewhere along the way.

You are making an assumption that is unwarranted.

You CAN DO the diagonalization procedure on the list of rational numbers. There is nothing to stop you. But then you are (incorrectly) assuming that the resulting number is rational. If it is rational, that contradicts your premise that all the rationals can be put into such a list. But your premise was not a hypothesis; it is a theorem. Therefore the number you constructed is not rational and contradicts nothing.

The point about the real numbers between 0 and 1 is that any number represented by 0. followed by an infinite number of digits is a real number. Ignore those ending with an infinite number of 9’s. Create a list, any list, that consists of unduplicated such numbers and that can be put into 1-1 correspondence with the whole numbers. That list may not be unique. But take any such list. Apply the diagonalization argument. You get a number that is not in the list but meets the definition of a real number. Therefore there is no way to list all the real numbers in (0, 1) in 1-1 correspondence to the natural numbers.

 

[Mates]

From your OP, it seems to me as if you are just confused about countable and uncountable sets.
It is often put that a countable set is either finite or denumerable. The later meaning that the set can put into a one-to-one correspondence with the set of all infinite sequences of zeros and ones. Then any set is either countable or it is un-countable. Cantor's diagonal argument was developed to prove that certain sets are not countable, such as the set of all infinite sequences of zeros and ones.

Maybe I am not reading your post correctly, but it seems as though you are saying that a countable set can be denumerable and that it can be "put into a one-to-one correspondence with the set of all infinite sequences of zeros and ones". And then you say that Cantor's argument showed the set of all infinite sequences of zeros and ones are not countable. Did you mean to put that, or did I misunderstand your post?

 

[Steven G]

From your OP, it seems to me as if you are just confused about countable and uncountable sets.
It is often put that a countable set is either finite or denumerable. The later meaning that the set can put into a one-to-one correspondence with the set of all infinite sequences of zeros and ones. Then any set is either countable or it is un-countable. Cantor's diagonal argument was developed to prove that certain sets are not countable, such as the set of all infinite sequences of zeros and ones.

Maybe I am not reading your post correctly, but it seems as though you are saying that a countable set can be denumerable and that it can be "put into a one-to-one correspondence with the set of all infinite sequences of zeros and ones". And then you say that Cantor's argument showed the set of all infinite sequences of zeros and ones are not countable. Did you mean to put that, or did I misunderstand your post?

Please try yourself to determine if pka is correct or not.

 

[Mates]

You are making an assumption that is unwarranted.

You CAN DO the diagonalization procedure on the list of rational numbers. There is nothing to stop you. But then you are (incorrectly) assuming that the resulting number is rational. If it is rational, that contradicts your premise that all the rationals can be put into such a list. But your premise was not a hypothesis; it is a theorem. Therefore the number you constructed is not rational and contradicts nothing.

I am still confused, so I will just ask about one part of your post first.

I don't understand why I can't construct the rational 1/3, that would be shown as 0.3 repeating. The rule would be "not 3" for every nth row intersecting with every nth column, in a diagonal pattern.

 

[Mates]

Please try yourself to determine if pka is correct or not.

Believe me, I looked at it many times before posting. I am trying hard.

 

[NotJeffM]

I am still confused, so I will just ask about one part of your post first.

I don't understand why I can't construct the rational 1/3, that would be shown as 0.3 repeating. The rule would be "not 3" for every nth row intersecting with every nth column, in a diagonal pattern.

I think I know where your confusion is coming from.

Let’s start with a demonstration (this is not a demonstration I created) that each distinct rational number can be matched to a distinct natural number. A rational number is defined as a/b, where a and b are integers and b is not zero. Any rational number can be expressed in lowest terms. That is, 1/3, 2/6, 3/9 can all be expressed as 1/3. So we are only considering rational numbers that are expressed in lowest form so that we have no duplicates. We associate the rational number 0 with the natural number 1. From this point on, we can assume a is not zero because zero in lowest terms is 0/1. We associate the rational number a/b if it is negative with the natural number [imath]2^{|a|} * 3^{|b|}[/imath]. We associate the rational number a/b if it is positive with the natural number [imath]5^{|a|} * 7^{|b|}[/imath]. So 1/3 will be associated with the number 1715. I hope you see that this procedure means that we can match each distinct rational number to a unique whole number.

(The demonstration above does not show 1-1 correspondence. For that we have to show as well that we can match each natural number to a distinct rational number, but that is trivial.)

OK. You now say that we can construct a list of all the rational numbers expressed in decimal form (avoiding decimal expansions ending with an infinite number of 9’s). We know that the number of items in that list is the number of whole numbers. We construct a new number that differs from the nth rational number in that list by the nth digit after the decimal point. By construction, that number differs from every number in the list. What can we conclude from the twin facts that the constructed number is not in the list but every rational number is in the list? We must have constructed an irrational number so of course it is not in the list. Diagonalization causes no problem.

Now notice the difference when we get to the real numbers. Every number that can be represented by 0. followed by an infinite string of digits is a real number. We have no procedure that shows how to put all of those into 1-1 correspondence with the natural numbers as we did with the rational numbers. We make an assumption that it can be done and that consequently a list can be made of all the real numbers in (0, 1). Now we use diagonalization to construct a real number that is not in the list. But the list was supposed to contain all real numbers. Contradiction. The assumption is false.

Diagonalization creates no issue with the rational numbers because the irrational numbers were never included in the list in the first place. But the irrationals provide no escape for the real numbers, which do include the irrationals.

 

[Mates]

I think I know where your confusion is coming from.

Let’s start with a demonstration (this is not a demonstration I created) that each distinct rational number can be matched to a distinct natural number. A rational number is defined as a/b, where a and b are integers and b is not zero. Any rational number can be expressed in lowest terms. That is, 1/3, 2/6, 3/9 can all be expressed as 1/3. So we are only considering rational numbers that are expressed in lowest form so that we have no duplicates. We associate the rational number 0 with the natural number 1. From this point on, we can assume a is not zero because zero in lowest terms is 0/1. We associate the rational number a/b if it is negative with the natural number [imath]2^{|a|} * 3^{|b|}[/imath]. We associate the rational number a/b if it is positive with the natural number [imath]5^{|a|} * 7^{|b|}[/imath]. So 1/3 will be associated with the number 1715. I hope you see that this procedure means that we can match each distinct rational number to a unique whole number.

(The demonstration above does not show 1-1 correspondence. For that we have to show as well that we can match each natural number to a distinct rational number, but that is trivial.)

OK. You now say that we can construct a list of all the rational numbers expressed in decimal form (avoiding decimal expansions ending with an infinite number of 9’s). We know that the number of items in that list is the number of whole numbers. We construct a new number that differs from the nth rational number in that list by the nth digit after the decimal point. By construction, that number differs from every number in the list. What can we conclude from the twin facts that the constructed number is not in the list but every rational number is in the list? We must have constructed an irrational number so of course it is not in the list. Diagonalization causes no problem.

I emboldened what I am replying to.

You are saying that we must have created a irrational number, but I still have to ask (I am sorry if you already answered it as I cannot find it) why can't we create a rational repeating number like 0.333...? The rule would be "not 3" at every nth decimal place. If we can do this, then it seems that we have used the same proof that Cantor used for the reals. Of course there must be a crucial difference.

One difference is that with Cantor's argument, any number (except repeating 9's of course) can be chosen. With my example, only a repeating nth decimal place, or finite sequences that repeat, can be used to create an unlistable number.

Now notice the difference when we get to the real numbers. Every number that can be represented by 0. followed by an infinite string of digits is a real number. We have no procedure that shows how to put all of those into 1-1 correspondence with the natural numbers as we did with the rational numbers. We make an assumption that it can be done and that consequently a list can be made of all the real numbers in (0, 1). Now we use diagonalization to construct a real number that is not in the list. But the list was supposed to contain all real numbers. Contradiction. The assumption is false.

Diagonalization creates no issue with the rational numbers because the irrational numbers were never included in the list in the first place. But the irrationals provide no escape for the real numbers, which do include the irrationals.

I understand what you are saying here, but I will see what your response is to the above.

 

[blamocur]

...why can't we create a rational repeating number like 0.333...? The rule would be "not 3" at every nth decimal place.

The above is rather confusing.

If you believe that you can prove non-countability of all rational numbers I suggest you post a detailed formal proof (i.e., modified Cantor's proof), then we'll have something concrete to discuss.

 

[NotJeffM]

I emboldened what I am replying to.

You are saying that we must have created a irrational number, but I still have to ask (I am sorry if you already answered it as I cannot find it) why can't we create a rational repeating number like 0.333...? The rule would be "not 3" at every nth decimal place. If we can do this, then it seems that we have used the same proof that Cantor used for the reals. Of course there must be a crucial difference.

One difference is that with Cantor's argument, any number (except repeating 9's of course) can be chosen. With my example, only a repeating nth decimal place, or finite sequences that repeat, can be used to create an unlistable number.[/QOUTE]

First, there is no need to “create“ the decimal representation of 1/3 to ADD to the list of the decimal representations of every rational number. It is ALREADY there one time by definition. With me on that?

Second, you are making diagonalization unnecessatily complex as well as missing the point. If, for example, 1/3‘s expansion is the 1715th expansion in the list, then our creation of our new number insets any digit except 3 or 9 as the 1715th digit to the right of the decimal point in the new number being constructed. Therefore, that number will not equal 1/3: it will not be all 3’s by construction. Of course, it could be identical to the expansion of 1/3 in every other digit up to that one, but it will not equal 1/3 because it differs by at least one digit.

Moreover, that number being constructed will not equal the first number in the list because the number being constructed will differ from the first number in the list by at least the first digit to the right of the decimal point. It will not equal the the second number in the list because it will differ from the second number by at least the second digit to the right of the decimal point. In short, the new number constructed cannot be in the list. This is true whether diagonalization is applied to the list of all rational numbers or the hypothetical list of all real numbers.

You seem to have persuaded yourself that we cannot apply the diagonalization process to the list of rational numbers. This is simply not true as I hope you now realize.

So, the answer to your fundamental question that you started out with (Why can’t we apply the diagonalization process to the list of the decimal expansion of all rational numbers) is that you CAN DO THAT, and you get the SAME IMMEDIATE RESULT, namely the specification of a real number that is not in the list.

It is the CONSEQUENCE of that immediate result that differs between rational and real numbers. There is no contradiction in finding a real number that is necessarily not in the list of all rationals; there are real numbers that are not rational numbers, namely the irrationals. There is a contradiction in finding a real number that necessarily is not in the purported list of all real numbers.

I doubt I can make the argument clearer so I hope I have succeeded this time.

[QOUTE]
I understand what you are saying here, but I will see what your response is to the above.

I tried.

 

[NotJeffM]

The above is rather confusing.

If you believe that you can prove non-countability of all rational numbers I suggest you post a detailed formal proof (i.e., modified Cantor's proof), then we'll have something concrete to discuss.

@blamocur I don’t think the OP is trying to dispute the denumerability of the rational numbers. He either thinks (wrongly) that you cannot apply the diagonalization process to the list of all rational numbers. Or else he thinks (very wrongly) that constructing a real number not in the list is just as fatal to the idea of a list of all rational numbers as it is to the idea of a list of all real numbers.

Not all students are boys is perfectly possible.

Not all students are students is obvious nonsense.

Another way to put it is that he does not seem to understand that the only point of diagonalization is to construct a real number not in the list.

Because I am something of a finitist, I sympathize with the OP’s struggling to comprehend Cantor; it does depend on a difference between real numbers and rational numbers. He is right about that.

 

[Mates]

The above is rather confusing.

If you believe that you can prove non-countability of all rational numbers I suggest you post a detailed formal proof (i.e., modified Cantor's proof), then we'll have something concrete to discuss.

I am absolutely under no illusion that I have proved anything. I brought this up because it means that I do not understand something about the Cantor's diagonal argument.

Here is what it looks like. Just remember that the rule is "not 3" for the "intersection" of the nth row to the nth column.