Trouble with Understanding Cantor's Diagonal Argument

[Mates]

(This is not a homework question, but I still hope for some help so that I can understand these math concepts better for future math courses.)


I can't make sense of Cantor's Diagonal Argument as presented by some notes I found from Virginia Common Wealth University. I am far from a mathematician, but I have enough university calculus and linear algebra to understand what the notes are talking about.


Here are the notes that I will refer to, http://www.people.vcu.edu/~rhammack/BookOfProof/Cardinality.pdf from VCU.


On page 218, they use a function that shows a bijection between |N| and |Z|. However, there are probably some functions that would not work such as f(n) = n; this would leave out all of the negative numbers of course. I take this to mean that a function failing to show a bijection does not imply that a bijection does not exist.


Then on page 219, they use some function that fills the right column with what seems to be random real numbers, okay. They also state the rule that leaves out a real number called b.


Before I get into my main issue, why does there need to be this extravagant rule to get b; why not just make the requirement that f can't equal some number? And can't we just make the exact same kind of rule for matching |N| to |Z|? And it would still exhaust all n leaving out an element of |Z|.


Anyways, my main issue is that they only show one function that does not match every n to every f(n). To address this, on page 220 it says "since this argument applies to any function f: N -> R ..." where are they getting that from? I don't understand how they know this is true for any function.


Either I am missing something - and I feel that I must - or Cantor's Diagonal Argument is not a very convincing argument at all.

 

[pka]

I can't make sense of Cantor's Diagonal Argument as presented by some notes I found from Virginia Common Wealth University. I am far from a mathematician, but I have enough university calculus and linear algebra to understand what the notes are talking about.

Anyways, my main issue is that they only show one function that does not match every n to every f(n). To address this, on page 220 it says "since this argument applies to any function f: N -> R ..." where are they getting that from? I don't understand how they know this is true for any function.

Either I am missing something - and I feel that I must - or Cantor's Diagonal Argument is not a very convincing argument at all.

It is not an to much to say Cantor's Diagonal Argument gave us much of modern mathematics. But as you say there are hundreds of different ways to construct the arguments. But all are based on one beautifully simple idea. Suppose you have a set that you think is countable then you can list each of the set's elements. Using that list, if we can construct an element of the set which cannot be in the list then that would be a contradiction to the set being countable.
I tried to download that pdf three times. But each time it caused a freeze, the anti-virus did not like it. If one accepts the idea of excluded middle the agrument is sound.

 

[Mates]

It is not an to much to say Cantor's Diagonal Argument gave us much of modern mathematics. But as you say there are hundreds of different ways to construct the arguments. But all are based on one beautifully simple idea. Suppose you have a set that you think is countable then you can list each of the set's elements. Using that list, if we can construct an element of the set which cannot be in the list then that would be a contradiction to the set being countable.
I tried to download that pdf three times. But each time it caused a freeze, the anti-virus did not like it. If one accepts the idea of excluded middle the agrument is sound.

I am not quite there yet. I am still trying to understand the argument.


I watched this video www.youtube.com/watch?v=aYH37IIyqfs from UCDavis, and it led me to think of a new issue.


Like the notes I posted, the video also uses one assumed correspondence from each natural to each real. It seems like each of these examples just finds one function for n that does not give a correspondence to the reals. If I use the wrong function to correspond the naturals to the rationals, I can leave out a rational number just as easily.


For example,


Our rule will be anytime there is a 4 we will put a 5 in the excluded number x, and anytime there is a 5, the excluded number gets a 4.


1) 0.4
2) 0.45
3) 0.454
4) 0.4545
5) 0.45454
.
.
.
x = 0.54545 ...


So when we use all elements of |N|, x = 6/11.


We can exhaust all elements of |N| and leave out a rational number just like we did with the video's example using a real number. I really don't understand the difference between this argument and the examples in the notes and video.

 

[pka]

I am not quite there yet. I am still trying to understand the argument.
nce from each natural to each real. It seems like each of these examples just finds one function for n that does not give a correspondence to the reals. If I use the wrong function to correspond the naturals to the rationals, I can leave out a rational number just as easily.
We can exhaust all elements of |N| and leave out a rational number just like we did with the video's example using a real number. I really don't understand the difference between this argument and the examples in the notes and video.

Today I was able to download the pdf file. It is boilerplate material. In fact, I think it is good. I wish I had been able to see it yesterday.

As said there are multiple ways to construct a particular real number. But there is no unique way. For example: every real number is the limit of a sequence of rational numbers. While a particular real number is unique there are many sequences of rationals that converge to it.
The Cantor argument says that any time we think that we have a countable table of countable strings that exhausts the real numbers, it is possible to change the diagonal elements so as to get a new number not in that table. Thus it is not exhaustive.

If we have the collection of all bit-strings (sequences of only zeros & ones), that collection is not countable but represents all real numbers.

 

[Mates]

As said there are multiple ways to construct a particular real number. But there is no unique way. For example: every real number is the limit of a sequence of rational numbers. While a particular real number is unique there are many sequences of rationals that converge to it.
The Cantor argument says that any time we think that we have a countable table of countable strings that exhausts the real numbers, it is possible to change the diagonal elements so as to get a new number not in that table. Thus it is not exhaustive.

If we have the collection of all bit-strings (sequences of only zeros & ones), that collection is not countable but represents all real numbers.

I don't doubt that all of the reals is a larger infinity than all of the naturals. I just haven't yet understood how the argument in the notes, and in many other demonstrations of the diagonal argument, indicates that it is a larger infinity.


All I did was do what seems to be the exact same thing as in the notes, except with matching naturals to rationals. It gives the same result as with the reals.

 

[Mates]

If someone can just explain to me why this doesn't work, then I will probably understand Cantor's diagonal argument.


Same as Cantor's argument, except I will match the naturals to only rationals. The list will use only 1's and 0's between 0.1 and 0.111....


1 --> 0.1000 ...
2 --> 0.1100 ...
3 --> 0.0010 ...
4 --> 0.1010 ...
.
.
.


In the same way as Cantor's argument, we can always create a different rational number, but the rationals are suppose to be the same size of infinity as the naturals.


Using real numbers would appear to present the exact same demonstration.


1 --> 0.1000 ...
2 --> 0.1100 ...
3 --> 0.0010 ...
4 --> 0.1010 ...
.
.
.

 

[HallsofIvy]

All rational numbers, written in base 10, give either repeating or terminating decimals. The number you get by Cantor's method, choosing the nth digit to be different from the nth digit of the nth number will in general not have repeating or terminating decimals so is not a rational number.

 

[pka]

If someone can just explain to me why this doesn't work, then I will probably understand Cantor's diagonal argument. Same as Cantor's argument, except I will match the naturals to only rationals. The list will use only 1's and 0's between 0.1 and 0.111...

Here is a summery of the diagonal argument. We claim that a certain can be counted by labeling each of the members with a natural number. But then a new element of the original collect is constructed and shown to be none of the labeled objects. Therefore, we have a contradiction. In any countable labeling of the collection always leaves out at least one of of the collection we claim to have counted.

A sequence is a countable collection of elements.
Suppose that \(\displaystyle \bf{B}\) is the collection of all bit-sequences (sequences of zeros & and ones).
Claim: The set \(\displaystyle \bf{B}\) can be labeled as \(\displaystyle \bf{B}=\{\beta_n : n\in\mathbb{N}\}\).
Define \(\displaystyle \gamma_k=\begin{cases}0&: \beta_{k,k}=1 \\ 1 &: \beta_{k,k}=0\end{cases}\)

Do you have any doubt that \(\displaystyle \gamma\in \bf{B}~?\)
Do you have any doubt that \(\displaystyle \gamma\ne \beta_n,~\forall n~?\)

Did we count \(\displaystyle \gamma\) among the \(\displaystyle \beta_n~?\).
If not the the \(\displaystyle \beta_n\) do not lable the set \(\displaystyle \bf{B}\)!
Thus the set \(\displaystyle \bf{B}\) cannot be counted.

If you do not have difficulties with that proof, [then] post a problem using the diagonal argument.

 

[Mates]

All rational numbers, written in base 10, give either repeating or terminating decimals. The number you get by Cantor's method, choosing the nth digit to be different from the nth digit of the nth number will in general not have repeating or terminating decimals so is not a rational number.

But still, why can I show the exact same thing as Cantor's argument when trying to match the naturals to the rationals?

 

[pka]

But still, why can I show the exact same thing as Cantor's argument when trying to match the naturals to the rationals?

You say why can I show the exact same thing as Cantor's argument when trying to match the naturals to the rationals? Because the set of rationals is equivalent to the set of rationals. The set \(\displaystyle \mathfrak{J}=\{(m,n): m\in\mathbb{Z}^+~\&~ n\in\mathbb{Z}^+\}\).
Define \(\displaystyle \Phi :\mathfrak{J}\to \mathbb{Z}^+\cup\{0\}+\) as \(\displaystyle \Phi:~(m,n)\mapsto 2^m\cdot 3^n\).

[We] can prove that \(\displaystyle \Phi\) is injective so that proves that the non-negative rationals are indeed countable. If that is the case then it is trivial that the negative rationals are countable.

 

[Mates]

You say why can I show the exact same thing as Cantor's argument when trying to match the naturals to the rationals? Because the set of rationals is equivalent to the set of rationals. The set \(\displaystyle \mathfrak{J}=\{(m,n): m\in\mathbb{Z}^+~\&~ n\in\mathbb{Z}^+\}\).
Define \(\displaystyle \Phi :\mathfrak{J}\to \mathbb{Z}^+\cup\{0\}+\) as \(\displaystyle \Phi:~(m,n)\mapsto 2^m\cdot 3^n\).

[We] can prove that \(\displaystyle \Phi\) is injective so that proves that the non-negative rationals are indeed countable. If that is the case then it is trivial that the negative rationals are countable.

That wasn't the point of my post. The point of my post is to try to understand the significance of the diagonal argument.

 

[HallsofIvy]

But still, why can I show the exact same thing as Cantor's argument when trying to match the naturals to the rationals?

I answered that question in post #7:

All rational numbers, written in base 10, give either repeating or terminating decimals. The number you get by Cantor's method, choosing the nth digit to be different from the nth digit of the nth number will in general not have repeating or terminating decimals so is not a rational number.

 

[Mates]

I answered that question in post #7:

But that is because we made a rule that guarantees an unlisted number. We can do the exact same thing except with rationals.
Or ...?

 

[HallsofIvy]

No, we can't "do the same thing with rational numbers". All rational numbers, written as decimals, are either "terminating decimals" (such as 1/8= 0.125) or "repeating decimals" (such as 1/3= 0.33333....). Using the "Cantor method" of writing the rational numbers in a "list" then writing a new number by setting its first digit different from the first digit in the first number, the second digit different from the second digit in the second number, etc. fails because the resulting number is not, in general, a "terminating decimal" or a "repeating decimal".

 

[Mates]

Using the "Cantor method" of writing the rational numbers in a "list" then writing a new number by setting its first digit different from the first digit in the first number, the second digit different from the second digit in the second number, etc. fails because the resulting number is not, in general, a "terminating decimal" or a "repeating decimal".

Why couldn't it be a repeating number?

 

[HallsofIvy]

Why couldn't it be a repeating number?

I didn't say "it couldn't be"! The point is that you cannot be sure it is.

 

[Mates]

I didn't say "it couldn't be"! The point is that you cannot be sure it is.

Now why don't we just add to the rule so that only rational numbers are listed. Wouldn't we still leave out a rational while using the rest of the original rule? It would seem that I could always leave out a rational when matching to the naturals.

 

[HallsofIvy]

This is becoming very confusing! You say we "could always leave out a rational when matching to the naturals." Yes, we could but that is not the point. The original "Cantor's Diagonal Argument" was to show that the set of all real numbers is not "countable". It was an "indirect proof" or "proof by contradiction", starting by saying "suppose we could associate every real number with a natural number", which is the same as saying we can list all real numbers, the shows that this leads to a contradiction- we can construct a real number that is not on the list.

To try to prove the same for the set of rational numbers, we would do the same thing- start by assuming a list of all rational numbers. That is, we stipulate at the start that we have not "left out a rational".

Again, if we use Cantor's method to try to construct a rational number that is not on the list, it fails because we cannot prove that the resulting number is a rational number. Obviously, it is a "number" but it might be an irrational number. We do not arrive at a contradiction.

 

[Mates]

I didn't say "it couldn't be"! The point is that you cannot be sure it is.

(I should have responded to this post this way)


But if it is a rational number, then didn't we show that at least one rational number cannot be matched to the naturals?

 

[HallsofIvy]

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!)