55
$\begingroup$

This question already has an answer here:

The Continuum Hypothesis say that there is no set with cardinality between that of the reals and the natural numbers. Apparently, the Continuum Hypothesis can't be proved or disproved using the standard axioms of set theory.

In order to disprove it, one would only have to construct one counterexample of a set with cardinality between the naturals and the reals. It was proven that the CH can't be disproven. Equivalently, it was proven that one cannot construct a counterexample for the CH. Doesn't this prove it?

Of course, the issue is that it was also proven that it can't be proved. I don't know the details of this unprovability proof, but how can it avoid a contradiction? I understand the idea of something being independent of the axioms, I just don't see how if there is provably no counterexample the hypothesis isn't immediately true, since it basically just says a counterexample doesn't exist.

I'm sure I'm making some horrible logical error here, but I'm not sure what it is.

So my question is this: what is the flaw in my argument? Is it a logical error, or a gross misunderstanding of the unprovability proof in question? Or something else entirely?

$\endgroup$

marked as duplicate by Mikhail Katz, Namaste logic Sep 27 '17 at 17:15

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • 5
    $\begingroup$ The flaw is in your understanding. That you cannot construct a counter example in ZF does not mean that within ZF, you can construct a proof of CH. Confusion between the object language and the metalanguage, the language used to talk about ZF, is the flaw. $\endgroup$ – William Elliot Sep 26 '17 at 1:44
  • 8
    $\begingroup$ As Asaf's answer gets at, you seem to be assuming that there is One True Set Theory and that CH is innately either true or false; but what the proofs construct is different set theories which settle the question differently. $\endgroup$ – Steven Stadnicki Sep 26 '17 at 2:19
  • 8
    $\begingroup$ It might help to think of the parallel postulate of (Euclidean) geometry; neither it nor its negation can be proven from the other postulates because there are models in which each is valid. $\endgroup$ – Steven Stadnicki Sep 26 '17 at 2:32
  • 8
    $\begingroup$ @Wildcard: What a silly comment... Let me know when you figure out how many numbers are between the fifth and sixth Ramsey numbers. $\endgroup$ – Asaf Karagila Sep 26 '17 at 7:49
  • 2
    $\begingroup$ @Wildcard: Interesting. So you're claiming that the $n$th Ramsey number is exactly $n$? But sure, let's make it as explicit as humanly possible. When Mr. Wildberger, or you for that matter, find out exactly which natural numbers lie between the fifth and sixth Ramsey numbers, then I will hear more about how CH makes set theory "not mathematics". Or maybe I'll just ask about the interval between the sixth and seventh instead... who knows. $\endgroup$ – Asaf Karagila Sep 26 '17 at 10:14
54
$\begingroup$

I think the basic problem is in your statement that "In order to disprove it, one would only have to construct one counterexample of a set with cardinality between the naturals and the reals." Actually, to disprove CH by this strategy, one would have to produce a counterexample and prove that it actually has cardinality between those of $\mathbb N$ and $\mathbb R$.

So, from the fact that CH can't be disproved in ZFC, you can't infer that there is no counterexample but only that no set can be proved in ZFC to be a counterexample.

$\endgroup$
  • 4
    $\begingroup$ If you're the kind of person who believes there is a standard model of ZFC which is the "real" universe of sets, then I think this is exactly it: you believe that CH is either true or not, but ZFC alone does not tell you which. $\endgroup$ – Ben Millwood Sep 26 '17 at 12:28
  • 4
    $\begingroup$ I like this answer because it points out the specific problem in my logic rather than giving a general lesson on how axioms work. I assume that showing CH is not disprovable means showing there is no counterexample, when really you would show that no set can be proved to be a counterexample. $\endgroup$ – RothX Sep 26 '17 at 13:56
  • $\begingroup$ This paper seems related, but it is to difficult for me. What do you think about it? Where is it wrong? $\endgroup$ – Hjan Sep 26 '17 at 19:01
  • 5
    $\begingroup$ @Hjan, as a rule of thumb you can disregard anything claiming to disprove Cantor's theorem :P After a glance it looks like the claim "When N is large, counting the number of nodes is the same as counting the number of paths (to infinity) in the tree." in Proposition 2.2 is incorrect $\endgroup$ – Kai Rüsch Sep 26 '17 at 21:04
  • 1
    $\begingroup$ @rus9384: Let's not. Have a nice day. $\endgroup$ – Asaf Karagila Sep 28 '17 at 11:05
89
$\begingroup$

Here's an example axiomatic system:

  1. There exist exactly three objects $A, B, C$.
  2. Each of these objects is either a banana, a strawberry or an orange.
  3. There exists at least one strawberry.

Let's name the system $X$.

Vincent's Continuum Hypothesis (VCH): Every object is either a banana or a strawberry (i.e., there are no oranges).

Now, to disprove this in $X$, you would have to show that one of $A, B, C$ is an orange ("construct a counterexample"). But this does not follow from $X$, because the following model is consistent with $X$: A and B are bananas, C is a strawberry.

On the other hand, VCH does not follow from $X$ either, because the following model is consistent with $X$: A is a banana, B is a strawberry, C is an orange.

As you can see, there is no contradiction, because you have to take into account different models of the axiomatic system.

$\endgroup$
  • 20
    $\begingroup$ I love this answer for it's immediate accessibility for wider public. $\endgroup$ – Maciej Sep 26 '17 at 8:39
  • $\begingroup$ Great answer. It was so hard to pick which one to accept. This one is very useful, but it doesn't answer my question as directly as the one I accepted. $\endgroup$ – RothX Sep 26 '17 at 22:24
  • 5
    $\begingroup$ I'm pretty sure I've been searching for an example just like this for years and just never knew how to ask for it. $\endgroup$ – KDecker Sep 27 '17 at 13:01
  • 1
    $\begingroup$ This must be the canonical example of MSE going bananas. $\endgroup$ – Mikhail Katz Sep 27 '17 at 17:04
  • $\begingroup$ Is this actually how the real CH was proven independent of ZFC? Did we construct models of ZFC with CH and !CH? If so, what framework did we construct those models in? $\endgroup$ – ASKASK Oct 4 '17 at 8:09
32
$\begingroup$

How would you prove that not all groups are abelian? Namely, how would you prove that the axioms of groups do not imply $\forall x\forall y(xy=yx)$?

Well. You'd find a model for the theory, namely a group, which is not abelian. At the same time, you can also show this is not disprovable by finding an abelian group.

So, does that mean that all groups are abelian, because the axiom $\forall x\forall y(xy=yx)$ is independent of the axioms of a group? No. It does not.

The independence of the continuum hypothesis from ZFC goes along the same lines. We can show there are models of ZFC where CH holds, and others where it fails. This is regardless to the techniques we use, which are clever and useful for so much more in set theory.

$\endgroup$
  • $\begingroup$ So the idea is that ZFC describes a system where CH is true as well as a system where CH is false? $\endgroup$ – RothX Sep 26 '17 at 13:54
  • 1
    $\begingroup$ Well, there's some issue with "true" and "false" here. You should perhaps read math.stackexchange.com/questions/494099/… where I wrote about that in length. $\endgroup$ – Asaf Karagila Sep 26 '17 at 14:04
  • 1
    $\begingroup$ @RothX That sounds correct, but I'd phrase it a bit more carefully. There are multiple different systems that are described by ZFC; and among those systems which are described by ZFC, there is at least one system where CH is true, as well as at least one system where CH is false. $\endgroup$ – Tanner Swett Sep 26 '17 at 17:21
  • $\begingroup$ @TannerSwett Yeah, I think that's pretty much what I was trying to say. I just need to get used to using mathematical language more. $\endgroup$ – RothX Sep 27 '17 at 11:38
7
$\begingroup$

The situation is really rather similar to that of non-Euclidean geometry.

From the first four Euclidean postulates, you can neither prove nor disprove the fifth (parallel) postulate. This has been proven only two millennia after Euclid wrote his Elements. If you assume the fifth postulate is true, you get Euclidean geometry; if you assume it is false, you get elliptic or hyperbolic geometry. The common ground to both is absolute geometry.

Similarly, from ZFC, you can neither prove nor disprove the continuum hypothesis. If you assume it is true, you get one kind of set theory; if you assume it is false, you get another. The common ground to both is ZFC.

$\endgroup$
  • 2
    $\begingroup$ Correction: elliptic geometry is inconsistent with absolute geometry. If you replace the parallel postulate with its negation, you get hyperbolic geometry. $\endgroup$ – eyeballfrog Sep 26 '17 at 8:31
1
$\begingroup$

CH: "There is no set with cardinality between that of the reals and the natural numbers."

disprove CH by: demonstrating such a set

You can't demonstrate such a set. Therefore, you can't disprove it.

To prove it, you have to show that ALL sets have cardinality:

  1. less than or equal to natural numbers -or-
  2. greater than or equal to real numbers

You can't prove it either.

Therefore, you can neither prove nor disprove CH.

The basic problem is the unfounded assumption that you can prove something by simply showing that you can't disprove it. You'll have to prove that one first.

Actually, the continuum hypothesis itself demonstrates that you can't, by virtue of "you can't prove it" above.

$\endgroup$
  • $\begingroup$ It isn't necessarily true, I think. - to anyone with a background more in theoretical computer science, there is no "I think" here; reasoning about proving is not so far away from reasoning about computability, and assuming something is true only because you cannot prove that it is false is a very basic fallacy. $\endgroup$ – AnoE Sep 27 '17 at 17:01
  • $\begingroup$ fine. Removed "I think". But in response, I AM an algorithm, therefore "I think.." is still valid within the domain of theoretical computer science. But that is of course not the subject of this thread. $\endgroup$ – allwind Sep 27 '17 at 17:27
  • $\begingroup$ You can think whatever you want, and so can I, that's the beauty of it. :D (My comment was not related to a vote in either direction). $\endgroup$ – AnoE Sep 27 '17 at 17:50

Not the answer you're looking for? Browse other questions tagged or ask your own question.