\documentclass{amsart}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{mathabx}
\usepackage{stmaryrd}
\usepackage{mathbbol}


\theoremstyle{plain}
\newtheorem{thm}{Theorem}[section]
\newtheorem{cor}[thm]{Corollary}
\newtheorem{lem}[thm]{Lemma}



\theoremstyle{definition}
\newtheorem{defn}[thm]{Definition}
\newtheorem{exer}{Exercise}
\newtheorem{exam}{Example}


\theoremstyle{remark}
\newtheorem{rem}[thm]{Remark}
\newtheorem{fact}[thm]{Fact}
\newtheorem{hyp}[thm]{Hypothesis}

\newcommand{\Q}{\mathbb{Q}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\N}{\mathbb{N}}
\newcommand{\bP}{\mathbb{P}}
\newcommand{\bone}{\mathbb{1}}
\newcommand{\res}{\restriction}
\newcommand{\dom}{\operatorname{dom}}
\newcommand{\ran}{\operatorname{ran}}
\newcommand{\cof}{\operatorname{cof}}
\newcommand{\ot}{\text{o.t.}}
\newcommand{\on}{\text{ON}}
\newcommand{\card}{\text{CARD}}
\newcommand{\ac}{\text{AC}}
\newcommand{\zf}{\text{ZF}}
\newcommand{\zfc}{\text{ZFC}}
\newcommand{\sP}{\mathcal{P}}
\newcommand{\sL}{\mathcal{L}}
\newcommand{\ch}{\text{CH}}
\newcommand{\gch}{\text{GCH}}
\newcommand{\vb}{\text{var}}
\newcommand{\pa}{\text{PA}}
\newcommand{\fa}{\text{F}}
\newcommand{\con}{\text{CON}}


\newcommand{\bz}{\boldsymbol{0}}
\newcommand{\lD}{{\Delta}}
\newcommand{\lS}{{\Sigma}}
\newcommand{\lP}{{\Pi}}
\newcommand{\models}{\vDash}
\newcommand{\proves}{\vdash}
\newcommand{\sg}{\text{sg}}
\newcommand{\seq}{\text{Seq}}
\newcommand{\lh}{\text{lh}}
\newcommand{\pred}{\text{pred}}
\newcommand{\hod}{\text{HOD}}
\newcommand{\od}{\text{OD}}
\newcommand{\trcl}{\text{tr\,cl}}
\newcommand{\cl}{\text{cl}}
\newcommand{\rank}[1]{|#1|}
\newcommand{\llex}{<_{\text{lex}}}
\newcommand{\comp}{\parallel}
\newcommand{\forces}{\Vdash}
\newcommand{\fn}{\text{FN}}
\newcommand{\ccc}{\text{c.c.c.}}
\newcommand{\cc}{\text{c.c.}}
\newcommand{\sat}{\text{sat}}
\newcommand{\coll}{\text{coll}}




\begin{document}




\begin{center}
\bf Forcing and the Continuum
\end{center}
\bigskip



\section{Cardinal Arithmetic}


Our first goal is to show the independence of $\ch$ from 
$\zfc$. First consider the partial order for adding a single real
number $x \in 2^\omega$. One way would be to take the partial
order $\sP_1= \langle 2^{< \omega}, \leq \rangle$, that is, conditions
are finite sequences of $0$'s and $1$'s, and $p \leq q$ iff $p$ 
extends $q$. $\sP_1$ can thus be viewed as the full binary tree. 
Alternatively, we could consider $\sP_2$ which consists of all 
partial functions $p \colon \omega \{ 0, 1\}$ with finite support
(that is, a finite domain), and again ordered by extension. 
There is clearly a dense embedding (namely inclusion) of $\sP_1$
into $\sP_2$, and thus forcing with $\sP_1$ is equivalent to
forcing with $\sP_2$ by lemma~\ref{lemdenseem}. It is for the moment
a little more convenient to work with $\sP_2$. We will call this the
Cohen forcing, and refer to a generic $G$ for this forcing as a 
Cohen real. Technically a generic filter $G \subseteq \sP_2$
is not a real, but can be identified with one. Namely, let 
$x(n)= i$ iff $\exists p \in G\ (p(n)=i)$. This defines a function
as any two conditions in $G$ are compatible, and this function
has domain $\omega$ as $D_n= \{ p \colon n \in \dom(p) \}$
is dense for each $n \in \omega$. Clearly $M[G]=M[x]$, and 
we henceforth identify a generic with the corresponding real $x$. 
Although this produces a model $M[x]$ which satisfies 
$V \neq L$, and in fact $V \neq \hod$ (as we show later), 
adding a single real is not enough to change the value of the 
continuum function. To do this we must add more reals. 

Let us work in a model $M$ of (enough of) $\zf$, and 
let $\kappa$ be a cardinal (i.e., $(\kappa \in \card)^M$). 
The natural generalization of $\sP_2$ to add $\kappa$ many reals
would be the partial order $\fn (\kappa \times \omega , 2)=$
all partial functions from $\kappa \times \omega$ to 
$\{ 0, 1\}$ with finite support. We order again by extension,
that is $p \leq q$ iff $p \res \dom(q)=q$.
Of course, a function 
$F \colon \kappa \times \omega \to 2$ can be identified with a $\kappa$
sequence of functions $F_\alpha \colon \omega \to 2$, namely
$F_\alpha(n)=F(\alpha,n)$. A filter $G$ on 
$\fn (\kappa \times \omega ,2)$ can again be identified
with a partial function from $\kappa \times \omega $ to $2$. 
If $G$ is generic, then this function (which we will aslo call $G$)
has domain $\kappa \times \omega$. This is because for each $\alpha
< \kappa$, $n \in \omega$, the set $D_{\alpha,n}=\{ 
p \colon (\alpha,n) \in \dom(p) \}$ is dense. We summarize this
discussion in the following lemma.


\begin{lem} \label{lemcon1}
Let $M$ be a transitive model of $\zf$, $\kappa$ a cardinal of $M$,
and $G$ an $M$-generic for $\fn(\kappa \times \omega, 2)^M$. 
Then $G$ can be identified with a function $G \colon \kappa \times
\omega \to 2$. If $\{ G_\alpha \}){\alpha < \kappa}$ is the 
correspoding sequnce of reals, then $G_\alpha \neq G_\beta$ whenever 
$\alpha \neq \beta$. 
\end{lem}



\begin{proof}
If $\alpha \neq \beta$, then $D_{\alpha,\beta} = \{ 
p \colon \exists n \in \omega\ p(\alpha, n) \neq p(\beta,n) \}$
is dense (we mean here that both $p(\alpha,n)$, $p(\beta,n)$ are defined
and not equal). 
\end{proof}



Note that $\fn (\kappa\times \omega,2)$ is isomorphic to 
$\fn (\kappa,2)$, by taking a bijection between $\kappa \times \omega$
and $\kappa$. Thus, we may work with $\fn(\kappa,2)$ which is
notationally a little easier. 



If $G$ is generic for $\fn (\kappa,2)$, then from lemma~\ref{lemcon1}
in $M[G]$ we have $2^\omega \geq \kappa$. So, if we take $\kappa=
(\omega_2)^M$, then in $M[G]$ we have $2^\omega \geq (\omega_2)^M$. 
To get a model of $\neg \ch$, we also need to know that 
$(\omega_2)^M=(\omega_2)^{M[G]}$. 
In fact, we will show that this forcing preserves all cardinals and
cofinalities. There is a general principle involved which is
useful in many arguments. 



\begin{defn}
A partial order $\sP$ has the {\em countable chain condition}, or is 
said to be \ccc if every antichain $A \subseteq P$ is countable. 
More generally, $\sP$ is said to be $\kappa$-c.c. if every antichain 
$A \subseteq P$ has size $< \kappa$. The saturation of a 
partial order $\sat(\sP)$, also called its cellularity, is the least
$\kappa$ such that $\sP$ has the $\kappa$-c.c. 
\end{defn}


Thus, \ccc is the same as $\omega_1$-c.c.\ This definition is also made
for topological spaces: a topological space is $\kappa$-c.c. if 
every collection of pairwise disjoint open sets has size $< \kappa$. 
If we recall that every partial order $\sP$ can also
be viwed as a topological space (with basic open sets of the form 
$N_p=\{ q \colon q \leq p\}$), then the two definitions coincide. 


\begin{exer}
Show that for topological spaces $2^{\text{nd}}$ countable $\Rightarrow$
separable $\Rightarrow \ccc$. Give examples to show that the implications are
not reversible (hint: see the following exercise).
\end{exer}



\begin{exer}
Show that $\prod_{\alpha \in I} \R_{\text{std}}$ is \ccc (hint:see 
lemma~\ref{lemdelta} below).
\end{exer}



The significance of the notion of $\kappa$-c.c. for forcing is explained 
in the following lemma. 



\begin{lem} \label{cccov}
Let $M$ be a transitive model of $\zf$, and $\sP \in M$ a partial 
order which is wellorderable in $M$ and with 
$(\sP \text{ is } \kappa-c.c.)^M$. Let $G$ be $M$-generic for $\sP$. 
Then if $A,B \in M$ and $f \colon A \to B$ is a function, $f \in M[G]$,
then there is a function $F \colon A \to \sP(B)$, $F \in M$, with 
$f(a) \in F(a)$ for all $a \in A$ and $(\forall a \in A\ |F(a)| < \kappa)^M$.
\end{lem}


\begin{proof}
Let $tau \in M^\sP$ and $p \forces (\tau$ is a function from 
$\check{A}$ to $\check{B})$. Since $\sP$ is wellorderable, 
working in $M$ there is a
function $H \colon A \to \sP(P)$ satisfying:
\begin{enumerate}
\item
$\forall a \in A\ H(a)$ is an antichain in $P$.
\item
$\forall a \in A\ \forall p \in H(a)\ \exists b \in B \ (
p \forces \tau(\check{a})=\check{b}$.
\item
$H(a)$ is maximal subject to $(1)$ and $(2)$.
\end{enumerate}
Working still in $M$, 
let $F(a)= \{ b \in B \colon \exists p \in H(a)\ (p \forces 
f(\check{a})=\check{b}) \}$. Since $| H(a) | < \kappa$, 
$| F(a)| < \kappa$ as well. If $f(a)=b \in B$, then for some
$p \in P$, $p \forces (\tau(\check{a})= \check{b})$.
By $(3)$, there is a $q \in H(a)$ such that $p \parallel q$. 
Let $r \leq p,q$. So, $r \forces (\tau(\check{a})= \check{b})$. 
Since $q \in H(a)$, $q \forces (\tau(\check{a})= \check{c})$
for some $c \in b$, and we must have $b=c$. So, $b \in H(a)$. 
\end{proof}



\begin{defn}
Let $M$ be a transitive model of $\zf$ and $\sP \in M$. 
We say $\sP$ preserves cardinals if $(\kappa \in \card)^M 
\leftrightarrow (\kappa \in \card)^{M[G]}$. We say $\sP$ 
preserves cardinals $\leq \lambda$ (or $\geq \lambda$, $< \lambda$, etc.)
if for all $\kappa \leq \lambda$, $(\kappa \in \card)^M 
\leftrightarrow (\kappa \in \card)^{M[G]}$. 
We say $\sP$ preserves cofinalities if for all $\alpha \in \on \cap M$,
$(\cof(\alpha)^M=(\cof(\alpha))^{M[G]}$. We say $\sP$ preserves
cofinalities $\leq \lambda$ (or $\geq \lambda$, etc.) if 
whenever $(\cof(\alpha) \leq \lambda)^M$ then 
$\cof(\alpha)^M=\cof(\alpha)^{M[G]}$. 
\end{defn}



We note two simple facts.


\begin{fact}
If $M$ is a transitive model of $\zf$ and $\sP \in M$, then 
$\sP$ preseves cofinalities iff for all $\kappa \in M$, 
$(\kappa$ is regular$)^M \leftrightarrow(\kappa$ is regular$)^{M[G]}$. 
Similarly, if 
$(\kappa$ is regular$)^M \leftrightarrow(\kappa$ is regular$)^{M[G]}$
for all $\kappa \leq \lambda$ (or $\kappa \geq \lambda$), then 
$\sP$ preserves cofinalities $\leq \lambda$ (or $\geq \lambda$).
\end{fact}

\begin{proof}
We prove the first statement, the other being essentially the same.
Suppose $(\cof(\alpha)=\lambda)^M$, so $(\lambda$ is regular $)^M$. 
Let $f \colon \lambda \to \alpha$, $f \in M$,  be increasing and cofinal.
By assumption, $\lambda$ is regular in $M[G]$. From lemma~\ref{cof2}
we have in $M[G]$ that $\cof(\alpha)=\cof(\lambda=\lambda$.
\end{proof}


\begin{fact}
If $M$ is a transitive model of $\zfc$ and $\sP \in M$, then if 
$\sP$ preserves cofinalities then it preserves cardinals. Similarly,
if $\sP$ preserves cofinalities $\leq \lambda$, then it preserves 
cardinals $\leq \lambda$. If $\sP$ preserves cardinals $\geq \lambda$
and $(\lambda$ is regular$)^M$, then $\sP$ preserves cardinals
$\geq \lambda$. 
\end{fact}




\begin{proof}
We prove by induction on the cardinals $\kappa$ of $M$ that they
are cardinals of $M[G]$. For limit cardinals $\kappa$ of $M$
the inductive step is trivial (since a limit or cardinals is a cardinal).
If $\kappa$ is a successor cardinal of $M$, then since $M$ satisfies
$\zfc$, $\kappa$ is regular in $M$. By assumption, $\kappa$ is regular 
in $M[G]$, and hence is a cardinal of $M[G]$. 
\end{proof}




\begin{thm}
Let $M$ be a transitive model of $\zf$, and $\sP \in M$ with $(\sP
\text{ is } \kappa \cc)^M$, where $\kappa$ is a regular cardinal of
$M$.  Then $\sP$ preserves cardinals $\geq \kappa$ and preserves
cofinalities $\geq \kappa$.
\end{thm}


\begin{rem}
Tarski's theorem \ref{thmtarski} says that $\sat(\sP)$ is 
always a regular cardinal (assuming $\zfc$ or $P$ is wellorderable). 
Thus, there is no loss of generality in assuming the $\kappa$ of the
lemma is a regular cardinal in $M$.
\end{rem}


\begin{proof}
We first show $\sP$ preserves cardinals $\geq \kappa$. 
Let $\lambda \geq \kappa$ with $(\lambda \in \card)^M$. 
Suppose $(\lambda \notin \card)^{M[G]}$. Let $f \colon 
\alpha \to \lambda$ be onto, where $f \in M[G]$ and $\alpha < \lambda$. 
By lemma~\ref{cccov}, there is a $F \in M$ with 
$F \colon \alpha \to \sP(\lambda)$, $f(\beta) \in F(\beta)$
for all $\beta < \alpha$, and $(|F(\beta)| < \kappa)^M$
for all $\beta < \alpha$. 
If $\lambda=\kappa$, then $F$ expresses, in $M$, $\kappa$ as a union
of $\alpha$ ($< \kappa$) union of sets each of which has size $< \kappa$,
a contradiction to the regularity of $\kappa$ in $M$. 
If $\lambda > \kappa$, then in $M$ $F$ gives a map from 
$\alpha \cdot \kappa$ onto $\lambda$, a contradiction as $\lambda$
is a cardinal in $M$. 

To see $\sP$ preserves cofinalities $\geq \kappa$, let $\lambda \geq \kappa$
with $(\lambda$ is a regular cardinal$)^M$. 
If $\lambda$ is not regular in $M[G]$, let $f\in M[G]$ with 
$f \colon \alpha \to \lambda$ cofinal, for some $\alpha < \lambda$. 
Let $F \in M$ be as in lemma~\ref{cccov}. Since $\rho$ is regular in $M$,
each $F(\beta)$ is a bounded subset of $\lambda$. By regularity of 
$\rho$ again, $F$ has bounded range in $\lambda$, a contradiction
as $f(\beta) \in F(\beta)$ and $f$ is cofinal.
\end{proof}




\begin{cor} \label{corcardpres}
If $M$ is a transitive model of $\zf$, $\sP \in M$ and 
$(\sP \text{ is} \cc)^M$, then $\sP$ preserves all cardinals and
cofinalities. 
\end{cor}



We now show that the Cohen poset for adding an arbitrary number
of real, that is $\fn(\kappa,2)$, is \ccc{} The following
combinatorial lemma embodies the heart of the proof. It is 
known as the $\lD$-system lemma.



\begin{lem} \label{dsystem}
Let $\alpha \in \on$ and $A$ an uncountable collection of finite
subsets of $\alpha$. Then there is a ``root'' $r \in A^{< \omega}$
and an uncountable $B \subseteq A$ such that $r \subseteq s$
for all $s \in B$, and $\{ s-r \colon s \in B\}$ are pairwise disjoint.
\end{lem}


\begin{proof}
Without loss of generality we may assume $|A|=\omega_1$ (note that 
$A$ is wellorderable, so there is no problem discussing its
cardinality). Replacing $\alpha$ with $\cup A$, we may assume 
$|\alpha |=\omega_1$, and by taking a bijection with $\omega_1$
we may assume $\alpha=\omega_1$.
Write each element of $A$ in the form $s=(\alpha_0(s),\dots,\alpha_k(s))$
where $\alpha_0< \dots < \alpha_k < \omega_1$. 
Thinning out $A$, we may assume that each $s \in A$ has size $k+1$ 
for some fixed $k \in \omega$. For $l \leq k$, let 
$$\beta_l= 
\sup \{ \alpha_l \colon s=(\alpha_0,\dots,\alpha_l,\dots \alpha_k) \in A\}.
$$
Note that $\beta_0 \leq \beta_1 \leq \dots \leq \beta_k$. 
If $\beta_k < \omega_1$, then every $s \in A$ is a subset of
the countable ordinal $\beta_k$. This is impossible as there are only
countably many finite subsets of $\beta_k$.  So, let $l \leq k$
be least such that $\beta_l= \omega_1$. Inductively choose
$A_1 =\{ t_\gamma \}_{\gamma < \omega_1} \subseteq A$
such that if $\gamma_1 < \gamma_2$ then $\alpha_k(t_{\gamma_1})
< \alpha_l(t_{\gamma_2})$. Since $\alpha_0(s), \dots, \alpha_{l-1}(s)
< \beta_{l-1} < \omega_1$ for all $s \in A_1$, there is an uncountable
$B \subseteq A_1$ and $\alpha_0 < \dots < \alpha_{l-1}$
such that $(\alpha_0(s), \dots, \alpha_{l-1}(s))=
(\alpha_0 < \dots < \alpha_{l-1})$ for all $s \in B$. Then $B$ is as
desired, with the root of the ``$\lD$-system'' being 
$r=\{ \alpha_0,\dots,\alpha_{l-1} \}$.
\end{proof}


\begin{lem} \label{lemcc}
For any $\kappa$, $\fn (\kappa,2)$ is c.c.c.
\end{lem}

\begin{proof}
Suppose $\{ p_\alpha \}$ were an uncountable antichain. Let 
$s_\alpha= \dom(p_\alpha)$. From lemma~\ref{dsystem} we may 
assume the $s_\alpha$ form a $\lD$ system with root $r$. However, 
there are only finitely many possibilities for $p \res r$ and so we 
may get $\alpha, \beta < \omega_1$ with $p_\alpha \res r= 
p_\beta \res r$. Then $p_\alpha$, $p_\beta$ are compatible, a contradiction.
\end{proof}





Summarizing, we have now show the following.


\begin{thm} \label{thmnch}
Let $M$ be a transitive model of $\zf$ anf $\sP=\fn( \omega_1^M,2)$. 
Let $G$ be $M$-generic for $\sP$. Then $(2^\omega \geq \omega_2)^{M[G]}$.
\end{thm}


\begin{proof}
Let $\kappa= \omega_2^M$. Then in $M[G]$ there is a $\kappa$
sequence of distinct reals. From lemma~\ref{dsystem} and
corollary~\ref{corcardpres} we have that $\omega_2^M=(\omega_2)^{M[G]}$.
Thus $($There is an $\omega_2$ sequence of distinct reals$)^{M[G]}$.
So, $(\neg \ch)^{M[G]}$.
\end{proof}


From theorem~\ref{thmnch} and our previous metamathematical
remarks on forcing, we now have the following.

\begin{cor}
$\zfc$ does not prove $\ch$.
\end{cor}


Thus, the continuum hypothesis is not provable from within $\zfc$
set theory. 


Although G\"{o}del's model $L$ provides a model of $\ch$ (in fact $\gch$), 
we can also use forcing to get a model of $\ch$. This also introduces another
very useful forcing poset. 







\begin{defn}
$\coll (\omega, \kappa)$ is the poset of all partial functions $p \colon 
\omega \to \kappa$ with finite domain. The partial functions are ordered by 
$p \leq q $ iff $p$ extends $q$. 
More generally, if $\lambda < \kappa$
are cardinals with $\lambda$ regular, then 
$\coll(\lambda, \kappa)$ is the poset of partial
functions $p \colon \lambda \to \kappa$ with $|\dom(p)| < \lambda$.
\end{defn}




Easily, in any generic extension by $\coll (\lambda, \kappa)$
we will have $|\lambda|=|\kappa|$. Thus, this forcing collapses
$\kappa$ to have cardinality $\lambda$. We would like to show, though,
that the forcing does not add any bounded subsets of $\lambda$. 
This brings us to another important property of partial orders. 



\begin{defn}
We say a poset $\sP$ is $\leq \lambda$ closed (or $< \lambda$ closed)
is whenever $\alpha \leq \lambda$ (respectively, $\alpha < \lambda$)
and $p_0 \geq p_1 \geq \dots \geq p_\beta \geq \dots$, $\beta< \alpha$,
is an $\alpha$-decreasing sequence in $P$, then there is a $p \in P$
with $p \leq p_\beta$ for all $\beta < \alpha$. We say $P$ is 
$\leq \lambda$ (or $< \lambda$) distributive if whenever $\alpha \leq \lambda$
($\alpha < \lambda$) and $\{ D_\beta \}_{\beta < \alpha}$ are dense in $P$,
then $\{ p \colon \forall \beta < \alpha\ \exists q \in D_\beta\
(p \leq q) \}$ is dense. 
\end{defn}



The name distributive comes from the fact if $P$ is a complete Boolean
algebra, then the definition of $\leq \lambda$ distributive
is equivalent to saying $P$ satisfies the $\lambda$-length distributive
law: $\prod_{\alpha < \lambda} \sum _{\beta \in I_\alpha} a_{\alpha,\beta}
= \sum_{f \in \prod I_\alpha} \prod_{ \alpha < \lambda} a_{\alpha, f(\alpha)}$.
[brief sketch: let $b$ the left-hand side, and $c$ the right-hand side.
Clearly $c \leq b$. Suppose $b-c \neq 0$. For each $\alpha < \lambda$
let $D_\alpha=\{ p \colon (\forall \beta \in I_\alpha\ (p \perp 
a_{\alpha, \beta})) \vee (\exists \beta \in I_\alpha\ 
(p \leq a_{\alpha, \beta})) \}$. Each $D_\alpha$ is clearly dense. 
By assumption, $D=\{ p \colon \forall \alpha < \lambda\ \exists 
q \in D_\alpha\ (p \leq q) \}$ is dense. 
Let $u \in D$ with $u \leq b-c$. 
Then either for all $\alpha < \lambda$ we have $u \leq a_{\alpha,\beta}$
for some $\beta \in I_\alpha$, or else for some $\alpha$, $p$ is 
incompatible with all elements $a_{\alpha, \beta}$. In the first case,
this defines a function $f \in \prod I_\alpha$ such that 
$u \leq a_{\alpha, f(\alpha)}$ for all $\alpha < \lambda$, and hence 
$u \leq \prod _{\alpha < \lambda} a_{\alpha, f(\alpha)}$. 
This shows $u \leq c$, a contradiction. In the second case, 
$ u \perp \sum_{\beta \in I_\alpha} a_{\alpha, \beta}$ for some
$\alpha$, and thus $u \perp b$, also a contradiction.]



It is easy to see that $\leq \lambda$ closed (or $< \lambda$ closed)
implies $\leq \lambda$ (or $< \lambda$) distributive. 
To see this, let $D_\beta$, $\beta < \alpha$ be dense. Let $p \in P$. Define
inductively for $\beta \leq \alpha$ an element $p_\beta$ such that 
$p \geq p_0 \geq p_1 \geq \dots \geq p_\beta$ where $p_\beta
\in D_\beta$. We can do this as $P$ is  $\leq \lambda$ closed, say. 
Then $p_\alpha \leq p$ and $p_\alpha$ extends elements in each of the 
$D_\beta$. 


\begin{exer}
Show that id $\sP$ is $\leq \lambda $ distributive and 
$D_\alpha$, $\alpha < \lambda$ are all dense below $p \in P$,
then any generic filter containing $p$ contains a 
$q \in G$  such that $\forall \alpha < \lambda\ \exists r \in D_\alpha\
(q \leq r) \}$.
\end{exer}





In practice, most of the posets we see which are $\lambda$-distributive
are actually $\lambda$-closed, but the proof of the main fact
goes through for the notion of $\lambda$-distributive.
This is expressed in the following lemma. 





\begin{lem} \label{lemclosed}
Let $M$ be a transitive model of $\zf$, and $\sP \in M$
be  $\leq \lambda$ distributive in $M$. Let $G$ be $M$
generic for $\sP$. If $f \colon \lambda \to M$ is a function
in $M[G]$, then $f \in M$. 
\end{lem}


\begin{proof}
Let $f=\tau_G$. Let $q \forces (\tau$ is a function with domain
$\check{\lambda})$, with $q \in G$. For each $\alpha < \lambda$, let 
$D_\alpha=\{ p \colon \exists x \in M \ (p \forces \tau(\check{\alpha})
= \check{x}) \}$. Clearly each $D_\alpha$ is dense below $q$. 
Thus there is a $r \in G$ which extends elements of each $D_\alpha$.
So, $\forall \alpha < \lambda\ \exists ! x \in M\ (r \forces
\tau(\check{\alpha})=\check{x})$. This shows $f$ is definable in $M$
and so is in $M$ (by replacement in $M[G]$ we may assume 
the given $f$ has range in a set in $M$). 
\end{proof}



We have the following fact whose proof is immediate.

\begin{lem}
If $\lambda$ is regular and $\lambda < \kappa$, then 
$\coll (\lambda, \kappa)$ is $< \lambda$-closed.
\end{lem}


\begin{thm}
Let $M$ be a transitive model of $\zfc$, and 
$\sP=(\coll(\omega_1,2^\omega))^M$. Then for any $G$ which is
$M$-generic over $\sP$, $(2^\omega=\omega_1)^{M[G]}$.
\end{thm}


\begin{proof}
Since $G$ gives a function from $\omega_1^M$ onto $(2^\omega)^M$,
we have $(|(2^\omega)^M| \leq |\omega_1|^M \leq \omega_1)^{M[G]}$.
Since $\sP$ is $< \omega_1$ closed in $M$, we have that 
$\sP(\omega)^M=\sP(\omega)^{M[G]}$. So, $(2^\omega \leq \omega_1)^{M[G]}$.
\end{proof}


\begin{cor}
$\zfc$, if it is consistent, cannot prove $\neg \ch$. 
\end{cor}


We now know that $\ch$ is independent of $\zfc$; that is,  
$\zfc$ set theory can neither prove $\ch$ nor prove
$\neg \ch$. 








\section{More on the Continuum Function}


We will show a little later that starting with a model $M$ 
of $\zfc$ we may force over $M$ to get a model of $\zfc + \gch$. 
Furthermore, starting with a model of $\zfc+\gch$ we may then 
force to get a model of $\zfc$ where the continuum function 
takes any values on the regular cardinals consistent with 
monotonicity (if $\kappa < \lambda$ then $2^\kappa \leq 
2^\lambda$), Cantor's theorem ($2^\kappa > \kappa$) and 
K\"{o}nig's theorem ($\cof(2^\kappa)>\kappa$). In this section, we 
prove a warm-up version. 

First we show that we may force to get the $\gch$ up to 
any $\omega_n$.


\begin{lem} \label{lemfingch}
Let $M$ be a countable transitive model of $\zfc$.  Then for every $n
\in \omega$ there is a generic extension $M[G]$ such that $(\forall k
\leq n\ 2^{\omega_k}=\omega_{k+1})^{M[G]}$.
\end{lem}



\begin{proof}
Let $M$ be a countable transitive model of $\zfc$. 
Let $\sP_0= (\coll(2^\omega, \omega_1)^M$. So, $\sP_0 \in M$
and is $< \omega_1$ closed in $M$. Let $G_0$ be $M$ generic for
$\sP_0$. Let $M_1=M[G_0]$. 
Then $(2^\omega=\omega_1)^{M_1}$. Let 
$\sP_1=(\coll (2^{\omega_1}, \omega_2))^{M_1}$. So, $\sP_1$ is 
$< (\omega_2)^{M_1}$ closed in $M_1$. Let $G_1$ be $M_1$ generic
for $\sP_1$. Let $M_2=M_1[G_1]$. Since forcing with $\sP_1$
does not add any new subsets of $\omega$, we have 
$(2^\omega)^{M_1}=(2^\omega)^{M_2}$ and $(\omega_1)^{M_1}=
(\omega_1)^{M_2}$. Thus, we still have $(2^\omega=\omega_1)^{M_2}$. 
We clearly have $(| 2^{\omega_1} |^{M_1} \leq | (\omega_2)^{M_1}| \leq
\omega_2)^{M_2}$, and thus $((2^{\omega_1})^{M_1} \leq \omega_2)^{M_2}$. 
Since forcing with $\sP_1$
does not add any new subsets of $\omega_1$, we also have 
$(2^{\omega_1})^{M_1}=(2^{\omega_1})^{M_2}$. We now have 
$(2^{\omega_1 } \leq \omega_2)^{M_2}$, and so 
$(2^\omega=\omega_1 \wedge 2^{\omega_1 } = \omega_2)^{M_2}$. 
Continuing in this manner we finish.
\end{proof}




The partial orders $\fn (\kappa,2)$ and $\coll (\kappa, \lambda)$
are both special cases of the following.


\begin{defn}
$\fn (\kappa, \lambda, \rho)$ is the partial order of 
partial functions $p \colon \kappa \to \lambda$ with $|\dom(p)|
< \rho$. We define $p \leq q$ iff $p$ extends $q$.
\end{defn}


Thus, $\fn(\kappa,2)=\fn(\kappa,2, \omega)$, and 
$\coll(\kappa,\lambda)=\coll(\kappa,\lambda, \kappa)$. 



The following generalizes lemma~\ref{lemcc}.


\begin{lem} \label{lemgcc}
$\fn (\kappa, \lambda, \rho)$ is $(\lambda^{< \rho})^+$ c.c.
\end{lem}



\begin{proof}
Suppose $A \subseteq \fn (\kappa, \lambda, \rho)$ is an antichain
of size $(\lambda^{< \rho})^+$. 
Let $\delta= (\lambda^{< \rho})^+$, so $\delta$ is regular. 
Note that $\delta > \rho$.
Let $A=\{ p_\alpha \}_{\alpha < \delta}$, and let $d_\alpha=
\dom(p_\alpha)$. Without loss of generality we may assume that 
$\kappa=\delta$ (there are at most $\rho \cdot \delta=\delta$
elements of $\bigcup_{\alpha < \delta} d_\alpha$). Since $\delta$ is regular
and $\delta > \rho$, there is a $\tau < \rho$ such that for $\delta$
many $\alpha$ we have $\ot (d_\alpha)=\tau$. So, we may assume 
$\ot(d_\alpha) =\tau$ for all $\alpha < \delta$. For $\beta < \tau$ let 
$\eta(\beta) = \sup \{ d_\alpha(\beta) \colon \alpha < \delta\}$, where 
$d_\alpha(\beta)$ denotes the $\beta^{\text{th}}$ element of 
$d_\alpha$. For some $\beta < \tau$ we must have $\eta(\beta)=\delta$,
for otherwise, since $\delta > \tau$ is regular, we would have that 
$\sup_{\beta< \tau} \eta(\beta) < \delta$. This would say that all
of the $d_\alpha$ are subsets of some $\delta' < \delta$. Hence,
$|\{ d_\alpha \}|| 
\leq (\delta')^\tau$. But, $|\delta' |\leq \lambda^{< \rho}$,
so $ (\delta')^\tau \leq \lambda^{< \rho \cdot \tau} =\lambda^{< \rho}
<\delta$. Hence $|A| \leq \lambda^{< \rho} \cdot \lambda ^\tau < \delta$,
a contradiction.

Let $\beta_0< \tau$ be least such that $\eta(\beta_0) = \delta$. 
Since $\delta$ is regular, it is straightforward using the definition
of $\beta_0$ to thin 
$\{ d_\alpha \}$ to a subsequence of size $\delta$ such that 
if $\alpha_1 < \alpha_2$ then $\sup(d_{\alpha_1}) < d_{\alpha_2}(\beta_0)$.
We assume that the $d_\alpha$ now have this property. Let 
$\eta=\sup \{ \eta(\beta) \colon \beta < \beta_0\}$. By regularity
of $\delta$, $\eta < \delta$. We have $d_\alpha \res \beta_0
\subseteq \eta$. However there are then at most $\eta ^\tau < \delta$
(as argued above) many possibilities for $d_\alpha$. 
So, we may assume the $d_\alpha$ are are equal to some fixed $d$.
But then there are only $\lambda^\tau <\delta$ many possibilities
for $p_\alpha \res d$. Thus we may assume all the $p_\alpha$
agree on $d$. But any two such $p_\alpha$ are compatible, a 
contradiction.
\end{proof}



To compute the cardinality of the subsets of $\kappa$ in $M[G]$,
we need to have a reasonable representation for the subsets of 
$\kappa$ in $M[G]$. The following lemma, which does that, is a refinement
of the argument used to show the power set axiom in $M[G]$. 


\begin{lem} \label{lemnice}
Let $M$ be a transitive model of $\zf$, and $\sP \in M$. 
Let $\tau \in M^\sP$. Let $\mu \in M^\sP$. Then there is a
{\em nice name} (for a subset of $\tau$) 
$\sigma \in M^\sP$ such that $\bone \forces 
(\mu \subseteq \tau \rightarrow \mu = \sigma)$. By a nice name we mean
a name of the form $\bigcup_{\pi \in \dom(\tau)} \pi \times A_\pi$,
where $A_\pi \subseteq P$ is an antichain. 
\end{lem}


\begin{proof}
Let $\sigma=\{ \langle \pi ,p \rangle \colon \pi \in \dom (\tau) 
\wedge (p \forces \pi \in \mu) \}$. Let $G$ be $M$ generic for $\sP$.
We must show that $(\mu_G \subseteq \tau_G \rightarrow 
\mu_G= \sigma_G)$. So, assume $\mu_G \subseteq \tau_G$. 
If $z \in \sigma_G$, then $z= \pi_G$ where $p \forces \pi \in \mu$
and $p \in G$. So, $z=\pi_G \in \mu_G$. For the other direction, assume
$z \in \mu_G$. Since $\mu_G \subseteq \tau_G$, $z= \pi_G$ for
some $\langle \pi ,p \rangle \in \tau$ with $p \in G$. 
Let $q \leq p$ with $q \forces \pi \in \mu$. Then $\langle \pi ,q \rangle
\in \sigma$ and $q \in G$, so $z=\pi_G \in \sigma_G$. 
\end{proof}



In particular, every subset of an ordinal $\alpha$ in $M[G]$
has a name of the form $\bigcup_{\beta < \alpha} 
(\check \beta \times A_\beta)$, where the $A_\beta$ are antichains. 




\begin{lem} \label{lemupbd}
Let $M$ be a transitive model of $\zfc$ and $\sP \in M$ be $\lambda$-c.c.\ 
Let $G$ be $M$ generic for $P$, and $\kappa$ a cardinal of $M[G]$.
Then in $M[G]$ we have $2^\kappa \leq [(|P|^{< \lambda})^\kappa]^M$. 
\end{lem}


\begin{proof}
Since $P$ is $\lambda$-c.c., there are at most $(|P|^{< \lambda})^M$ many 
antichains of $P$ which lie in $M$. Thus, there are at most
$[(|P|^{< \lambda})^\kappa]^M$ many 
nice names for a subset of $\kappa$ which lie in $M$. In $M[G]$, there
is a map from this set of nice names onto $\sP(\kappa)$ by 
lemma~\ref{lemnice}.
\end{proof}


We now show that starting with a model of $\gch$, we may force
to get the continuum function to take arbitrary values on finitely 
many regular cardinals, subject to monotonicity and Cantor's and
K\"{o}nig's theorems.




\begin{lem} \label{lemfinreg}
Let $M$ be a countable transitive model of $\zfc+\gch$. 
Let $\kappa_1 < \dots < \kappa_n$ be regular in $M$. 
Let $\lambda_1 \leq \dots \leq \lambda_n$ be cardinals of $M$
with $\cof(\lambda_i) > \kappa_i$. Then there is a forcing extension
$M[G]$ of $M$ which preserves all the cardinals and cofinalities 
of $M$ and such that
$(2^{\kappa_1}=\lambda_1 \wedge \dots \wedge 2^{\kappa_n}=\lambda_n)^{M[G]}$.
\end{lem}


\begin{proof}
Let $M_0=M$. We construct a sequence of forcing extensions 
$M_0 \subseteq M_1 \subseteq \dots \subseteq M_n$, each of which will
preserve cardinals and cofinalities. Assume inductively that 
$M_i$ has been defined and 

\begin{enumerate}
\item \label{u1}
$M$ and $M_i$ have the same functions $f \colon \kappa \to \on$,
for all $\kappa < \kappa_{n-i+1}$.
\item \label{u2}
$ (\forall \kappa < \kappa_{n-i+1}\ (2^\kappa=\kappa^+))^{M_i}$.
\item \label{u3}
$(2^{\kappa_{n-i+1}}=\lambda_{n-i+1} \wedge \dots \wedge 2^{\kappa_n}
=\lambda_n )^{M_i}$.
\end{enumerate}
Note that (\ref{u1}) implies (\ref{u2}) given that cardinals are
preserved from $M$ to $M_i$. 
Let $\sP= \fn( \kappa_{n-i} \times \lambda_{n-i},2, \kappa_{n-i})^{M_i}
\cong \fn( \lambda_{n-i},2, \kappa_{n-i})^{M_i}$. Thus, in $M_i$, 
$\sP$ is $(2^{< \kappa_{n-i}})^+= \kappa_{n-i}^+$-c.c.\ 
Since $\sP$ is $< \kappa_{n-i}$ closed, it preseves all 
cardinals and cofinalities $\leq \kappa_{n-i}$. 
Since $\sP$ is  $\kappa_{n-i}^+$-c.c.\ it preserves all cardinals
and cofinalities $> \kappa_{n-i}$. Thus, $\sP$ preserves
all cardinals and cofinalities. Since $\sP$ is again 
$< \kappa_{n-i}$ closed, it adds no new functions 
$f \colon \kappa \to \on$ for $\kappa < \kappa_{n-i}$. 
Thus, (\ref{u1}) and (\ref{u2}) hold for $M_{i+1}$. 
We clearly have $(2^{\kappa_{n-i}} \geq \lambda_{n-i})^{M_{i+1}}$.
By (\ref{u1}), $(\lambda_{n-i}^{\kappa_{n-i}})^{M_i}=
(\lambda_{n-i}^{\kappa_{n-i}})^M$. Since $(\cof(\lambda_{n-i}) >
\kappa_{n-i})^M$ it follows from the $\gch$ in $M$ that 
$(\lambda_{n-i}^{\kappa_{n-i}} = \lambda_{n-i})^M$. Thus,
$(\lambda_{n-i}^{\kappa_{n-i}} = \lambda_{n-i})^{M_i}$. 
In $M_i$, $\sP$ has cardinality at most 
$\sum_{\kappa < \kappa_{n-i}} \lambda_{n-i}^\kappa = \lambda_{n-i}$.
From lemma~\ref{lemupbd} $(2^{\kappa_{n-i}} \leq 
(\lambda_{n-i}^{\kappa_{n-i}})^{\kappa_{n-i}} = \lambda_{n-i})^{M_{i+1}}$.
\end{proof}





As a corollary of lemmas~\ref{lemfinreg} and \ref{lemfingch},
it follows that starting with a countable transitive model 
$M$ of $\zfc$, we may get a forcing extension $M[G]$ in which
the continuum function moves the first $n$ many infinite cardinals
to any other $\omega_m$'s, subject to monotonicity and
Cantor's theorem (K\"{o}nig's theorem is irrelevant as all of the
$\omega_m$ are regular). For example:


\begin{cor}
If $\zfc$ is consistent, then so is 
$\zfc + 2^\omega=\omega_5 \wedge 2^{\omega_1}= \omega_8 \wedge 
2^{\omega_2}=\omega_8 \wedge 2^{\omega_7}=\omega_9$.
\end{cor}


\begin{exer}
Compute the continuum function in the model $M[G]$
of lemma~\ref{lemfinreg}.
\end{exer}




\section{Tarski's Theorem}


We prove the following theorem, valid for any partial order.



\begin{thm} ($\zfc$) \label{thmtarski}
Let $\sP= \langle P, \leq \rangle$ be a partial order. Then 
$\sat(P)$ is a regular cardinal. 
\end{thm}


\begin{proof}
Let $\kappa= \sat(P)$, so every antichain of $P$ has size $< \kappa$,
but for every $\lambda < \kappa$ there is an antichain of $P$
of size $\lambda$. Suppose $\cof(\kappa)=\rho < \kappa$. 
Let $B=\{ p \colon \forall q \leq p \ (\sat(q)=\kappa) \}$, where
$\sat(q)= \sup \{ |A| \colon A \subseteq N_q \text{ is an antichain }\}$
(recall $N_q =\{ r \colon r \leq q\}$). Suppose first that $B \neq \emptyset$,
and let $p \in B$. Let $A \subseteq N_p$ be an antichain of size 
$|A| = \rho$. For each $q \in A$, let $A_q \subseteq N_q$ be an
antichain of size $f(q)< \kappa$, where $f \colon A \to \kappa$ is
cofinal (we may do this since $p \in B$). Then $\bigcup_{q \in A}A_q$
is an antichain of $P$ of size $\kappa$, a contradicion. 

Suppose next that $B = \emptyset$. Let $D= \{ p \colon 
\sat(p) < \kappa \}$. Thus, $D$ is dense. Let $A \subseteq P$
be maximal subject to $A$ being an antichain and $A \subseteq D$. 
Since $D$ is dense, $A$ is easily a maximal antichain, that is,
for every $q \in P$ there is a $p \in A$ such that $q \parallel p$. 
By assumption, $|A| < \kappa$. Also, we must have 
$\sup \{ \sat(p) \colon p \in A\} = \kappa$. This is because for any regular
$\lambda < \kappa$ with $\lambda > |A|$ 
there is an antichain of $P$ of size $\lambda$,
and there must be a single $p \in A$ such that $\lambda$ many 
elements of this antichain are compatible with $p$ (this then gives
an antichain of size $\lambda$ in $N_p$). We may now construct 
$\{ p_\alpha \}_{\alpha < \rho} \subseteq A$ such that 
$\sat(p_\alpha) > \sup \{ \sat(p_\beta) \colon \beta < \alpha\}$ and 
$\sup_{\alpha < \rho} \sat(p_\alpha)=\kappa$. 
For each $\alpha < \rho$, let $A_\alpha \subseteq N_{p_\alpha}$
be an antichain of size $\geq \sup_{\beta < \alpha} \sat(p_\beta)$. 
Then $\bigcup_{\alpha<\rho} A_\alpha$ is an antichain of $P$
of size $\kappa$, a contradiction. 
\end{proof}


















\end{document}