\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{\sB}{\mathcal{B}}
\newcommand{\ch}{\text{CH}}
\newcommand{\gch}{\text{GCH}}
\newcommand{\vb}{\text{var}}
\newcommand{\pa}{\text{PA}}
\newcommand{\fa}{\text{F}}
\newcommand{\con}{\text{CON}}


\newcommand{\bz}{\boldsymbol{0}}
\newcommand{\lD}{{\Delta}}
\newcommand{\lS}{{\Sigma}}
\newcommand{\lP}{{\Pi}}
\newcommand{\models}{\vDash}
\newcommand{\proves}{\vdash}
\newcommand{\sg}{\text{sg}}
\newcommand{\seq}{\text{Seq}}
\newcommand{\lh}{\text{lh}}
\newcommand{\pred}{\text{pred}}
\newcommand{\hod}{\text{HOD}}
\newcommand{\od}{\text{OD}}
\newcommand{\trcl}{\text{tr\,cl}}
\newcommand{\cl}{\text{cl}}
\newcommand{\rank}[1]{|#1|}
\newcommand{\llex}{<_{\text{lex}}}
\newcommand{\comp}{\parallel}
\newcommand{\forces}{\Vdash}
\newcommand{\inter}{\text{int}\,}
\newcommand{\defeq}{\doteq}
\newcommand{\lb}{\llbracket}
\newcommand{\rb}{\rrbracket}



\begin{document}




\begin{center}
\bf Introduction to Forcing
\end{center}
\bigskip


The forcing method ia a technique for taking a model 
of $\zf$ (usually $\zfc$) and enlarging it by adding a new
object $G$, called a generic, to produce a bigger 
universe $V[G]$. The method gives us enough control
over the model $V[G]$ that we can arrange that various 
statements of interest will be true in $V[G]$, if we choose
the $G$ in the right way. 


Before discussing the method itself, we first discuss a logical
problem. Since $V$ is, by definition, the class of all sets, 
we cannot enlarge it at all. What exactly do we mean then? 
This problem is actually not very serious, and can be dealt
with in several different ways. We mention one way now, and 
touch on the others later. First, if we are willing
to assume a tiny bit more than $\zfc$, namely $\zfc+ 
\con(\zfc)$, then the problem disappears altogether. 
For the theory $\zfc + \con(\zfc)$ proves that there
is a set model $M$ of $\zfc$. Since $M$ is a set, there is now
no reason why we cannot enlarge it to a bigger model $M[G]$. 
Since $M$ is a model of $\zfc$, it is just as good a starting point
as $V$. We could even (assuming $\ac$ in $V$) take $M$
to be countable by theorem~\ref{ctbsub}. 

If we are not willing
to strengthen $\zfc$, we can still proceed as follows. We would like
to argue that there is a model of $\zfc + \phi$, say. If not, 
then $\zfc \proves \neg \phi$, and so for finitely
many of the axioms of $\zfc$, say, $\{ \psi_1,\dots,\psi_n\}$
we would have $\{ \psi_1,\dots,\psi_n\} \proves \neg \phi$. 
However by the reflection theorem and theorem~\ref{ctbsub}
there is a countable set $M$ which satisfies 
$\{ \psi_1,\dots,\psi_n\}$. We may also assume $M$ satisfies
as many additional (but finitely many) axioms of $\zfc$
as we wish, so that any of the arguments needed for the 
forcing construction are also true in $M$. Then we may
do the forcining construction starting from $M$ to produce
$M[G]$, and we will have $\psi_1,\dots,\psi_n$ and $\phi$ all 
holding in $M[G]$ (the latter by the forcing construction). 
This will contradict the fact that 
$\{ \psi_1,\dots,\psi_n\} \proves \neg \phi$. 


The argument of the preceeding paragragh took place in the
meta-theory, but it will be easily formalizable to give
the theorem $\con(\zfc) \proves \con(\zfc + \phi)$. 


In what follows, we usually suppress mentioning these logical
points, and just assume $M$ is a countable transitive
model of $\zf$ or $\zfc$. We now turn to the forcing 
method itself. 



The basic setup for the forcing method will be a transitive
model $M$ of (enough of) $\zf$, and a partial order $\bP = \langle
P, \leq \rangle$ in $M$. Recall a partial order means a 
reflexive, transitive, binary relation on a set $\bP$. 
It is sometimes convenient, though not necessary, to assume
the partial order has a largest element, which we denote by 
$\bone$ (we can always adjoin a new maximal element to the
partial order, and none of the arguments below will be
effected). 



If $P$ is a partial order and $p,q \in P$, we say $p$ and 
$q$ are {\em compatible}, written $p \comp q$, 
 if there is an $r \in P$ such that 
$r \leq p$ and $r \leq q$. Otherwise they are 
incompatible, written $p \perp q$. If $A \subset P$ consists
of pairwise incompatible elements, we say $A$ is an {\em antichain}.
We say $D \subseteq P$ is {\em dense} if 
$\forall p \in P\ \exists q \leq p\ (q \in D)$. We say 
$D \subseteq P$ is {\em predense} if $\forall p \in P\ 
\exists q \in D\ (q \comp p)$. This is equivalent
to saying the downward closure $\{ p \in P \colon 
\exists q \in D\ p \leq q \}$ of $D$ is dense. 


\begin{defn}
A filter $G$ on a partial order $\bP$ is a $G \subseteq P$ 
satisfying
\begin{enumerate}
\item
$\forall p, q \in G\ (p \comp q)$.
\item
$\forall p \in G\ \forall q \geq p\ (q \in G)$.
\end{enumerate}
\end{defn}


\begin{exam}
Let $P=2^{< \omega}$, and define $p \leq q$ iff $p$ extends $q$. 
Then any filter $G$ on $P$ defines a $f_G \colon 2^\alpha \to 
\{ 0,1 \}$ for some $\alpha \leq \omega$. Conversely, any 
``real'' $x \in 2^\omega$ defines a filter over $P$. We could also consider
the variation where $P$ consists of finite partial functions
from $\omega$ to $2$. Again,  $p \leq q$ iff $p$ extends $q$. 
A filter gives a partial function from $\omega$ to $2$, and
any $x \in 2^\omega$ again defines a filter on $P$. 
\end{exam}


The next definition is a central one in the theory of forcing.


\begin{defn}
Let $M$ be a model of $\zf$, and $\bP \in M$ a 
partial order. We say a filter $G$ over $\bP$ is 
$M$-generic is $G \cap D \neq \emptyset$ for all 
dense $D \subseteq P$ with $D \in M$. 
\end{defn}


\begin{exer} \label{exerfor1}
Show that $G$ is $M$-generic iff $G$ meets all of the predense
sets $D \subseteq P$ in $M$ iff $G$ meets all of the 
maximal antichains $A \subseteq P$ in $M$. 
\end{exer}



\begin{exer} \label{exerfor2}
Show that if $A$ is dense below $p$, then any generic containing $p$
will meet $A$. 
\end{exer}



A generic $G$ is required to meet all of the dese sets $D$ 
which lie in $M$. $G$ itself will, in all non-triial cases, 
not be in $M$ itself. By non-trivial we can take the following.

\begin{defn}
$\bP$ is {\em splitting} if $\forall p \in P\ \exists 
q \leq p \ \exists r \leq p \ ( q \perp r)$. 
\end{defn}


\begin{lem}
If $G$ is $M$-generic for $\bP$, $p \in P$ and 
$\forall q \in G\ (p \parallel q)$, then $\exists q \in G\ (q \leq p)$.
\end{lem}


\begin{proof}
Let $D =\{ q \in P \colon (q \perp p) \vee (q \leq p)\}$.
Easily $D$ is dense. Let $q \in G \cap D$. We cannot have 
$q \perp p$ by assumption, so $q \leq p$.
\end{proof} 




\begin{lem}
If $M$ is a transituve model of $\zf$, $\bP \in M$, $\bP$ is splitting, and
$G$ is $M$-generic for $\bP$, then $G \notin M$. 
\end{lem}


\begin{proof}
Suppose $G \in M$. Consider $D=\{ p \in P \colon 
\exists q \in G\ (p \perp q)\}$. To see $D$ is dense, fix 
$p \in P$. Let $q \leq p$, $r \leq p$ with $q \perp r$. 
Then at least one of $q,r$ must be in $D$ as otherwise we could
extend $q,r$ to $q', r'$ respectively with $q', r' \in G$. 
Since $G$ is a filter, we could get an $s \leq q'$, $s \leq r'$,
contradicting $q \perp r$. So, $D$ is dense, and by assumption 
then $G \cap D \neq \emptyset$. This violates $G$ being a filter. 
\end{proof}



Can we find generics? The next lemma shows that we can always do this in 
the case where $M$ is countable. 



\begin{lem}
Let $M$ be a countable model of $\zf$, and $\bP \in M$. 
Then there is a $M$-generic filter $G$ for $P$. 
\end{lem}


\begin{proof}
Let $D_0, D_1, \dots$ enumerate the dense subsets of $P$ which 
lie in $M$. Using the denseness of the $D_n$, define a sequence 
$p_0 \geq p_1 \geq p_2 \geq \dots$ where $p_n \in D_n$. Let 
$G=\{ p \in P \colon \exists n \ (p \geq p_n) \}$. 
$G$ is easily a filter and by constuction meets all of the $D_n$.
\end{proof}



We will see the significance of generics shortly. First we describe
the constuction of the model $M[G]$ for $G$ a filter 
on the partial order $\bP \in M$ (we don't need $G$ to be 
generic for this construction). We would like $M[G]$ to be
the smallest model containing $M$ and $G$, in some sense. 
Every element $x$ of $M[G]$ will have a {\em name} $\tau$ in $M$. 
The filter $G$ will define an evaluation map $\tau \to \tau_G$
from the names to the elements of $M[G]$, so every $x \in M[G]$
will be of the form $x=\tau_G$. The names will live in $M$ 
(i.e., be a class in $M$), but since $G \notin M$, the evaluation
map will not be definable in $M$. First we 
define the class $M^\bP$ of names.



\begin{defn}
Let $M$ be a model of $\zf$, and $\bP \in M$ a partial order. 
By transfinite recursion on $\on^{M}$ we define $M_\alpha^\bP$ 
as follows: $M_0^\bP= \emptyset$. For $\alpha$ limit, 
$M_\alpha^\bP= \bigcup_{\beta < \alpha} M_\beta^\bP$. 
We define $\tau \in M_{\alpha+1}$ iff $\tau \in M_\alpha$ or 
$\tau$ is a relation with $\dom(\tau) \subseteq M_{\alpha}$ and
$\ran(\tau) \subseteq P$. We let $M^\bP= 
\bigcup_{\alpha \in \on^M} M_\alpha^\bP$.
\end{defn}



Thus a name $\tau$ is a set of ordered pairs $\langle 
\sigma, p \rangle$ where $\sigma$ is a name of smaller rank and
$p \in P$. Note that the construction of the names is exactly
like the construction of the universe of sets itself (i.e., the rank
hierarchy) except that the elements of a set are ``tagged'' with
elements of the partial order $P$. Intuitively, the tag $p$ 
tells us to throw the corresponding element into the set
if $p \in G$. We define the evaluation map as follows.


\begin{defn}
Let $M$ be a model of $\zf$, and 
$\bP \in M$ a partial order. Let $G \subseteq P$ be a filter. 
for $\tau \in M^\bP$, $\tau_G$ is defined by transfinite recursion
on $\epsilon$ by: 
$\tau_G= \{ \sigma_G \colon \exists p \in G \colon \langle 
\sigma, p \rangle \in \tau \}$. 
\end{defn}

We define some canonical names which always evaluate to certain 
objects.


\begin{defn}
Let $M$ be a model of $\zf$, and $\bP \in M$ a partial order.
By transfinite recursion in $M$, define for each $x \in M$ the
name $\check{x}$ by: $\check{x}= \{ \langle \check{y},p \rangle 
\colon y \in x \wedge p \in P\}$. Define the name $\dot{G}$
by $\dot{G} =\{ \langle \check{p}, p \rangle \colon p \in P\}$.
\end{defn}



For any wellfounded model $M$ of $\zf$, it is a straightforward
induction to show that for all $x \in M$ that $\check{x}_G=x$. 
It follows that $(\dot{G})_G=G$. Thus, we have canonical names for
all of the sets in $M$ as well as the filter $G$. Note that the 
function $x \mapsto \check{x}$ is a class function in $M$. 
We thus have:

\begin{lem}
For any transitive model $M$ of $\zf$, partial order 
$\bP \in M$ and filter $G$ on $\bP$, $M \subseteq M[G]$ and 
$G \in M[G]$.
\end{lem}


We would like to say that $M[G]$ is the smallest model of $\zf$
containing $M$ and $G$, but we don't know that $M[G]$ is a 
model of $\zf$. This will not, in fact, be true for all $G$,
but will be true for the generic $G$. The forcing theorem
will give us the tools to show this, as well as relating truth
in $M[G]$ to truth in $M$ in general. First we prove a few more
simple facts about $M[G]$. 


\begin{lem}
$M[G]$ is transitive and $\on^{M[G]}=\on^{M}$.
\end{lem}

\begin{proof}
If $x \in M[G]$, then $x=\tau_G$ for some $\tau \in M^\bP$. 
If $y \in x$, then by definition of $\tau_G$ we have 
$y=\sigma_G$ for some $\sigma \in M^\bP$ (in fact, 
$\sigma \in \trcl(x)$). So, $y \in M[G]$.  Since $M$, $M[G]$
are transitive, $\on^M=\on \cap M$ and $\on^{M[G]}=
\on \cap M[G]$. So, to show $\on^M=\on^{M[G]}$ it suffices
to show that every $x \in M[G]$ has rank less than $\on^M$. 
By a straightforward induction on $\on^M$ we have that if 
$\tau \in M^\bP_\alpha$, then $|\tau_G| \leq \alpha$. 
\end{proof}



Since $M[G]$ is transitive, it satisfies foundation
and extensionality. One can also show directly that it
satisfies pairing and union. For example, if 
$\tau_G$, $\sigma_G \in M[G]$, then $\rho= \{ 
\langle \tau, \bone\rangle , \langle \sigma, \bone \rangle \}$
is such that $\rho_G=\{ \tau_G, \sigma_G \}$. Note that 
these fact do not require $G$ to be generic, they are 
true for any filter $G$ on $\bP$. To show the other
axioms, and to further explore the model $M[G]$ however
requires the forcing theorem which relates truth in 
$M[G]$ to truth in $M$ for generic $G$. 


\begin{defn}
By the {\em forcing language} we mean all statements of the form 
$\phi(\sigma_1,\dots,\sigma_n)$ where $\phi(x_1,\dots,x_n)$
is a formula in the language of set theory and 
$\sigma_1,\dots,\sigma_n \in M^\bP$. 
\end{defn}



We now define the forcing relation, which is the central concept in the
theory of forcing. For $p \in \bP$ and $\phi(\sigma_1,\dots,\sigma_n)$
in the forcing language, we define the notion 
$p \forces \phi(\sigma_1,\dots,\sigma_n)$ (read $p$ forces 
$\phi(\sigma_1,\dots,\sigma_n)$). Formally, this is defined by induction
on $\phi$, where for atomic $\phi$ it is defined by transfinite
recursion in $M$ on the maximum of the ranks of 
the $\sigma_i$. This definition, it is important to note,
takes place entirely inside of $M$ (more precisely, for each 
formula $\phi$ there is a class function in $M$ from 
$(M^\bP)^n$ to $\bP$ assigning to each $(\sigma_1,\dots,\sigma_n)
\in (M^\bP)^n$ the set $\{ p \in P \colon p \forces 
\phi(\sigma_1,\dots,\sigma_n)\}$). 


\begin{defn} \label{defforcing}
Let $M$ be a transitive model of $\zf$ and $\bP$ a partial
order in $M$. For $p \in P$ and $\phi(\sigma_1,\dots,
\sigma_n)$ in the forcing language, the relation 
$p \forces \phi(\sigma_1,\dots,\sigma_n)$ is defined 
by transfinite recursion through the following cases.

Case 1) $\phi= (\tau_1 \in \tau_2)$. 
\smallskip

\noindent
We define $p \forces \tau_1 \in \tau_2$ iff 
$\{ q \colon \exists \langle \sigma, r \rangle \in \tau_2\ 
(q  \leq r \wedge q \forces (\tau_1\approx  \sigma)) \}$ is dense below $p$.
\medskip


Case 2)  $\phi= (\tau_1 = \tau_2)$.
\smallskip

\noindent
We define  $p \forces \tau_1 \approx \tau_2$ iff
for all $\langle \sigma_1, q \rangle \in \tau_1$, the 
set $$\{ r \colon (r \leq q \rightarrow 
\exists \langle \sigma_2, s \rangle \in \tau_2\ 
r \leq s \wedge r \forces (\sigma_1 \approx \sigma_2)) \}$$ 
is dense below $p$, and likewise for all 
$\langle \sigma_2, q \rangle \in \tau_2$ the set 
$$\{ r \colon (r \leq q \rightarrow 
\exists \langle \sigma_1, s \rangle \in \tau_1\ 
r \leq s \wedge r \forces (\sigma_1 \approx \sigma_2)) \}$$ 
is dense below $p$. 
\medskip


Case 3) $\phi= \alpha \wedge \beta$.
\smallskip


\noindent
We define $p \forces \alpha \wedge \beta$ iff 
$p \forces \alpha$ and $p \forces \beta$. 
\medskip




Case 4) $\phi= \neg \psi$.
\smallskip

\noindent
We define $p \forces \neg \psi$ iff $\neg \exists q \leq p \
q \forces \psi$.
\medskip




Case 5) $\phi(\sigma_1,\dots,\sigma_n)=\exists x \psi(\sigma_1,\dots,
\sigma_n,x)$. 
\smallskip

\noindent
We define $p \forces \exists x \psi(\sigma_1,\dots,\sigma_n,x)$
iff $\{ q \colon \exists \tau \in M^\bP\ 
q \forces \psi(\sigma_1,\dots,\sigma_n,\tau) \}$ is dense below $p$.
\end{defn}



The motivation for the definition is our desire to control truth
in $M[G]$. We would like to have that $p \forces 
\phi(\sigma_1,\dots,\sigma_n)$ iff for every generic $G$
containing $p$ we have $M[G] \models \phi((\sigma_1)_G,\dots,
(\sigma_n)_G)$. In other words, for every statement
in the forcing language, the truth of the statement, view as a function
on the set of generics, is continuous. The reader will note the
analogy with a basic theorem in analysis. Namely, 
every reasonable (say, Borel) function $f \colon \R \to 
\{ 0, 1\}$ (or even $f \colon \R \to \R$) is continuous
when resticted to a certain comeager set. The generics serve the
role as the comeager set, for all truth functions for all
statements in the forcing language simultaneously. 

The motivation for the definitions in the various specific cases
should now be fairly clear if we keep in mind the definition
of a generic. For example, in Case~1 above, we are really asserting
that any generic $G$ which contains $p$ will contain a $q \leq p$
such that for some $\langle \sigma, r \rangle \in \tau_2$ with 
$q \leq r$ (hence $\sigma_G \in (\tau_2)_G$) we have 
$q \forces \tau_1=\sigma$ (which by induction should mean that 
$(\tau_1)_G=\sigma_G$). We have used here exercise~\ref{exerfor2}.


\begin{lem} \label{ftriv}
If $p \forces \phi$ and $q \leq p$, then $q \forces \phi$. 
Conversely, if $\{ q \colon q \forces \phi \}$ is dense below $p$, then
$p \forces \phi$. 
\end{lem}


\begin{proof}
Suppose $p \forces \phi$ and $q \leq p$. If $\phi$ is atomic or 
existential, the definition of $p \forces \phi$ is that a certain set $A$
is dense below $p$, and the definition of $A$ does not involve $p$. 
Trivially, $A$ is dense below $q$ as well, so $q \forces \phi$. 
The conjuction case follows immediately by induction. 
The negation case is trivial as if $\neg \exists s \leq p (s \forces
\psi)$ then $\neg \exists s \leq q (s \forces
\psi)$. 

Suppose next that $\{ q \colon q \forces \phi \}$ is dense below $p$. 
The atomic and existential cases follow from the fact that if 
$\{ q \colon A$ is dense below $q\}$ is dense below $p$, then $A$ is dense
below $p$. The conjuction case again follows immediately by induction. 
For the negation case $\phi=\neg \psi$, our assumption is that 
$\{ q \colon \neg \exists r \leq q\ (r \forces \psi)\}$ is dense
below $p$. Now, if $q \leq p$, then $q \nvdash \psi$, as otherwise 
from the first paragraph we would have that any extension of $q$
forces $\psi$, contradicting our assumption. Hence, by definition
$p \forces \neg \psi$. 
\end{proof}


\begin{cor} \label{corftriv}
If $p \nvdash \phi$, then for some $q \leq p$, $q \forces \neg \phi$.
In particular, for any $\phi$, $\{ p \colon (p \forces \phi)
\vee (p \forces \neg \phi)\}$ is dense.
\end{cor}

\begin{proof}
If the conclusion fails, then $\{ r \colon r \forces \phi \}$ is dense
below $p$. From lemma~\ref{ftriv} it follows that $p \forces \phi$.
\end{proof}




\begin{exer}
Show that $p \forces \neg \neg \phi$ iff $p \forces \phi$.
(hint: unravel the definition of $p \forces \neg \neg \phi$
and use the second part of lemma~\ref{ftriv}).
\end{exer}

\begin{lem} \label{ft1}
If $G$ is a generic filter and $p,q \in G$, then
$\exists r \in  G\ (r \leq p \wedge r \leq q)$. 
\end{lem}

\begin{proof}
Let $D=\{ r \colon (r \perp p) \vee (r \perp q) \vee
(r \leq p \wedge r \leq q)\}$. Easily $D$ is dense 
(if $t \in P$ then either $t \perp p$ or there is a 
$u \leq t$ with $u \leq p$. Either $u \perp q$ or there is a 
$v \leq u$ with $v \leq q$, and also $v \leq u \leq p$).
Let $r \in G \cap D$. Since $G$ is a filter, we cannot have
$r \perp p$ or $r \perp q$, so $r \leq p$ and $r \leq q$.
\end{proof}





We now state precisely and prove the forcing theorem. For the
theorem to make sense, we need to know that generic filters exist, 
and so we will now require the model $M$ to be countable. 




\begin{thm} [Forcing Theorem] \label{fthm}
Let $M$ be a countable, transitive model of $\zf$ and $\bP \in M$ a 
partial order. 
\begin{enumerate}
\item
For any $p \in P$ and $\sigma_1,\dots,\sigma_n \in M^\bP$,
$p \forces \phi(\sigma_1,\dots,\sigma_n)$ iff 
for all generic $G$ containing $p$, $\phi((\sigma_1)_G,\dots,
(\sigma_n)_G)^{M[G]}$.
\item
For any generic $G$, and $\sigma_1,\dots,\sigma_n \in M^\bP$,
$\phi((\sigma_1)_G,\dots,(\sigma_n)_G)^{M[G]}$ iff 
$\exists p \in G\ p \forces \phi(\sigma_1,\dots,\sigma_n)$.
\end{enumerate}
\end{thm}



\begin{proof}
We first show that (2) implies (1). Assume first that 
$p \forces \phi$, and let $G$ be a generic containing $p$. 
By (2), $\phi^{M[G]}$.
Assume next that 
for all generic $G$ containing $p$ that $\phi^{M[G]}$. 
If $p \nVdash \phi$, then by corollary~\ref{corftriv}
there would be a $q \leq p$ such that $q \forces \neg \phi$. 
Let $G$ be a generic filter containing $q$. From (2), 
$(\neg \phi)^{M[G]}$, which contradicts our assumption. 

We turn our attention to (2). We prove this by induction on
$\phi$, and when $\phi=(\tau_1 \approx \tau_2)$ by induction
on the maximum rank of $\tau_1$, $\tau_2$. 
We consider cases as in the definition of the forcing relation. 


Case 1) $\phi=(\tau_1 \in \tau_2)$. 
\smallskip

\noindent
First assume $p \forces \phi$. Let $G$ be generic containing $p$.
By definition, $D=\{ q \colon \exists \langle \sigma, r \rangle \in 
\tau_2\ (q \leq r \wedge q \forces (\tau_1 \approx \sigma)) \}$
is dense below $p$. Since $G$ is generic, $\exists q \in G \cap D\ 
(q \leq p)$. Let $\langle \sigma, r \rangle \in \tau_2$ 
be such that $q \leq r$ and $ q \forces (\tau_1 \approx \sigma)$. 
By the equality case (proven next) 
we may assume that $(\tau_1)_G= \sigma_G$. 
Since $r \in G$, $\sigma_G \in (\tau_2)_G$ by definition of 
$(\tau_2)_G$. Thus, $(\tau_1)_G \in (\tau_2)_G$. 

Next assume that $G$ is generic and $\phi^{M[G]}$, that is, 
$(\tau_1)_G \in (\tau_2)_G$. Let $\langle \sigma, q \rangle \in 
\tau_2$ be such that $q \in G$ and $(\tau_1)_G= \sigma_G$. 
By the equality case, let $r \in G$ be such that 
$r \forces (\tau_1 \approx \sigma)$. From lemma~\ref{ft1},
let $p \in G$ with $p \leq q, r$. Then $p \forces 
\tau_1 \in \tau_2$ since for any $s \leq p$ we have 
$\langle \sigma, q \rangle \in \tau_2$, $s \leq p \leq q$, and
$s \forces (\tau_1 \approx \sigma)$ since $s \leq r$. Thus, the
set required to be dense below $p$ in the definition of $p \forces 
\tau_1 \in \tau_2$ is actually all $s \leq p$.  
\medskip


Case 2)  $\phi=(\tau_1 \approx \tau_2)$.
\smallskip

\noindent
First assume $p \forces \tau_1 \approx \tau_2$. 
Let $G$ be generic containing $p$. 
It suffices by symmetry to show that $(\tau_1)_G \subseteq (\tau_2)_G$.
Let $x \in (\tau_1)_G$, say $x= (\sigma_1)_G$ where $\langle \sigma_1, q
\rangle \in \tau_1$ and $q \in G$. By definition, the set 
$D=\{ r \colon (r \leq q \rightarrow 
\exists \langle \sigma_2, s \rangle \in \tau_2\ 
r \leq s \wedge r \forces (\sigma_1 \approx \sigma_2)) \}$ is dense below $p$.
$D'= \{ r \leq p \colon (r \perp q) \vee (
r \leq q \wedge r \in D) \}$. 
Then $D'$ is easily dense below $p$ (if $t \leq p$ then either 
$t \perp q$ or we can extend $t$ to a $u \leq t$ with $u \leq q$.
since $u \leq p$, we can get $v \leq u$ with $v \in D$. 
Then $v \leq t$ and $v \in D'$.) Let $r \in G \cap D'$. 
We cannot have $r \perp q$  as $q \in G$. So, $r \leq q$ and 
$r \in D$. By definition of $D$ we now have a 
$\langle \sigma_2,s \rangle \in \tau_2$ with 
$r \leq s$ and $r \forces  (\sigma_1 \approx \sigma_2)$. 
By induction, $(\sigma_1)_G=(\sigma_2)_G$. Since $r \in G$ and $r \leq s$,
$(\sigma_2)_G \in (\tau_2)_G$. Hence, $x=(\sigma_1)_G=(\sigma_2)_G
\in (\tau_2)_G$. 


Next assume that $\phi^{M[G]}$, that is, $(\tau_1)_G=(\tau_2)_G$.
Let 
\begin{equation*}
\begin{split}
D=& \{ p \colon (p \forces \tau_1 \approx \tau_2) \vee \\ & 
\exists \langle \sigma_1,q_1 \rangle \in \tau_1 \ 
[p \leq q_1 \wedge \forall r \leq p\ \forall \langle \sigma_2, q_2 \rangle 
\in \tau_2\ \neg (r \leq q_2 \wedge r \forces \sigma_1 \approx \sigma_2) ]\, \}.
\end{split}
\end{equation*}
We first claim that $D$ is dense. To see this, let $p \in P$. 
If $p \forces \tau_1 \approx \tau_2$, then $p \in D$. Otherwise, 
for some $\langle \sigma_1,q_1 \rangle \in \tau_1$ the set 
$A= \{ s \colon (s \leq q_1 \rightarrow \exists \langle \sigma_2,q_2 \rangle 
\in \tau_2\ (s \leq q_2 \wedge s \forces \sigma_1 \approx \sigma_2)) \}$
is not dense below $p$. Let $p' \leq p$ be such that $\forall s \leq p'\ 
s \notin A$. Thus, for all $s \leq p'$ we have 
$s \leq q_1$ (so in particular $p' \leq q_1$), and 
$\neg \exists \langle \sigma_2,q_2 \rangle 
\in \tau_2\ (s \leq q_2 \wedge s \forces \sigma_1 \approx \sigma_2))$.
Thus, $p' \in D$. This shows $D$ is dense. Let $p \in G \cap D$. 
If $p \forces \tau_1 \approx \tau_2$, we are done, so suppose the
second disjunct in the definition of $D$ holds. 
Let $\langle \sigma_1, q_1 \rangle $ with $p \leq q_1$ be as in the
second disjunct. Since $p \in G$, $(\sigma_1)_G \in (\tau_1)_G= (\tau_2)_G$. 
So, let $\langle \sigma_2,q_2 \rangle \in \tau_2$ be such that 
$q_2 \in G$ and $(\sigma_1)_G=(\sigma_2)_G$. By induction, let 
$q \in G$ be such that $q \forces \sigma_1 \approx \sigma_2$. 
Let $r \leq p,q, q_2$. Then $r$ violates the definition of $p \in D$. 
\medskip


Case 3) $\phi=\alpha \wedge \beta$.
\smallskip

\noindent
If $p \forces \phi$, then by definition $p \forces \alpha$ and $p \forces \beta$. 
By induction, $\alpha^{M[G]}$ and $\beta^{M[G]}$, and so 
$\phi^{M[G]}$. Conversely, if $\phi^{M[G]}$, then $\alpha^{M[G]}$
and $\beta^{M[G]}$. By induction, $\exists p \in G\ p \forces 
\alpha$ and $\exists q \in G\ q \forces \beta$. Let $r \in G$ with 
$r \leq p,q$. Then $r \forces \alpha$, $r \forces \beta$, and so 
$r \forces \phi$.
\medskip


Case 4) $\phi= \neg \psi$.
\smallskip

\noindent
Assume first $p \forces \phi$. If $\psi^{M[G]}$ then by induction
$\exists q \in G\ (q \forces \psi)$. Let $r \leq p,q$. 
Then $r \forces \neg \psi$ and $r \forces \psi$, a contradiction
to the definition of $r \forces \neg \psi$. Thus, $\phi^{M[G]}$.
Next assume $\phi^{M[G]}$. Let $D=\{ p \colon 
(p \forces \psi) \vee (p \forces \neg \psi) \}$. Then $D$ is dense,
so let $p \in G \cap D$. If $p \forces \neg \psi$ we are done, so
assume $p \forces \psi$. By induction, $\psi^{M[G]}$ which
contradicts $\phi^{M[G]}$. 
\medskip

Case 5) $\phi(\vec \sigma)= \exists x\ \psi(\vec \sigma, x)$.
\smallskip


First assume $p \forces \phi$ and $G$ is generic containing $p$. 
By definition $D=\{ q \colon \exists \tau \in M^\bP\ (q \forces
\psi(\vec \sigma, \tau)) \}$ is dense below $p$. Let $q \in G \cap D$
with $q \leq p$. Let $\tau \in M^\bP$ witness $q \in D$, so 
$q \forces \psi(\vec \sigma, \tau)$. By induction, 
$\psi((\sigma_1)_G,\dots,(\sigma_n)_G,\tau_G)^{M[G]}$. Thus, 
$\phi((\sigma_1)_G,\dots,(\sigma_n)_G)^{M[G]}$. 

Next assume that $g$ is generic and 
$\phi((\sigma_1)_G,\dots,(\sigma_n)_G)^{M[G]}$.
Let $\tau \in M^\bP$ be such that 
$\psi((\sigma_1)_G,\dots,(\sigma_n)_G), \tau_G)^{M[G]}$. 
By induction, $\exists p \in G\ 
p \forces \psi(\sigma_1,\dots,\sigma_n,\tau)$. Trivially then 
$D=\{ q \colon \exists \tau \in M^\bP\ (q \forces
\psi(\vec \sigma, \tau) \}$ is dense below $p$ (it contains all 
$q \leq p$), and so $p \forces \phi(\sigma_1,\dots,\sigma_n)$.
\end{proof}


This completes the proof of the forcing theorem.


We next show that if $M$ satisfies $\zf$ or $\zfc$, then so does $M[G]$.
Although we are mainly interested in what additional properties we 
can arrange to hold in $M[G]$, the proof will give us some practice
in using the forcing theorem. 


\begin{thm}
Let $M$ be a transitive model of $\zf$ (or $\zfc$), and $\bP \in M$
a partial order. Suppose $G$ is $M$-generic for $\bP$. Then 
$M[G]$ satisfies $\zf$ (or $\zfc$).
\end{thm}


\begin{proof}
We have already checked that $M[G]$ is transitive and satisfies foundation,
extensionality and pairing. Union is also easy to check directly
as if $x= \tau_G \in M[G]$, let $\sigma= \{ \langle \rho, \bone \rangle 
\colon \exists \pi \in M^\bP\ \exists p,q \in P \ 
(\langle \pi, p \rangle \in \tau \wedge \langle \rho, q \rangle \in 
\pi) \}$. Clearly $\cup x \subseteq \sigma_G$. 
As $M \subseteq M[G]$, and $\omega \in M$, $\omega \in M[G]$ and 
by absoluteness $M[G]$ satifies the infinity axiom. 

To verify Power Set, let $x= \tau_G \in M[G]$. Let 
$\rho= \{ \langle \sigma, \bone \rangle \colon \dom(\sigma) \subseteq 
\dom(\tau) \}$. Clearly $\rho$ is a set in $M$ and $\rho \in M^\bP$. 
We claim that $\sP(x)^{M[G]} \subseteq \rho_G$, which suffices. To see this, let 
$y \subseteq x$, $y \in M[G]$. Say, $y= \mu_G$. Let $\sigma=\{ 
\langle \pi, p \rangle \colon \pi \in \dom(\tau) \wedge 
p \forces (\pi \in \mu) \}$. Clearly $\langle \sigma, \bone \rangle 
\in \rho$ and so $\sigma_G \in \rho_G$. We claim that $\sigma_G=
\mu_G$. If $z \in \sigma_G$, then $z= \pi_G$ where 
$\langle \pi, p \rangle \in \sigma$ and $p \in G$. Since 
$p \forces (\pi \in \mu)$ (from the definition of $\sigma$) 
we have $z=\pi_G \in \mu_G$ by the forcing theorem. If 
$z \in \mu_G$, then since $\mu_G \subseteq x$ we have 
$z= \pi_G$ for some $\langle \pi, p \rangle \in \tau$. 
By the forcing theorem, there is a $q \in G$ such that 
$q \forces \pi \in \mu$, and hence $\langle \pi, q \rangle \in 
\sigma$ and so $z \in \sigma_G$. 


To verify Comprehension, let $\phi(x_1,\dots,x_n, y,z)$ be a formula and 
$a_1=(\sigma_1)_G$, $\dots,a_n=(\sigma_n)_G$, $b=\tau_G \in M[G]$. 
We must show that $$\{ z \in b \colon \phi^{M[G]}(a_1,\dots,a_n, 
b,z) \} \in M[G].$$ Let $\rho= \{ \langle \pi ,p \rangle \colon 
(\pi \in \dom \tau) \wedge (p \forces \phi(\sigma_1,\dots,\sigma_n,
\tau, \pi) \wedge \pi \in \tau) \}$. 
We show that $\rho_G$ works. If $z \in \rho_G$, 
then $z= \pi_G$ where $p \in G$ and $p \forces \phi(\sigma_1,\dots,\sigma_n,
\tau, \pi)$ and $p \forces \pi \in \tau$. 
Thus, $\phi^{M[G]}(a_1,\dots,a_n,b, z)$ and $z=\pi_G \in \tau_G=b$. 
Conversely, suppose $z \in b$ and $\phi^{M[G]}(a_1,\dots,a_n, 
b,z)$. Then $z= \pi_G$ for some $\pi \in \dom(\tau)$. 
By the forcing theorem, there is a $p \in G$ such that 
$p \forces \phi(\sigma_1,\dots,\sigma_n,
\tau, \pi) \wedge \pi \in \tau$. Then $\langle \pi, p \rangle \in 
\rho$, and so $z= \pi_G \in \rho_G$. 


To verify Replacement, let $\phi(x_1\dots,x_n, y,z,w)$ be a formula
and $a_1=(\sigma_1)_G$, $\dots,a_n=(\sigma_n)_G$, $A=\tau_G \in M[G]$.
Assume that $$\forall z \in A\ \exists w \in M[G]\ 
\phi^{M[G]}(a_1,\dots,a_n,A,z,w).$$
By replacement in $M$ there is a set
of names $S \in M$ such that for all $\pi \in \dom (\tau)$ and 
all $p \in P$, if $\exists \mu \in M^\bP\ 
(p \forces \phi(\sigma_1,\dots,\sigma_n, \tau, \pi, \mu))$, then 
$\exists \mu \in S\ 
(p \forces \phi(\sigma_1,\dots,\sigma_n, \tau, \pi, \mu))$.
Let $\rho=\{ \langle \mu , \bone \rangle \colon \mu \in S \}$. 
We show that $\rho_G$ verifies this instance of replacement in $M[G]$. 
For suppose $z \in A$, say $z= \pi_G$ where $\pi \in \dom(\tau)$, 
and suppose $\exists w \in M[G]\  \phi^{M[G]}(a_1,\dots,a_n,A,z,w)$. 
Fix such a $w=\mu_G$. By the forcing theorem, there is a $p \in G$ such that 
$p \forces \phi(\sigma_1,\dots,\sigma_n, \tau, \pi, \mu)$. 
From the definition of $S$ it follows that for some $\mu \in S$ that 
$p \forces \phi(\sigma_1,\dots,\sigma_n, \tau, \pi, \mu)$. Fix such a 
$\mu$. Then $\mu_G \in \rho_G$ and by the forcing theorem 
$\phi^{M[G]}(a_1, \dots, a_n, A, z,\mu_G)$. 


We have now verified $\zf$ in $M[G]$. Suppose finally that $\ac$ holds
in $M$, and we check it holds in $M[G]$ as well. Let $x= \tau_G \in M[G]$. 
Let $f \colon \alpha \to \dom(\tau)$, $f \in M$ be a bijection, where 
$\alpha \in \on^M$. In $M[G]$ define $F$ with domain $\alpha$ by 
$F (\beta)=f(\beta)_G$. Then $x \subseteq \ran(F)$, which suffices to
show that $x$ can be wellordered in $M[G]$ (recall $M[G]$ already satisfies
$\zf$). 
\end{proof}




\begin{exer}
Show that if $M$ is a transitive model of $\zf$, $\bP \in M$
is a partial order, and $G \subseteq P$ is a filter (not 
necessarily generic), then $M[G] \models 
\forall x\ \exists f\ \exists \alpha\ (\alpha \in \on \wedge 
f \colon \alpha \overset{\text{onto}}{\longrightarrow} x)$.
\end{exer}




\section{Forcing and Complete Boolean Algebras}


The forcing theorem holds for arbitrary partial orders, but it is 
an interesting fact that there is no loss of generality 
(assuming our models $M$ are models of $\zf$) in considering
only partial orders which are complete Boolean algebras (where
$p \leq q$ recall means $p \cdot q^c=0$). Although most of the time
we deal directly with a partial order, there are times when this
point of view is useful. Given a partial order 
$\bP=\langle P,\leq \rangle$, we will associate to it a complete 
Boolean algebra $\sB_P$ which we will call the {\em completion}
of $\bP$. This construction is just a slight generalization 
of the construction of the completion of a Boolean algebra, but 
we give the construction from scratch. 

For $p \in P$, let $N_p=\{ q \in P \colon q \leq p\}$. 
The idea of the construction is to identify every set 
$D \subseteq N_p$ which is dense below $p$ with all of 
$N_p$. One way to make this precise is as follows. 
Define a topology $\tau$, on $P$ by taking as a base sets of the 
form $N_p$. Recall $B\subseteq \sP(X)$ is a base for a topology on a set $X$ 
iff whenever $U, V \in B$ and $x \in U \cap V$, then there is a 
$W \in B$ such that $x \in W \subseteq U \cap V$. This condition is
satisfied here since in fact if $r \in N_p \cap N_q$ then 
$N_r \subseteq N_p \cap N_q$ (by transitivity). So, $A \subseteq P$
is $\tau$-open iff $A$ is downwards closed, that is, 
$\forall p \in A\ \forall q \leq p \ (q \in A)$. Note that $N_p$
is the smallest open set containing $p$. Recall a set $U$ in a
topological space is {\em regular open} if $U= \inter \cl (U)$. 
Thus, an open set is regular open iff it contains
any neighborhood in which it is dense. 
Recall also that for any set $A \subseteq X$ that $\inter \cl (A)$
is regular open. [One direction, namely $U \subseteq \inter \cl (U)$
holds for any open set. For the other direction note that 
$\inter \cl ( \inter\, \cl (A)) \subseteq \inter \cl\, \cl (A) 
=\inter \cl (A)$.] It is easy to see that the intersection of two 
regular open sets is regular open. 


\begin{exer}
Show directly that an open $U \subseteq P$ is regular open iff 
whenever $U$ is dense below a $p \in P$, then $p \in U$. 
\end{exer}


\begin{defn}
Let $\bP=\langle P, \leq \rangle$ be a partial order. Then 
$\sB_P$ is the collection of all regular open subsets of $P$
with the following operations: $U + V= \inter \cl (U \cup V)$, 
$U \cdot V= U \cap V$, $-U=int(P-U)$. Also, define $0_\sB= \emptyset$ and 
$1_\sB=P$ (note: we use here $-U$ for the Boolean complement
operation to avoid confusion.)
\end{defn}



\begin{lem} \label{parcomp}
For any partial order $\bP$, $\sB_P$ is a complete Boolean algebra.
Moreover, the map $\pi \colon P \to \sB$ defined by $\pi(p)=\inter \cl(N_p)$
satisfies the following:
\begin{enumerate}
\item
If $p \leq q$ then $\pi(p) \leq \pi(q)$. 
\item
$p \perp q$ iff $\pi(p) \perp \pi(q)$.
\item
$\pi^{''}\bP$ is dense in $\sB$. 
\end{enumerate}
\end{lem}


\begin{proof}
In fact, for any topological space $X$ the regular open sets form a 
complete Boolean algegra (with the same operations defined above).
Checking this is straightforward but tedious. 
The commutative, identity, and $0-1$ laws are trivial to check. 
For any open set $U$, $U \cup \inter (X-U)$ is dense, and so 
$U + (-U)=1$. Since $-U \subseteq (X-U)$, we have $U \cdot (-U)=0$. 
This checks the negation laws. 
The associative law for $\cdot$ is trivial. To check the associative
law for addition, let $U, V,W$ be regular open. Since
addition is commutative, it is enough to check that 
$U+(V+W) \subseteq (U+V)+W$.  Since $V \cup W \subseteq 
(U+V)+W$, $V+W=\inter \cl(V \cup W) \subseteq \inter \cl ((U+V)+W)
=(U+V)+W$ since $(U+V)+W$ is regular open. Thus, $U \cup (V+W) 
\subseteq (U+V)+W$, and again $U+(V+W) \subseteq 
\inter \cl ((U+V)+W)=(U+V)+W$, and we are done. 

To verify the distributive law $U \cdot (V+W)=U \cdot V + U \cdot W$,
first note that $U \cdot V  \cup U \cdot W \subseteq 
U \cdot (V+W)$, and since the latter is regular open we have 
$U \cdot V + U \cdot W =\inter \cl  (U \cdot V  \cup U \cdot W )
\subseteq U \cdot (V+W)$. For the other direction, let 
$x \in U \cdot (V+W)$. Let $O$ be a neighborhood in which 
$V \cup W$ is dense. Since $U$ is open, we may assume $O \subseteq U$. 
But then $U\cap V \cup U \cap W$ is dense in $O$, and so 
$x \in \inter \cl (U \cdot V \cup U \cdot W)=U \cdot V + U \cdot W$.

To verify the distributive law $U+(V \cdot W)=(U+V)\cdot(U+W)$,
first note that $U \cup (V\cdot W) \subseteq (U+V)\cdot(U+W)$, and 
since the latter is regular open we have 
$U+(V \cdot W)\subseteq(U+V)\cdot(U+W)$. For the other direction, let 
$x \in (U+V)\cdot(U+W)$. Let $O_1$ be a neighborhood of $x$ in which 
$U \cup V$ is dense, and $O_2$ a neighborhood of $x$ in which 
$U \cup W$ is dense. Let $O= O_1 \cap O_2$. We show that 
$U \cup (V \cap W)$ is dense in $O$, which suffices. Let $O_3
\subseteq O$ be open. If $O_3 \cap U \neq \emptyset$, we are done.
Otherwise, $V$ and $W$ are each dense in $O_3$. Since $V,W$
are regular open, $O_3 \subseteq V \cap W$ and we are done. 

For $U$ a regular open set we claim that $- (-U)=U$. Clearly
$U \subseteq -(-U)$. For the other direction, let 
$x \in -(-U)$. Then there is a neighborhood $O$ of $x$ such that 
$O \cap (-U)= \emptyset$. This means every neighborhood of every
point in $O$ intersects $U$, that is, $U$ is dense in $O$.
Since $U$ is regular open, $O \subseteq U$, so $x \in U$. 
From this it follows that we need only check one of
de Morgan's laws. We check $-(U \cdot V)= (-U) + (-V)$. 
Since $U^c \subseteq (U\cdot V)^c$, $\inter (U^c) \subseteq 
\inter ( (U\cdot V)^c)$. So, $-U \subseteq -(U \cdot V)$. Likewise,
$-V \subseteq  -(U \cdot V)$, and so $(-U) \cup (-V) 
\subseteq  -(U \cdot V)$. Since the latter is regular open, 
$(-U) + (-V) \subseteq  -(U \cdot V)$. Let $x \in -(U \cdot V)$. 
Let $O$ be a neighborhood of $x$ missing $U \cap V$. We claim that 
$(-U) \cup (-V)$ is dense in $O$, which suffices. 
Let $O_1 \subseteq O$ be open. If $-U$ misses $O_1$, then 
$U$ is dense in $O_1$, and hence $O_1 \subseteq  U$ as $U$
is regular open. Likewise, if $-V$ also misses $O_1$ then 
$O_1 \subseteq V$ and so $O_1 \subseteq U \cap V$, a contradiction. 

We have now shown that that the regular open sets in any 
topological space form a Boolean algebra. To see they form a complete
Boolean algebra, it suffices to show that if $\{ U_\alpha \}$ are 
regular open, then there is a least upper bound for the $U_\alpha$. 
Let $U = \inter \cl ( \bigcup_\alpha U_\alpha)$, so $U$ is regular open. 
Clearly $U_\alpha \leq U$ for each $\alpha$. For $U,V$ regular open it is
easy to check that $U \leq V$ (i.e., $U \cdot (-V)=0$) iff 
$U \subseteq V$. So if $W$ is regular open and $U_\alpha \leq W$
for all $\alpha$, then $U_\alpha \subseteq W$ for each $\alpha$, so 
$\bigcup_\alpha U_\alpha \subseteq W$. Then 
$U = \inter \cl ( \bigcup_\alpha U_\alpha) \subseteq \inter \cl(W)=W$.
Thus $U \leq W$. This shows $U$ is the least upper bound of the $U_\alpha$. 


Finally, we verify $\pi$ satisfies (1)-(3). If $p \leq q$
then $N_p \subseteq N_q$ so $\inter \cl (N_p) \subseteq 
\inter \cl (N_q)$. Hence $\pi(p) \leq \pi(q)$. 
If $p \parallel q$, then (1) implies that $\pi(p) \parallel \pi(q)$. 
Suppose $p \perp q$ but $\pi(p) \parallel \pi(q)$, that is, 
$\pi(p) \cdot \pi(q) \neq 0$. Let $r \in \inter \cl(N_p) \cap 
\inter \cl (N_q)$. Thus, $N_r \subseteq \cl(N_p)$ and 
$N_r \subseteq \cl(N_q)$. The first says that $r$ can be extended 
to a $s \leq r$, $s \in N_p$, and the second says that we may extend 
$s$ to a $t \leq s$, $t \in N_q$. Then $t \leq p,q$, a contradiction.
\end{proof}


The map $\pi$ of lemma~\ref{parcomp} is not necessarily 
one-to-one, but it is under a very mild condition on $P$
which is always satisfied in practice. Namely, suppose whenever 
$p \nleq q$ then $\exists r \leq p \ (r \perp q)$. Then if 
$p \neq q$, say $p \nleq q$, and we let $r \leq p$, $r \perp q$,
then $r \in N_p$ but $r \notin \inter \cl(N_q)$. Sometimes the
word {\em separative} is used to denote this condition. 


We next show that forcing with $\bP$ is equivalent to forcing with
its completion $\sB_P$. The proof of this does not use the fact that $\sB_P$
is a complete Boolean algebra, just properties (1)-(3) above. 
We abstract these properties into a definition.



\begin{defn} \label{defdenseem}
Let $\bP$, $\bQ$ be partial orders. We say $\pi \colon P \to Q$
is a {\em dense embedding} if:
\begin{enumerate}
\item
If $p \leq q$ then $\pi(p) \leq \pi(q)$. 
\item
$p \perp q$ iff $\pi(p) \perp \pi(q)$.
\item
$\pi^{''}\bP$ is dense in $\bQ$. 
\end{enumerate}
\end{defn}




\begin{lem} \label{lemdenseem}
Let $\bP$, $\bQ$ be partial orders in a transitive model $M$ of $\zf$. 
Let $\pi \colon P \to Q$ be a dense embedding, $\pi \in M$. Then:
\begin{enumerate}
\item
If $H \subseteq Q$ is $M$-generic for $\bQ$, then $G \defeq 
\pi^{-1}(H)$ is $M$-generic for $\bP$.
\item
If $G \subseteq P$ is $M$-generic for $\bP$, then 
$H \defeq \{ q \in Q \colon \exists p \in G\ (\pi(p) \leq q) \}$
is $M$-generic for $Q$. 
\end{enumerate}
In either case, $M[G]=M[H]$. 
\end{lem}



\begin{proof}
Suppose $H \subseteq Q$ is generic for $\bQ$. Then $G$ is easily closed
upwards. Also, if $p,q \in G$, then $\pi(p) \parallel \pi(q)$ as
they both lie in $H$. From (2) it follows that $p \parallel q$, hence
$G$ is a filter. To see it is generic, let $D \subseteq P$
be dense. Let $E=\pi^{''}D$. Then $E$ is dense in $Q$ from (3) [If 
$p \in Q$, let $q \leq p$ be in the range of $\pi$, say 
$q= \pi(t)$. As $D$ is dense, let $u \leq t$, $u \in D$. Then 
$\pi(u) \in E$, $\pi(u) \leq \pi(t) \leq p$ using (1).]
Let $p \in H \cap E$. Say $p =\pi(t)$, where $t \in D$.
Then $t \in G \cap D$. 

Suppose next that $G \subseteq P$ is $M$-generic for $P$. 
Define $H \subseteq Q$ as above. $H$ is upwards closed by definition, and
it is easy to check it is a filter using (1). 
To see it is generic, let $E \subseteq Q$ be dense. 
Let $D=\{ p \in P\colon  \exists q \in E \ (\pi(p) \leq q)\}$. To see 
$D$ is dense, let $p \in P$. Since $E$ is dense, let 
$q \in E$, $q \leq \pi(p)$. By (3), let $r \leq q$ with 
$r \in \ran(\pi)$, say $r=\pi(t)$. Since $\pi(t)=r \leq \pi(p)$,
by (2) we have $p \parallel t$. Let $u \leq p$, $u \leq t$. 
By (1), $\pi(u) \leq \pi(p)$, $\pi(u) \leq \pi(t) \leq q$. 
As $q \in E$, this shows $u \in D$, so $D$ is dense. 
Let now $p \in G \cap D$.  Since $p \in D$, let 
$q \geq \pi(p)$ with $q \in E$. Then $q \in H \cap E$ and we are done.

To see that $M[G]=M[H]$, simply note that in $M[G]$ we may define 
$H$ since $\pi \in M$, so $M[H] \subseteq M[G]$. 
Likewise $M[G] \subseteq M[H]$. 
\end{proof}


Thus, there is no difference between forcing with a partial order
$\bP$ and forcing with its completion $\sB_P$, which is a complete
Boolean algebra. 

If $\pi \colon P \to Q$ is a dense embedding, then lemma~\ref{lemdenseem}
says that generics for $P$ and $Q$ correspond; they are essentially the
same thing. If we relax condition (3) of definition~\ref{defdenseem},
then $Q$ may be much larger than $P$, and we do not expect 
generics for $P$ to give generics for $Q$. 
However, we can still get that generics for $Q$ give $P$ generics if
we replace (3) by a suitable condition. This is the concept
of a {\em complete embedding}, defined next.


\begin{defn}
Let $\bP$, $\bQ$ be partial orders. We say $\pi \colon P \to Q$
is a complete embedding if it satisfies the following.
\begin{enumerate}
\item
If $p \leq q$ then $\pi(p) \leq \pi(q)$. 
\item
$p \perp q$ iff $\pi(p) \perp \pi(q)$.
\item
For every $q \in Q$ there is a $p \in P$ such that 
$\forall r \leq p\ (\pi(r) \parallel q)$.
\end{enumerate}
\end{defn}


To motivate (3), note that if $\pi \colon P \to Q$, and 
whenever $H \subseteq Q$
is $M$-generic for $Q$, then $P \defeq \pi^{-1}(H)$ is also generic
for $P$, then we must have (3). Otherwise, for some $q \in Q$, 
$\{ p \in P \colon \pi(p) \perp q \}$ is dense in $P$. Let $H$
be generic for $Q$ with $q \in H$. If $G=\pi^{-1}(H)$
is also generic, then $\exists p \in G \cap D$. But then 
$q, \pi(p) \in H$ and are incompatible, a contradiction. 

The definition of complete embedding in more natural when $P$, $Q$
are complete Boolean algebras. In this case, $\pi \colon 
P \to Q$ is a complete embedding iff $\pi$ is a ono-to-one
homomorphisms of Boolean algebras (i.e., $\pi$ preserves the 
Boolean algebra operations) which is {\em complete}, that is, 
it preserves arbitrary sups and infs: for $\{ p_\alpha \} \subseteq
P$, $\pi(\sup(\{ p_\alpha \}))= \sup( \{ \pi(p_\alpha) \})$. 
To see this, suppose $P,Q$ are complete Boolean algebras and 
(1)-(3) hold. Let $\{ p_\alpha \} \subseteq P$ and 
$p= \sup(\{ p_\alpha\})$. By (1), $\pi(p) \geq \pi(p_\alpha)$
for all $\alpha$, so $\pi(p) \geq \sup(\{ \pi(p_\alpha) \})$. 
Suppose $q=\pi(p)-\sup(\{ \pi(p_\alpha) \}) =neq 0_Q$. By (3),
let $r \in P$ be such that $\forall s \leq r\ (\pi(s) \parallel q)$. 
In particular $\pi(r) \parallel q$, so $\pi(r) \parallel \pi(p)$. 
By (2), $r \parallel p$. Let $s \leq p, r$. We claim that 
$s \perp p_\alpha$ for each $\alpha$, a contradiction (since then 
$p-s$ is an upper bound for the $p_\alpha$). To see this, suppose 
$s \parallel p_\alpha$, say $t \leq s$, $t\leq p_\alpha$. 
Then $\pi(t) \leq \pi(p_\alpha)$ and since $t \leq r$, 
$\pi(t) \parallel q$, a contradiction to the definition of $q$. 
This show (1)-(3) imply that $\pi$ preserves sups. A similar
argument shows that $\pi$ preserves arbitrary infs (exercise~\ref{exerinf}).
Since for any Boolean algebra $p+q=\sup \{p,q\}$ and 
$p \cdot q= \inf \{ p,q\}$ it follows that $\pi$ preserves $+$
and $\cdot$. To see $\pi$ preserves Boolean complements, 
note that $\pi(p) \cdot \pi(-p)=0$ by (2). If $\pi(-p) \neq 
- \pi(p)$, then $q \defeq -(\pi(p)+ \pi(-p)) \neq 0_Q$. 
Let $r \in P$ be as in (3) for $q$. Without loss of 
generality suppose $r \parallel p$, and let 
$s \leq r,p$. Then by (1) $\pi(s) \leq \pi(p)$, and by 
definition of $r$, $\pi(s) \parallel q$. This contradicts the
definition of $q$. It is immediate from (1) that $\pi(0_P)=
0_Q$ and $\pi(1_P)=1_Q$. Finally, $\pi$ is one-to-one, for suppose
$p \ne q$ but $\pi(p)=\pi(q)$. Without loss of generality assume 
$r \defeq p-q \neq 0_P$. Then $r \perp q$ but $\pi(r) \parallel
\pi(q)$, contradicting (2). 




Conversely, suppose $P$, $Q$ are complete Boolean algebras and 
$\pi \colon P \to Q$ is a one-to-one homomorphism which is
complete (i.e., preserves arbitrary sups and infs). Properties 
(1) and (2) are immediate as $\pi$ is a homomorphism. 
To see (3), fix $q \in Q$. Let $p= \inf \{ r \in P \colon 
\pi(r) \geq q \}$. Suppose $s \leq p$. Since $p-s \lneq p$, 
we must have $\pi(p-s) \ngeq q$. As $\pi(p)=\pi(s) + \pi(p-s)$,
we have $\pi(s) \parallel q$. 



\begin{exer}
Show that if $\pi \colon P \to Q$ satisies (1)-(3) where $P$, $Q$
are complete Boolean albebras, then $\pi$ preserves arbitrary 
infimums.
\end{exer}




\begin{thm}
Let $\bP$, $\bQ$ be partial orders in a transitive model $M$
of $\zf$. Let $\pi \colon P \to Q$, $\pi \in M$, be a complete embedding.
If $H \subseteq Q$ is $M$-generic for $Q$, then $G=\pi^{-1}(H)$
is $M$-generic for $P$. Furthermore, $M[G] \subseteq M[H]$. 
\end{thm}



\begin{proof}
Let $H \subseteq Q$ be $M$-generic for $Q$, and let 
$G=\pi^{-1}(H)$. Let $D \subseteq P$ be dense. Now 
$\pi^{''}D$ is not necessarily dense in $Q$, but $E= \{ q \colon 
\forall p \in D\ ( q \perp \pi(p)) \vee \exists p \in D\ 
(q \leq \pi(p)) \}$ is dense in $Q$. Let $q \in H \cap E$. 
We cannot have $\forall p \in D\ ( q \perp \pi(p))$, for if so, 
let $p \in P$ be as in (3) for $q$. Let $r \in D$, $r \leq p$. 
Then $\pi(r) \parallel q$, a contradiction. So, 
$\exists p \in D\ (q \leq \pi(p))$. Thus, $\pi(p) \in H$, so 
$p \in G$. 

Since $\pi \in M$, working in $M[H]$ we may clearly define $G$,
so $G \in M[H]$. Thus, $M[G] \subseteq M[H]$.
\end{proof}




If we deal with partial orders which are complete Boolean algebras
(which we can do without loss of generality by lemma~\ref{lemmadenseem}),
then the definition of forcing simplifies considerably.
This is because if $A \subseteq N_p=\{ q \colon q \leq p\}$
is dense below $p$, then $\sup(A)=p$. Also, if $q \forces \phi$
for all $q \in A$, then $\sup(A) \forces \phi$. Thus, the various dense
sets that appear in the general definition will ``collapse'' when
dealing with complete Boolean algebras. We make this more precise
in the following definition. 




\begin{defn} \label{defbval}
Let $M$ be a transitive model of $\zf$ and $\sB \in M$ with 
$(\sB$ is a complete Boolean algebra$)^M$. For 
$\phi(\tau_1,\dots,\tau_n)$ a statement in the forcing
language, we define its {\em Boolean value} $\lb \phi \rb$ by induction on 
$\phi$ (and for the equality case by induction on the ranks of the names)
as follows. (note: we use $\sum$, $\prod$ for supremums and
infimums).
\begin{enumerate}
\item
$\llbracket \tau_1 \in \tau_2 \rrbracket= 
\sum_{\langle \sigma, p \rangle \in \tau_2} (p \cdot \llbracket 
\tau_1 \approx \sigma \rrbracket)$.
\item
$\llbracket \tau_1 \approx \tau_2 \rrbracket= 
\prod_{\sigma \in \dom(\tau_1)} ( -\llbracket \sigma \in \tau_1 \rrbracket
+ \llbracket \sigma \in \tau_2) + 
\prod_{\sigma \in \dom(\tau_2)} ( -\llbracket \sigma \in \tau_2 \rrbracket
+ \llbracket \sigma \in \tau_1) \rrbracket$. 
\item
$\llbracket \phi \wedge \psi \rrbracket = \llbracket \phi \rrbracket
+ \llbracket \psi \rrbracket$.
\item
$\llbracket \neg \phi \rrbracket = -\llbracket \phi \rrbracket$. 
\item
$\llbracket \exists x\  \phi(\vec \tau,x)  \rrbracket=
\sum_{\sigma \in M^\sB} \llbracket \phi(\vec \tau, \sigma) \rrbracket$.
\end{enumerate}
\end{defn}


When $\sB$ is a complete Boolean algebra, the notion of generic filter
can be reformulated and simplified a bit as well. First note that 
a generic filter on $\sB$ is necessarily an ultrafilter, that is, 
for any $p \in \sB$, either $p \in G$ or $-p \in \sB$. This follows
from the fact that $\{ q \in \sB \colon q \leq p \vee q \leq (-p) \}$
is dense in $\sB$. Also, if $p,q \in \sB$ then $p \cdot q \in \sB$. 
This follows since $\{ r \colon (r \leq p \cdot q) \vee (r \cdot 
p=0) \vee (r \cdot q=0) \}$ is dense. Thus, when dealing with
complete Boolean algebras we speak of generic ultrafilters on $\sB$. 
We can reformulate the density condition in the definition of generic
as follows.


\begin{lem} \label{genreform}
Let $M$ be a transitive model of $\zf$ and $\sB \in M$ with 
$(\sB$ is a complete Boolean algebra$)^M$. Then $G$ is an $M$-generic 
filter on $\sB$ iff $G$ is an ultrafilter on $\sB$ which 
respects supremums and infimums from $M$. 
That is, if $S \subseteq \sB$, then $\sum S \in G$ iff 
$\exists p \in S\ (p \in G)$ and $\prod S \in G$ iff 
$\forall p \in G\ (p \in G)$. 
\end{lem}


\begin{proof}
We have already seen that if $G \subseteq \sB$ is a generic filter
on $\sB$ then it is an ultrafilter. If $S \subseteq \sB$, then 
$D=\{ p \in \sB \colon (p \cdot \sum S=0) \vee (\exists s \in S\ 
p \leq s) \}$ is dense. If $\sum S \in G$, and if we let 
$p \in G \cap D$, then we have $p \leq s$ for some $s \in S$. 
Thus $s \in G$ as well. The proof that $G$ respects infimums is
similar. 

Finally, if $G$ respects supremums and infimums, then in particular
whenever $D \subseteq \sB$ is dense, that is $\sum D =1_{\sB}$,
we must have $p \in G$ for some $p \in D$. So, $G$ is generic.
\end{proof}


 
The connection between the forcing relation and Boolean values is
given in the next lemma.


\begin{lem}
Let $M$ be a transitive model of $\zf$, $\sB \in M$, and 
$(\sB$ is a complete Boolean algebra$)^M$. Then for any statement 
$\phi$ in the forcing language, $p \forces \phi$ iff 
$p \leq \llbracket \phi \rrbracket$. 
\end{lem}

\begin{proof}
The proof by induction on $\phi$ is straightforward, we consider
just one case here, say $\phi=(\tau_1 \in \tau_2)$. 
Now  
\begin{equation*}
\begin{split}
p \leq \llbracket \phi \rrbracket& = 
\sum_{\langle \sigma, q \rangle \in \tau_2 \rangle} (q \cdot \llbracket 
\tau_1 \approx \sigma \rrbracket) 
\\ & \leftrightarrow
\{ r \leq p \colon \exists  \langle \sigma, q \rangle \in \tau_2\  
r \leq q \cdot \llbracket \tau_1 \approx \sigma \rrbracket \}
\text{ is dense below } p \\ & \leftrightarrow
\{ r \leq p \colon \exists  \langle \sigma, q \rangle \in \tau_2\  
r \leq q \wedge r \leq  \llbracket \tau_1 \approx \sigma \rrbracket \}
\text{ is dense below } p\\ & \leftrightarrow
\{ r \leq p \colon \exists  \langle \sigma, q \rangle \in \tau_2\  
r \leq q \wedge r \forces \tau_1 \approx \sigma  \} \text{ is dense below } p.
\\ & \leftrightarrow p \forces (\tau_1 \in \tau_2)
\end{split}
\end{equation*}
The first equivalence is the fact that $p \leq \sum S$ iff 
$\{ q \leq p \colon \exists s \in S \ (q \leq s)\}$ is dense below $p$. 
The next to last eqivalence is by induction, and the last equivalence
is the definition of $p \forces (\tau_1 \in \tau_2)$.
\end{proof}


An alternative possibility when considering forcing with complete
Boolean algebras is that we introduce definition~\ref{defbval},
and then {\em define} the forcing relation by $p \forces \phi$
iff $p \leq \llbracket \phi \rrbracket$. This has the advantage that the 
definition of forcing is somewhat simpler and more natural. 
Of course, in this approach one must now prove the forcing theorem
directly: for all generic ultrafilters $G$ on $\sB$, 
$\phi^{M[G]}$ iff $\llbracket \phi \rrbracket \in G$. The proof is essentially
the same as before. For example, consider the case 
$\phi=(\tau_1 \in \tau_2)$. Suppose first 
$\llbracket \phi \rrbracket= 
\sum_{\langle \sigma, q \rangle \in \tau_2 \rangle} (q \cdot \llbracket 
\tau_1 \approx \sigma \rrbracket) \in G$. 
From lemma~\ref{genreform} it follows that 
for some $\langle \sigma, q \rangle   \in \tau_2$ 
that $q \cdot \llbracket 
\tau_1 \approx \sigma \rrbracket \in G$. Thus, $q \in G$ and 
$\llbracket \tau_1 \approx \sigma \rrbracket \in G$. By induction, 
$(\tau_1)_G \approx \sigma_G$. Since $q \in G$, $\sigma_G \in (\tau_2)$,
and we are done. For the other direction, suppose 
$(\tau_1)_G= (\tau_2)_G$. Fix $\langle \sigma, q \rangle \in \tau_2$
such that $q \in G$ and $(\tau_1)_G=\sigma_G$. By induction, 
$\llbracket \tau_1 \in \sigma \rrbracket \in G$. Since $G$ is a filter,
$q \cdot \llbracket \tau_1 \in \sigma \rrbracket \in G$. Thus, 
$\sum_{\langle \sigma, q \rangle \in \tau_2 } (q \cdot \llbracket 
\tau_1 \approx \sigma \rrbracket) \in G$. 


























\end{document}