Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

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?

share|improve this question
1  
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). –  cody Dec 3 '12 at 16:53
3  
Didn't take that long :) –  Suresh Venkat Dec 3 '12 at 18:45
    
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... –  Steven Stadnicki Dec 6 '12 at 0:53
add comment

1 Answer 1

up vote 13 down vote accepted

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.

share|improve this answer
1  
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). –  djkern Dec 3 '12 at 17:14
1  
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... –  Steven Stadnicki Dec 5 '12 at 23:36
    
@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. –  Yury Dec 6 '12 at 0:00
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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