# Explain Cantor's Diagonal Method to a Non-Math Person **URL:** \ **Category:** Factual Questions\ **Created:** [November 19, 2008, 3:12pm UTC](https://boards.straightdope.com/t/explain-cantors-diagonal-method-to-a-non-math-person/473454 "2008-11-19T15:12:57Z")\ **Posts on this page:** 20\ **Page:** 1
**Author:** ![FrustratedIdiot](https://avatars.discourse-cdn.com/v4/letter/f/77aa72/32.png) [@FrustratedIdiot](https://boards.straightdope.com/u/FrustratedIdiot)\ **Post date:** [November 19, 2008, 3:12pm UTC](https://boards.straightdope.com/t/explain-cantors-diagonal-method-to-a-non-math-person/473454/1 "2008-11-19T15:12:57Z")
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? ---
**Author:** ![Capt.Ridley\_s\_Shooting\_Party](https://avatars.discourse-cdn.com/v4/letter/c/cc9497/32.png) [@Capt.Ridley\_s\_Shooting\_Party](https://boards.straightdope.com/u/Capt.Ridley_s_Shooting_Party)\ **Post date:** [November 19, 2008, 3:24pm UTC](https://boards.straightdope.com/t/explain-cantors-diagonal-method-to-a-non-math-person/473454/2 "2008-11-19T15:24:26Z")
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.) ---
**Author:** ![hawthorne](https://avatars.discourse-cdn.com/v4/letter/h/c89c15/32.png) [@hawthorne](https://boards.straightdope.com/u/hawthorne)\ **Post date:** [November 19, 2008, 3:27pm UTC](https://boards.straightdope.com/t/explain-cantors-diagonal-method-to-a-non-math-person/473454/3 "2008-11-19T15:27:39Z")
Take [this image](http://en.wikipedia.org/wiki/Image:Diagonal_argument_2.svg) 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. ---
**Author:** ![Tyrrell\_McAllister](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/tyrrell_mcallister/32/16772_2.png) [@Tyrrell\_McAllister](https://boards.straightdope.com/u/Tyrrell_McAllister)\ **Post date:** [November 19, 2008, 4:30pm UTC](https://boards.straightdope.com/t/explain-cantors-diagonal-method-to-a-non-math-person/473454/4 "2008-11-19T16:30:34Z")
> [@FrustratedIdiot](#): > > 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? 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. ---
**Author:** ![Lumpy](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/lumpy/32/446_2.png) [@Lumpy](https://boards.straightdope.com/u/Lumpy)\ **Post date:** [November 19, 2008, 4:45pm UTC](https://boards.straightdope.com/t/explain-cantors-diagonal-method-to-a-non-math-person/473454/5 "2008-11-19T16:45:43Z")
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. ---
**Author:** ![FrustratedIdiot](https://avatars.discourse-cdn.com/v4/letter/f/77aa72/32.png) [@FrustratedIdiot](https://boards.straightdope.com/u/FrustratedIdiot)\ **Post date:** [November 20, 2008, 1:47am UTC](https://boards.straightdope.com/t/explain-cantors-diagonal-method-to-a-non-math-person/473454/6 "2008-11-20T01:47:18Z")
> [@Capt.Ridley\_s\_Shooting\_Party](#): > > 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.) Why can’t I just find the number that’s in the diagonal and list it in the table? ---
**Author:** ![FrustratedIdiot](https://avatars.discourse-cdn.com/v4/letter/f/77aa72/32.png) [@FrustratedIdiot](https://boards.straightdope.com/u/FrustratedIdiot)\ **Post date:** [November 20, 2008, 1:49am UTC](https://boards.straightdope.com/t/explain-cantors-diagonal-method-to-a-non-math-person/473454/7 "2008-11-20T01:49:16Z")
> [@Tyrrell\_McAllister](#): > > 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_. I have no idea what this means. You seem to recycle the same terms, and I can’t keep straight what’s what. ---
**Author:** ![ultrafilter](https://avatars.discourse-cdn.com/v4/letter/u/3d9bf3/32.png) [@ultrafilter](https://boards.straightdope.com/u/ultrafilter)\ **Post date:** [November 20, 2008, 1:58am UTC](https://boards.straightdope.com/t/explain-cantors-diagonal-method-to-a-non-math-person/473454/8 "2008-11-20T01:58:23Z")
> [@FrustratedIdiot](#): > > Why can’t I just find the number that’s in the diagonal and list it in the table? You can, but we can repeat the whole exercise and come up with a new number that isn’t in the new table. ---
**Author:** ![FrustratedIdiot](https://avatars.discourse-cdn.com/v4/letter/f/77aa72/32.png) [@FrustratedIdiot](https://boards.straightdope.com/u/FrustratedIdiot)\ **Post date:** [November 20, 2008, 2:08am UTC](https://boards.straightdope.com/t/explain-cantors-diagonal-method-to-a-non-math-person/473454/9 "2008-11-20T02:08:08Z")
> [@ultrafilter](#): > > 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. ---
**Author:** ![ultrafilter](https://avatars.discourse-cdn.com/v4/letter/u/3d9bf3/32.png) [@ultrafilter](https://boards.straightdope.com/u/ultrafilter)\ **Post date:** [November 20, 2008, 2:15am UTC](https://boards.straightdope.com/t/explain-cantors-diagonal-method-to-a-non-math-person/473454/10 "2008-11-20T02:15:33Z")
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. ---
**Author:** ![FrustratedIdiot](https://avatars.discourse-cdn.com/v4/letter/f/77aa72/32.png) [@FrustratedIdiot](https://boards.straightdope.com/u/FrustratedIdiot)\ **Post date:** [November 20, 2008, 2:17am UTC](https://boards.straightdope.com/t/explain-cantors-diagonal-method-to-a-non-math-person/473454/11 "2008-11-20T02:17:24Z")
> [@ultrafilter](#): > > 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? ---
**Author:** ![ultrafilter](https://avatars.discourse-cdn.com/v4/letter/u/3d9bf3/32.png) [@ultrafilter](https://boards.straightdope.com/u/ultrafilter)\ **Post date:** [November 20, 2008, 2:23am UTC](https://boards.straightdope.com/t/explain-cantors-diagonal-method-to-a-non-math-person/473454/12 "2008-11-20T02:23:55Z")
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. ---
**Author:** ![FrustratedIdiot](https://avatars.discourse-cdn.com/v4/letter/f/77aa72/32.png) [@FrustratedIdiot](https://boards.straightdope.com/u/FrustratedIdiot)\ **Post date:** [November 20, 2008, 2:24am UTC](https://boards.straightdope.com/t/explain-cantors-diagonal-method-to-a-non-math-person/473454/13 "2008-11-20T02:24:56Z")
But what does this proof show, then? And what am I missing? ---
**Author:** ![Lumpy](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/lumpy/32/446_2.png) [@Lumpy](https://boards.straightdope.com/u/Lumpy)\ **Post date:** [November 20, 2008, 2:26am UTC](https://boards.straightdope.com/t/explain-cantors-diagonal-method-to-a-non-math-person/473454/14 "2008-11-20T02:26:24Z")
> [@FrustratedIdiot](#): > > 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. 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. ---
**Author:** ![FrustratedIdiot](https://avatars.discourse-cdn.com/v4/letter/f/77aa72/32.png) [@FrustratedIdiot](https://boards.straightdope.com/u/FrustratedIdiot)\ **Post date:** [November 20, 2008, 2:32am UTC](https://boards.straightdope.com/t/explain-cantors-diagonal-method-to-a-non-math-person/473454/15 "2008-11-20T02:32:30Z")
> [@Lumpy](#): > > 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. 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. ---
**Author:** ![Jamaika\_a\_jamaikaiake](https://avatars.discourse-cdn.com/v4/letter/j/7993a0/32.png) [@Jamaika\_a\_jamaikaiake](https://boards.straightdope.com/u/Jamaika_a_jamaikaiake)\ **Post date:** [November 20, 2008, 2:40am UTC](https://boards.straightdope.com/t/explain-cantors-diagonal-method-to-a-non-math-person/473454/16 "2008-11-20T02:40:16Z")
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. ---
**Author:** ![FrustratedIdiot](https://avatars.discourse-cdn.com/v4/letter/f/77aa72/32.png) [@FrustratedIdiot](https://boards.straightdope.com/u/FrustratedIdiot)\ **Post date:** [November 20, 2008, 2:42am UTC](https://boards.straightdope.com/t/explain-cantors-diagonal-method-to-a-non-math-person/473454/17 "2008-11-20T02:42:45Z")
> [@Jamaika\_a\_jamaikaiake](#): > > 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. That diagonal that you’ve identified, why can’t you just pair it with a natural number further down the list? ---
**Author:** ![DrCube](https://avatars.discourse-cdn.com/v4/letter/d/a3d4f5/32.png) [@DrCube](https://boards.straightdope.com/u/DrCube)\ **Post date:** [November 20, 2008, 2:45am UTC](https://boards.straightdope.com/t/explain-cantors-diagonal-method-to-a-non-math-person/473454/18 "2008-11-20T02:45:36Z")
> [@FrustratedIdiot](#): > > 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. 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. ---
**Author:** ![Indistinguishable](https://avatars.discourse-cdn.com/v4/letter/i/90ced4/32.png) [@Indistinguishable](https://boards.straightdope.com/u/Indistinguishable)\ **Post date:** [November 20, 2008, 2:47am UTC](https://boards.straightdope.com/t/explain-cantors-diagonal-method-to-a-non-math-person/473454/19 "2008-11-20T02:47:05Z")
> [@FrustratedIdiot](#): > > 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. 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. ---
**Author:** ![FrustratedIdiot](https://avatars.discourse-cdn.com/v4/letter/f/77aa72/32.png) [@FrustratedIdiot](https://boards.straightdope.com/u/FrustratedIdiot)\ **Post date:** [November 20, 2008, 2:48am UTC](https://boards.straightdope.com/t/explain-cantors-diagonal-method-to-a-non-math-person/473454/20 "2008-11-20T02:48:10Z")
> [@DrCube](#): > > 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. 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? [Next page](https://boards.straightdope.com/t/explain-cantors-diagonal-method-to-a-non-math-person/473454.md?page=2)