Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I'm trying to go through Timothy Chow's A Beginner's Guide to Forcing (arxiv pdf).

My particular question is about the first paragraph of Section $5$ (on p. $7$ of the above pdf).

First, my vague understanding of the broad idea of what's being done here, which anyone should feel to point out flaws in as well: we are crossing $\aleph_{2}$ with $\aleph_{0}$ and taking a function into $2 = \{0, 1\}$ (this is basically taking the power set of something, where $0$ means "exclude from subset" and $1$ means "include in subset"). More precisely, we are working with something that "looks like" $\aleph_{2}, \aleph_{0}$ in our countable standard transitive model $M$, but we note that $\aleph_{0}$ is absolute (in the sense given at the end of the previous section) so that really it's just the former that might be a bit different, hence we denote it as $\aleph_{2}^M$. The reason we have chosen $\aleph_{2}$ rather than $\aleph_{1}$ is we are hoping to "skip" over the latter and match up the powerset of $\aleph_{0}$ such that it is at least the size of $\aleph_2$; then we will have constructed a model satisfying 'not $CH$.'

The details, though, elude me. In particular, I am confused starting with: "We may interpret $F$ as a sequence of functions from $\aleph_0$ into $2$. Because $M$ is countable and transitive, so is $\aleph_{2}^M$; thus we can easily arrange for these functions to be pairwise distinct. Now, if $F$ is already in $M$, then $M$ satisfies 'not $ CH$'!"

Questions: I would be grateful if anyone could explain precisely what is meant by interpreting $F$ in the manner described above, what it means for $\aleph_{2}^M$ (a cardinal number) to be transitive (since the paper has defined it for a model), how we know the functions can be arranged to be pairwise distinct, and exactly why $F$ "shows us that the powerset of $\aleph_0$ in $M$ must be at least $\aleph_2$ in $M$."

Any additional assistance clarifying how forcing works would, of course, be welcomed as well.

share|cite|improve this question
I was deciding whether or not to go back to sleep, and this question made me get up. Then both Brian and Arthur answer, and I really have nothing to add... tough luck. :-) – Asaf Karagila Feb 18 '13 at 14:49
@AsafKaragila I'm sure you have something to add! If you feel up to writing out your own explanation, I can only imagine it would be helpful. The two answers here are already somewhat different in their phrasing; my feeling is that the more (good) answers, the better. – Benjamin Dickman Feb 18 '13 at 16:11
I will, but first I am going back to sleep for an hour or so. :-) – Asaf Karagila Feb 18 '13 at 16:15
I hope you didn't oversleep! – Benjamin Dickman Feb 19 '13 at 3:41
No, but I forget a lot. :-) (Today I did oversleep!) – Asaf Karagila Feb 20 '13 at 15:22
up vote 3 down vote accepted

Because $M$ is transitive, every element of $M$ is a subset of $M$. In particular, $\aleph_2^M$ is a subset of $M$. Since $M$ is countable, so is $\aleph_2^M$. Thus, in $V$ we may index $\aleph_2^M$ as $\{x_n:n\in\omega\}$. For each $n\in\omega$ define

$$F_n:\aleph_0\to\{0,1\}:k\mapsto F(x_n,k)\;;$$

if you know $F$, you know the functions $F_n$ for $n\in\omega$, and conversely, you can reconstruct $F$ from the functions $F_n$. $\langle F_n:n\in\omega\rangle$ is the sequence of functions that Chow has in mind when he says that we can think of $F$ as a sequence of functions from $\aleph_0$ to $2$.

Since there are uncountably many functions from $\aleph_0$ to $2$, we can certainly pick a sequence $\langle F_n:n\in\omega\rangle$ of distinct functions from $\aleph_0$ to $2$ and piece them together to form the function $$F:\aleph_2^M\times\aleph_0\to 2:\langle x_n,k\rangle\mapsto F_n(k)\;.$$ This function $F$ may or may not be in $M$. If it is, then from $M$’s point of view it provides an enumeration of $\aleph_2$ distinct functions from $\aleph_0$ to $2$, even though from our (or $V$’s) point of view $\aleph_2^M$ is only countable. That is, from $M$’s point of view there are actually $\aleph_2$ functions $F_n$, because the $x_n$’s are the elements of $\aleph_2^M$, the ordinal that $M$ ‘thinks’ is $\aleph_2$. In other words, if we let $f_{x_n}=F_n$ for each $n\in\omega$, then


where $f_\xi:\aleph_0\to 2:k\mapsto F(\xi,k)$ for each $\xi\in\aleph_2^M$. Since the $f_\xi$ for $\xi\in\aleph_2^M$ are all distinct, $\{f_\xi:\xi\in\aleph_2^M\}$ is from $M$’s point of view a family of $\aleph_2$ distinct functions from $\aleph_0$ to $2$.

The rest of the paper deals with what we do if $F\notin M$, i.e., how we add such an $F$ to $M$ without changing the rest of $M$ too much.

share|cite|improve this answer
Thanks for the detailed answer! – Benjamin Dickman Feb 19 '13 at 14:37
@B.D: You’re welcome! – Brian M. Scott Feb 19 '13 at 14:39
@Brian: You seem to be the only person I know (other than myself) who uses a curly quotation mark! =D – Haskell Curry Feb 26 '13 at 20:10

First note that cardinal numbers are just ordinals numbers of a particular kind. (Von Neumann) ordinals are transitive sets (since every ordinal is the set of all strictly smaller ordinals). I actually dislike using cardinal number notations (e.g., $\aleph_\alpha$) when cardinalities are not important, and will use ordinal notations below instead. Just remember that $\omega_\alpha = \aleph_\alpha$ as sets; the former is used generally to emphasize that it is an ordinal, and the latter that it is a cardinal.)

A function $F : \omega_2 \times \omega \to 2$ can be viewed as a ($\omega_2$-)sequence of functions $f_\alpha : \omega \to 2$ by defining $f_\alpha ( n ) = F ( \alpha , n )$ for all $\alpha < \omega_2$ and all $n < \omega$. Working inside a countable transitive model $M$ of ZFC we have $M$'s version of $\omega_2$, denoted $\omega_2^M$, as well as $M$'s version of $\omega$, which happens to be $\omega$. So consider some function $F : \omega_2^M \times \omega \to 2$. This function does not itself have to be in $M$. In the same way as above, we get an ($\omega_2^M$-)sequence of functions $f_\alpha : \omega \to 2$.

For these functions to be distinct the following must hold:

Given distinct $\alpha , \beta < \omega_2^M$ there is an $n \in \omega$ such that $f_\alpha ( n ) \neq f_\beta ( n )$.

As $\omega_2^M$ is countable we can find an injection $h : \{ ( \alpha , \beta ) : \alpha < \beta < \omega_2^M \} \to \omega$ and ensure that whenever $\alpha < \beta < \omega_2^M$ that $f_\alpha ( h ( \alpha , \beta ) ) \neq f_\beta ( h ( \alpha , \beta ) )$. (For instance, we can first assign $f_\alpha ( h ( \alpha , \beta ) ) = 0$ and $f_\beta ( h ( \alpha , \beta ) ) = 1$ for all $\alpha < \beta < \omega_2^M$, and afterwards fill in any undefined values by $0$.)

Now, if $F \in M$, then as $M$ is a model of ZFC it will follow that $f_\alpha \in M$ for all $\alpha < \omega_2^M$, and so $\{ f_\alpha : \alpha < \omega_2^M \} \subseteq ( {^{\omega}} 2 )^{M}$ (i.e., $M$'s version of the set of all functions $\omega \to 2$). Thus, it must be that $M \models | {^{\omega}}2 | = | \mathcal{P} ( \omega ) | \geq | \omega_2^M | = \aleph_2$, and so $M$ cannot satisfy the Continuum Hypothesis.

However, if $F \notin M$, then we would like to "add" $F$ to $M$ and create a new countable transitive model $M^*$ of ZFC. As above it will follow that $M^* \models | \mathcal{P}^{M^*} ( \omega ) | \geq | \omega_2^M |$. All that's left to do is ensure that $M^* \models | \omega_2^M | > \aleph_1$ and then $M^*$ will satisfy the negation of CH.

(This part of the paper appears to be introductory and does not go into details. Precisely how all of this is accomplished should be explained in further sections in the paper. I'm just noting the "plausibility" of this approach.)

share|cite|improve this answer
Thanks for your answer as well; I appreciate the multiple responses! – Benjamin Dickman Feb 19 '13 at 14:41
@B.D. I hope that it added a small bit after Brian's excellent answer; as happens too frequently for my liking I received the automated message saying that a new answer was posted and knew instinctively that it was either Brian or Asaf, and after reading the answer questioned whether or not I should even press the "Post Your Answer" button. – arjafi Feb 19 '13 at 15:55
Well, I'm glad you posted it. In fact, I was hoping Asaf would post a response too... – Benjamin Dickman Feb 19 '13 at 19:16
@B.D: After these two answers, I really have nothing to add. Sorry... :-) – Asaf Karagila Feb 20 '13 at 15:27

Your Answer


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.