\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}