56
$\begingroup$

The Continuum Hypothesis says 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$
26
  • 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
    Commented Sep 26, 2017 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
    Commented Sep 26, 2017 at 2:19
  • 9
    $\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
    Commented Sep 26, 2017 at 2:32
  • 10
    $\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 ♦
    Commented Sep 26, 2017 at 7:49
  • 3
    $\begingroup$ @Wildcard: I disagree. This is a question of someone not as familiar with logic. Wildberger is just... Let's not finish this comment. $\endgroup$
    – Asaf Karagila ♦
    Commented Sep 26, 2017 at 10:31

5 Answers 5

Reset to default
104
$\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$
5
  • 25
    $\begingroup$ I love this answer for it's immediate accessibility for wider public. $\endgroup$
    – Maciej
    Commented Sep 26, 2017 at 8:39
  • 1
    $\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
    Commented Sep 26, 2017 at 22:24
  • 7
    $\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
    Commented Sep 27, 2017 at 13:01
  • 1
    $\begingroup$ This must be the canonical example of MSE going bananas. $\endgroup$
    – Mikhail Katz
    Commented Sep 27, 2017 at 17:04
  • 1
    $\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
    Commented Oct 4, 2017 at 8:09
57
$\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$
14
  • 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
    Commented Sep 26, 2017 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
    Commented Sep 26, 2017 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
    Commented Sep 26, 2017 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
    Commented Sep 26, 2017 at 21:04
  • 1
    $\begingroup$ @rus9384: Let's not. Have a nice day. $\endgroup$
    – Asaf Karagila ♦
    Commented Sep 28, 2017 at 11:05
34
$\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$
4
  • $\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
    Commented Sep 26, 2017 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 ♦
    Commented Sep 26, 2017 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
    Commented Sep 26, 2017 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
    Commented Sep 27, 2017 at 11:38
8
$\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$
1
  • 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
    Commented Sep 26, 2017 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$
3
  • $\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
    Commented Sep 27, 2017 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
    Commented Sep 27, 2017 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
    Commented Sep 27, 2017 at 17:50

Not the answer you're looking for? Browse other questions tagged .