Proof. Let $D=\{D_n:n\in \mathbb{N}\}$. Pick $p_0\in D_0$ arbitrarily and define by recursion $p_{i+1}$ by picking some $q\le p_i$ with $q\in D_{i+1}$.

Then $\{p_i:i\in \mathbb{N}\}$ is a filter base, so let $F$ be the filter generated by it. Then it is $D$-generic by construction. □

Proof. If $x\in X$, find $p\in F\cap D_x$, then $x\in \mathrm{dom}(p)$, TODO □

Proof. Fix $y$ and define

$E_{y,y^{\prime }}$ guarantees that $y\mapsto Ay$ is an injection. □

Proof. Induction. □

Proof. Calculate:

Proof. Suppose $z\in \mathrm{val}(u_{\tau },F)$.

So $z=\mathrm{val}({\sigma }^{\prime },F)$ for some $({\sigma }^{\prime },r)\in u_{\tau }$ with $r\in F$.

So $\exists \sigma ,p,q$ with $(\sigma ,p)\in \tau$, $({\sigma }^{\prime },q)\in \sigma$, $r\le p,q$.

So $p,q\in F$. Hence $\mathrm{val}(\sigma ,F)\in \mathrm{val}(\tau ,F)$, $z=\mathrm{val}({\sigma }^{\prime },F)\in \mathrm{val}(\sigma ,F)$.

So $z\in \bigcup \mathrm{val}(\tau ,F)$.

Conversely, suppose $z\in \bigcup \mathrm{val}(\tau ,F)$. Then $\exists y,z\in y\in \mathrm{val}(\tau ,F)$ ($z\to ({\sigma }^{\prime },q)\in \sigma$ with $q\in F$, $y\to (\sigma ,\rho )\in \tau$ with $p\in F$).

Hence since $F$ a filter, find $r\le p,q$ with $r\in F$.

Then $({\sigma }^{\prime },r)\in u_{\tau }$, so $z\in \mathrm{val}(u_{\tau },F)$. □

Proof of Separation in $M[G]$. Let $\phi (x,x_1,\dots ,x_n)$ be an $L_{\in }$-formula (not in the forcing language) and $x\in M[G]$. Need a name for

[For readability, we now drop parameters $\overline{p}$].

Fix $\sigma$ such that $\mathrm{val}(\sigma ,G)=x$. Define

By the Definability Theorem, $\varrho$ is a name in $M$.

Claim: $\mathrm{val}(\varrho ,G)=A$.

• “$\subseteq$” If $z\in \mathrm{val}(\varrho ,G)$, then there is $(\pi ,p)\in \varrho$ such that $z=\mathrm{val}(\pi ,G)$, $p\in G$. Since $(\pi ,p)\in \varrho$, we get $\pi \in \mathrm{dom}(\sigma )$, $p⊩\pi \in \sigma \wedge \phi (\pi )$. Together with $p\in G$, we get

  $$M[G]\models \underset{z\in x\wedge \phi (z)}{\underbrace{\pi \in \sigma \wedge \phi (\pi )}}.$$

  Hence $z\in A$.

• “$\supseteq$” If $z\in A$, then $z\in x$ and $M[G]\models \phi (z)$. So there is $\pi \in \mathrm{dom}(\sigma )$, $z=\mathrm{val}(\pi ,G)$.

  By the Forcing THeorem, $\exists p\in G$, $p⊩\phi (\pi )$. Also, there is $q\in G$ and $q⊩\pi \in \sigma$. Find $r\in G$, $r\le p,q$ such that $r⊩\pi \in r\wedge \phi (\pi )$.

  Hence $(\pi ,r)\in \varrho$, so $z=\mathrm{val}(\pi ,G)\in \mathrm{val}(\varrho ,G)$. □

Proof of power set. Example Sheet 3. □

Proof. Example Sheet 3 □

Proof. If this is true for $\phi$ of the form ${\tau }_0={\tau }_1$ and of the form ${\tau }_0\in {\tau }_1$, then it’s true for all formulas.

For $\phi$ atomic, we get that (ii) $⟹$ (i) and (ii) $⟹$ (iii) are trivial.

(i) $⟹$ (ii) follows from Lemma 3.18(i).

(iii) $⟹$ (i) follows from Lemma 3.18(ii). □

Proof of Definability Theorem from Syntactic Forcing Theorem.

• $\Leftarrow$ This is just Syntactic Forcing Theorem.
• $\Rightarrow$ Suppose $p⊩\phi$. By Lemma 3.18, we need to show

  $$\{r\le p:r{⊩}^{\ast }\phi \}$$

  is dense below $p$.

  Suppose not. Then I find $q\le p$ such that $\forall r\le q$, $r⁄{⊩}^{\ast }\phi$. So $q{⊩}^{\ast }\neg \phi$.

  If $q\in G$, then $p\in G$. Since $p⊩\phi$, $M[G]\models \phi$. Since $q{⊩}^{\ast }\neg \phi$, $M[G]\models \neg \phi$. Contradiction! □

Proof of the Syntactic Forcing Theorem. The Theorem for $=$ can be proved by induction on ${\mathrm{Name}}_{\alpha }$.

The Theorem for $\in$ can be proved once the Theorem has been established for $=$.

Rest is induction on formula complexity.

Let’s do $\neg$ and leave the rest to Example Sheet 3. Assume we have proved it for $\phi$. We will prove it for $\neg \phi$.

• $\Rightarrow$ $M[G]⊩\neg \phi$. Consider

  $$D:=\{p:p{⊩}^{\ast }\phi \text{ or }p{⊩}^{\ast }\neg \phi \}.$$

  By definition of ${⊩}^{\ast }\neg$, this is dense. Find $p\in G\cap D$.

  By assumption, $p⁄{⊩}^{\ast }\phi$, so $p{⊩}^{\ast }\neg \phi$.

• $\Leftarrow$ Let $p\in G$ such that $p{⊩}^{\ast }\neg \phi$. By definition, $\forall q\le p$, $q⁄{⊩}^{\ast }\phi$. If $M[G]⁄\models \neg \phi$, thus $M[G]\models \phi$. By induction hypothesis, find $r\in G$, $r{⊩}^{\ast }\phi$. So $q\le r,p,q\in G$.

  By Lemma, $q{⊩}^{\ast }\phi$, contradiction to $\forall q\le p,q⁄{⊩}^{\ast }\phi$.

Proof.

• $\Rightarrow$ Assume that $M[G]\models {\tau }_0\in {\tau }_1$, i.e. $\mathrm{val}({\tau }_0,G)\in \mathrm{val}({\tau }_1,G)$. Thus, there is $(\pi ,s)\in {\tau }_1$ such that $\mathrm{val}(\pi ,G)=\mathrm{val}({\tau }_0,G)$ ($⟺M[G]\models \pi ={\tau }_0$) and $s\in G$. So by Syntactic Forcing Theorem for $=$, find $r\in G$ such that $r{⊩}^{\ast }\pi ={\tau }_0$.

  Find $p\le r,s$ such that $p\in G$.

  Claim that $D$ is dense below $p$. Let $q\in D$ and pick the above $(\pi ,s)$. Then we have $q\le p\le s$ and $q{⊩}^{\ast }\pi ={\tau }_0$ (since $q\le p\le r$).

• $\Leftarrow$ Assume $p\in G$, $p{⊩}^{\ast }{\tau }_0\in {\tau }_1$, i.e. $D$ is dense below $p$. By Lemma 3.18(iv), find $q\in G\cap D$, thus there is $(\pi ,s)\in {\tau }_1$ such that $q\le s$, $q{⊩}^{\ast }\pi ={\tau }_0$. Since $q\in G$, $s\in G$, we have $\mathrm{val}(\pi ,G)\in \mathrm{val}({\tau }_1,G)$. By Syntactic Forcing Theorem for “$=$”, we have $\mathrm{val}(\pi ,G)=\mathrm{val}({\tau }_0,G)$. So $\mathrm{val}({\tau }_0,G)\in \mathrm{val}({\tau }_1,G)$. □

Proof.

• $\Leftarrow$ Assume $p\in G$ such that $p{⊩}^{\ast }{\tau }_0={\tau }_1$. Need to prove $\mathrm{val}({\tau }_0,G)=\mathrm{val}({\tau }_1,G)$.

  We’ll show that the fact that $D_0$ is dense below $p$ implies $\mathrm{val}({\tau }_0,G)\subseteq \mathrm{val}({\tau }_1,G)$. The other direction is the same proof but with $0$ and $1$ flipped.

  Proof of this: Let $x\in \mathrm{val}({\tau }_0,G)$, so find $({\pi }_0,s_0)\in {\tau }_0$ such that $s_0\in G$ and $x=\mathrm{val}({\pi }_0,G)$. So, the corresponding $D_0$ is dense below $p$. Find $q\le s_0,p$ such that $q\in G$. Then $D_0$ is dense below $q$. So find $r\le q$ such that $r\in G\cap D_0$. (Note that $r\le q\le s_0$, so $r\le s_0$).

  Since $r\in D_0$ and $r\le s_0$, find $({\pi }_1,s_1)\in {\tau }_1$ such that $r\le s_1\wedge r{⊩}^{\ast }{\pi }_0={\pi }_1$. By induction hypothesis, $r\in G$ and $r{⊩}^{\ast }{\pi }_0={\pi }_1$, which implies $x=\mathrm{val}({\pi }_{,}v)=\mathrm{val}({\pi }_1,G)$ (since $({\pi }_1,s_1)\in {\tau }_1$ and $s_1\in G$).

• $\Rightarrow$ Assume $\mathrm{val}({\tau }_0,G)=\mathrm{val}({\tau }_1,G)$. Consider the set $$\begin{array}{llll}\hfill D& :=\{r:r{⊩}^{\ast }{\tau }_0={\tau }_1\text{ or }& \hfill & \\ \hfill & {\mathrm{\Phi }}_r^0 \exists ({\pi }_0,s_0)\in {\tau }_0(r\le s_0\wedge \forall ({\pi }_1,s_1)\in {\tau }_1,\forall q((q\le s_1\wedge q{⊩}^{\ast }{\pi }_0={\pi }_1)\to q\perp r)& \hfill & \\ \hfill & {\mathrm{\Phi }}_r^1 \exists ({\pi }_1,s_1)\in {\tau }_1(r\le s_1\wedge \forall ({\pi }_0,s_0)\in {\tau }_0,\forall q((q\le s_0\wedge q{⊩}^{\ast }{\pi }_0={\pi }_1)\to q\perp r)& \hfill & \\ \hfill & \}& \hfill & \end{array}$$

  Claim: $D$ is dense. If $p{⊩}^{\ast }$, then $p\in D$, so nothing to show. If $p⁄{⊩}^{\ast }{\tau }_0={\tau }_1$, then there is some $D_0∕D_1$ that fails to be dense below $p$.

  We’ll show: if $D_0$ is not dense below $p$, then we can find $r\le p$ such that ${\mathrm{\Phi }}_r^0$ holds.

  (Other proof: $D_1$ not dense below $p$ $\to {\mathrm{\Phi }}_r^1$ is flipping $0$ and $1$).

  Suppose $p⁄{⊩}^{\ast }{\tau }_0={\tau }_1$ and there is $({\pi }_0,s_0)\in {\tau }_0$ such that $D_0$ is not dense below $p$. This means: there is $r\le p$ such that

  $$\forall q\le r(q\le s_0\wedge \forall ({\pi }_1,s_1)\in {\tau }_1\neg (q\le s_1\wedge q{⊩}^{\ast }{\pi }_0={\pi }_1).$$

  So, we get

  $$r\le s_0\wedge \forall ({\pi }_1,s_1)\in {\tau }_1$$

  for any $q$ that satisfies $q\le s_1\wedge q{⊩}^{\ast }{\pi }_0={\pi }_1$. It can’t be compatible with $r$ (finishes the proof of the claim that $D$ is dense).

  Summary: We now have that $D$ is dense.

  $$D=\{r:r{⊩}^{\ast }{\tau }_0={\tau }_1\text{ or }{\mathrm{\Phi }}_r^0\text{ or }{\mathrm{\Phi }}_1^r\}.$$

  Claim 2: If $r\in G$, then neither ${\mathrm{\Phi }}_r^0$ nor ${\mathrm{\Phi }}_r^1$ holds (again, just do ${\mathrm{\Phi }}_r^0$ and then flip $0$ and $1$ for ${\mathrm{\Phi }}_r^1$).

  If ${\mathrm{\Phi }}_r^0$ holds, then find $({\pi }_0,s_0)\in {\tau }_0$ such that $r\le s_0$ and the incompatibility statement holds. $r\in G\to s_0\in G$, so $\mathrm{val}({\pi }_0,G)\in \mathrm{val}({\tau }_0,G)$. If $({\pi }_1,s_1)\in {\tau }_1$ such that TODO

  Put everything together: since $D$ is dense by Claim 1, find $r\in D\cap G$. Therefore, by Claim 2, ${\mathrm{\Phi }}_r^0$, ${\mathrm{\Phi }}_r^1$ do not hold.

  Thus $r{⊩}^{\ast }{\tau }_0={\tau }_1$. □