Can't prove Continuum Hypothesis
My teacher said (and I checked on Wikipedia too), that there is a theory, the Continuum hypothesis, that can neither be proved nor disproved. However, the theory states that:
There is no set whose cardinality is strictly between that of the integers and the real numbers.
And it happens that there is an easy way to prove an existence theory, and that is showing a set that exists and that it fits the proposition. If this hypothesis cannot be proved, then, from where I can see, at least one of these must be true:
- There are some (infinite) sets whose cardinality can't be found
- There are some sets that are unthinkable, indescribable or ineffable
I don't think 1 is true, because, if it is, I would imagine it would be an 'axiom hole' way bigger in set theory than the fact that you can't prove the existence of a set with cardinality between integers and reals. The fact that you cant prove CH given the axioms would be trivial compared to the astonishing fact that you can't show the cardinality of some sets given the axioms. But maybe it is the reason...
As for 2, I know that it is somewhat true. What I see is: there are transcendental numbers (the majority of them) that have no 'mathematical interpretation' (like e or pi) and no 'construction formula' (like Liouville's or Chapernowne's number). That is, a number with a unrepeating, patternless set of digits like pi but with no particular mathematical meaning. This number, and, let's say, the set containing only this number, or the set containing the decimal separation fractions of this number, in a way, can't be 'described'. Using similar ideas, we can imagine a pletora of other ineffable sets, some of which I have doubts regarding their cardinality. I don't know if that is relevant to the fact that some sets are 'ineffable', and if the fact that this sets exist really mean that we can't prove them. Maybe it doesn't make sense to assume this ineffable number to have any meaning because it doesn't by construction. If it had any interesting property then we could use it to describe it anyway.
Could someone please elaborate on that? My questions are: is 1 true? Is 2 true? Is the reason I presented the (one of the, only, main) reason why 2 is true? And most important, which one, 1, 2, or both equally, are the reasons why we can't prove the Continuum Hypothesis? Or is there a third reason I am not seeing as how come an existence theorem can't be proven?
Solution 1:
The continuum hypothesis can be proved. And disproved, too. Wait, what?
Well, in order to make sense of that, and of the fact that the continuum hypothesis can/cannot be proved/disproved, we first need to understand that proofs don't exist in vacuum. Proofs are sequences of formal statements which include either axioms, or statements derived from previous statements in the sequence. We say that a certain sequence is a proof of a statement, if that statement is the last one in the sequence.
So first, before talking about proving or disproving the continuum hypothesis (or anything else) we need to talk about the axioms, and the inference rules. Well, the inference rules part is somewhat more standard through the most of mathematics, so I will kindly disregard this part. What about the axioms? Set theory comes in many flavors. The main one (to the cries of several people) is $\sf ZFC$, the theory of Zermelo and Fraenkel with the Axiom of Choice.
We can add, or remove, some axioms from the list of axioms which is $\sf ZFC$, but mainly set theorists work within the confines of this theory (and any addition is specified in particular).
So what can we say? We can say that the continuum hypothesis cannot be proved, nor disproved from the axioms of $\sf ZFC$. The proof itself was historically given in two parts, Kurt Gödel showed that we can add another axiom, called today $V=L$, such that $\mathsf{ZFC}+V=L$ proves the continuum hypothesis; and that by adding this axiom we do not introduce an inconsistency (namely, if $\sf ZFC$ didn't prove a false statement, then $\mathsf{ZFC}+V=L$ did not prove one). And two decades later Paul Cohen showed that if $\sf ZFC$ did not prove any false statements then $\sf ZFC+\lnot CH$ did not prove any false statement either.
This shows that $\sf ZFC$ cannot prove, nor disprove the continuum hypothesis. If it could prove it, then Cohen's proof wouldn't work; and if it could disprove it then Gödel's proof wouldn't work. Both proofs do work, to the best of our knowledge, and so it seems that $\sf ZFC$ simply does not prove the continuum hypothesis, unless of course it proves a false statement (in which case we don't want to use these axioms anyway).
Of course, throughout the entire process we assume that $\sf ZFC$ is consistent, otherwise what's the point? And therefore it has a model, namely a particular structure interpreting the relation $\in$ in such way that all the axioms of $\sf ZFC$ are true in that structure. And of course, in a given structure the continuum hypothesis is either true, or it is false. Because in a given structure every sentence is either true, or false (but not both!).
The difficulty, I find, comes from understanding that set theory, like any other theory, has different models. Whether or not there is one intended universe that we care about is irrelevant from this point of view. The theory itself has different models, and within each different statements might be true or false. Statements like the continuum hypothesis.
So what about the two reasons that you gave? Well, neither quite exactly is the reason that the continuum hypothesis is unprovable, but both are true.
First of all, what does it mean that we "find the cardinality of a set"? I can write down a simple definition of a set. Now this definition is interpreted in different models of set theory, in some this set is going to be empty, in others non-empty. What is the set? What is its cardinality? We can't "find out" until we find out which model we are using.
This is the situation with the continuum hypothesis. If we know the model we work in, we have a fighting chance of finding out whether or not it is true or false; but since set theory does not have "an intended model", it doesn't have some guideline as to whether or not this statement is true or false.
Secondly, sets which are ineffable and unthinkable, those are all around us. Can you even imagine how does the set $V_\gamma$ where $\gamma=\beth_{\omega_1^{CK}+\omega}$ looks like? It's quite unthinkable. Pretty much anything that you can imagine already happened so far below this set. And yet, it's just a small fragment of a universe of set theory.
Not to mention that as before, we run into difficulties since the set I wrote above is just a definition of a set, and in different models of set theory it will be interpreted differently. So even if you can imagine it in one model of set theory, you might not be able to imagine it in another. Not in "vivid details" like you can imagine the natural numbers.
And for that matter, can you even imagine a difference between $\Bbb Q$ and $\Bbb{R\setminus Q}$? Both have the same properties as ordered sets, but they are not of the same cardinality. Imagination is overrated when it comes to infinite sets, and even more so when it comes to uncountable sets. And in set theory, countable sets are just the tip of the iceberg.
So why is the continuum hypothesis unprovable? Well, because we chose a weak theory (namely $\sf ZFC$). But that's a good thing. It's good when you theory is weak, because it would require less justifications (philosophically or mathematically) as to why it is true.
I think that somewhere in the early 1960s it was expected that Gödel's axiom, $V=L$ will be accepted into the set theoretical canon. But it didn't, and thank goodness too. Because Cohen's proof opened up a huge world of interest in unprovable statements, that the majority of which are incompatible with $V=L$.