Georg Cantor's diagonal argument, what exactly does it prove?

Question

I'm having this discussion with some friends, and it seems we all don't really understand this topic. Now, I understand that Cantor's diagonal argument is supposed to prove that there are "bigger infinities" than others. Now, honestly, I only think that there is something I must not understand here. I don't really know what it is here, but here I watched a video on YouTube by Numberphile titled "Infinity is bigger than you think". I'd post the link but I'm not sure I'm allowed to in this forum.

ANYWAY, here I'll try to describe what I don't understand: it seems to me that the argument goes "no matter what your list is, with this method I can write a number that is not on that list". But then again, at the same time, the entire topic is about infinite lists. If you had an infinite list of numbers, it would clearly contain every number, right? I mean, if you had a list that was truly INFINITE, then you simply couldn't find a number that is not on the list! For example:

. . . 0.12345 0.12346 0.12347 0.12348 0.12349 . . .

The first thing i already don't understand is this: do you have to add a digit to every number on the list for every number that you add to the list? Because I mean, if I had 6 numbers on the list above instead of five, how could you possibly exectute this diagonal-method thing when there are only five digits after the 0.? And the second thing I don't understand: if you had a truly INFINITE list, how could you find a number that is not on that list? It seems to me that this only works with finite lists, doesn't it? Because a truly infinite list would contain all numbers. The guy in the video claims that you could always make another number that's not on that list, but on an infinite list, what number could there possibly be that doesn't show up on the list?

Guys, I am not even really sure what it is that I don't understand, I just think that I must not be understanding something. If you can somehow see what my thinking error is, please let me know. And try to answer my questions. Thanks a bunch.

Answer 1

For your specific questions:

Georg Cantor's diagonal argument, what exactly does it prove?

(This is the question in the title as of the time I write this.) It proves that the set of real numbers is strictly larger than the set of positive integers. In other words, there are more real numbers than there are positive integers. (There are various other equivalent ways of stating it but that's the way I prefer and have most often seen.) One might think "well, obviously that's the case" but nothing is really that obvious when dealing with infinity. For example, the set of positive integers $\{1, 2, 3, 4, 5, \dots\}$ and the set of positive, even integers $\{2, 4, 6, 8, 10, \dots\}$ have exactly the same size, even though one might intuitively expect the latter to be exactly half the size of the former. (To show why these have the same size is relatively straightforward but too much of a deviation from your main question IMO.)

do you have to add a digit to every number on the list for every number that you add to the list? Because I mean, if I had 6 numbers on the list above instead of five, how could you possibly exectute this diagonal-method thing when there are only five digits after the 0.?

Yes, this is necessary in order for the proof to work. Of course in practice we can't continue this process forever, but the idea of the proof is that we can indefinitely do this in theory. And this is legitimate because the list is supposed to be a list of real numbers. The set of real numbers contains infinitely many numbers whose decimal expansions continue indefinitely, such as rational numbers like $1/11 = 0.09090909...$ and irrational numbers like $\sqrt{2} = 1.41421536...$. So there is certainly no shortage of numbers like this to include in your list (because there are infinitely many such numbers).

And the second thing I don't understand: if you had a truly INFINITE list, how could you find a number that is not on that list? It seems to me that this only works with finite lists, doesn't it? Because a truly infinite list would contain all numbers. The guy in the video claims that you could always make another number that's not on that list, but on an infinite list, what number could there possibly be that doesn't show up on the list?

You seem to think that "infinite list" is the same thing as "list containing everything possible" but this is not true. It's entirely possible to have an infinite list of numbers that does not contain every possible number.

To more easily understand this, consider the positive integers:

$$ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, \dots$$

I think we can agree that this list is infinite, because there are infinitely many positive integers. (To find the next integer, just add $1$ to the current integer.)

Now, what about positive, even integers? That list would look like this:

$$ 2, 4, 6, 8, 10, 12, \dots $$

I think we can also agree that this list is infinite, because there are infinitely many positive, even integers. (To find the next even integer, just add $2$ to the current integer.)

So, the second list is an infinite list of positive integers (specifically, the even ones) but it does not contain all of the positive integers.

---

Similarly, in Cantor's diagonal argument the point is to construct an infinite list of real numbers, where each real number is "labeled" with $1, 2, 3, 4, 5, \dots$. That is, you pair up each real number with a positive integer in an attempt to show that there are what's called a "countable" or "countably infinite" amount of real numbers. (Infinite sets whose sizes are equal to the size of the positive integers are called countable because we can essentially "count" the elements of the set by pairing each element in the set with exactly one positive integer.) But then the diagonal argument shows how to construct a number that can't possibly be on the list. Therefore the list can't possibly contain every real number (which, again, doesn't contradict the fact that the list is infinite), which means the amount of real numbers is greater than the amount of positive integers.

---

Re: your comment

But then again, the only way you could create a number that's not on the list is if the list isn't truly infinite. Isn't that true? Because if the list WAS infinite, what number could there possibly not be on there?

No. The diagonal argument explicitly shows you which number can't be on the list. "Infinite list of numbers" and "contains all possible numbers" are not the same thing but you seem to still be thinking they are. See my positive integer vs. positive, even integer example in my original post above. Did you perhaps understand that but you're just not convinced how that logic extends to real numbers in general and not just integers? Here's another example with more general numbers.

Consider the set of all real numbers whose first digit after the decimal is $1.$ This list contains numbers such as the following: \begin{align*} -&9.148754829...\\ &0.1326544685...\\ &12.1389749827429857...\\ &0.1111111111...\\ &31.123123123123...\\ &0.1487648348999... \end{align*} Now suppose we remove from this list all numbers that are strictly larger than $1$ or less than $0$. Then our new list would actually be a subset of the old list. And the first, third, and fifth numbers I listed above would not be on this list. Do you agree that we are removing an infinite number of numbers from the list? We are. But do you really think that the new list is finite? It isn't, because even between $0$ and $1$ there are infinitely many different numbers whose first decimal digit is $1$. \begin{align*} &0.1326544685...\\ &0.1111111111...\\ &0.1487648348999...\\ &0.1\\ &0.197865413897...\\ &0.125 \end{align*} This is an infinite list of real numbers that doesn't contain every real number. It doesn't even contain every real number whose first decimal digit is $1$, but it's still an infinite list.

On an infinite list of numbers with infinitely many digits, this argument could uh... well,I guess it could never be done. The diagonal line of digits would continue to infinity, yet could never make a number that is not on that list. I get so confused thinking about these infinite lists, but do you get what I mean? It seems that this argument depends on the list ending somehow.

This train of thought is actually at the center of why some people reject Cantor's argument but the mathematical community by and large accepts it. It actually doesn't depend on the list ending, because not all real numbers have decimal expansions that end.

The fact that the argument or process can never be finished doesn't make it invalid or incorrect. By that same token, one could say that there aren't infinitely many integers because we can't write all of them down. Would you agree with that statement? Personally I wouldn't, because we can still describe the set of all integers and exhibit a pattern that tells us how to find the "next" integer. And it's common knowledge that to find the "next" (as in, next one to the right on the number line) integer we just add $1$ to the "current" integer. But some people reject this notion on the grounds that this is not a finite process. This is something I've only recently learned about - on this site, actually. It's called ultrafinitism.

Answer 2

"If you had an infinite list of numbers, it would clearly contain every number, right? . . . Because a truly infinite list would contain all numbers."

Certainly not.

For instance, the list "$2, 4, 6, 8, ...$" doesn't even contain every natural number! (Note that we are indeed talking about infinite lists here.)

---

So that's the mistake you're making; now, why is Cantor's claim true?

You ask how we can produce a number not on a given infinite list; well, this is what Cantor does! For simplicity, let's look at real numbers in $[0, 1]$ in base $2$, and temporarily ignore the fact that some reals like $0.0111111...=0.1000000...$ have multiple binary expansions (this is easily fixed later on, but makes things harder to understand at the beginning).

Now suppose I have a list of these reals - that is, a sequence $r_i$ (for $i\in\mathbb{N}$) where each $r_i$ is some real in $[0, 1]$. To help visualize this, let's write them in an array. For instance, maybe they look like

• $0.01101000...$

• $0.10101100...$

• $0.11111111...$

• $0.01100001...$

I want to build a real number $s$ in $[0, 1]$ that I know isn't on this list. This means I have a bunch of requirements to meet: I need $s\in [0, 1]$, and I need $$s\not=r_1,\quad s\not=r_2, \quad s\not=r_3, \quad. . ..$$

The idea is that I'll define my real number so that each binary digit takes care of some requirement.

First, to make $s=[0, 1]$, let's begin with "$0.----$". There, that was easy. Now what about the other requirements?

I'm going to rewrite our array above, but with certain digits suggestively highlighted:

• $0.{\color{red} 0}1101000...$

• $0.1{\color{red} 0}101100...$

• $0.11{\color{red} 1}11111...$

• $0.011{\color{red} 0}0001...$

And remember that two real numbers are different if their binary expansions are ever different. (As remarked above, this isn't quite true on the nose, but ignore it for now; it's easy to fix after you get the general idea.) So e.g. to make sure $s\not=r_1$ I just need $s$ and $r_1$ to have one different digit, and so forth.

So here's how we do that:

• Take all the red digits and put them together - this is the diagonal sequence. In this case it's {\color{red} $0010...$}. The $n$th number of the diagonal sequence is the $n$th digit of the $n$th real on our list (check this!)

• Reverse them! Change each $0$ to a $1$, and each $1$ to a $0$. This is the antidiagonal sequence, and in our case is $1101...$

• Put a "$0.$" in front of the antidiagonal sequence to get a real in $[0, 1]$ (here, "$0.1101...$"); this is our $s$.

Now clearly $s\in [0, 1]$ so it's enough to check that $s$ isn't on our list.

• $s\not=r_1$, since $s$ and $r_1$ differ on the first binary digit: $s$ has a $1$ but $r_1$ has a $0$.

• $s\not=r_2$, since $s$ and $r_2$ differ on the second binary digit: $s$ has a $1$ but $r_1$ has a $0$.

• In general, $s\not=r_n$ for any $n$, since $s$ and $r_n$ will always have different $n$th binary digits.

So $s$ isn't on the list! And what we've shown, in fact, is that no list contains every real number.

(Except for that small detail about reals having two different binary expansions. You can try to fix this as an exercise on your own, or look at a full treatment of the proof in a textbook or online.)

Answer 3

Imagine you were waiting in a line of people of countable length. The nice thing about this is that even though this line is infinite, it is still countable, meaning there exists an integer $n$ such that there are only $n$ people in front of you so although $n$ may be a very large integer, you're guaranteed to be waiting in line for a finite amount of time.

In the context of computer programming, this means if I have an algorithm that I want to run on a countable set, there exists a way I can perform a function/operation on all the elements in a such a way that for each element $s$, the program will perform said operation on $s$ at some point during the program's runtime.

As for uncountable sets, they are so "big" that you can't even list them. As a thought experiment, try to think of a way that you could list or order the real numbers such that every number would be "attended to" in a finite amount of time. One initial attempt might be to first go through the numbers that have $1$ digit in its decimal representation. Then go through all the numbers that have $2$ digits in its digital representation, and so on and so forth. Each of these sets (the set of real numbers with $n$ digits in its representation) is finite, so it seems that we can use this method to generate all the real numbers in a way that for every real number $r$, our algorithm reaches $r$ in a finite amount of time. However, this breaks down for numbers with infinite decimal representations such as $1/3 = 0.3333\dots$. No matter how long we run our algorithm, it'll never reach $1/3$, there will always be an infinite number of "ahead" of it "in line"

Cantor's diagonalization argument proves the real numbers are not countable, so no matter how hard we try to arrange the real numbers into a list, it can't be done. This also means that it is impossible for a computer program to loop over all the real numbers; any attempt will cause certain numbers to never be reached by the program.

Answer 4

You seem stuck on the following thought: If you have an infinite list of numbers ... what number could possibly be missing?

Well, here is an infinite list of numbers:

2,4,6,8,...

This is of course the beginning of an infinite list of even numbers. Now, are there numbers not on the list? Of course! 1,3,5,... are all not on the list.

So this is an immediate counterexample to the idea that if you have infinitely many numbers, you somehow must have all of them. In fact, this example involves the natural numbers, which are clearly countable: there is a 'first' number (1), a 'second' (2), etc. And yet, waht the example above demonstrates is that:

You can have an infinite list of natural numbers without all of the infinite natural numbers being on it!

Now, of course, the natural numbers are 'listable':

1 2 3 4 ...

So why can't we list the real numbers?

For example, you consider:

. . . 0.12345 0.12346 0.12347 0.12348 0.12349 . . .

Isn't this a list? No.

First a technical point: the list can be infinite, but we typically require it has a beginning. OK. Fine, let's just list the real numbers between 0 and 1, so we have an obvious beginning (and even an end!):

0 0.00001 0.00002 ... 1

Isn't that a list of all numbers between 0 and 1? No. The number 0.000000001 isn't on there.

OK, fine, just 'fill in' the missing numbers:

0 ... 0.00001 ... 0.00002 ... 1

Isn't that a list? No! And this is a very important to understand:

The important thing of a list is that for each entry we can say at exactly which spot (1st? 2nd? 17th?) it is going to be (basically, what its 'index' is), so that we can associate a natural number with that entry, and thus define the surjection from the natural numbers to the set of objects listed, thus proving that that set of objects is enumerable.

So: what is the 'index' of 0.00001? It's not the first entry on the list, and nor is it the second ... but which is it? And the thing is .. because there are infinitely numbers between 0 and 0.00001, 0.00001 ends up having no index whatsoever ... so this is not a list. You are not allowed to have these ....'s in the middle of the list.

OK, then how about this:

0 1 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 0.01 0.02 0.03 ...

So in this listing of real numbers from 0 to 1, we first list all the real numbers with 0 digits after the decimal point, then all the ones with 1 digit after the decimal point, then all the ones with 2, etc. So, there are no ...'s in the middle of this list. So, isn't this a listing of all real numbers from 0 to 1?

No, because $\frac{1}{3} = 0.33333...$ will never make an appearance on this list: the way I defined this list, every entry in this list will have a finite number of digits after the decimal point.

OK, so what should we try now? Well, maybe you can try some other things, but I hope that at this point I have made it clear to you that is is at least really difficult to create a list of all real numbers. And what Cantor's diagonalization argument shows, is that it is in fact impossible to do so.