I’m looking for a good explanation of Cantor’s diagonal proof, but most of the sites I’ve seen use set theory notation, which is REALLY HARD TO FOLLOW. Is there any site with a better explanation of it?
The whole point of the argument is that a supposedly complete enumeration of a set cannot possibly be complete by constructing a member that is not in the enumeration.
So, suppose you create a giant table of all the decimal expansions of the real numbers, removing any duplicates, one number to one row. You can attempt to label each row of the table with a natural number. This is the assumption that the enumeration is complete, and hence the naturals and the reals are in bijective correspondence with each other.
But now, here comes the clever part, as a new number not in the table is constructed. Take the decimal expansion in the first row and change its first digit to something else, change the second digit of the number in the second row, third digit of the number in the third row etc. Now, reading this new number off diagonally, it’s shown that it cannot possibly be listed in the table, as all numbers listed differ from it by at least one digit! QED
(This is rushed, as I have a meeting now, but that’s the gist of the argument. Others will no doubt fill in my holes/errors.)
Take this image from wikipedia: We try to list all the numbers, but can show it’s incomplete because at the bottom we can write one which is different from any by using the one in red.
It would help if you tried to say exactly where the proof becomes confusing to you.
I’ll give a short description. It’s no better than the ones you can find elsewhere, but maybe you can point out exactly where it loses you.
Define a decimal expansion to be an assignment, to each positive integer k, of one of the digits from 0 through 9. A decimal expansion may be thought of as an infinitely long list of digits. You do this by thinking of the digit assigned to k as the k-th item on the list for each positive integer k.
Define a list of decimal expansions to be an assignment, to each positive integer n, of a decimal expansion. Again, you can think of this as a list in the normal sense by thinking of the decimal expansion assigned to n as the n-th item on the list for each positive integer n.
The claim is that, given a list L of decimal expansions, some decimal expansion is not assigned to any positive integer by L. In other words, no list contains all decimal expansions.
Proof: Suppose we are given a list L of decimal expansions. We will show that there is a decimal expansion E that is not assigned to any positive integer by L. For every pair of positive integers i and j, let d[sub]i,j[/sub] be the digit assigned to j by the decimal expansion assigned to i by L.
(That is, the i-th item on the list L is the infinitely long list of digits d[sub]i,1[/sub], d[sub]i,2[/sub], d[sub]i,3[/sub], d[sub]i,4[/sub], . . . .)
Then there is a decimal expansion D (which may or may not appear on the list L) that assigns the digit d[sub]i,i[/sub] to i for each positive integer i. Intuitively speaking, D is the “diagonal” of the list L.
Now consider a new decimal expansion E that assigns d[sub]i,i[/sub] - 1 to i if d[sub]i,i[/sub] > 0, and which assigns 9 to i otherwise. (Thinking of decimal expansions as infinitely long lists, E is what you get if you take each digit in D and subtract 1 from it, unless it’s already 0, in which case you “cycle around” and replace it by 9.)
We claim that E is not assigned to any positive integer by L. For suppose that E were assigned to some positive integer by L. Call this positive integer n. Then, on the one hand, since E is assigned to n by L, E itself assigns the digit d[sub]n,n[/sub] to n. On the other hand, d[sub]n,n[/sub] is also the digit assigned to n by D.
Here is where the contradiction happens. By construction, D and E assign different digits to n. Hence, the supposition that E was on the list L led to a contradiction. This means that E is not on the list, proving the claim.
That is the diagonal proof. Now, the most famous application of this result is that the real numbers aren’t denumerable. That requires going into how real numbers are represented by decimal expansions. But you seemed to express confusion with the “diagonal” part of the proof, so I’ve just focused on that part.
It’s a little hard to avoid set theory because Cantor’s diagonal is one of the foremost examples used by it, but I’ll try to put in English…
Cantor discovered that not all infinities are the same. Surprising, since you would think that infinity is Infinity. But what Cantor did was show that you can compare different sets of things, like infinite series, by showing you can (or not) match up the members of the two sets with each other. For example, is the infinite list of all whole numbers bigger than the infinite list of just the even numbers? Actually no, since you can pair off the lists against each other: 1,2; 2,4; 3,6. In fact almost any infinite thing that you CAN make a list of is the same infinity, called Aleph-Zero. And the pairing off itself defines a function relating the two sets, and then… well, you get into set theory.
So are all infinities the same? No, Cantor’s Diagonal shows that the real numbers (all numbers on a number line, including irrationals) can’t be reduced to a list. He uses a Reducto Ad Absurdum argument, creating a supposed list of all real numbers, and then showing by definition that you could generate a real number that isn’t on the list.
Why can’t I just find the number that’s in the diagonal and list it in the table?
I have no idea what this means. You seem to recycle the same terms, and I can’t keep straight what’s what.
You can, but we can repeat the whole exercise and come up with a new number that isn’t in the new table.
Yes, but if you do that infinitely, what does it prove about the mapping between integers and real numbers? It seems like the integers would have an infinite number of slots open for the real numbers that you pick out from the diagonal.
Doesn’t matter. The point is that no matter how you try to map the integers onto the real numbers, you’re always missing at least one. If you try to think about repeating the process infinitely, you’ll get into the situation of needing to distinguish between countable and uncountable infinities, which is probably not something you want to think about in depth.
Isn’t the difference between countable and uncountable infinities precisely the thing shown by this proof that I can’t understand?
Not quite as generally. The issue is that if you repeat the process infinitely many times, there’s a first time you do it, and a second time, and so on. Therefore, you’re only doing it a countably infinite number of times. Since the reals are uncountable, you won’t hit them all.
But what does this proof show, then? And what am I missing?
Except the reals are infinitely more infinite than the integers. Since to specify a real you have to give an infinite string of numbers following the decimal (even if the string was just infinite zeros), it requires an infinite integer list just to specify ONE real! You could say that the infinite decimal expansion gives the reals more “room” to be infinite than the integers could possibly hold.
The list is already supposed to have every possible real number in it. Since each entry on the list has an infinite number of decimal places, and the list itself is infinitely long, there’s no way to directly compare a given real number to the list; you can only say “can you in principle match this real number one-to-one with some entry on the list?” And the point is that by definition the diagonal is mispaired to any possible entry on the list. So Reductio Ad Absurdum some presumption of the case must be faulty- namely that the real numbers can be paired to an integer list.
I guess what I’m asking is why once you identify the decimal in the diagonal, you can’t just pair it with an integer further down the list.
Lemme try.
So you understand the diagonal picture, but why can’t you add the new element to the list? Good question.
Let’s start over.
Assume you could list all the real numbers (between 0 and 1) in order, according to the natural numbers, like so:
1 - 0.12321…
2 - 0.32344352345234…
3 - 0.4324324234…
4 - 0.4323342398789078…
etc.
Ok, now remember that we are assuming that since there aren’t more real numbers than natural numbers, then this list could contain all of the real numbers between 0 and 1. This is our assumption.
Now look at that diagonal element. That number is not on our list. So what went wrong? The only thing that could have been wrong was our assumption that there are only as many real numbers as natural numbers.
Thus, there are more reals than naturals. Now this is important: what do I mean by “more”? Well, the definition that set theorists use is that one set of things is less than or equal to another precisely if I can do a list like above.
So for example, I know that {4,5,6} has less than or equal to as many things in it as {a,b,c,d}, since I can do a list:
a - 4
b - 5
c - 6
d -
…where I list all the elements of the first set.
This is why we started with the (false) assumption that we could list all the real numbers (between 0 and 1) using the natural numbers, and then showed that no matter how you construct the list, you must leave something out.(namely, that diagonal argument.)
Hope this helps,
JaJ, Set Theorist.
That diagonal that you’ve identified, why can’t you just pair it with a natural number further down the list?
One of the assumptions of the proof is that you already used up all the integers. You are comparing two infinities. The whole point of the argument is to see whether all the integers are paired up. This proves that they are, and that there are real numbers left over that can’t be paired with an integer.
The argument directly establishes this: Any given list is missing some number.
What you are countering is: Ok, but after being shown the number missing from some list, can’t I make another different list containing that number?
To which the answer is: Yes, but so what? We already established that any given list is missing some number. You can keep making new lists to your heart’s content, but we’ve already established that none of them will be complete,
As an analogy, consider this proof that there’s no finite list of all integers: given any finite list of integers, we can take the highest number within it and add 1 to get a new integer not in the given list.
Counter: Yeah, but can’t I just add that new integer to the list? I.e., can’t I just make a new list that contains that number?
Proper reply: Sure, that gets you a new finite list. And the new finite list is still incomplete. We demonstrated in step 1 that any finite list of positive integers will be incomplete, so this result will continue to stand for any list you make.
That makes perfect sense now. I would need a second infinite well of integers in order to form pairs with the diagonals from the real numbers, correct?
Are there infinite sets larger than that of the reals? If so, how can we know?