I've read a few different presentations of Cohen's proof. All of them (that I've seen) eventually make a move where a Cartesian product (call it CP) between the (M-form of) $\aleph_2$ and $\aleph_0$ into {1, 0} is imagined. From what I gather, whether $CP \in M$ is what determines whether $\neg$CH holds in M or not such that if $CP \in M$ then $\neg$CH.

Anyway, my question is: Why does this product, CP, play this role? How does it show us that $\aleph_2 \in M$ (the 'relativized' form of $\aleph_2$, not the $\aleph_2 \in V$)? Could not some other set-theoretical object play the same role?

  • 1
    $\begingroup$ You could probably get a faster answer at mathoverflow.net . This is more of a mathematical question than it is a computer science one (not that I would mind a strong logic community in this forum). $\endgroup$
    – cody
    Dec 3, 2012 at 16:53
  • 3
    $\begingroup$ Didn't take that long :) $\endgroup$ Dec 3, 2012 at 18:45
  • $\begingroup$ That said, it still might make sense to migrate this Q over to math.SE since it's a much more natural fit there than in TCS-world... $\endgroup$ Dec 6, 2012 at 0:53

1 Answer 1


Our goal is to prove that $\aleph_1 < 2^{\aleph_0}$ in the model $M[G]$, and therefore the Continuum Hypothesis is not true in $M[G]$. This is equivalent to saying that $\aleph_2 \leq 2^{\aleph_0}$. So we need to construct a model $M[G]$ such that there is an injective map $f$ from $\aleph_2$ to $2^{\aleph_0}$ in $M[G]$. Note that each element of $2^{\aleph_0}$ is a function from $\aleph_0$ to $\{0,1\}$ (by definition). Thus $f(x)$ (the value of $f$ at point $x$) is actually a function that maps a natural number to $\{0,1\}$. In the proof, we treat $f$ as a function of two parameters $$h(x,y) = f(x)(y)$$ where $x\in \aleph_2$ and $y\in \aleph_0$. This is the reason why we want to prove that there exist a function $h$ from $\aleph_2 \times \aleph_0$ to $\{0,1\}$ satisfying certain properties.

The choice of $\aleph_2$ here is not arbitrary. Say, if we wanted to prove that $2^{\aleph_0} > \aleph_{19}$, we would consider functions from $\aleph_{20} \times \aleph_0$ to $\{0,1\}$.

BTW, $\aleph_2^M$ is always an element of $M$ and $M[G]$ (for any generic set $G$); on the other hand $\aleph_2$ is usually neither an element of $M$ nor $M[G]$, since $M$ is a countable transitive model of ZFC (or more precisely is a countable model of a large finite fragment of ZFC). So I'm not sure what you mean in the last paragraph.

  • 1
    $\begingroup$ Great explanation, Yury. As for the last paragraph, you are right, I skipped the qualification of $\aleph_2$ as the $\aleph_2$ within M (i.e. 'relativized' to M). $\endgroup$
    – djkern
    Dec 3, 2012 at 17:14
  • 1
    $\begingroup$ In some sense the choice of $\aleph_2$ is arbitrary, isn't it? i.e., there's no special property of $\aleph_2$ that's being used for the argument... $\endgroup$ Dec 5, 2012 at 23:36
  • $\begingroup$ @StevenStadnicki: I agree. We could choose any cardinal $\apha > \aleph_1$ instead and prove that $2^{\aleph_0} \geq \alpha$. That would also show that CH doesn't hold in our model. But at least, the choice of $\aleph_2$ in some sense is very natural. $\endgroup$
    – Yury
    Dec 6, 2012 at 0:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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