# Cantor's Diagonal Proof **URL:** \ **Category:** Factual Questions\ **Created:** [March 15, 2019, 4:49pm UTC](https://boards.straightdope.com/t/cantors-diagonal-proof/831185 "2019-03-15T16:49:38Z")\ **Posts on this page:** 13\ **Page:** 1
**Author:** ![whc.03grady](https://avatars.discourse-cdn.com/v4/letter/w/a6a055/32.png) [@whc.03grady](https://boards.straightdope.com/u/whc.03grady)\ **Post date:** [March 15, 2019, 4:49pm UTC](https://boards.straightdope.com/t/cantors-diagonal-proof/831185/1 "2019-03-15T16:49:38Z")
From the excellent appendix to Wesley Salmon’s _[Zeno’s Paradoxes](https://books.google.com/books/about/Zeno_s_Paradoxes.html?id=0AzP9WLLJLcC&printsec=frontcover&source=kp_read_button#v=onepage&q&f=false)_ (Bobbs-Merrill, 1970), p. 258_ff_: > [@Salmon](#): > > Cantor has given an elegant proof that the class of real numbers is not denumerable…The demonstration proceeds by reductio ad absurdum. Let us suppose that some enumeration–_any_ enumeration–of the real numbers could exist; it would constitute a list of real numbers corresponding to the positive natural numbers in the following manner: > > 1 0.25978… > 2 0.53224… > 3 0.43725… > 4 0.22897… > 5 0.97862… > . > . > . > > Cantor now shows us how to find a real number between zero and one that is not in the supposedly complete list. We begin by looking at the digit in the first decimal place of the first number; it is two. We choose another digit, say three, which differs from the one we found. **Moreover, we always choose a digit other than zero.**" [My emphasis; formatting won’t allow as much space as I’d like between the list of naturals on the left and the list of reals on the right.] Salmon leaves as a question for the reader _why_ we always choose a digit other than zero, but I’m not smart enough to figure it out. So, why? ---
**Author:** ![Chronos](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/chronos/32/134_2.png) [@Chronos](https://boards.straightdope.com/u/Chronos)\ **Post date:** [March 15, 2019, 4:51pm UTC](https://boards.straightdope.com/t/cantors-diagonal-proof/831185/2 "2019-03-15T16:51:04Z")
I can give you 0.9999… good reasons to avoid using 0 as a digit. ---
**Author:** ![ITR\_champion](https://avatars.discourse-cdn.com/v4/letter/i/c67d28/32.png) [@ITR\_champion](https://boards.straightdope.com/u/ITR_champion)\ **Post date:** [March 15, 2019, 4:52pm UTC](https://boards.straightdope.com/t/cantors-diagonal-proof/831185/3 "2019-03-15T16:52:04Z")
Presumably so that the hypothetical not-in-the-list number is not 0 . ---
**Author:** ![whc.03grady](https://avatars.discourse-cdn.com/v4/letter/w/a6a055/32.png) [@whc.03grady](https://boards.straightdope.com/u/whc.03grady)\ **Post date:** [March 15, 2019, 4:55pm UTC](https://boards.straightdope.com/t/cantors-diagonal-proof/831185/4 "2019-03-15T16:55:45Z")
(Also, a tangential spoiler alert for those who aren’t familiar with the proof: you keep going down that list, choosing digits differing from zero (apparently) and the _n_th digit, where _n_ is the natural number on the left. String these all together behind an initial zero and you get a number that can’t be on the list–for every _n_, it’s different from that number at the _n_th place. Therefore there aren’t enough numbers to count all the numbers, therefore mind blown.) ---
**Author:** ![DPRK](https://avatars.discourse-cdn.com/v4/letter/d/4491bb/32.png) [@DPRK](https://boards.straightdope.com/u/DPRK)\ **Post date:** [March 15, 2019, 4:57pm UTC](https://boards.straightdope.com/t/cantors-diagonal-proof/831185/5 "2019-03-15T16:57:56Z")
I have not read that book, but I hope the author proves that the only way a real number cannot be uniquely expressed as a decimal is if it ends in an infinite string of zeros or nines. Then, you need to deal with that one way or the other. ---
**Author:** ![leahcim](https://avatars.discourse-cdn.com/v4/letter/l/b4bc9f/32.png) [@leahcim](https://boards.straightdope.com/u/leahcim)\ **Post date:** [March 15, 2019, 5:31pm UTC](https://boards.straightdope.com/t/cantors-diagonal-proof/831185/6 "2019-03-15T17:31:36Z")
To be clear, any terminating decimal can be expressed as: 0.d[sub]1[/sub]d[sub]2[/sub]d[sub]3[/sub]…d[sub]n-1[/sub]d[sub]n[/sub]000000000… or as: 0.d[sub]1[/sub]d[sub]2[/sub]d[sub]3[/sub]…d[sub]n-1/sub999999999… Where d[sub]i[/sub] are the non-zero digits. If we allowed either to be picked, Cantor’s argument would fail because we could say, “the diagonal number is not in the list in that form, but maybe it is actually in the list in its other form”. Requiring zero to never be picked ensures that we only get the latter form of each number. ---
**Author:** ![whc.03grady](https://avatars.discourse-cdn.com/v4/letter/w/a6a055/32.png) [@whc.03grady](https://boards.straightdope.com/u/whc.03grady)\ **Post date:** [March 15, 2019, 5:32pm UTC](https://boards.straightdope.com/t/cantors-diagonal-proof/831185/7 "2019-03-15T17:32:17Z")
> [@whc.03grady](#): > > (Also, a tangential spoiler alert for those who aren’t familiar with the proof: you keep going down that list, choosing digits differing from zero (apparently) and the _n_th digit, where _n_ is the natural number on the left. String these all together behind an initial zero and you get a number that can’t be on the list–for every real corresponding to any _n_, the number you made is different from the number at the _n_th place by one. Therefore there aren’t enough numbers to count all the numbers, therefore mind blown.) Fixed. ---
**Author:** ![septimus](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/septimus/32/410_2.png) [@septimus](https://boards.straightdope.com/u/septimus)\ **Post date:** [March 15, 2019, 6:16pm UTC](https://boards.straightdope.com/t/cantors-diagonal-proof/831185/8 "2019-03-15T18:16:42Z")
One way to avoid the bother of problems like 0.400000 = 0.3999999… in proofs like this is to use a representation of the reals which guarantees uniqueness. For example, [Continued fractions](https://en.wikipedia.org/wiki/Continued_fraction) provide a unique mapping between the real segment (0,1] and sequences of natural numbers (finite or infinite sequences for rationals or irrationals resp.). Other examples? ---
**Author:** ![ftg](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/ftg/32/2801_2.png) [@ftg](https://boards.straightdope.com/u/ftg)\ **Post date:** [March 15, 2019, 8:08pm UTC](https://boards.straightdope.com/t/cantors-diagonal-proof/831185/9 "2019-03-15T20:08:09Z")
I once worked thru doing Cantor’s proof using base 2 (I’m a Computer Scientist). So picking a different digit is forced, there’s only one other option. The .1111… problem is an issue that has to be handled separately. But I see nothing wrong with picking zero here and there. And if you end up always picking zero since there’s a 1 in the _n_th spot of the _n_th number and end up with 0, then the list must not include 0 which violates the condition. As far as unique representations of all numbers in [0,1) there’s the [Stern-Brocot tree](https://en.wikipedia.org/wiki/Stern%E2%80%93Brocot_tree). (Which of course is a continued fraction thing in another form.) Note that the irrational numbers are merely infinite paths in the tree. Something the Wikipedia article doesn’t point out.\* So numbers are encoded using L, R paths (why the article uses “H” instead of “R” is beyond me). And you can do diagonalization, swapping L and R, but the extra complication are the finite paths with no “zero” in the notation.\*\* - The discussion of this tree and numbers is excellent in the article’s first reference: Graham, Knuth, Patashnik, _Concrete Mathematics_. Knuth strikes the SDMB again. \*\* You merely ignore it and go on to the next one. Clearly any such skipped finitely long number will not be the same infinitely long number you end up with. ---
**Author:** ![OldGuy](https://avatars.discourse-cdn.com/v4/letter/o/3bc359/32.png) [@OldGuy](https://boards.straightdope.com/u/OldGuy)\ **Post date:** [March 15, 2019, 8:25pm UTC](https://boards.straightdope.com/t/cantors-diagonal-proof/831185/10 "2019-03-15T20:25:10Z")
> [@ftg](#): > > So numbers are encoded using L, R paths (why the article uses “H” instead of “R” is beyond me). Without looking at it, I’d guess if comes from a horizontal rather than vertical tree. Then H and L stand for High and Low rather than Right and Left. ---
**Author:** ![Andy\_L](https://avatars.discourse-cdn.com/v4/letter/a/c67d28/32.png) [@Andy\_L](https://boards.straightdope.com/u/Andy_L)\ **Post date:** [March 15, 2019, 9:11pm UTC](https://boards.straightdope.com/t/cantors-diagonal-proof/831185/11 "2019-03-15T21:11:25Z")
> [@septimus](#): > > One way to avoid the bother of problems like 0.400000 = 0.3999999… in proofs like this is to use a representation of the reals which guarantees uniqueness. For example, [Continued fractions](https://en.wikipedia.org/wiki/Continued_fraction) provide a unique mapping between the real segment (0,1] and sequences of natural numbers (finite or infinite sequences for rationals or irrationals resp.). Other examples? It’s been 30 years since I studied this subject, and I had completely forgotten the need to avoid numbers with dual representation; I also had never known that continued fractions were unique, so thanks! ---
**Author:** ![TemporalFix](https://avatars.discourse-cdn.com/v4/letter/t/c6cbf5/32.png) [@TemporalFix](https://boards.straightdope.com/u/TemporalFix)\ **Post date:** [March 15, 2019, 9:22pm UTC](https://boards.straightdope.com/t/cantors-diagonal-proof/831185/12 "2019-03-15T21:22:10Z")
Like ftg’s post above, [Cantor’s original publication](https://www.digizeitschriften.de/dms/img/?PID=GDZPPN002113910&physid=phys85#navi) (referred to by [Wikipedia’s version](https://en.wikipedia.org/wiki/Cantor%27s_diagonal_argument)), does not use _choosing_, and he uses 2 symbols in his example. However Cantor does not talk about “constructing a real number not on the list”, he talks about coordinates, functions, and contradiction. I think Cantor avoids the problem with cases like 0.1000… = 0.0111… (in binary) by the higher abstraction level in his publication; I confess not completely understanding it. ---
**Author:** ![septimus](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/septimus/32/410_2.png) [@septimus](https://boards.straightdope.com/u/septimus)\ **Post date:** [March 16, 2019, 3:25am UTC](https://boards.straightdope.com/t/cantors-diagonal-proof/831185/13 "2019-03-16T03:25:33Z")
> [@Andy\_L](#): > > It’s been 30 years since I studied this subject, and I had completely forgotten the need to avoid numbers with dual representation; I also had never known that continued fractions were unique, so thanks! I’m afraid I was (slightly?) wrong! :o Each rational number has two cf forms (one which ends in ‘1’ and one which doesn’t): 4/5 = [1,4] = [1,3,1] This can be fixed with a slight jiggle: Subtract 1 from the final term in a finite cf. (Jiggles to cope with the 0.400000 = 0.39999999… problem are less trivial.)