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.
Best Answer
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.)