# 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:** 8\ **Page:** 6
**Author:** ![walkinglobster](https://avatars.discourse-cdn.com/v4/letter/w/8e7dd6/32.png) [@walkinglobster](https://boards.straightdope.com/u/walkinglobster)\ **Post date:** [July 10, 2014, 5:41am UTC](https://boards.straightdope.com/t/explain-cantors-diagonal-method-to-a-non-math-person/473454/101 "2014-07-10T05:41:49Z")
> [@Indistinguishable](#): > > For example, if I choose to change digits by increasing them by 2 [wrapping around if necessary], in your example, the missing sequence would be 0.311702… I get it now. Thank you so much. It’s strange because I read that same thing at about 20 other places, but for some reason, your answer just made it make sense in my head. I continued to think that the new list that you get by doing (list + 2 mod 10) for every digit could reappear later on and still adhere to the diagonal. I actually had to redraw a new list in my head to make sense of it. ---
**Author:** ![Itself](https://avatars.discourse-cdn.com/v4/letter/i/d07c76/32.png) [@Itself](https://boards.straightdope.com/u/Itself)\ **Post date:** [July 11, 2014, 2:56am UTC](https://boards.straightdope.com/t/explain-cantors-diagonal-method-to-a-non-math-person/473454/102 "2014-07-11T02:56:54Z")
By the way, since the independence of the continuum hypothesis from ZFC is one of those results (like, for example, the Jordan curve theorem) that’s well-known but whose proof is not, let me mention that there’s a reasonably nice proof in Chapter III of Manin’s _Course in Mathematical Logic for Mathematicians_. It’s Cohen’s proof that the space of measurable real functions on X = Map(S, [0, 1]) for a large space S (modulo functions that vanish a.e., effectively) is a model of R that violates the continuum hypothesis. The proof is long but not particularly difficult; it’s pretty much just translating axioms into the language of set theory and showing that they hold for X. I thought it was nifty, at least. ---
**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:** [July 12, 2014, 3:30am UTC](https://boards.straightdope.com/t/explain-cantors-diagonal-method-to-a-non-math-person/473454/103 "2014-07-12T03:30:32Z")
That’s not a full proof, though-- Don’t you also need a model of R that violates the negation of the continuum hypothesis? ---
**Author:** ![Indistinguishable](https://avatars.discourse-cdn.com/v4/letter/i/90ced4/32.png) [@Indistinguishable](https://boards.straightdope.com/u/Indistinguishable)\ **Post date:** [July 12, 2014, 3:40am UTC](https://boards.straightdope.com/t/explain-cantors-diagonal-method-to-a-non-math-person/473454/104 "2014-07-12T03:40:57Z")
That’s considered the much easier part, though perhaps only because it was discovered much earlier. In particular, by restricting attention to Goedel’s “constructible” sets, one gets such a model. (Incidentally, my personal favorite exposition of the relative consistency of the negation of the continuum hypothesis is Dana Scott’s “A Proof of the Independence of the Continuum Hypothesis”, which, like the reference **Itself** refers to, frames things along measure-theoretic, which is to say, probabilistic lines) ---
**Author:** ![Itself](https://avatars.discourse-cdn.com/v4/letter/i/d07c76/32.png) [@Itself](https://boards.straightdope.com/u/Itself)\ **Post date:** [July 12, 2014, 5:28am UTC](https://boards.straightdope.com/t/explain-cantors-diagonal-method-to-a-non-math-person/473454/105 "2014-07-12T05:28:43Z")
> [@Chronos](#): > > That’s not a full proof, though-- Don’t you also need a model of R that violates the negation of the continuum hypothesis? Yes, but that part’s easy (once you have the right machinery, at least); it’s a fraction of the length of the proof in the opposite direction. I think it predates the harder part of the proof by a couple decades. ---
**Author:** ![Saint\_Cad](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/saint_cad/32/18907_2.png) [@Saint\_Cad](https://boards.straightdope.com/u/Saint_Cad)\ **Post date:** [July 13, 2014, 3:52pm UTC](https://boards.straightdope.com/t/explain-cantors-diagonal-method-to-a-non-math-person/473454/106 "2014-07-13T15:52:33Z")
I think for the OP, an example is in order so he can see how it works. When I learned it, my professor used only the digits 2 and 3. List every real number between 0 and 1 that has 2 and 3 as its digits. If it is countable (that it in 1-1 correspondence with the natural numbers) we could index (let’s ignore the concept of ordinals for a second) the real numbers and since it is 1-1 every real number is in that list. So let’s do that. 1. 0.22232333222332… 2. 0.2332223232323… 3. 0.33223232323232… 4. 0.33323332333333223… 5. 0.33223323232333… … Now I claim ever real between 0 and 1 using 2 and 3 as digits are on that list. What Cantor did was construct a number that was not on the list. The _i_th digit in the _i_th real is changed to the other choice. So for example the first digit in the first real is 2 so change it to a 3. The second digit in the second number is a 3 so change it to a 2, 3rd digit in #3 is 2 so it is change to a 3 and so on. Our new real starts out 0.32332… Cantor guaranties that this new real is not on the list because (proof by contradiction) if it were on the list in the _n_th position then the digits have to match but we know the two reals have different digits in the _n_th place and so the two reals cannot be the same. The conceptual leap comes from saying, “Well why can’t we just put the new real at the bottom of the list? After all, infinity+1 is still infinity.” While overly simplistic, this statement is actually true\*, but then we can repeat the process again and again an infinite number of times. The idea is since that process never ends, then there is no bijection between the naturals and our limited set of reals. Question to wrestle with: why can’t I continue this an infinite number of times? I mean, Cantor seems to play fast and loose with what you can do an infinite number of times (like construct a real using an infinite number of digit changes) and what you can’t like add an infinite number of reals to a list that already contains and infinite number of reals. The answer to that lies in all of that set theory you have been looking at. - To be pedantic, the idea is that adding one more element to a countable set creates a set that is still countable. ---
**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:** [July 13, 2014, 8:17pm UTC](https://boards.straightdope.com/t/explain-cantors-diagonal-method-to-a-non-math-person/473454/107 "2014-07-13T20:17:50Z")
> [@](#): > > The conceptual leap comes from saying, “Well why can’t we just put the new real at the bottom of the list? After all, infinity+1 is still infinity.” Where is the bottom of the list? ---
**Author:** ![ultrafilter](https://avatars.discourse-cdn.com/v4/letter/u/3d9bf3/32.png) [@ultrafilter](https://boards.straightdope.com/u/ultrafilter)\ **Post date:** [July 13, 2014, 9:16pm UTC](https://boards.straightdope.com/t/explain-cantors-diagonal-method-to-a-non-math-person/473454/108 "2014-07-13T21:16:23Z")
The OP was six years ago, so I wouldn’t expect too much response from people early in the thread. [Previous page](https://boards.straightdope.com/t/explain-cantors-diagonal-method-to-a-non-math-person/473454.md?page=5)