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.
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.
That’s not a full proof, though-- Don’t you also need a model of R that violates the negation of the continuum hypothesis?
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)
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.
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.
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 ith digit in the ith 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 nth position then the digits have to match but we know the two reals have different digits in the nth 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.
Where is the bottom of the list?
The OP was six years ago, so I wouldn’t expect too much response from people early in the thread.