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