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.

Re: posting links, it'd be perfectly fine in this context but I think posting a link requires a certain amount of reputation (greater than $1$). — , Mar 07 '17 at 17:52
Cantor's argument says that it is impossible to create an injective function $f:\mathbb R\to \mathbb N$ And if no such injection exists then the real numbers are uncountable. — Doug M, Mar 07 '17 at 17:59
I too am having trouble understanding your question... fundamentally you seem to be assuming that all infinite lists must be of the same "size", and this is precisely what Cantor's argument shows is false. Choose one element from each number on our list (along a diagonal) and add $1$, wrapping around to $0$ when the chosen digit is $9$. Our new number differs from every other number on our list by at least one digit, so it must not have been included. — Brevan Ellefsen, Mar 07 '17 at 17:59
Consider the list of real numbers $1,10^{-1},10^{-2},10^{-3},\cdots$. This list contains an infinite number of entries, but it misses 'most' real numbers (anything with the digit 2 won't show up, for instance). The point of the diagonal argument is that this issue can't be repaired: There's no way to construct a list of real numbers that doesn't miss some of them. — Semiclassical, Mar 07 '17 at 17:59
The basic thing you need to know to understand this reasoning is the definition of the natural numbers and the statement that this is a countable infinite set. What Cantors argument shows is that there are 'different' infinities with different so called cardinalities, where two sets are said to have the same cardinality if there is a bijection between this two sets. For two infinite sets of the same cardinality the cardinality does not change if you add a finite number of elements to one of them. — Thomas, Mar 07 '17 at 17:59
The diagonal argument is a proof by contradiction; it rests on the assumption that we can list all the real numbers, pairing them with natural numbers in such a way as to match each real to exactly one natural. Yet, assuming that we have done so, and that there are no more naturals to use up, we can still construct more reals not paired yet. Thus, our assumption was incorrect. — Rob, Mar 07 '17 at 18:01
@RobBland It's worth pointing out that it doesn't need to be an argument by contradiction. It constructively proves that for each list of reals, there's a real not on that list. — Noah Schweber, Mar 07 '17 at 19:58

score 3 · Answer 1 · 2017-03-07T21:03:05.920

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.

Damn, you guys sure are fast. I left my computer for a couple of minutes and I got answers pouring in. I didn't expect to read an answer to this before at least an hour. Thanks a lot! I do have questions though: — Kaktus, Mar 07 '17 at 19:28
I'm not sure what to think of this, that's where I'm confused.
Actually just one "question". I guess I'm asking what you think of my thought. — Kaktus, Mar 07 '17 at 19:30
@Kaktus, it's a proof by contradiction. You start by assuming that you have a list of all possible numbers. Then you specifically show how to construct a number that can't be on this list. This is a contradiction, which means the list can't actually contain all possible numbers. Proof by contradiction is a common technique in math. — , Mar 07 '17 at 19:40
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? 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. — Kaktus, Mar 07 '17 at 19:54
@Kaktus, see my updates at the bottom of my post. Too long to put in a comment box. — , Mar 07 '17 at 20:36
Really I thank you for all your elaborate answers, I just think I thought about this too much for today. All of my thoughts are just very confusing, but I think I do understand now how this concept works. I'm gonna try to answer and ask some more stuff about this tomorrow, just for today my brain is done.
A question I have: How much do you think do these theoretical mathematical concepts apply in the real world? In physics for example. One might argue that just because that's how infinity works in math doesn't mean it has to be how infinity works in reality if it exists — Kaktus, Mar 07 '17 at 20:59
@Kaktus, no problem! Yep, welcome to thinking about $\infty$. That's usually what happens when thinking about it too much. I'm not aware of any practical applications (as far as physics or biology or engineering, etc.) of the diagonal argument or of the concept of different sizes of $\infty$, but that doesn't mean there aren't any. It's not something I've ever looked too much into. — , Mar 07 '17 at 21:41
@Kaktus "Because if the list WAS infinite, what number could there possibly not be on there?" Again, that is simply not true. There are lots of infinite lists of things that are not complete - e.g. the list "$2, 4, 6, ...$" does not contain every natural number. And indeed Cantor proved that there can be no listing of reals which contains every real. There's no getting around this point; the thing you want to be true, isn't. — Noah Schweber, Mar 09 '17 at 19:16

Noah Schweber · Answer 2 · 2017-03-07T18:12:04.327

3

"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.)

edited Mar 07 '17 at 18:12

answered Mar 07 '17 at 18:04

Noah Schweber

245,398

Damn, you guys sure are fast. I left my computer for a couple of minutes and I got answers pouring in. I didn't expect to read an answer to this before at least an hour. Thanks a lot! I do have questions though: – Kaktus Mar 07 '17 at 19:26
I understand that it's kind of pointless to ask for the practical implications of this, since we can only do this in theory. But still: this is uh, how can I put this... I don't even know how to say it but I'll still try: let's say there actually WAS a list of ALL numbers, so an infinite list. On one hand, sure, you could do this diagonal-method to infinity, always changing the next digit of every row, to get a new number, but on the other hand on an infinite list containing all possible numbers, you couldn't possibly find a number that's not on that list.

Kaktus

Mar 07 '17 at 19:27

I'm not sure what to think of this, that's where I'm confused. – Kaktus Mar 07 '17 at 19:27

Actually just one "question". I guess I'm asking what you think of my thought. – Kaktus Mar 07 '17 at 19:28

@Kaktus The conclusion of Cantor's argument is that there can't be such a list. Think about the irrationality of $\sqrt{2}$: the response to "but what if we consider a pair of integers $a, b$ with $a^2=2b^2$?" is "we know there aren't any." – Noah Schweber Mar 07 '17 at 19:30

Okay maybe I put it wrong, here's what I mean:

Theoretically, there is no reason why you couldn't have an infinite list of all integers, other than that we can't practically do or imagine it. If you had a list with infinitely many integers that each contain infinitely many digits, you simply couldn't find any integer that's not on that list. Is this impossible too? If so, please try to explain some other way because I'm not that deeply into math. Thanks for the answers!

– Kaktus Mar 07 '17 at 19:43

@Kaktus "If you had a list with infinitely many integers that each contain infinitely many digits" Integers don't contain infinitely many digits. Maybe you mean real numbers? In that case the sentence "Theoretically, there is no reason why you couldn't have an infinite list of all [real numbers]" is wrong: Cantor's proof is such a reason. Just because you can imagine a thing without any obvious obstacles to its existing, doesn't mean it actually can exist. – Noah Schweber Mar 07 '17 at 19:56

No I actually meant integers but I still worded it wrong, thinking about this stuff is very confusing at times. I'll put it differently:

5492121564921... to infinity 9635734265832... to infinity 3684576329563... to infinity 6053242365803... to infinity And here downwards it continues to infinity too.

And let's assume the list above is not random but in order. I just did it that way for simplicity. The diagonal string of digits would then also be infinite, yet on this infinite list of numbers, there couldn't be any number that's not on that list.

– Kaktus Mar 07 '17 at 20:41

It seems as though this "diagonal argument" only works if you imagine infinity as somehow finite, or as an "infinitely growing number". But I mean suppose you HAD an infinite list, infinite in both the number of numbers and in the digits of those numbers. And that list was in order. I understand that through that diagonal string you would always get a number that's not on the list, but then again whatever number you can name would somewhere come up on that list... but of course the diagonal string of digits would be infinite, so you couldn't name it... dude that is so confusing. – Kaktus Mar 07 '17 at 20:41

I think I need to think about this a bit more. – Kaktus Mar 07 '17 at 20:41

@Kaktus "And that list was in order." You can't even list the rationals in order! – Noah Schweber Mar 09 '17 at 19:17

score 0 · Answer 3 · answered Mar 07 '17 at 18:34

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.

Bram28 · Answer 4 · 2017-03-08T16:39:42.733

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.

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

4 Answers4