Georg Cantor's diagonal argument, what exactly does it prove? 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.
 A: 
"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.)
A: 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.
A: 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.
