The point is that no such listing works. For any list you give me, you will have to leave out some real number.
If they could be listed, then give me a list, any list, I dare you. I bet you I could find a real number you didn’t fit in.
Sorry, I was too quick to post but too slow to edit.
What I meant was that one of your assumptions is you’ve already used up all the integers in your list. By showing that there are still decimals left over, you prove that real numbers can’t be put in one-to-one correspondence with the integers.
I think I understand the proof now (but not the version that’s in set theoretic terms with 18 variations of k, kth, n, and nth (MY BRAIN HURTS JUST TRYING TO KEEP THE TERMS STRAIGHT; I understand that proofs are written that way because they have to apply to all numbers, but they are quite difficult to grasp with such abstract references to numbers)).
The assumption I was overlooking is that the list on the left side (integers) HAS ALREADY BEEN EXHAUSTED. Therefore, there’s no way for me to “pair” an integer further down the list with any diagonal, becaues there are no integers left to pair the diagonal with.
Kudos
A similar argument to what’s been presented shows that the set of all sets of integers is strictly larger than the set of integers. That can be generalized to show that for any set S, the set of all subsets of S is strictly larger than S. Therefore, there is no largest set.
The thing is proposing what seems to be a paradox. If I list off every single possible combination of numbers there is and put it in a box, I can always create a new combination using his method that won’t be a member of any of the items in the box.
Yes, although actually, a second collection of integers won’t suffice (don’t worry, this isn’t obvious from the diagonal proof. It’s a further fact: since you can line up “one well of integers” with “two wells of integers” [e.g., consider splitting the integers into the evens and the odds], anything you can list with two wells of integers you can list with just one well of integers). You need a much larger infinite well to cover the reals. For example… the well of real numbers. 
Yes, the diagonalization proof, done properly, generalizes very far.
Let K be some particular “kind” of object (e.g., it could be “integers” or “reals” or “humans”). Let’s say a K-predicate is a function that takes in things of type K and returns a truth value (e.g., “Yes” or “No”) as an answer. (For example, “is even” is an integer-predicate, “is between 1/2 and 9/7” is a real-predicate, “is a United States citizen” is a human-predicate, etc.).
Suppose someone gives you a function F that takes in things of type K as inputs and returns K-predicates as outputs. We’ll prove that there’s some K-predicate not in the range of F.
Define the K-predicate FDiagonal which, when given x as an input, returns the answer “The opposite of whatever F(x) says about x”. FDiagonal can’t be in the range of F. Why not? Well, by definition, for every x, FDiagonal says about x the opposite of whatever F(x) says about x; thus, FDiagonal can’t be the same as any F(x).
Thus, since there can be no function from Ks to K-predicates which hits all of the latter, we can conclude that the number of K-predicates is not equal to the number of Ks.
There is, however, a function from Ks to K-predicates which, while it doesn’t hit all of the latter, at least sends distincts inputs to distinct outputs. For example, consider the function which sends the input x to the output predicate “is equal to x”. Because we can do this sort of thing, we say that there are at least as many K-predicates as there are things of type K.
Putting the results of the last two paragraphs together, we can conclude that there are more K-predicates than things of type K. In particular, there are more real-predicates than real numbers. (And more human-predicates than humans, more pizza topping-predicates than pizza toppings, etc.)
(I’m sure that explanation was difficult to follow, so, uh, let me know which parts are confusing, and I’ll try to clarify them) [I’m pretty sure I should have chosen more evocative names than “K” and “F”…]
That makes sense, because (what little I remember from set theory) the empty set is always a subset of any set. So the set of all subsets of integers would include the set of all integers AND the empty set, making this set larger than the set of all integers.
No; the thing is saying if you have a function from integers to real numbers, then there is a real number not in its range.
You can still put all the real numbers in a box. That box’s contents just won’t be the range of any function on the domain of the integers.
Well, your reasoning shows that the obvious mapping from integers into sets of integers doesn’t hit all of the latter. But it doesn’t show that some other, more devious correspondence couldn’t be constructed between the two. That’s what you need the diagonalization argument for.
Incidentally, I think the diagonalization argument is best put in the following form, without discussion of lists or sets or what have you, just functions:
Suppose you have some function F : (A, A) -> B [i.e., F takes in two things of type A as inputs and produces a thing of type B as output] with the property that every function of type A -> B is equal to F with its first argument held fixed to some value. Then every function of type B -> B, has a fixed point [i.e., sends some input to itself].
Proof: Let arbitrary N : B -> B be given, and define NewFunc : A -> B by NewFunc(x) = N(F(x, x)). We know that there is some k such that NewFunc is the same as F with its first argument held fixed to k. But then, we can conclude, F(k, k) = NewFunc(k) = N(F(k, k)); thus, N has a fixed point.
Corollary: If some function of type B -> B is known to lack a fixed point, then there can be no F : (A, A) -> B such that every function of type A -> B is in F’s “range”.
This shows us how to find some value which is equal to its image under N (or leverage the nonexistence of such to prove further impossibilities); it is interesting to note that the argument goes through just as well for an arbitrary relation instead of equality, as long as the substitution is made in all the appropriate places.
Reflecting on just what little structure is needed to carry out this general argument, we can suitably formalize it as a theorem about “categories with finite products” and immediately interpret it in a very wide variety of settings; the most familiar one, of course, is in the category of sets, where we get Cantor’s Theorem (no set surjects its powerset). However, in other categories, this theorem becomes the existence of Curry’s fixed point combinator in the lambda calculus, Turing’s proof of the undecidability of the Halting Problem, Tarski’s Indefinability Theorem, Goedel’s First Incompleteness Theorem (and Rosser’s sharpening of it), Kleene’s recursion theorem, and much more.
Of course, that level of abstraction is far too much to expect FrustratedIdiot to fully handle just yet, but it really is fascinating how all these disparate results do not merely share certain resemblances in proof, but, in fact, actually are just the same theorem, applied in different contexts.
I’ve been math-challenged for a while (try taking 8 am Latin and 3 pm Calculus in the same year as first-semester Haskell, a language that shall live in infamy even if it did teach me recursion by etching it onto my retinas. I think I have a mental block now) but as I understand it…
Infinite is infinite, but when you start defining a set of numbers or marbles or people there is something not included. You can have an infinite number of Americans, but that infinity is smaller than an infinite number of humans because, by its nature, any set of anything is at least partly defined by what it is not. Humans are not army ants, so the set of humans, however infinite, does not include them. The set of all Earth life that could be, however, does, and it is a larger infinite than any of the sets below it. But all matter that could be on Earth is bigger than that, and all matter in the solar system that could be is bigger than that…
There is no expansion that can take in everything, because there IS infinity. By the very nature of infinity, it encompasses infinite infinities inside it. It can’t be complete or it wouldn’t be infinity.
Does that describe this?
Sorry, not quite. As far as I can tell, you are just pointing out that some infinite collections do not contain some things, and then jumping (unsupportedly, in my eyes) to the conclusion “every infinite collection lacks something, and is thus a proper subset of another one”. Basically, you are simply talking about the relations of subset and superset.
The OP is about a much coarser notion of size and a much less immediate fact: not only do some infinite collections contain different elements, but, furthermore, there is no way to “line up” the one with the other or even come close (that is, for suitable infinite collections A and B, no function from A to B, no matter how devious its definition, will actually hit everything in B).
It actually isn’t really directly about infinities, though; that just happens to be one of the more surprising aspects of its application. It’s really about function-spaces and surjections.
(Incidentally, I used a very small amount of Haskell notation in my last post (mixed with a small amount of ML notation, I suppose). I… apologize. :))
What are you smoking and where can I get some?
Oh, okay. I liked mine better, it was more fun. I think I ran into this in a programming class when poking around with sets.
And yes, I had flashbacks.
I’m high on an English degree. Well, I do have some cake here. 
Imagining infinities gives me the sort of mind-expanding headache I have only previously experienced upon entering my dorm room after my roommate and her friend were trying to see if they could hotbox an entire room.
Just because one set is a proper subset of another, doesn’t mean that the sets are different sizes. The even integers are a proper subset of the integers, but those two sets have exactly the same size.
Hmm, slightly related, but I’ve seen an alternative abstraction of diagonalization (I think due to Quine) outlined in “Introduction to Mathematical Logic” by Kleene. I can’t quite remember the statement. Do you know it?
(It had something to do with “resolving” paradoxes. Inputting “2” to a certain function made a diagonalization argument drop out. Perhaps unhelpfully vague, and a Google search turns up nothing.)
Sorry; I can’t think of what it is, but now you’ve got me curious. (Alas, flipping through my copy of Kleene’s earlier “Introduction to Metamathematics” didn’t seem to resolve this curiosity… Perhaps if you could remember some more details? What kind of function was it that “2” was input to?)
The way I prefer to “visualize” what we are talking about is to imagine counting the real numbers as counting the points in a line. You take your pen, find a point and mark it with a number, then find the next point, and so on. Obviously you will need to make an infinite number of marks. But it turns out that even if you do that, and every integer has been written onto the line, there are still points between your marks that you didn’t get.
On the other hand, if you’re counting only the rational numbers, it turns out that it’s possible (if you mark them in the correct order) not to miss any. When every integer has been written onto the line, there will not be any rational numbers between them.
WF Tomba. That is a consequence of Cantor’s proof. It is not a proof in itself. E.g., maybe someone cleverer (more clever?) can come along and find a way to mark all the reals. Cantor says no.
There are several “hidden diagonalization” proofs that I like to give in teaching Computer Science. E.g., it’s very easy to prove there can never be a perfect malware detector program. But these require knowledge of how computer programs work and can be modified.
I think similar proofs of the uncountability of the reals (or a related concept) might exist but no one has thought of them yet.