I'm a bit confused by this question because looking around on this site I've been reading about the continuum hypothesis and it seems like that says that my question is independent of ZFC. My only guess is that some set existing with cardinality between |N| and |P(N)| is not provable or disprovable but that set being a subset of P(N) is disprovable? Any help or clarification would be appreciated.

  • 1
    $\begingroup$ The existence of a set whose cardinality is strictly between $|\Bbb N|$ and $|wp(\Bbb N)|$ is neither provable nor disprovable from the usual axioms for set theory. If there is such a set, however, there is one that is a subset of $\wp(\Bbb N)$. $\endgroup$ – Brian M. Scott Dec 19 '16 at 2:39
  • $\begingroup$ Yes, the existence of such a set is neither provable nor disprovable. It is the Continuum Hypothesis $\endgroup$ – Hayden Dec 19 '16 at 2:39
  • $\begingroup$ $|\mathbb{N}| = \aleph_0$ and $|\mathcal P(\mathbb N)| = \mathfrak c$ so this is equivalent to continuum hypothesis. $\endgroup$ – Henricus V. Dec 19 '16 at 2:40
  • $\begingroup$ @BrianM.Scott, thanks, but could you explain how we would know that if there is such a set that one such set is a subset of the powerset of N (sorry I don't know how to do the natural numbers notation) $\endgroup$ – Alex Carton Dec 19 '16 at 2:53
  • 1
    $\begingroup$ @Alex: If $|S|\le|\wp(\Bbb N)$, then by definition there is an injection $f:S\to\wp(\Bbb N)$, and $f[S]$ is then a subset of $\wp(\Bbb N)$ of the same cardinality as $S$, since $f\upharpoonright$ is a bijection from $S$ to $f[S]$. (You can get $\Bbb N$ with \Bbb N.) $\endgroup$ – Brian M. Scott Dec 19 '16 at 2:55

The answer to your titular question (call it "$\phi$") is that the usual axioms of set theory "$\mathsf{ZFC}$" (along with the assumption that $\mathsf{ZFC}$ is consistent; i.e. $\mathsf{ZFC}$ does not prove a contradiction "$\psi\,\wedge\,\neg\psi$") does not prove $\phi$, and does not prove $\neg\phi$.

Assume "the continuum hypothesis" does not hold. Therefore there exists a set $A$ such that


It seems your questions is:

Q: Can $A$ be a subset of $\mathscr{P}(\mathbb{N})$?

A: From $(1)$, $A$ does not have to be. Because $|A|<|\mathscr{P}(\mathbb{N})|$, there exists an injection

$$ f:A\hookrightarrow \mathscr{P}(\mathbb{N}) $$

Then the image of $f$ is a subset of $\mathscr{P}(\mathbb{N})$ with property $(1)$.

  • $\begingroup$ What happens if we work in $\mathsf{ZF}$? $\endgroup$ – MathematicsStudent1122 Dec 19 '16 at 3:55
  • 1
    $\begingroup$ @MathematicsStudent1122 How would that change things? Nothing in this answer assumes choice. $\endgroup$ – Noah Schweber Dec 19 '16 at 3:57
  • $\begingroup$ @NoahSchweber Right, never mind! $\endgroup$ – MathematicsStudent1122 Dec 19 '16 at 3:58

Alberto's answer is correct; let me add to it by addressing your question about what the undecidability of the continuum hypothesis (CH) means.

You write:

My only guess is that some set existing with cardinality between |N| and |P(N)| is not provable or disprovable

This is a reasonable guess, but it's not the only possibility. The other possibility is: maybe every subset of $P(\mathbb{N})$ that we can think of has cardinality that of either $\mathbb{N}$ or $P(\mathbb{N})$, but we can't prove that there isn't some other, weirder set we haven't thought of.

This latter is indeed the case. In fact, by results in descriptive set theory, we can prove that any counterexample to CH would have to be "hard to define" in various precise senses. So the issue is really the subsets of $P(\mathbb{N})$ which we haven't thought of. Maybe no counterexamples exist (this is what CH claims), but we'd have to prove that; showing that every "natural" set satisfies CH doesn't do the job.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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