| I think I figured it out: you must be one of the aliens predicted by the downward Löwenheim–Skolem theorem! If we could have a model of set theory (a set1 of all set2s, where a set1 is a set in our set theory and a set2 a modeled set, like an interpreter), which is necessarily infinitely large, then the downward Löwenheim–Skolem theorem implies there is a model that is only countably infinite. There is a model of the real numbers in there, so from our point of view, the real numbers are countable! Though from the model's point of view, Cantor's diagonal argument still works, and they are not countable! My theory is that you are looking at our real numbers and thinking they are countable because you have a much more powerful set of natural numbers than the rest of us. Unfortunately for you, your bijection between our reals and your naturals does not carry over to our set theory. You should find, however, that you do not have a bijection between your reals and your naturals. One problem with this is that Gödel's incompleteness theorem implies that if we ever had a model and could prove it was a model, then set theory would be inconsistent. More seriously, Cantor's argument as usually given is not Cantor's original argument. He originally did something involving nested closed intervals, but it was simplified to listing out the digit expansions of a list of real numbers. I am partial to the following argument: suppose there were an invertible function f between N and infinite sequences of 0's and 1's. The type of f is written N -> (N -> Bool) since an infinite sequence of 0's and 1's is a function from N to {0,1}. Let g(n)=not f(n)(n). This is a function N -> Bool. Since f is invertible, let finv be the inverse f : (N -> Bool) -> N. Then finv(g) is a natural number. Plug this into g: g(finv(g)) = not f(finv(g))(finv(g))
= not g(finv(g))
Uh oh, the value of g at finv(g) is not whatever its value is. Something must be wrong: it could be there is no set of natural numbers or booleans (unlikely), that g is not definable (but it is a simple expression of f, and not even recursive; unlikely), or that there is no such function f (this is the only assumption remaining, so there must not have been an f that is a bijection).Notice there was nothing special about N in this argument. It could have been a finite set, an infinite set, or even the real numbers, and we still would have concluded there is some value at which g is not its own value! It is possible to prove that there are at least as many real numbers as there are sequences N -> Bool using infinite series. It is also possible to prove there are no more real numbers than there are such sequences. |