\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{\bQ}{\mathbb{Q}}
\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{\sA}{\mathcal{A}}
\newcommand{\sF}{\mathcal{F}}
\newcommand{\sB}{\mathcal{B}}
\newcommand{\sI}{\mathcal{I}}
\newcommand{\ch}{\text{CH}}
\newcommand{\gch}{\text{GCH}}
\newcommand{\sh}{\text{SH}}
\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}}
\newcommand{\cub}{\text{c.u.b.}}
\newcommand{\conc}{{}^\smallfrown}
\newcommand{\dq}{\dot{Q}}
\newcommand{\ts}{\bP * \dq}
\newcommand{\tss}{\bP_1 * \dot{\bP}_2}
\newcommand{\lb}{\llbracket}
\newcommand{\rb}{\rrbracket}
\newcommand{\supp}{\text{supp}}
\newcommand{\itf}{\langle \bP_\beta, \dq_\beta \rangle_{\beta< \alpha}}
\newcommand{\ma}{\text{MA}}
\begin{document}
\begin{center}
\bf Iterations and Martin's Axiom
\end{center}
\bigskip
\section{Two Step Iterations}
We showed in lemma~\ref{lemprod} that forcing with $\bP \times \bQ$
is equivalent to first forcing with $\bP$ to get $M[G]$, and then forcing
with $\bQ$ over $M[G]$ to get $M[G][H]$. This, however, is not the most
general case of a two step iteration as in this case we are assuming
$\bQ \in M$. More generally we could have that $\bP \in M$ and $\bQ \in M[G]$.
Note that this breaks the symmetry between $\bP$ and $\bQ$; we cannot
force with $\bQ$ first now. We wish to describe this situation in
more detail now; in particular, how do we describe a two-step iteration
as a single forcing over the ground model? To motivate the definition of
the partial order for the two-stage iteration, let $\bQ= \tau_G$,
where $\tau \in M^\bP$. Let $p \in P$ with $p \forces
(\tau$ is a partial order$)$. To be precise, $\tau$ actually
abbreviates a triple of names $\langle \tau_Q, \tau_\leq, \tau_\bone
\rangle$, but it will be clear from the context what we mean. We are assuming
(without loss of generality) that all our partial orders have maximal
elements. It is easy to see that there is a $\tau' \in M^\bP$ such that
$\bone \forces (\tau'$ is a partial order$)$ and $\bone \forces
((\tau$ is a partial-order$)\rightarrow (\tau'=\tau))$. [Let
$A=A_1 \cup A_2$ be a maximal antichain of $p \in P$ such that either
$p \forces (\tau$ is a partial order$)$ (this defines $A_1$) or
$p \forces \tau$ is not a partial-order$)$. Let $\tau'= \{ \tau \} \times
A_1 \cup \{ \rho \} \times A_2$ where $\rho$ is a any name such that
$\bone \forces (\rho$ is a partial-order$)$].
Thus, there will
be no loss of generality if we require that $\bone \forces (\tau$
is a partial-order$)$. Also, if $q_1, q_2 \in \bQ$ and $q_1 \leq q_2$,
there are $\sigma_1, \sigma_2 \in \dom(\tau)$ such that
$q_1=(\sigma_1)_G$, $q_2=(\sigma_2)_G$, and there are $p_1, p_2 \in \bP$
such that $p_1 \forces (\sigma_1 \in \tau)$, $p_2 \forces
(\sigma_2 \in \tau)$, and $p_2 \forces (\sigma_1 \leq_Q \sigma_2)$.
With this as motivation we now define two step iteration forcing.
\begin{defn} \label{deftwostep}
Let $M$ be a transitive model of $\zf$ and $\bP \in M$ a partial order.
Let $\dq \in M^\bP$ be a name with $\bone_P \forces
(\dq$ is a partial-order$)$. The two-step iteration forcing
$\ts$ is the partial order in $M$ defined to be the set of all
$\langle p, \tau \rangle$ such that $p \in P$, $\tau \in \dom(\dq)$,
and $p \forces (\tau \in \dq)$. The ordering of $\ts$ is defined by
$\langle p_1, \tau_1 \rangle \leq \langle p_2, \tau_2 \rangle$
iff $p_1 \leq_P p_2$ and $p_1 \forces (\tau_1 \leq \tau_2)$.
\end{defn}
We assume there is a name $\bone_Q \in \dom(\dq)$ such that
$\bone_P \forces (\bone_Q$ is maximal in $\dq)$. It is easy to see
then that $\langle \bone_P, \bone_Q \rangle$ is a maximal element
of $\ts$.
If $G \subseteq P$ is $M$-generic and $H \subseteq \dq_G$ is a filter
on $\dq_G$ in $M[G]$, we define $G * H \subseteq \ts$ by
$(p, \tau) \in G*H$ iff $p \in G$ and $\tau_G \in H$. It is easy to see
that $G*H$ is a filter:
\begin{exer}
Show under the hypotheses above that $G*H$ is a filter on
$\ts$.
\end{exer}
Conversely, suppose $F \subseteq \ts$ is $M$-generic. Let
$G=\{ p \in P \colon (p,\bone_Q) \in F\}$. Let
$H \subseteq \dq_G$ be defined by $H=\{ \tau_G \colon \tau \in \dom(\dq)
\wedge \exists p \in P \ (p,\tau) \in F\}$. We will verify in
the proof of the next theorem that $G,H$ are filters on $\bP$,
$\dq_G$ respectively.
\begin{thm} \label{thmts}
Let $M$ be a transive model of $\zf$ and $\ts \in M$.
If $G \subseteq P$ is $M$-generic and $H \subseteq \dq_G$ is $M[G]$
generic for $\dq_G$, then $G*H$ is $M$ generic for $\ts$.
Conversely, if $F \subseteq \ts$ is $M$ generic for
$\ts$ and $G=\{ p \in P \colon (p,\bone_Q) \in F\}$,
$H=\{ \tau_G \colon \tau \in \dom(\dq)
\wedge \exists p \in P \ (p,\tau) \in F\}$, then $G$ is $M$-generic for
$\bP$, $H$ is $M[G]$-generic for $\dq_G$, and $M[F]=M[G][H]$.
\end{thm}
\begin{proof}
First assume that $F \subseteq \ts$ is $M$-generic and define $G$, $H$
as above. To see $G$ is $M$-generic for $\bP$, let $D \subseteq
P$ be dense with $D \in M$. Then $E=\{ (p,\tau) \in \ts \colon
p \in D\}$ is dense in $\ts$ [given
$(q,\sigma)\in \ts$, there is a $p \leq q$ with $q \in D$.
Then $(p,\tau) \in \ts$ as $p \forces (\tau \in \dq)$ and
also $(p,\tau) \in E$]. Let $(p, \tau) \in E \cap F$. Then
$(p, \bone_Q) \in F$ and so $p \in D \cap G$.
We check that $H$ is a filter on $Q= \dq_G$.
Suppose $x, y \in H$. Say $x=\tau_G$, $y=\sigma_G$, where
$(p,\tau) \in F$, $(q, \sigma) \in F$. Since $F$ is a filter, let
$(r, \pi) \leq (p,\tau), (q,\sigma)$ with $(r, \pi ) \in F$.
By definition of $G$, $r \in G$. Also $r \forces (\pi \leq \tau)$,
so $\pi_G \leq_Q \tau_G$. Similarly, $\pi_G \leq_Q \sigma_G$.
Also, $\pi_G \in H$ by definition of $H$. Next suppose
$x \in H$ and $x \leq y$. Say $x= \tau_G$ with $(p, \tau) \in F$.
Let $y = \sigma _G$ where $\sigma \in \dom(\dq)$. Since
$\tau_G \leq_Q \sigma_G$ (and since $G$ is generic by the above)
there is a $q \in G$ with
$q \forces (\tau \leq \sigma \wedge \sigma \in \dq)$.
Since $F$ is a filter, let $(r,\pi) \in F$ with
$(r,\pi) \leq (p,\tau), (q,\bone_Q)$. Then $r \forces
(\pi \leq \tau)$ and $r \forces \tau \leq \sigma$ (as $r \leq q$)
so $r \forces \pi \leq \sigma$. So, $(r,\pi) \leq (r,\sigma)$.
As $F$ is a filter, $(r, \sigma) \in F$. Thus, by definition of $H$,
$y=\sigma_G \in H$.
We next show $H$ is $M[G]$ generic for $\bQ= \dq_G$. Note that in
$M[G]$, $\bQ$ is a partial order. Let $D \subseteq \bQ$ be dense,
where $D \in M[G]$. Fix $\sigma \in M^\bP$ with $D=\sigma_G$.
Fix also $p_0 \in \bP$ with $p_0 \forces (\sigma$ is dense in $\dq )$.
We must show that $\tau_G \in D \cap H$
for some $\tau \in \dom(\dq)$. Let $E=\{ (p,\tau) \in \ts \colon
p \forces (\tau \in \sigma) \}$. To see $E$ is dense below
$(p_0,\bone_Q)$ in $\ts$, let $(q,\rho) \in \ts$ with $q \leq p_0$.
So, $q \forces \exists x\ (x \in \sigma \wedge x \leq \rho)$.
Thus for some $r \leq q$ and $\pi \in \dom(\dq)$ we have
$r \forces (\pi \in \sigma \wedge \pi \leq \rho)$ (you can see this
by taking a generic containing $q$). Hence $(r,\pi) \in \ts$ and
in fact $(r, \pi) \in E$. By definition, $(r,\pi) \leq (q, \rho)$.
So $E$ is dense below $(p_0,\bone_Q)$. Since $(p_0,\bone_Q) \in F$,
it follows that $F \cap E \neq \emptyset$. Let
$(p, \tau) \in E \cap F$. Then $p \in G$ and also
$p \forces \tau \in \sigma$. Hence $\tau_G \in \sigma_G=D$. Also
$\tau_G \in H$ by definition of $H$.
We next show that $F=G*H$. If $(p, \tau) \in F$ then $(p ,\bone_Q) \in
F$ and so $p \in G$. By definition of $H$, $\tau_G \in H$.
By definition of $G*H$, $(p,\tau) \in G*H$. Suppose now
$(p, \tau) \in G*H$. Thus, $p \in G$ and $\tau_G \in H$. By definition
of $G$, $(p, \bone_Q) \in F$. By definition of $H$,
$\tau_G=\pi_G$ where $(q,\pi) \in F$. Let $r \in G$ with
$r \forces (\tau=\pi)$. Thus, $(r, \bone_Q) \in F$.
Since $F$ is a filter, let $(s,\rho)\in F$ extend
$(p, \bone_Q)$, $(q, \pi)$, and $(r, \bone_Q)$. Since
$s \forces \rho \leq \pi$ and $s \forces \pi =\tau$, $s \forces
\rho \leq \tau$. Thus, $(s,\rho) \leq (p ,\tau)$, and since $F$ is a filter,
it follows that $(p, \tau) \in F$.
Finally, it is clear that from $F$ we may define $G$, and then
define $H$, so $M[G][H] \subseteq M[F]$. Since $F=G*H$,
from $G$ and $H$ we may define $F$, so $M[F] \subseteq M[G][H]$.
Thus, $M[F]=M[G][H]$.
This completes one direction of the theorem.
For the other direction, assume now $G \subseteq \bP$ is
$M$-generic and $H \subseteq \bQ= \dq_G$ is $M[G]$-generic.
Let $F=G*H \subseteq \ts$. As we showed already, $F$ is a filter
on $\ts$. To see it is generic, let $D \subseteq \ts$ be dense, with
$D \in M$. We must find a $(p, \tau) \in D$ with $p \in G$ and
$\tau_G \in H$. Let $E \subseteq \bQ= \dq_G$ be defined by
$E=\{ \tau_G \colon \exists p \in G\ (p,\tau) \in D\}$. Clearly
$E \in M[G]$. To see $E$ is dense in $\bQ$, let
$\sigma_G \in \bQ$, where $\sigma \in \dom(\dq)$.
Let $p \forces (\sigma \in \bQ)$, $p \in G$. Let $A=\{ q \leq p \colon
\exists \rho \in \dom(\dq) \ ((q,\rho) \in D \wedge
(q, \rho) \leq (p,\sigma))\}$. Easily $A$ is dense below $p$.
Let $q \in G \cap A$. Let $\rho \in \dom(\dq)$ be such that
$(q,\rho) \in D$ and $(q, \rho) \leq (p, \sigma)$. Since $q \in G$
and $q \forces (\rho \leq \sigma)$, we have $\rho_G \leq \sigma_G$.
By definition of $E$, $\rho_G \in E$. This shows $E$ is dense in $\bQ$.
Let $\tau_G \in E \cap H$. Then there is a $p \in G$ such that
$(p, \tau) \in D$, and we are done.
\end{proof}
We next prove an important fact about preservation of $\kappa$-c.c.{}
under finite iterations.
\begin{lem} \label{itcc}
Let $\kappa$ be a regular cardinal. Suppose $\bP$ is $\kappa$-c.c.,
and $\bone_P \forces (\dq \text{ is } \kappa$-c.c.$)$. Then
$\ts$ is $\kappa$-c.c.{}
\end{lem}
\begin{proof}
Suppose $(p_\alpha, \tau_\alpha)$, $\alpha < \kappa$ is an antichain in
$\ts$. If $G$ is generic for $\bP$ and $p_\alpha$, $p_\beta \in G$, then
$(\tau_\alpha)_G$ and $(\tau_\beta)_G$ are incompatible in $\dq_G$.
For if $\sigma_G$ extended them both, then we could get $p \in G$
with $p \forces \sigma \leq \tau_\alpha$ and $p \forces \sigma \leq
\tau_beta$. Since $G$ is a filter, we may assume $p \leq p_\alpha, p\beta$.
But then $(p, \sigma) \leq (p_\alpha, \tau_\alpha)$, $p \leq
(p_\beta,\tau_\beta)$, a contradiction. Since $\dq_G$ is $\kappa$-c.c.,
it follows that $\{ \alpha \colon p_\alpha \in G\}$ has size $< \kappa$.
This shows that $D=\{ p \in \bP \colon \exists \beta < \kappa \
p \forces \forall \alpha\ (p_\alpha \in \dot{G} \rightarrow
\alpha < \check{\beta}) \}$ is dense in $\bP$. Let $A \subseteq \bP$
be maximal subject to being an antichain and $A \subseteq D$.
Since $D$ is dense, $A$ is a maximal antichain of $\bP$. For
$p \in A$, let $\beta(p)< \kappa$ be as in the definition of $D$.
Since $\kappa$ is regular and $|A| <\kappa$, $\gamma=\sup_{p \in A} \beta(p)
< \kappa$. This is a contradiction, as we can take a generic $G$
containing some $p_\alpha$ for $\alpha > \gamma$ (this generic
must meet $A$).
\end{proof}
Lemma~\ref{itcc} does not say that the product of $\kappa$-c.c.{}
partial orders is $\kappa$-c.c.{} In fact, it is independent of
$\zfc$ whether the product of two \ccc{} partial orders is \ccc{}
We will see below that under Martin's axiom and $\neg \ch$, the
product of two \ccc{} partial orders is \ccc{} On the other hand,
$\ch$ implies that that there are two \ccc{} partial orders
whose product is not \ccc{} Such an example is more easily constructed
from the existence of a Suslin tree. Suppose $T$ is a Suslin tree.
We view $T$ as a partial order by $x \leq y$ iff $x \geq_T y$, i.e.,
by reversing the tree order. Clearly $T$ is still \ccc{} viewed as a partial
order this way. However, the partial order $T \times T$ is not \ccc{}
To see this, first assume without loss of generality that $T$ is pruned,
and then that $T$ is splitting (by considering the subtree $T'$ of $T$
obtained by restricting to levels $\alpha_i$, $i < \omega_1$, where
every element of $T$ at level $\alpha_i$ has incompatible extensions
at level $\alpha_{i+1}$). So assume $T$ is splitting. For each $x \in T$,
let $l(x)$, $r(x)$ be incompatible immediate extensions of $x$ in $T$.
Then $\{ (l(x),r(x)) \}_{x \in T}$ forms an antichain in $T \times T$.
In fact, the next lemma characterizes when a product of $\kappa$-c.c.{}
partial orders is $\kappa$-c.c.{}
\begin{lem}
Let $P$, $Q$ be partial orders. Then $P \times Q$ is $\kappa$-c.c.{}
iff $P$ is $\kappa$-c.c.{} and $\bone_P \forces (\check{Q}$ is
$\kappa$-c.c.$)$.
\end{lem}
\begin{proof}
One direction is immediate from lemma~\ref{itcc}.
Suppose that $\bone_P \nVdash (\check{Q}$ is
$\kappa$-c.c.$)$. Let $p \in P$ and $\tau \in M^P$ be such that
$p \forces [(\tau \colon \check{\kappa} \to \check{Q}) \wedge
\forall \alpha < \beta < \kappa\ (\tau(\alpha) \perp \tau(\beta))]$.
For $\alpha < \kappa$ let $p_\alpha \leq p$ and $q_\alpha \in Q$
be such that $p_\alpha \forces \tau(\alpha)= q_\alpha$. Let
$A=\{(p_\alpha,q_\alpha)\}_{\alpha < \kappa}$. We show that $A$ is an
antichain in $P \times Q$. Fix $\alpha < \beta$, and suppose
$(r,q) \leq (p_\alpha,q_\alpha), (p_\beta,q_\beta)$. Then
$r \forces \tau(\alpha)=q_\alpha$ and $r \forces \tau(\beta)=q_\beta$,
and since $r \leq p$ it follows that $r \forces q_\alpha \perp q_\beta$,
a contradiction.
\end{proof}
\section{Intermediate Extensions}
Suppose $M$ is a transitive model of $\zfc$ and $M[G]$ is a generic extension
of $M$. Let $N$ be a model of $\zfc$ with $M \subseteq N \subseteq M[G]$.
We show that we can ``factor'' the extension through $N$, that is,
get a two step iteration $M \subseteq M[G_1] \subseteq M[G_1][G_2]=M[G]$
with $M[G_1]=N$. Also, if $X \in M[G]$ and $X \subseteq M$ (e.g., $X$
is a set of ordinals), then there is a minimal transitive model
$M[X]$ of $\zfc$ containing $X$, and thus we can write $M[G]=M[G_1][G_2]=
M[X][G_2]$ as a two-step iteration.
First we show the following lemma which shows we can do the factoring
in the case where $N=M[G_1]$ where $G_1$ is $M$-generic for
a partial order which is completely embedded into $\bP$.
\begin{defn}
Let $M$ be a transitive model of $\zfc$, $\bP$, $\bQ$ partial orders
in $M$, and $e \colon \bP \to \bQ$ a complete embedding which
lies in $M$. For $G \subseteq \bP$, let $\bQ/G = \{ q \in \bQ
\colon \forall p \in G\ (e(p) \parallel q) \}$.
\end{defn}
\begin{lem} \label{lemfactor}
Let $M$ be a transitive model of $\zfc$, $\bP$, $\bQ$ partial orders
in $M$, and $e \colon \bP \to \bQ$ a complete embedding in $M$.
Let $H \subseteq \bQ$ be $M$-generic for $\bQ$. Let $G= e^{-1}(H)$.
Then $G$ is $M$ generic for
$\bP$, $H \subseteq \bQ/G$ and is $M[G]$-generic for $\bQ/G$.
Also, $M[H]=M[G][H]$ (here $M[G][H]$ refers to the extension
of $M[G]$ by forcing with $\bQ/G$).
\end{lem}
\begin{proof}
Since $e \colon \bP \to \bQ$ is complete, $G=e^{-1}(H)$ is $M$-generic
for $\bP$. Clearly $H \subseteq \bQ/G$, since any $q \in H$ is
compatible with $e(p)$ for any $p \in G$ (since $e(p) \in H$).
We show $H$ is $M[G]$-generic for $\bQ/G$. Let $D \subseteq
\bQ/G$, with $D \in M[G]$, be dense in $\bQ/G$. Fix
$\tau \in M^\bP$ with $D=\tau_G$. Let $p_0 \in G$, $p_0
\forces (\tau$ is dense
in $\check{Q}/\dot{G})$. Define
$$
E=\{ q \in \bQ \colon \exists p \in \bP\ \exists q_1 \in \bQ\ [(p
\forces \check{q}_1 \in \tau) \wedge (q \leq q_1) \wedge (q \leq e(p))] \}.
$$
We claim that $E$ is dense below $e(p_0)$. To see this, let $q_1 \leq
e(p_0)$. Let $p_1 \in \bP$ be a reduction of $q_1$. Then $p_1 \forces
(q_1 \in \bQ/\dot{G})$ [For let $G'$ be generic for $\bP$ containing
$p_1$. Let $p_2 \in G'$, and we show $e(p_2) \parallel q_1$. Let
$p_3\in G$ with $p_3 \leq p_1,p_2$. Then $e(p_3) \leq e(p_2)$, and
$e(p_3) \parallel q_1$ since $p_1$ is a reduction of $q_1$ and $p_3
\leq p_1$. Thus, $e(p_2) \parallel q_1$.] Since $e(p_1) \parallel
q_1$, $e(p_1) \parallel e(p_0)$, and thus $p_1 \parallel p_0$ (as $e$
is complete). So we may assume $p_1 \leq p_0$. Also, $p_1 \forces
(\tau$ is dense in $\bQ/\dot{G})$. Thus we can get $p_2, q_2$ with $p_2
\forces (\check{q_2} \in \tau \subseteq \check{Q}/\dot{G})$ and $q_2
\leq q_1$. Since $p_2 \forces (\check{q_2} \in \check{Q}/\dot{G})$ it
follows that $e(p_2) \parallel q_2$. Let $q \leq e(p_2), q_2$. Then
$q \in E$.
Let now $q \in E \cap H$. Let $p \in \bP$ and $q_1 \in \bQ$
witness $q \in E$. Since $q \leq e(p)$, $e(p) \in H$ and thus
$p \in G$. Also, $q_1 \in H$. Since $p \in G$ and
$p \forces (\check{q_1} \in \tau)$, we have $q_1 \in D$. So,
$q_1 \in H \cap D$. This shows $H$ is $M[G]$-generic for $\bQ/G$.
Finally, $M[H]=M[G][H]$ is immediate since $G \in M[H]$.
\end{proof}
We now state precisely our theorem on intermediate extensions.
\begin{thm} \label{thminter}
Let $M$ be a transitive model of $\zfc$, $\bP \in M$ a partial order,
and let $G \subseteq \bP$ be $M$-generic for $\bP$. Then if $N$
is a transitive model of $\zfc$ with $M \subseteq N \subseteq M[G]$,
then there is a two stage iteration partial order $\tss$ in $M$ and
an $M$-generic $G_1 * G_2$ for $\tss$ such that $N= M[G_1]$ and
$M[G]=M[G_1][G_2]$. Also, if $X \in M[G]$ and $X \subseteq M$, then
there is a smallest transitive model $N$ of $\zfc$ containing
$M$ and $X$, and thus we have $M \subseteq M[X]=M[G_1] \subseteq M[G_1][G_2]=
M[G]$ for some two stage forcing $\tss$ and generic $G_1* G_2$.
\end{thm}
\begin{rem}
We need the hypothesis that $X \subseteq M$; the result is
not true for arbitrary $X \in M[G]$.
\end{rem}
First consider the case where $M \subseteq M[G]$, where $G$ is
$M$-generic for $\bP$ and $X \in M[G]$, $X \subseteq \on$.
Let $\sB$ be the completion of $\bP$, so $\sB$ is a complete Boolean
algebra and $M[G]=M[G']$ where $G'$ is $M$-generic for $\sB$. Thus,
we may assume that $\bP$ is a complete Boolean algebra. Fix a
$\tau \in M^\sB$ with $X=\tau_G$. For $\alpha < \eta \doteq \sup(X)$,
define $b_\alpha= \lb \check{\alpha} \in \tau \rb$. Let $\sA \subseteq
\sB$ be the complete subalgebra of $\sB$ generated by the $b_\alpha$.
By this we mean $\sA$ is the smallest subalgbra of $\sB$ containing
the $b_\alpha$ and closed under the $\sum$ and $\prod$ operations of $\sB$
(this easily exists). Let $H=G \cap \sA$. The identity (inclusion) map
$i \colon \sA \to \sB$ is a complete embedding, and thus
$i^{-1}(G)=G \cap \sA=H$ is $M$ generic for $\sA$. In particular,
$M[H]$ is a model of $\zfc$. We show that $M[H]=M[X]$. First, $X \in M[H]$,
since $\alpha \in X$ iff $b_\alpha \in G$ iff $b_\alpha \in H$ (since
$b_\alpha \in \sA$). Next we show any transitive model $N$ of $\zfc$
which contains $X$ must contain $H$, and this finishes.
Now, the subalgebra $\sA$ can be constructed as follows.
Let $\sA_0= \{ \lb b_\alpha \rb\}$. At limit stages let $\sA_\beta=
\bigcup_{\gamma < \beta} \sA_\gamma$. At successor steps, let
$\sA_{\beta+1}= \sA_\beta \cup \{ -a \colon a \in \sA_\beta \}
\cup \{ \sum E \colon E \subseteq \sA_\beta\}$ (here $\sum$ refers
to the supremum operation of $\sB$; we continue this construction until
$\sA_\beta=\sA_{\beta+1}$). We show by induction on $\beta$
that $G \cap \sA_\beta$ lies in $N$ (more precisely, we are actually
giving a definition by transfinite recursion in $N$ of the function
$\gamma \to G \cap \sA_\gamma$).
For $\beta=0$ we have
$\lb b_\alpha \rb \in G$ iff $\alpha \in X$. Since $X \in N$,
this shows $G \cap \sA_0 \in N$. For $\beta$ limit the inductive step
is trivial. At successor steps we have $-a \in G$ iff
$a \notin G$, and $\sum E \in G$ iff $G \cap E \neq \emptyset$ (recall that
since $\sB$ is a complete Boolean algebra, $G$ is a a generic ultrafilter
on $\sB$). This gives a definition by transfinite recursion in $N$ of the
function $\gamma \to G \cap \sA_\gamma$, and shows in particular that
$G \cap \sA_\gamma \in N$ for all $\gamma$. For $\gamma$ large enough
this gives $G \cap \sA \in N$. Thus, $M[H]=M[X]$. The same argument
just given also works if $X \subseteq M$ (with $X \in M[G]$).
We next show that if $N$ is any model of $\zfc$ with $M \subseteq N
\subseteq M[G]$ then $N=M[H]$ for some generic extension $M[H]$ of $M$.
Let $S= \sP(\sB) \cap N= \sP^N(\sB)$. For any $X \in N$, there is a
set of ordinals $A(X) \in N$ which ``codes'' $X$ in that $X$ lies
in any transitive model of $\zf$ containing $A(X)$.
In particular, $A(S) \in N$. By the previous paragraph, $M[A(S)]$
exists and $M[A(S)]=M[H]$ for some generic extension $M[H]$ of $M$.
Fix now $X \in N$. Let $\sA(X)$
be the complete subalgebra of $\sB$ constucted above so that $M[A(X)]=
M[\sA(X) \cap G]$ (this actually depends on the choice of name for
$A(X)$, but this doesn't matter). Since $M[A(X)] \subseteq N$, we have
$\sA(X) \cap G \in N$. Thus, $\sA(X) \cap G \in S$. This show
$X \in M[S]=M[H]$. Thus, $N \subseteq M[H]$ and so $N=M[H]$.
We have shown that if $N$ is a model of $\zfc$ with $M \subseteq N \subseteq
M[G]$ then $N=M[H]$ is a generic extension of $M$, and if
$X \in M[G]$, $X \subseteq M$, then $M[X]$ exists and
$M[X]=M[H]$ is a generic extension. In both cases $H$ is an $M$-generic for
a complete Boolean algebra which a complete subalgebra of $\sB$ (where
$G$ is $M$ generic for $\sB$). Lemma~\ref{lemfactor} now finishes the proof
of theorem~\ref{thminter}.
\section{General Iterations}
We now extend the discussion from two step iterations to
iterations of general length. Definition~\ref{deftwostep}
shows how to unravel a two-step iteration into a partial order
in the ground model. We will use the same definition for
successor steps in the general definition. That is, an iteration
$\bP_{\alpha+1}$ of successor length will be (isomorphic to) a
partial order of the form $\bP_\alpha * \dq_\alpha$ where
$\bP_\alpha$ is an $\alpha$ length iteration and $\dq_\alpha \in M$
is a $\bP_\alpha$ name with $\bone_\alpha \forces (\dq_\alpha$ is
a partial order$)$. There will actually be a slight ``notational''
isomorphism involved. For example, an element of a three step iteration
would, by definition~\ref{deftwostep} iterated twice, be an element
of the form $\langle \langle x,y \rangle , z\rangle$, whereas in
our official definition we will take the elements to be
sequences of length $3$ (i.e., functions with domain $3$).
The main question is what to do at limit ordinals, and there are a variety
of possibilities, all of which are useful in different arguments.
Following Kunen we consider fairly general possibilites by allowing
the ``supports'' of the conditions to lie in a general ideal on $\alpha$.
The precise definition follows.
\begin{defn}
Let $M$ be a transitive model of $\zf$, $\alpha$ an ordinal of $M$,
and $\sI \subseteq \sP(\alpha)$ an ideal on $\alpha$ (possibly
improper, that is, $\sI = \sP(\alpha)$) which lies in $M$. An
$\alpha$ stage iterated forcing is a pair of sequences in $M$ of the
form $\langle \bP_\beta \rangle_{\beta \leq \alpha}$,
$\langle \dq_\beta \rangle_{\beta< \alpha}$. Each $\bP_\beta$
will be a partial order in $M$ (with a maximal element $\bone_{\bP_\beta}$),
and $\dq_\beta$ is a $\bP_\beta$ name with $\bone_{\bP_\beta}
\forces (\dq_\beta$ is a partial order with maximal element $\bone_{\dq_\beta})$.
Each $\bP_\beta$ will consist of $p=\langle \rho_\gamma \rangle_{\gamma < \beta}$
which are sequences of length $\beta$.
The $\bP_\beta$ satisfy the following inductive conditions.
\begin{enumerate}
\item
$\bP_0$ is a partial order in $M$.
\item
$p= \langle \rho_\gamma \rangle_{\gamma < \beta +1} \in \bP_{\beta+1}$ iff
$p \res \beta \in \bP_\beta$, $\rho_\beta \in \dom(\dq_\beta)$, and
$p \res \beta \forces_{\bP_\beta} (\rho_\beta \in \dq_\beta)$. If
$p'=\langle \rho'_\gamma \rangle_{\gamma < \beta +1} \in \bP_{\beta+1}$
then $p \leq p'$ iff $p \res \beta \leq_{\bP_\beta} p' \res \beta $
and $p \forces_{\bP_\beta} (\rho_\beta \leq \rho'_\beta)$.
\item
For $\beta$ limit, $p=\langle \rho_\gamma \rangle_{\gamma < \beta}
\in \bP_\beta$ iff $\forall \gamma < \beta\ p\res \gamma \in \bP_\gamma$
and the {\em support} of $p$ is in $\sI$, where the support of
$p$ is defined by $\supp(p)=\{ \gamma < \beta \colon \rho_\gamma \neq
\bone_{\dq_\gamma} \}$.
For $p, p' \in \bP_\beta$, we have $p \leq p'$ iff
$\forall \gamma < \beta \ (p\res \gamma \leq p' \res \gamma)$
\end{enumerate}
We define $\bone_{\bP_\beta}$ to be the sequence $\langle \bone_{\dq_\gamma}
\rangle_{\gamma < \beta}$.
\end{defn}
The final $\alpha$ stage iteration $\bP_\alpha$ is determined
from the sequence of $\bP_\beta$ and $\dq_\beta$ for $\beta < \gamma$.
We will thus frequently abbreviate the above definition by
writing it as $\langle \bP_\beta, \dq_\beta \rangle_{\beta < \alpha}$.
\begin{defn}
We say an iteration is of {\em finite support} if $\sI$ is the ideal of finite
sets, of {\em countable support} if $\sI$ is the ideal of countable sets (in $M$),
and of {\em full support} if $\sI = \sP(\alpha)$.
\end{defn}
Note that by properly choosing $\sI$ it is possible to mix the
various types of iterations. For example, we might have an iteration of
length $\omega \cdot 3$ where we alternate finite and full supports.
then $\sI$ would be the ideal on $\omega \cdot 3$ of sets $A$
such that $A \cap \omega$ and $A \cap (\omega \cdot 2, \omega \cdot 3)$
are finite.
The next definition gives a natural embedding $e_{\beta \gamma}$
from $\bP_\beta$ to $\bP_\gamma$ when $\beta \leq \gamma \leq \alpha$,
and the following lemma shows this is a well-defined complete embedding.
Thus, a generic $G_\alpha$ for the $\alpha$ length iteration $\bP_\alpha$
induces generics $G_\beta$ for all $\beta< \alpha$.
\begin{defn}
Let $\langle \bP_\beta, \dq_\beta \rangle_{\beta < \alpha}$
be an $\alpha$ length iteration in a transitive model $M$ of $\zf$.
Define, in $M$, for $\beta \leq \gamma \leq \alpha$ the map
$e_{\beta \gamma} \colon \bP_\beta \to \bP_\gamma$ by
$e_{\beta \gamma}(p)=q$ where $q \res \beta =p$ and for
$\beta \leq \eta< \gamma$, $q(\eta)=\bone_{\dq_\eta}$.
\end{defn}
\begin{lem}
Let $\langle \bP_\beta, \dq_\beta \rangle_{\beta < \alpha} \in M$
be an $\alpha$ length iteration. Then for any $\beta \leq \gamma \leq
\alpha$, the map $e_{\beta \gamma}$ is a well-defined one-to-one map from
$\bP_\beta$ to $\bP_\gamma$ which is a complete embedding.
\end{lem}
\begin{proof}
Fix $\beta < \gamma \leq \alpha$ (if $\beta= \gamma$ the result is trivial).
Let $p=\langle \rho_\eta \rangle_{\eta < \beta} \in \bP_\beta$, and
let $q=e_{\beta \gamma}(p)$.
Clearly $q \in \bP_\gamma$ since for any $\eta < \gamma$,
$q \res \eta \forces (\bone_{\dq_\eta} \in \dq_\eta)$ (as $\bone_{\bP_\eta}
\forces (\bone_{\dq_\eta} \in \dq_\eta)$). Clearly $e_{\beta \gamma}$
is one-to-one.
We check that $e_{\beta \gamma}$ is complete.
It is trivial to check that if $p \leq p'$ then $e_{\beta \gamma}(p)
\leq e_{\beta \gamma}(p')$. Suppose now $p \perp_{\bP_\beta} p'$,
and we show $e_{\beta \gamma}(p) \perp_{\bP_\gamma} e_{\beta \gamma}(p')$.
If $q \leq e_{\beta \gamma}(p), e_{\beta \gamma}(p')$, then
$q \res \beta \leq p, p'$, so $p \parallel p'$.
Thus, $p \perp p' $ iff $e_{\beta \gamma}(p) \perp e_{\beta \gamma}(p')$.
Suppose now $q= \langle \rho_\eta \rangle_{\eta < \gamma} \in \bP_\gamma$.
Let $p= q \res \beta \in \bP_\beta$. We show that $p$ is a reduction
of $q$ for $e_{\beta \gamma}$. Suppose $p'=\langle \rho'_\eta \rangle_{\eta
< \beta} \leq p$. We must show that $e_{\beta \gamma}(p') \parallel q$.
Define $r$ by $r \res \beta= p'$ and $r \res(\gamma-\beta)= q \res(\gamma-\beta)$.
Clearly $r \res \beta \in \bP_\beta$. Since $q \in \bP_\gamma$,
a straightforward induction on $\eta \in (\gamma-\beta)$ shows that
$r \res \eta \in \bP\eta$ and $r \res \eta \leq q \res \eta$ (for example,
for the successor step: since $q\res \eta \forces (\rho_\eta
\in \dq_\eta)$ and $r \res \eta \leq q\res \eta$ by induction,
$r \res \eta \forces (\rho_\eta \in \dq_\eta)$. Thus,
$r \res (\eta+1) \in \bP_{\eta+1}$ and trivially $r \res (\eta+1) \leq
q \res (\eta+1)$). Also, $r \leq e_{\beta \gamma}(p')$ since
$r \res \beta = p' \res \beta$ and for $\eta \geq \beta$,
$r \res \eta \forces (\rho_\eta \leq \bone_{\dq_\eta})$.
Thus, $r \leq e_{\beta \gamma}(p), q$.
\end{proof}
If $\itf \in M$ is an $\alpha$ length iterated forcing, and $G$
is $M$-generic for $\bP_\alpha$, then for $\beta \leq \alpha$
we will write $G_{< \beta}$ for the generic for $\bP_\beta$ induced
by $G$ (so $G=G_{< \alpha}$). We also write $G_{\leq \beta}$ for
$G_{< \beta+1}$.
We can also define for $\beta < \alpha$
the generic $G_\beta \subseteq (\dq_\beta)_{G_{< \beta}}$.
This is defined by $G_\beta= \{ p(\beta)_{G_{< \beta}} \colon
p \in G_{\leq \beta} \}$. Now, $\bP_{\beta+1}$ is isomorphic
to $\bP_\beta * \dq_\beta$. Under this isomorphism,
$G_{\leq \beta}$ corresponds to $G_{< \beta} * G_\beta$ [To be explicit,
the isomorphism $\pi \colon \bP_{\beta+1} \to \bP_\beta * \dq_\beta$
is given by $\pi(p)= \langle \pi\res \beta, \pi(\beta) \rangle$.]
From theorem~\ref{thmts} we have that $G_\beta$ is $M[G_{< \beta}]$
generic for $(\dq_\beta)_{G_{< \beta}}$.
Finite and countable support iterations are frequently used, and we consider
some of the properties preserved under such iterations.
First we show that $\kappa$-c.c.{} is preserved under finite
support iterations.
\begin{lem} \label{lemfinccc}
Suppose $\kappa$ is a regular cardinal of $M$, and
$\itf$ is an $\alpha$ length iteration using finite supports.
Suppose for each $\beta < \alpha$ that $\bone_{\bP_\beta} \forces
(\dq_\beta \text{ is } \check{\kappa}\ \cc)$.
Then $\bP_\alpha$ is $\kappa$-c.c.{} in $M$.
\end{lem}
\begin{proof}
We show by induction on $\beta \leq \alpha$ that $\bP_\beta$ is $\kappa$-c.c.{}
in $M$. If $\bP_\beta$ is $\kappa$-c.c.{}, then $\bP_{\beta+1}$ is
$\kappa$-c.c.{} (in $M$) from lemma~\ref{itcc}.
Suppose now $\beta$ is limit, and is least such that $\bP_\beta$
is not $\kappa$-c.c.{} Let $\{p_\eta \}_{\eta < \kappa}$
be an antichain of $\bP_\beta$. Let $s_\eta=\supp(p_\eta)$. Thus,
$s_\eta \subseteq \beta$ is finite. We may assume the $s_\eta$
form a $\lD$-system (note that if $\beta < \kappa$ this is trivial)
with root $r \subseteq \beta$. Let $\gamma < \beta$ with $\gamma > \sup(r)$.
We claim that that $p_\eta \res \gamma$ form an antichain in $\bP_\gamma$,
a contradiction. To see this, let $p=\langle \rho_\xi \rangle_{\xi
< \beta}$ and $q=\langle \sigma_\xi \rangle_{\xi < \beta}$ be two elements
of the antichain $\{ p_\eta\}_{\eta< \kappa}$. Suppose $p \res \gamma$
and $q \res \gamma$ were compatible, say $r \leq p\res \gamma, q\res \gamma$.
Define $r'$ by
$$
r'(\xi)= \begin{cases}
r(\xi) & \text{ if } \xi < \gamma\\
\bone_{\dq_\xi} & \text{ if } \xi \geq \gamma \wedge \xi \notin (\supp(p)
\cup \supp(q)) \\
p(\xi) & \text{ if } \xi \geq \gamma \wedge \xi \in \supp(p)- \supp(q)\\
q(\xi) & \text{ if } \xi \geq \gamma \wedge \xi \in \supp(q)- \supp(p)
\end{cases}
$$
Since $r \leq p \res \gamma, q\res \gamma$, a straightforward induction
on $\xi$ shows that $r' \res \xi \in \bP_\xi$ and
$r' \res \xi \leq p \res \xi, q \res \xi$. Thus, $r' \leq p,q$,
a contradiction.
\end{proof}
\begin{cor}
A finite support iteration of \ccc{} forcings is \ccc{}
\end{cor}
We now consider iterations with countable support. We would like to
show that a countable support iteration of countably closed forcings
(i.e., $\bone_{\bP_\beta} \forces \dq_\beta$ is countably close$)$) is
countable closed, however, that is not true in complete generality. It
is true, however, if we choose the names $\dq_\beta$ for the partial
orders in a reasonable manner which, we will see, imposes no loss of
generality.
\begin{defn}
Let $M$ be a transitive model of $\zf$, $\bP$ be a partial order,
and $\pi \in M^\bP$. We say $\pi$ is {\em full} if $\pi= \dom(\pi)
\times \{ \bone_\bP \}$ and for all $p \in \bP$ and $\tau \in M^\bP$,
if $p \forces (\tau \in \pi)$ then there is a $\sigma \in \dom(\pi)$
such that $p \forces (\tau=\sigma)$.
If $\bone_\bP \forces (\pi$ is a partial order$)$, then we say
$\pi$ is $\omega$-full is whenever $p \in \bP$,
$\sigma_n \in \dom(\pi)$ and $p \forces (\sigma_n \in \pi \wedge
\sigma_{n+1} \leq \sigma_n)$ for all $n$, then there is a
$\sigma \in \dom(\pi)$ such that $p \forces (\sigma \leq \sigma_n)$
for all $n$.
\end{defn}
The next lemma shows that there is no loss of generality
is using full names for sets.
\begin{lem} \label{lemfull}
Let $M$ be a transitive model of $\zfc$ and $\pi \in M^\bP$.
Assume $\bone_\bP \forces (\pi \neq \emptyset)$.
Then there is a full name $\pi'$ such that $\bone_\bP \forces
(\pi=\pi')$.
\end{lem}
\begin{proof}
Let $\pi'$ be the set of all $\langle \bone_\bP, \sigma \rangle$
where $\sigma \in \sP(\bP \times \dom^2(\pi))$ and
$\bone_\bP \forces (\sigma \in \pi)$, where $x \in \dom^2(\pi) $
iff $\exists \tau \in \dom(\pi) \ (x \in \dom(\tau))$. Clearly
$\pi' \in M^\bP$ and is of the desired form. It is also clear
that $\bone \forces (\pi' \subseteq \pi)$ [for any generic $G$,
$\pi'_G \subseteq \pi_G$ since if $x \in \pi'_G$, then
$x=\sigma_G$ for some $\sigma$ such that $\bone \forces (\sigma \in \pi)$].
To show $\bone \forces (\pi \subseteq \pi')$ and to show fullness
it suffices to show that for any $p \in \bP$ and $\rho \in M^\bP$,
if $p \forces (\rho \in \pi)$ then for some $\sigma \in \dom(\pi')$
we have $p \forces (\rho=\sigma)$. Let $p, \rho$ be as above, so
$p \forces (\rho \in \pi)$. Let $A \subseteq \bP$ be maximal subject
to being an antichain and for all $q \in A$ either $q \leq p$ and
for some $\pi_q \in \dom (\pi)$, $q \forces (\rho = \pi_q )$ or
$q \perp p$ and for some $\pi_q \in \dom(\pi)$ we have
$q \forces (\pi_q \in \pi)$. Clearly $A$ is a maximal antichain of $\bP$.
For each $q \in A$ we will define a name $\tilde{\pi}_q$, and then we
will take $\sigma$ to be the union of all the $\tilde{\pi}_q$.
Fix $q \in A$ and the corresponding $\pi_q \in \dom(\pi)$.
Let $\tilde{\pi}_q=\{ \langle r, u \rangle \colon \exists \langle s, u \rangle
\in \pi_q \ (r \leq q, s) \}$.
Let $\sigma = \bigcup_{q \in A} \tilde{\pi}_q$. We must show that
$\bone \forces (\sigma \in \pi)$ and $p \forces (\sigma=\rho)$.
First, since $A$ is an antichain, for any $q \in A$ we have
$q \forces (\sigma = \tilde{\pi}_q)$. We also have
$q \forces (\tilde{\pi}_q=\pi_q)$ [Let $G$ be generic containing
$q$. If $x \in (\tilde{\pi}_q)_G$, then $x= u_G$ for some
$\langle r, u \rangle \in \tilde{\pi}_G$, $r \in G$, with say
$r \leq s$ and $\langle s, u \rangle \in \pi_q$. Thus $x=u_G \in (\pi_q)_G$.
If $x \in (\pi_q)_G$, then $x=u_G$ for some $\langle s, u \rangle
\in \pi_q$, where $s \in G$. Let $r \leq q,s$. Then $\langle
r, u \rangle \in \tilde{\pi}_q$. Hence $x=u_G \in (\tilde{\pi}_q)_G$.]
So, $q \forces (\sigma= \pi_q)$. Since $A$ is a maximal antichain, this
gives $\bone \forces (\sigma \in \pi)$.
Next we show $p \forces (\rho=\sigma)$. For any $q \in A$ with
$q \leq p$ we have $q \forces (\sigma = {\pi}_q)$ as above.
But also, $q \forces (\rho=\pi_q)$ by definition of $A$ and $\pi_q$.
So, $q \forces (\rho=\sigma)$ for all $q \in A$ with $q \leq p$.
Thus, $p \forces (\rho=\sigma)$.
\end{proof}
The previous lemma shows that there is no loss generality in using
full names for non-empty sets, in particular for the partial orders in
an iterated forcing. The next lemma shows that if we do this,
and if the partial orders are forced to be countably closed, then
$\omega$ fullness condition is satisfied.
\begin{lem}
Suppose $M$ is a transitive model of $\zfc$, $\bP \in M$, $\pi \in M^\bP$
is a full name for a non-empty set and $\bone_\bP \forces (\pi$ is a countably
closed partial order$)$. Then $\pi$ is $\omega$-full for $\bP$.
\end{lem}
\begin{proof}
Let $p \in \bP$ and suppose $p \forces (\sigma_{n+1} \leq \sigma_n)$
for all $n$. We follow the argument of the previous lemma. Let $A \subseteq
\bP$ be maximal subject to being an antichain and for all $q \in A$
either $q \leq p$ and there is a $\pi_q \in \dom(\pi)$ such that
$q \forces (\forall n\ \pi_q \leq \sigma_n)$, or $q \perp p$ and
for some $\pi_q \in \dom(\pi)$ we have $q \forces (\pi_q \in \pi)$.
Using the fact that $\bone \forces (\pi$ is countably closed $)$ it
follows that $A$ is a maximal antichain of $\bP$. For each $q \in A$
we construct $\tilde{\pi}_q$ as in the previous lemma, and then
let $\sigma= \bigcup_{q \in A} \tilde{\pi}_q$ as before. Exactly as before,
for $q \in A$, $q \forces (\sigma= \pi_q)$, and thus $\bone \forces (\sigma
\in \pi)$. Also, for all $q \in A$ with $q \leq p$ we have
$q \forces (\forall n\ \pi_q \leq \sigma_n)$. Thus, $p \forces
(\forall n\ \sigma \leq \sigma_n)$. By fullness, since
$p \forces (\sigma \in \pi)$, we have that for some $\sigma' \in \dom(\pi)$
that $p \forces (\sigma=\sigma')$. Hence, $p \forces (\forall n\
\sigma' \leq \sigma_n)$.
\end{proof}
Thus, in iterating countably closed forcings, there is
no harm in assuming the $\omega$ fullness condition is satisfied.
This next theorem shows that for countable support iterations, this is
enough to guarantee the iteration is countably closed.
\begin{thm} \label{thmctbsupp}
Let $M$ be a transitive model of $\zfc$, and $\itf \in M$ is an $\alpha$
length iteration with countable supports. Suppose for each $\beta < \alpha$
that $\bone_{\bP_\beta} \forces (\dq_\beta$ is countably closed $)$, and
that $\dq_\beta$ is $\omega$-full for $\bP_\beta$. Then $\bP_\alpha$
is countably closed.
\end{thm}
\begin{proof}
Work in $M$, and suppose $p^n = \langle \rho^n_\beta \rangle \in
\bP_\alpha$ are such that $p_{n+1} \leq p_n$ for all $n \in \omega$.
We define $p=\langle \rho_\beta \rangle \in \bP_\alpha$ with $p \leq
p^n$ for all $n$. Let $S_n = \supp(p^n)$, and $S=\bigcup_n S_n$. So,
$S \subseteq \alpha$ is countable. We define $\rho_\beta$ by
induction on $\beta$. Let $\rho_0 \in \bP_0$ extend all of the
$\rho^n_0$, which we can do as $\bP_0$ is countably closed. If $\beta
< \alpha$ is limit, let $p \res \beta= \bigcup_{\gamma < \beta} p \res
\gamma$. Assume now $p \res \beta$ is defined and $p \res \beta \leq
p^n \res \beta$ for all $n$. If $\beta \notin S$, let $\rho_\beta=
\bone_{\dq_\beta}$. Clearly in this case $p \res(\beta+1) \leq p^n\res
(\beta+1)$ for all $n$. Suppose now $\beta \in S$. For each $n$ we
have $p^{n+1} \res \beta \leq p^n \res \beta$ and $p^{n+1} \res \beta
\forces (\rho^{n+1}_\beta \leq \rho^n_\beta)$. So, $p \res \beta
\forces \forall n\ (\rho^{n+1}_\beta \leq \rho^n_\beta)$. By
$\omega$-fullness there is a $\rho_\beta \in \dom(\dq_\beta)$ such
that $p \res \beta \forces \forall n \ (\rho_\beta \leq
\rho^n_\beta)$. This defines $\rho_\beta=p(\beta)$, and thus $p \res
(\beta+1)$. Clearly $p \res (\beta+1) \leq p^n \res(\beta+1)$ for all
$n$. This defines $p$. By construction $\supp (p) \subseteq S$, so $p
\in \bP_\alpha$. Also, $p \leq p^n$ for all $n$.
\end{proof}
\section{Martin's Axiom}
We introduce Martin's axioms and use an iteration of finite support
\ccc{} forcings to show it is consistent (with $\neg \ch$).
\begin{defn}
Let $\kappa$ be an infinite cardinal. $\ma(\kappa)$ is the statement:
if $\bP$ is a \ccc{} partial order and $\{ D_\alpha \}_{\alpha < \kappa}$
is a $\kappa$ size family of dense subsets of $\bP$, then there is a
filter $G \subseteq \bP$ such that $G \cap D_\alpha \neq \emptyset$
for all $\alpha < \kappa$. $\ma$ is the statement that $\forall \kappa <
2^\omega\ \ma(\kappa)$.
\end{defn}
The following simple lemma is important for the proof.
\begin{lem} \label{lemmarred}
$\ma(\kappa)$ is equivalent to the statement that for any
$\ccc{}$ partial order $\bP= \langle \kappa, \leq \rangle$ on
$\kappa$, and any collection $\{ D_\alpha \}_{\alpha < \kappa}$
of dense subsets of $\bP$, there is a filter $G \subseteq \kappa$
meeting all of the $D_\alpha$.
\end{lem}
\begin{proof}
Let $\bQ = \langle Q, \leq_Q \rangle$ be a \ccc{} partial order.
Let $P \subseteq Q$ with $|P|= \kappa$ and $P$ sufficiently closed.
Specifically, we require:
\begin{enumerate}
\item \label{ma1}
For all $p \in P$ and all $\alpha < \kappa$, there is a $q \in D_\alpha$
with $q \leq p$.
\item \label{ma2}
If $p,q \in P$ are compatible in $\bQ$, then for some $r \in P$
we have $r \leq p,q$.
\end{enumerate}
Let $\bP=\langle P, \leq_\bP \rangle$ where
$\leq_\bP=\leq_\bQ \cap (P \times P)$. Let $E_\alpha= D_\alpha \cap P$
for $\alpha < \kappa$. Thus, $E_\alpha$ is dense in $\bP$.
Note that $\bP$ is still \ccc{} by \ref{ma2} (an antichain of $\bP$
is also an antichain of $\bQ$).
Suppose $G \subseteq P$ and $G \cap E_\alpha \neq \emptyset$
for all $\alpha < \kappa$. Let $H \subseteq Q$ be the filter on $\bQ$
generated by $G$ (i.e., $H=\{ q \in Q \colon \exists r \in G\
(r \leq q)\}$). Then $H \cap D_\alpha \neq \emptyset$ for all $\alpha
< \kappa$.
\end{proof}
The following technical lemma will also be used.
\begin{lem} \label{lemmartech}
Let $M$ be a transitive model of $\zf$, $\bP$, $\bQ$ partial orders
in $M$, and $e \colon \bP \to \bQ$ a complete embedding in $M$.
Let $H \subseteq Q$ and $G=e^{-1}(H)$. For $\sigma \in M^\bP$
we define $e'(\sigma) \in M^\bQ$ inductively by
$e'(\sigma)= \{ \langle e'(\rho), e(p) \rangle \colon
\langle \rho, p \rangle \in \sigma \}$. Then
for all $\sigma \in M^\bP$ we have $\sigma_G= (e'(\sigma))_H$.
\end{lem}
\begin{proof}
By induction on $\sigma$. We have
\begin{equation*}
\begin{split}
e'(\sigma))_H= & \{ e'(\rho)_H \colon \exists \langle \rho,p \rangle
\in \sigma\ (e(p) \in H) \} \\
& = \{ \rho_G \colon \exists \langle \rho,p \rangle
\in \sigma\ (e(p) \in H) \} \\
&= \{ \rho_G \colon \exists \langle \rho,p \rangle
\in \sigma\ (p \in G) \} \\
& = \sigma_G
\end{split}
\end{equation*}
\end{proof}
We are now ready to show the consistency of Martin's axiom.
\begin{thm}
Let $M$ be a transitive model of $\zfc$ and $\kappa$ a regular
cardinal of $M$ with $(2^{< \kappa}=\kappa)^M$.
Then there is a \ccc{} partial order $\bP \in M$
such that if $G$ is $M$-generic for $\bP$ then $M[G]$
satisfies $\ma + 2^\omega=\kappa$. In particular (since $\bP$
preserves cardinals), $\con(\zfc) \rightarrow
\con(\zfc + \ma + \neg \ch)$.
\end{thm}
\begin{proof}
We construct $\bP$ as a $\kappa$ length iteration of \ccc{}
forcings with finite support. It will then follow from lemma~\ref{lemfinccc}
that $\bP$ is \ccc{}. Thus $\bP$ will preserve all cardinals and
cofinalities. In particular, $\kappa$ will be a regular cardinal of
$M[G]$. Each stage $\bP\alpha$ (for $\alpha < \kappa$) of the iteration
will have size $< \kappa$ in $M$. The idea is to arrange so that
the iteration eventually forces with all possible $\bP_\alpha$
names for \ccc{} partial orders on some $\lambda < \kappa$, for all
$\alpha < \kappa$.
Fix in $M$ a bijection $b \colon \kappa \to \kappa \times \kappa$
with $b^{-1}$ increasing in each argument (so if $b(\alpha)=
(\beta, \gamma)$ then $\beta, \gamma \leq \alpha$).
As we define $\bP_\beta$ (for $\beta < \kappa$) we
simultaneously fix an enumeration $\{ \dq_\beta^\gamma \}_{\gamma < \kappa}$
of the the $\bP_\alpha$ nice names for a partial order on some
$\lambda_\gamma < \kappa$, that is, nice names such that such that
$$\bone_{\bP_\beta} \forces (\dq_\beta^\gamma
\text{ is a \ccc{} partial order} ).$$
Assuming inductively that
$|\bP_\beta| < \kappa$ and $\bP_\beta$ is \ccc{}, we can do this
as there at most $\sum_{\lambda < \kappa} (|\bP_\alpha|^{\omega})^{\lambda}
=\kappa$ many such names (this cardinality computed in $M$; we are also
implicitly using $\ac$ in $M$).
We now give the inductive definition of the $\dq_\alpha$, and hence of the
iteration (again, the iteration will be of finite support).
Suppose for $\beta \leq \alpha$ that $\bP_\beta$ is defined,
is \ccc{} in $M$, and
$|\bP_\beta| < \kappa$. Let $b(\alpha)=(\beta,\gamma)$.
Let $\dq_\alpha= e'_{\beta \alpha}(\dq_\beta^\gamma)$, where
$e_{\beta \alpha} \colon \bP_\beta \to \bP_\alpha$ is the
canonical embedding and $e'_{\beta \alpha}$ is as in lemma~\ref{lemmartech}.
From lemma~\ref{lemmartech} we have that $\bone_{\bP_\alpha}
\forces (\dq_\alpha$ is \ccc{} $)$. Clearly $\bP_{\alpha+1}$
satisfies our inductive hypotheses (note that in $M$ we have
$| \dq_\alpha | \leq \lambda_\gamma \cdot | \bP_\beta| < \kappa$).
The inductive hypotheses are satisfied at limit $\alpha$
from lemma~\ref{lemfinccc} (which show $\bP_\alpha$ is \ccc{}),
and the finite support condition (which gives that $|\bP_\alpha|=
\sum_{\beta<\alpha} |\bP_\beta| < \kappa$ by induction, as
$\kappa$ is regular).
Let $G$ be $M$-generic for $\bP=\bP_\kappa$. We claim that if
$\lambda < \kappa$ and $x \subseteq \lambda$ with $x \in M[G]$, then
for some $\alpha < \kappa$ we have $x \in M[G_{\leq \alpha}]$. To
see this, let $\sigma \in M^\bP$ be a nice name for $x$.
Clearly $|\sigma|< \kappa$. As $\kappa$ is regular, there is an
$\alpha < \kappa$ and a $\sigma' \in M^{\bP_\alpha}$ such that
$e'_{\alpha \kappa}(\sigma')=\sigma$. From lemma~\ref{lemmartech}
we have that $x=\sigma_G=(\sigma')_{G_{\leq \alpha}}$.
So $x \in M[G_{\leq \alpha}]$.
In particular, every $x \in \sP(\omega) \cap M[G]$ lies in some
$M[G_{\leq \alpha}]$. Thus there are at most
$\sum_{\alpha < \kappa} (|\bP\alpha|^\omega)^\omega = \kappa$
(this computation done in $M$) many reals in $M[G]$.
Thus, $(2^\omega \leq \kappa)^{M[G]}$. Since cofinally often
we force with the Cohen partial order, we clearly have
$(2^\omega \geq \kappa)^{M[G]}$. Hence $(2^\omega=\kappa)^{M[G]}$.
To show $M[G]$ satisfies $\ma$, it is enough to consider
by lemma~\ref{lemmarred} a partial order in $M[G]$
of the form $R= \langle \lambda, \leq_R \rangle$, where
$\lambda < \kappa$. Fix dense sets $\{ D_\delta \}_{\delta < \mu}$
where $\mu < \kappa$.
From the claim above, fix $\beta < \kappa$
such that $R \in M[G_{< \beta}]$ and $\{ D_\delta \}_{\delta < \mu} \in
M[G_{< \beta}]$. Let $\sigma \in M^{\bP_\beta}$
be a nice $\bP_\beta$ name for $R$. We may assume that
$\bone_{\bP_\beta} \forces (\sigma$ is a \ccc{} partial order$)$
[Let $p \in \bP_\beta$, $p \forces (\sigma$ is a \ccc{} partial order$)$.
Let $A \subseteq \bP_\beta$ be a maxiaml antichain containing $p$.
Fix a partial order $T$ in $M$. Let $\pi_p=\sigma$, and for
$q \in A$, $q \neq p$ let $\pi_q=\check{T}$. From $A$ and the $\pi_q$
we construct a name $\sigma'$ as in lemma~\ref{lemfull} such that
$p \forces (\sigma'=\sigma)$ and $\bone_{\bP\beta} \forces
(\sigma'$ is a \ccc{} partial order$)$. We may assume then
that $\sigma'$ is a nice name.] Let $\gamma < \kappa$ be such that
$\sigma'= \dq_\beta^\gamma$, and let $\alpha$ be such that
$b(\alpha)=(\beta,\gamma)$. Then $\dq_\alpha=e'_{\beta \alpha}(\sigma')$.
From lemma~\ref{lemmartech} we have $(\dq_\alpha)_{G_{< \alpha}}=
\sigma_{G_{< \beta}}=R$. From theorem~\ref{thmts}, $M[G_{\leq \alpha}]$
contains an $M[G_{< \alpha}]$-generic for $R$. This generic meets
all the dense sets $D_\delta$, $\delta < \mu$,
since they lie in $M[G_{< \beta}] \subseteq M[G_{< \alpha}]$.
Thus in $M[G]$ there is a filter meeting all of the dense sets
$D_\delta$.
\end{proof}
\end{document}