$ \newcommand{\func}{\operatorname} \newcommand{\lcm}{\func{lcm}} \newcommand{\hl}[1]{\textbf{#1}} \newcommand{\lf}{\lfloor} \newcommand{\rf}{\rfloor} \newcommand{\f}[1]{\left\lf #1 \right\rf} \newcommand{\bb}[1]{\left( #1 \right)} \newcommand{\Sb}[1]{\left\lbrack #1 \right\rbrack} \renewcommand{\ss}[1]{\left\lbrace #1 \right\rbrace} \renewcommand{\mod}[1]{\left\lvert #1 \rightrvert} \newcommand{\R}{\boldsymbol{R}} \newcommand{\C}{\boldsymbol{C}} \newcommand{\Z}{\boldsymbol{Z}} \newcommand{\Q}{\boldsymbol{Q}} \renewcommand{\P}{\mathbb{P}} \newcommand{\Po}{\mathcal{P}} \newcommand{\F}{\mathcal{F}} \newcommand{\Zz}{\Z_{\geq 0}} \renewcommand{\c}[1]{\left\langle #1 \right\rangle} \renewcommand{\mod}[1]{\left\lvert #1 \right\rvert} \newcommand{\norm}[1]{\left\lVert #1 \right\rVert} \renewcommand{\bar}[1]{\overline{#1}} \newcommand{\eqbreak}{\phantom{{} = {}}} \newcommand{\impliesbreak}{\phantom{{} \implies {}}} \newcommand{\iffbreak}{\phantom{{} \iff {}}} \newcommand{\del}{\partial} \renewcommand{\d}[1]{\, \mathrm{d} #1} \newcommand{\dydt}{\frac{\d{y}}{\d{t}}} \newcommand{\dydx}{\frac{\d{y}}{\d{x}}} \newcommand{\pd}[2]{\frac{\del #1}{\del #2}} \newcommand{\pp}[3]{\frac{\del^2 #1}{\del #2 \del #3}} \newcommand{\dd}[2]{\frac{\mathrm{d} #1}{\mathrm{d} #2}} \newcommand{\Inn}{\func{Inn}} \newcommand{\Aut}{\func{Aut}} \newcommand{\diag}{\func{diag}} \newcommand{\id}{\func{id}} \newcommand{\GL}{\func{GL}} \newcommand{\SL}{\func{SL}} \newcommand{\End}{\func{End}} \newcommand{\Hom}{\func{Hom}} \newcommand{\Tr}{\func{Tr}} \newcommand{\rank}{\func{rank}} \newcommand{\ORD}{\mathbf{ORD}} \newcommand{\OD}{\mathbf{OD}} \newcommand{\HOD}{\mathbf{HOD}} \newcommand{\ZF}{\mathsf{ZF}} \newcommand{\ZFC}{\mathsf{ZFC}} \newcommand{\ZC}{\mathsf{ZC}} \renewcommand{\AC}{\mathsf{AC}} \newcommand{\DC}{\mathsf{DC}} \newcommand{\CC}{\mathsf{CC}} \newcommand{\CH}{\mathsf{CH}} \newcommand{\SH}{\mathsf{SH}} \newcommand{\KH}{\mathsf{KH}} \newcommand{\GCH}{\mathsf{GCH}} \newcommand{\PA}{\mathsf{PA}} \newcommand{\BST}{\mathsf{BST}} \newcommand{\MA}{\mathsf{MA}} \newcommand{\Con}{\func{Con}} \newcommand{\ON}{\mathbf{ON}} \newcommand{\dom}{\func{dom}} \newcommand{\ran}{\func{ran}} \newcommand{\pred}{\func{pred}} \newcommand{\mos}{\func{mos}} \newcommand{\WF}{\mathbf{WF}} \newcommand{\type}{\func{type}} \newcommand{\V}{\mathbf{V}} \renewcommand{\L}{\mathcal{L}} \newcommand{\cl}{\func{cl}} \newcommand{\trcl}{\func{tc}} \newcommand{\TC}{\func{TC}} \newcommand{\A}{\mathfrak{A}} \newcommand{\B}{\mathfrak{B}} \newcommand{\add}{\func{add}} \newcommand{\cov}{\func{cov}} \newcommand{\non}{\func{non}} \newcommand{\cf}{\func{cf}} \newcommand{\forces}{\Vdash} \newcommand{\one}{\mathbbm{1}} \newcommand{\restrictedto}{\mathord{\upharpoonright}} \newcommand{\Fn}{\func{Fn}} \newcommand{\Col}{\func{Col}} \newcommand{\bigtriangle}{\triangle} \newcommand{\U}{\mathcal{U}} \newcommand{\W}{\mathcal{W}} \newcommand{\N}{\mathcal{N}} \newcommand{\Seq}{\mathit{Seq}} \newcommand{\lh}{\func{lh}} \newcommand{\Ult}{\func{Ult}} \newcommand{\In}{\func{In}} \newcommand{\otp}{\func{otp}} \newcommand{\symdiff}{\, \triangle \,} \newcommand{\crit}{\func{crit}} \newcommand{\sat}{\func{sat}} \renewcommand{\int}{\func{int}} \newcommand{\length}{\func{length}} \newcommand{\Lim}{\func{Lim}} \newcommand{\Succ}{\func{Succ}} \newcommand{\G}{\mathcal{G}} \newcommand{\T}{\mathcal{T}} \newcommand{\ext}{\func{ext}} \newcommand{\height}{\func{height}} \renewcommand{\diamond}{\diamondsuit} \newcommand{\D}{\mathcal{D}} \newcommand{\NS}{\mathrm{NS}} $
Exercise 14.1
Solution
We shall show that the $D$ in the hint is dense (for fixed $p, q \in P$). This gives the conclusion, as if $G$ is generic then $G \cap D \neq \emptyset$, so we have $r \in G \cap D$. Since all elements in $G$ are compatible, neither $r$ incompatible with $p$ nor $r$ incompatible with $q$ is possible. It follows that $r \leq p$ and $r \leq q$, as desired.
Let $s \in P$, and we consider two cases. If $s$ is incompatible with $p$ or $q$, then by definition of $D$, $s \in D$. Otherwise, $s$ is compatible with both $p$ and $q$, so there exists $t \in P$ such that $t \leq s, p, q$. Then, in particular, $t \leq p, q$ so $t \in D$, and $t \leq s$.
We shall show that the $D$ in the hint is dense (for fixed $p, q \in P$). This gives the conclusion, as if $G$ is generic then $G \cap D \neq \emptyset$, so we have $r \in G \cap D$. Since all elements in $G$ are compatible, neither $r$ incompatible with $p$ nor $r$ incompatible with $q$ is possible. It follows that $r \leq p$ and $r \leq q$, as desired.
Let $s \in P$, and we consider two cases. If $s$ is incompatible with $p$ or $q$, then by definition of $D$, $s \in D$. Otherwise, $s$ is compatible with both $p$ and $q$, so there exists $t \in P$ such that $t \leq s, p, q$. Then, in particular, $t \leq p, q$ so $t \in D$, and $t \leq s$.
$\square$
Exercise 14.2
Solution
$\implies$: Fix $p \in G$. Let $D \in M$ be dense below $p$. Define: $$ \begin{align*} D' := \lbrace q \in P : q \perp p \vee q \in D\rbrace \end{align*}$$ We see that $D'$ is dense in $P$. Indeed, for any $r \in P$, if $r \perp p$ then $r \in D'$. Otherwise, there exists $s \in P$ such that $s \leq p, r$. Since $D$ is dense below $p$, there exists $t \in D'$ such that $t \leq s \leq r$, as desired.
Thus, we have that $G \cap D' \neq \emptyset$. Let $q \in G \cap D'$. But since $p \in G$, we must have $q \not\perp p$, so $q \in D$. Hence $q \in G \cap D$.
$\impliedby$: Fix $D \in M$ dense in $P$, and let $p \in G$ be arbitrary. Consider: $$ \begin{align*} D' := \lbrace q \in D : q \leq p\rbrace \end{align*}$$ Clearly $D'$ is dense below $p$, so by hypothesis $\emptyset \neq G \cap D' \subseteq G \cap D$.
$\implies$: Fix $p \in G$. Let $D \in M$ be dense below $p$. Define: $$ \begin{align*} D' := \lbrace q \in P : q \perp p \vee q \in D\rbrace \end{align*}$$ We see that $D'$ is dense in $P$. Indeed, for any $r \in P$, if $r \perp p$ then $r \in D'$. Otherwise, there exists $s \in P$ such that $s \leq p, r$. Since $D$ is dense below $p$, there exists $t \in D'$ such that $t \leq s \leq r$, as desired.
Thus, we have that $G \cap D' \neq \emptyset$. Let $q \in G \cap D'$. But since $p \in G$, we must have $q \not\perp p$, so $q \in D$. Hence $q \in G \cap D$.
$\impliedby$: Fix $D \in M$ dense in $P$, and let $p \in G$ be arbitrary. Consider: $$ \begin{align*} D' := \lbrace q \in D : q \leq p\rbrace \end{align*}$$ Clearly $D'$ is dense below $p$, so by hypothesis $\emptyset \neq G \cap D' \subseteq G \cap D$.
$\square$
Exercise 14.3
Solution
$\implies$ is immediate. For $\impliedby$, let $D$ be a (not necessarily open) dense set in $P$. Define: $$ \begin{align*} D' := \lbrace q \in P : (\exists p \in D) \, q \leq p\rbrace = \bigcup_{p \in D} O(p) \end{align*}$$ where $O(p) := \lbrace q \in P : q \leq p\rbrace$ is the basic open set corresponding to $p$. Then clearly $D'$ is dense open, so by hypothesis $G \cap D' \neq \emptyset$, and say it contains the condition $r$. By definition of $D'$, there exists an $s \in D$ such that $r \leq s$. Then $s \in G$ as $G$ is upward closed, so $G \cap D \neq \emptyset$.
$\implies$ is immediate. For $\impliedby$, let $D$ be a (not necessarily open) dense set in $P$. Define: $$ \begin{align*} D' := \lbrace q \in P : (\exists p \in D) \, q \leq p\rbrace = \bigcup_{p \in D} O(p) \end{align*}$$ where $O(p) := \lbrace q \in P : q \leq p\rbrace$ is the basic open set corresponding to $p$. Then clearly $D'$ is dense open, so by hypothesis $G \cap D' \neq \emptyset$, and say it contains the condition $r$. By definition of $D'$, there exists an $s \in D$ such that $r \leq s$. Then $s \in G$ as $G$ is upward closed, so $G \cap D \neq \emptyset$.
$\square$
Exercise 14.4
Solution
$\impliedby$ is immediate. For $\implies$, let: $$ \begin{align*} D' := \lbrace q \in P : (\exists p \in D) \, q \leq p\rbrace \end{align*}$$ Then $D'$ is dense — indeed, let $r \in P$, and since $D$ is predense, $r$ is compatible with some $p \in D$, i.e. there exists $q \in P$ such that $q \leq r$ and $q \leq p$. Then $q \in D'$, so $D'$ is dense. By genericity of $G$, $G \cap D' \neq \emptyset$. Let $q \in G \cap D'$, so $q \leq p$ for some $p \in D$. Then $p \in G$ by upward closure, so $G \cap D \neq \emptyset$.
$\impliedby$ is immediate. For $\implies$, let: $$ \begin{align*} D' := \lbrace q \in P : (\exists p \in D) \, q \leq p\rbrace \end{align*}$$ Then $D'$ is dense — indeed, let $r \in P$, and since $D$ is predense, $r$ is compatible with some $p \in D$, i.e. there exists $q \in P$ such that $q \leq r$ and $q \leq p$. Then $q \in D'$, so $D'$ is dense. By genericity of $G$, $G \cap D' \neq \emptyset$. Let $q \in G \cap D'$, so $q \leq p$ for some $p \in D$. Then $p \in G$ by upward closure, so $G \cap D \neq \emptyset$.
$\square$
Exercise 14.5
Solution
Since every maximal antichain in $P$ is predense in $P$, this follows from Exercise 14.4.
Since every maximal antichain in $P$ is predense in $P$, this follows from Exercise 14.4.
$\square$
Exercise 14.6
Solution
As in the hint, let $D := \lbrace p \in P : p \notin F\rbrace$. Then for every $p \in P$, consider two cases: If $p \notin F$, then $p \in D$ and we're done. Otherwise, let $q, r \leq p$ be incompatible. Since all elements in $F$ are comparable, we have $q \notin F$ or $r \notin F$. Then $q \in D$ or $r \in D$, so $D$ is indeed dense.
If $G$ is a filter and $G \in M$, then $D \in M$ and $G \cap D = \emptyset$. Thus $G$ can't be generic.
As in the hint, let $D := \lbrace p \in P : p \notin F\rbrace$. Then for every $p \in P$, consider two cases: If $p \notin F$, then $p \in D$ and we're done. Otherwise, let $q, r \leq p$ be incompatible. Since all elements in $F$ are comparable, we have $q \notin F$ or $r \notin F$. Then $q \in D$ or $r \in D$, so $D$ is indeed dense.
If $G$ is a filter and $G \in M$, then $D \in M$ and $G \cap D = \emptyset$. Thus $G$ can't be generic.
$\square$
Exercise 14.7
Solution
By Theorem 14.7(i)(c), it suffices to show that no $q \leq p$ forces $\neg\varphi$. Suppose such a $q$ exists. By denseness we let $r \leq q$ such that $r \forces \varphi$. By Theorem 14.7(i)(a), $r \forces \neg\varphi$ as $r \leq q$, contradicting Theorem 14.7(i)(b).
By Theorem 14.7(i)(c), it suffices to show that no $q \leq p$ forces $\neg\varphi$. Suppose such a $q$ exists. By denseness we let $r \leq q$ such that $r \forces \varphi$. By Theorem 14.7(i)(a), $r \forces \neg\varphi$ as $r \leq q$, contradicting Theorem 14.7(i)(b).
$\square$
Exercise 14.8
Solution
$\implies$ follows immediately from the Forcing Theorem 14.6. Conversely, suppose $p \not\forces \sigma$. Then there exists $q \leq p$ such that $q \forces \neg\sigma$ (otherwise by Exercise 14.7 we have $p \forces \sigma$). Let $G \subseteq P$ be generic such that $q \in G$. Then $p \in G$ by upward closure, and since $q \forces \neg\sigma$ by the Forcing Theorem we have $M[G] \models \neg\sigma$ (so $M[G] \not\models \sigma$).
$\implies$ follows immediately from the Forcing Theorem 14.6. Conversely, suppose $p \not\forces \sigma$. Then there exists $q \leq p$ such that $q \forces \neg\sigma$ (otherwise by Exercise 14.7 we have $p \forces \sigma$). Let $G \subseteq P$ be generic such that $q \in G$. Then $p \in G$ by upward closure, and since $q \forces \neg\sigma$ by the Forcing Theorem we have $M[G] \models \neg\sigma$ (so $M[G] \not\models \sigma$).
$\square$
Exercise 14.9
Solution
We use the notations/definitions in the proof of Lemma 14.11. Fix a poset $(P,<)$ and let $(Q,<')$ be a separative quotient of $(P,<)$, along with an onto embedding $h : P \to Q$. It suffices to show that $(Q,<')$ is isomorphic to $({P/\!\sim},\prec)$, where $\sim$ is defined as in Lemma 14.11.
For $x \in P$, define $g : {P/\!\sim} \to Q$ by: $$ \begin{align*} g([x]) = h(x) \end{align*}$$ We show that this is well-defined. Suppose $x \sim y$ for some $x, y \in P$. Then for all $z \in P$, we have $z$ is compatible with $x$ iff $z$ is compatible with $y$. Thus $h(z)$ is compatible with $h(x)$ iff $h(z)$ is compatible with $h(y)$. Since $(Q,<')$ is separative and $h$ is onto, we have that $h(x) = h(y)$. By a reversed reasoning, we may also conclude that $g$ is one-to-one.
We now show that $g$ is order-preserving. Suppose $[x] \preceq [y]$, so $(\forall z \leq x)$[$z$ and $y$ are compatible]. This implies that, in $(Q,<')$, for all $z \leq h(x)$ we have that $z$ and $h(y)$ are compatible. By the hint again, this implies that $h(x) \leq h(y)$, as desired.
We use the notations/definitions in the proof of Lemma 14.11. Fix a poset $(P,<)$ and let $(Q,<')$ be a separative quotient of $(P,<)$, along with an onto embedding $h : P \to Q$. It suffices to show that $(Q,<')$ is isomorphic to $({P/\!\sim},\prec)$, where $\sim$ is defined as in Lemma 14.11.
For $x \in P$, define $g : {P/\!\sim} \to Q$ by: $$ \begin{align*} g([x]) = h(x) \end{align*}$$ We show that this is well-defined. Suppose $x \sim y$ for some $x, y \in P$. Then for all $z \in P$, we have $z$ is compatible with $x$ iff $z$ is compatible with $y$. Thus $h(z)$ is compatible with $h(x)$ iff $h(z)$ is compatible with $h(y)$. Since $(Q,<')$ is separative and $h$ is onto, we have that $h(x) = h(y)$. By a reversed reasoning, we may also conclude that $g$ is one-to-one.
We now show that $g$ is order-preserving. Suppose $[x] \preceq [y]$, so $(\forall z \leq x)$[$z$ and $y$ are compatible]. This implies that, in $(Q,<')$, for all $z \leq h(x)$ we have that $z$ and $h(y)$ are compatible. By the hint again, this implies that $h(x) \leq h(y)$, as desired.
$\square$
Exercise 14.10
Lemma 14.10.A
Let $X \subseteq B^+$ and define: $$ \begin{align*} D := \lbrace u \in B^+ : (\forall x \in X) \, u \leq x\rbrace \cup \lbrace u \in B^+ : (\exists x \in X) \, u \leq -x\rbrace \end{align*}$$ Then $D$ is an open dense subset of $B^+$.
Proof
Openness of $D$ is clear. Let $u \in B^+$, and we consider two cases. If $u \leq x$ for all $x \in X$, then immediately we have $u \in D$. Otherwise, $u \not\leq x$ implies that $u \cdot (-x) \neq 0$ for some $x \in X$. Then $u \cdot (-x) \leq -x$, and $u \cdot (-x) \in D$.
Let $X \subseteq B^+$ and define: $$ \begin{align*} D := \lbrace u \in B^+ : (\forall x \in X) \, u \leq x\rbrace \cup \lbrace u \in B^+ : (\exists x \in X) \, u \leq -x\rbrace \end{align*}$$ Then $D$ is an open dense subset of $B^+$.
Proof
Openness of $D$ is clear. Let $u \in B^+$, and we consider two cases. If $u \leq x$ for all $x \in X$, then immediately we have $u \in D$. Otherwise, $u \not\leq x$ implies that $u \cdot (-x) \neq 0$ for some $x \in X$. Then $u \cdot (-x) \leq -x$, and $u \cdot (-x) \in D$.
$\blacksquare$
Solution
Note that $0 \notin G$ so $G \subseteq B^+$. It's easy to see that $G$ is a filter on $B$ iff $G$ is a filter on $B^+$.
$\implies$: Note that $G \subseteq B^+$ remains an ultrafilter. Let $D \subseteq B^+$ be open dense. Suppose $G \cap D = \emptyset$. Then $X := \lbrace -u : u \in D\rbrace \subseteq G$, and since $G$ is generic in $B$, $\prod X \in G$. If $\prod X = 0$, then we have a contradiction immediately. Otherwise, $\prod X \in B^+$, so by denseness of $D$ we have that $v \leq \prod X$ for some $v \in D$. Then $v \leq -v$ and $v \neq 0$, a contradiction as well.
$\impliedby$: We first show that $G$ is an ultrafilter. Let $u \in B$ and let: $$ \begin{align*} D := \lbrace v \in B^+ : v \leq u \vee v \cdot u = 0\rbrace \end{align*}$$ By Lemma 14.10.A, $D$ is open dense. Since $G$ is generic in $B^+$, we have $v \in G \cap D$ for some $v \in B^+$. If $v \leq u$ then $u \in G$ by upward closure. Otherwise, $v \cdot u = 0$ so $v \leq -u$, hence $-u \in G$.
Now let $X \subseteq G$. Consider: $$ \begin{align*} D := \lbrace u \in B^+ : (\forall x \in X) \, u \leq x\rbrace \cup \lbrace u \in B^+ : (\exists x \in X) \, u \leq -x\rbrace \end{align*}$$ Again by Lemma 14.10.A, $D$ is open dense in $B^+$. Since $G$ is generic in $B^+$, we have that $v \in G \cap D$ for some $v \in B^+$. By compatibility of elements in $G$, we can't have $v \leq -x$ for any $x \in X \subseteq G$. Thus, we must have $v \leq x$ for all $x \in X$. By upward closure (and completeness of $B$), $\prod X \in G$.
Note that $0 \notin G$ so $G \subseteq B^+$. It's easy to see that $G$ is a filter on $B$ iff $G$ is a filter on $B^+$.
$\implies$: Note that $G \subseteq B^+$ remains an ultrafilter. Let $D \subseteq B^+$ be open dense. Suppose $G \cap D = \emptyset$. Then $X := \lbrace -u : u \in D\rbrace \subseteq G$, and since $G$ is generic in $B$, $\prod X \in G$. If $\prod X = 0$, then we have a contradiction immediately. Otherwise, $\prod X \in B^+$, so by denseness of $D$ we have that $v \leq \prod X$ for some $v \in D$. Then $v \leq -v$ and $v \neq 0$, a contradiction as well.
$\impliedby$: We first show that $G$ is an ultrafilter. Let $u \in B$ and let: $$ \begin{align*} D := \lbrace v \in B^+ : v \leq u \vee v \cdot u = 0\rbrace \end{align*}$$ By Lemma 14.10.A, $D$ is open dense. Since $G$ is generic in $B^+$, we have $v \in G \cap D$ for some $v \in B^+$. If $v \leq u$ then $u \in G$ by upward closure. Otherwise, $v \cdot u = 0$ so $v \leq -u$, hence $-u \in G$.
Now let $X \subseteq G$. Consider: $$ \begin{align*} D := \lbrace u \in B^+ : (\forall x \in X) \, u \leq x\rbrace \cup \lbrace u \in B^+ : (\exists x \in X) \, u \leq -x\rbrace \end{align*}$$ Again by Lemma 14.10.A, $D$ is open dense in $B^+$. Since $G$ is generic in $B^+$, we have that $v \in G \cap D$ for some $v \in B^+$. By compatibility of elements in $G$, we can't have $v \leq -x$ for any $x \in X \subseteq G$. Thus, we must have $v \leq x$ for all $x \in X$. By upward closure (and completeness of $B$), $\prod X \in G$.
$\square$
Exercise 14.11
Solution
It's easy to see that $W$ is a partition of $B$ iff $W$ is a maximal antichain of $B^+$. By Exercise 14.10, $G$ is a generic filter of $B^+$ iff $G$ is a generic ultrafilter of $B$. Finally, by Exercise 14.5 $G$ is a generic filter of $B^+$ iff $G \cap W \neq \emptyset$ for all maximal antichains $W \subseteq B^+$. The uniqueness of $u \in G \cap W$ comes from that $W$ is an antichain and $G$ is a filter.
It's easy to see that $W$ is a partition of $B$ iff $W$ is a maximal antichain of $B^+$. By Exercise 14.10, $G$ is a generic filter of $B^+$ iff $G$ is a generic ultrafilter of $B$. Finally, by Exercise 14.5 $G$ is a generic filter of $B^+$ iff $G \cap W \neq \emptyset$ for all maximal antichains $W \subseteq B^+$. The uniqueness of $u \in G \cap W$ comes from that $W$ is an antichain and $G$ is a filter.
$\square$
Exercise 14.12
Exercise 14.12(i)
Statement
$\Vert(\exists y \in x) \, \varphi(y)\Vert = \sum_{y \in \dom{x}} (x(y) \cdot \Vert\varphi(y)\Vert)$.
Solution
$$ \begin{align*} \Vert(\exists y \in x) \, \varphi(y)\Vert &= \Vert\exists y \, (y \in x \wedge \varphi(y))\Vert \\ &= \sum_{y \in V^B} \Vert y \in x \wedge \varphi(y)\Vert \\ &= \sum_{y \in V^B} \Vert y \in x\Vert \cdot \Vert\varphi(y)\Vert \\ &= \sum_{y \in V^B} \bb{\sum_{t \in \dom{x}} \Vert y = t\Vert \cdot x(t)} \cdot \Vert\varphi(y)\Vert \\ &= \sum_{t \in \dom{x}} x(t) \cdot \bb{\sum_{y \in V^B} \Vert y = t\Vert \cdot \Vert\varphi(y)\Vert} \\ &= \sum_{t \in \dom{x}} x(t) \cdot \bb{\sum_{y \in V^B} \Vert y = t \wedge \varphi(y)\Vert} \\ &= \sum_{t \in \dom{x}} x(t) \cdot \bb{\sum_{y \in V^B} \Vert y = t \wedge \varphi(t)\Vert} \\ &= \sum_{t \in \dom{x}} x(t) \cdot \bb{\sum_{y \in V^B} \Vert y = t\Vert \cdot \Vert\varphi(t)\Vert} \\ &= \sum_{t \in \dom{x}} x(t) \cdot \Vert\varphi(t)\Vert \cdot \bb{\sum_{y \in V^B} \Vert y = t\Vert} \\ &= \sum_{t \in \dom{x}} x(t) \cdot \Vert\varphi(t)\Vert \cdot \Vert\exists y \, (y = t)\Vert \\ &= \sum_{t \in \dom{x}} x(t) \cdot \Vert\varphi(t)\Vert \end{align*}$$
$\Vert(\exists y \in x) \, \varphi(y)\Vert = \sum_{y \in \dom{x}} (x(y) \cdot \Vert\varphi(y)\Vert)$.
Solution
$$ \begin{align*} \Vert(\exists y \in x) \, \varphi(y)\Vert &= \Vert\exists y \, (y \in x \wedge \varphi(y))\Vert \\ &= \sum_{y \in V^B} \Vert y \in x \wedge \varphi(y)\Vert \\ &= \sum_{y \in V^B} \Vert y \in x\Vert \cdot \Vert\varphi(y)\Vert \\ &= \sum_{y \in V^B} \bb{\sum_{t \in \dom{x}} \Vert y = t\Vert \cdot x(t)} \cdot \Vert\varphi(y)\Vert \\ &= \sum_{t \in \dom{x}} x(t) \cdot \bb{\sum_{y \in V^B} \Vert y = t\Vert \cdot \Vert\varphi(y)\Vert} \\ &= \sum_{t \in \dom{x}} x(t) \cdot \bb{\sum_{y \in V^B} \Vert y = t \wedge \varphi(y)\Vert} \\ &= \sum_{t \in \dom{x}} x(t) \cdot \bb{\sum_{y \in V^B} \Vert y = t \wedge \varphi(t)\Vert} \\ &= \sum_{t \in \dom{x}} x(t) \cdot \bb{\sum_{y \in V^B} \Vert y = t\Vert \cdot \Vert\varphi(t)\Vert} \\ &= \sum_{t \in \dom{x}} x(t) \cdot \Vert\varphi(t)\Vert \cdot \bb{\sum_{y \in V^B} \Vert y = t\Vert} \\ &= \sum_{t \in \dom{x}} x(t) \cdot \Vert\varphi(t)\Vert \cdot \Vert\exists y \, (y = t)\Vert \\ &= \sum_{t \in \dom{x}} x(t) \cdot \Vert\varphi(t)\Vert \end{align*}$$
$\square$
Exercise 14.12(ii)
Solution
We use $\to$ in place of $\Rightarrow$, and apply Exercise 7.27 and Exercise 14.12(i). $$ \begin{align*} \Vert (\forall y \in x) \, \varphi(y)\Vert &= -\Vert (\exists y \in x) \, \neg\varphi(y)\Vert \\ &= -\bb{\sum_{y \in \dom{x}} x(y) \cdot \Vert \neg\varphi(y)\Vert } \\ &= \prod_{y \in \dom(x)} -(x(y) \cdot \Vert \neg\varphi(y)\Vert ) \\ &= \prod_{y \in \dom(x)} (-x(y) + (-\Vert \neg\varphi(y)\Vert )) \\ &= \prod_{y \in \dom(x)} (-x(y) + \Vert \varphi(y)\Vert ) \\ &= \prod_{y \in \dom(x)} (x(y) \to \Vert \varphi(y)\Vert ) \end{align*}$$
We use $\to$ in place of $\Rightarrow$, and apply Exercise 7.27 and Exercise 14.12(i). $$ \begin{align*} \Vert (\forall y \in x) \, \varphi(y)\Vert &= -\Vert (\exists y \in x) \, \neg\varphi(y)\Vert \\ &= -\bb{\sum_{y \in \dom{x}} x(y) \cdot \Vert \neg\varphi(y)\Vert } \\ &= \prod_{y \in \dom(x)} -(x(y) \cdot \Vert \neg\varphi(y)\Vert ) \\ &= \prod_{y \in \dom(x)} (-x(y) + (-\Vert \neg\varphi(y)\Vert )) \\ &= \prod_{y \in \dom(x)} (-x(y) + \Vert \varphi(y)\Vert ) \\ &= \prod_{y \in \dom(x)} (x(y) \to \Vert \varphi(y)\Vert ) \end{align*}$$
$\square$
Exercise 14.13
Exercise 14.13(i)
Statement
If $x = y$ then $\Vert\check{x} = \check{y}\Vert = 1$ and if $x \neq y$ then $\Vert\check{x} = \check{y}\Vert = 0$.
Solution
It is likely that Jech wanted to use these exercises as the base case for the proof of Lemma 14.21, so we shall not use that result here. For convenience, we combine the solution of this exercise with Exercise 14.13(ii).
We induct on $\rho(x)$, the rank of $x$ in $V^B$. If $x = y$, then clearly $\check{x} = \check{y}$ so $\Vert\check{x} = \check{y}\Vert = 1$ by Lemma 14.15 (induction hypothesis not required).
If $x \in y$, we have $\Vert\check{x} \in \check{y}\Vert = \sum_{t \in \check{y}} (\Vert\check{x} = t\Vert \cdot \check{y}(t))$. By definition, $\check{x} \in \dom(\check{y})$ with $\check{y}(\check{x}) = 1$. Thus: $$ \begin{align*} \Vert\check{x} \in \check{y}\Vert \geq \Vert\check{x} = \check{x}\Vert \cdot \check{y}(\check{x}) = 1 \cdot 1 = 1 \end{align*}$$ Induction hypothesis is not required here either.
If $x \neq y$, WLOG suppose $x - y$ is non-empty. Let $z \in x - y$. Note that $\rho(z) < \rho(x)$, so by induction hypothesis $\Vert\check{z} \in \check{y}\Vert = 0$. Then: $$ \begin{align*} \Vert\check{x} \subseteq \check{y}\Vert &= \prod_{t \in \dom{\check{x}}} (\check{x}(t) \to \Vert t \in \check{y}\Vert) \\ &\leq \check{x}(\check{z}) \to \Vert\check{z} \in \check{y}\Vert \\ &= (-1) + 0 \\ &= 0 \end{align*}$$ so $\Vert\check{x} = \check{y}\Vert \leq \Vert\check{x} \subseteq \check{y}\Vert = 0$.
If $x \notin y$, then by the $x \neq y$ case above we have: $$ \begin{align*} \Vert\check{x} \in \check{y}\Vert &= \sum_{t \in \dom{\check{y}}} \Vert t = \check{x}\Vert \cdot \check{y}(t) \\ &= \sum_{z \in y} \Vert\check{z} = \check{x}\Vert \cdot \check{y}(\check{z}) \\ &= \sum_{z \in y} 0 \cdot \check{y}(\check{z}) \\ &= 0 \end{align*}$$
If $x = y$ then $\Vert\check{x} = \check{y}\Vert = 1$ and if $x \neq y$ then $\Vert\check{x} = \check{y}\Vert = 0$.
Solution
It is likely that Jech wanted to use these exercises as the base case for the proof of Lemma 14.21, so we shall not use that result here. For convenience, we combine the solution of this exercise with Exercise 14.13(ii).
We induct on $\rho(x)$, the rank of $x$ in $V^B$. If $x = y$, then clearly $\check{x} = \check{y}$ so $\Vert\check{x} = \check{y}\Vert = 1$ by Lemma 14.15 (induction hypothesis not required).
If $x \in y$, we have $\Vert\check{x} \in \check{y}\Vert = \sum_{t \in \check{y}} (\Vert\check{x} = t\Vert \cdot \check{y}(t))$. By definition, $\check{x} \in \dom(\check{y})$ with $\check{y}(\check{x}) = 1$. Thus: $$ \begin{align*} \Vert\check{x} \in \check{y}\Vert \geq \Vert\check{x} = \check{x}\Vert \cdot \check{y}(\check{x}) = 1 \cdot 1 = 1 \end{align*}$$ Induction hypothesis is not required here either.
If $x \neq y$, WLOG suppose $x - y$ is non-empty. Let $z \in x - y$. Note that $\rho(z) < \rho(x)$, so by induction hypothesis $\Vert\check{z} \in \check{y}\Vert = 0$. Then: $$ \begin{align*} \Vert\check{x} \subseteq \check{y}\Vert &= \prod_{t \in \dom{\check{x}}} (\check{x}(t) \to \Vert t \in \check{y}\Vert) \\ &\leq \check{x}(\check{z}) \to \Vert\check{z} \in \check{y}\Vert \\ &= (-1) + 0 \\ &= 0 \end{align*}$$ so $\Vert\check{x} = \check{y}\Vert \leq \Vert\check{x} \subseteq \check{y}\Vert = 0$.
If $x \notin y$, then by the $x \neq y$ case above we have: $$ \begin{align*} \Vert\check{x} \in \check{y}\Vert &= \sum_{t \in \dom{\check{y}}} \Vert t = \check{x}\Vert \cdot \check{y}(t) \\ &= \sum_{z \in y} \Vert\check{z} = \check{x}\Vert \cdot \check{y}(\check{z}) \\ &= \sum_{z \in y} 0 \cdot \check{y}(\check{z}) \\ &= 0 \end{align*}$$
$\square$
Exercise 14.13(ii)
Exercise 14.14
Exercise 14.14(i)
Solution
Recall that the statement "$G$ is an ultrafilter on $B$" is equivalent to the conjunction of the following:
Recall that the statement "$G$ is an ultrafilter on $B$" is equivalent to the conjunction of the following:
- $1 \in G$, $0 \notin G$.
- $(\forall u \in G)(\forall v \in B)(u \leq v \to v \in G)$.
- $(\forall u \in G)(\forall v \in G) \, u \cdot v \in G$.
- $(\forall u \in B)(u \in G \vee -u \in G)$.
- We have $\Vert \check{1} \in \dot{G}\Vert = \dot{G}(\check{1}) = 1$ and $\Vert \check{0} \in \dot{G}\Vert = \dot{G}(\check{0}) = 0$.
- Using Exercise 14.12(ii): $$ \begin{align*} &\eqbreak \Vert (\forall u \in \dot{G})(\forall v \in \check{B})(u \leq v \to v \in \dot{G})\Vert \\ &= \prod_{u \in \dom{\dot{G}}} \bb{\dot{G}(u) \to \Vert (\forall v \in \check{B})(u \leq v \to v \in \dot{G})\Vert } \\ &= \prod_{u \in B} \bb{(-u) + \Vert (\forall v \in \check{B})(\check{u} \leq v \to v \in \dot{G})\Vert } \end{align*}$$ Fix a $u \in B$. Then: $$ \begin{align*} \Vert (\forall v \in \check{B})(\check{u} \leq v \to v \in \dot{G})\Vert &= \prod_{v \in \dom{\check{B}}} (\check{B}(v) \to \Vert \check{u} \leq v \to v \in \dot{G}\Vert ) \\ &= \prod_{v \in B} ((-1) + \Vert \check{u} \leq \check{v} \to \check{v} \in \dot{G}\Vert ) \\ &= \prod_{v \in B} \Vert \check{u} \leq \check{v} \to \check{v} \in \dot{G}\Vert \\ &= \prod_{v \in B} ((-\Vert \check{u} \leq \check{v}\Vert ) + \Vert \check{v} \in \dot{G}\Vert ) \end{align*}$$ Now if $v \not\geq u$, then $-\Vert \check{u} \leq \check{v}\Vert = 1$, so it suffices to consider products over $v \geq u$. Thus: $$ \begin{align*} \prod_{v \in B} ((-\Vert \check{u} \leq \check{v}\Vert ) + \Vert \check{v} \in \dot{G}\Vert ) &= \prod_{\substack{v \in B \\ u \leq v}} \dot{G}(\check{v}) \\ &= \prod_{\substack{v \in B \\ u \leq v}} v \\ &= u \end{align*}$$ Therefore: $$ \begin{align*} \prod_{u \in B} \bb{(-u) + \Vert (\forall v \in \check{B})(\check{u} \leq v \to v \in \dot{G})\Vert } = \prod_{u \in B} ((-u) + u) = 1 \end{align*}$$
- We have: $$ \begin{align*} \Vert (\forall u \in \dot{G})(\forall v \in \dot{G}) \, u \cdot v \in \dot{G}\Vert = \prod_{u \in B} \bb{(-u) + \Vert (\forall v \in \dot{G}) \, \check{u} \cdot v \in \dot{G}\Vert } \end{align*}$$ So we fix $u \in B$. Then: $$ \begin{align*} \Vert (\forall v \in \dot{G}) \, \check{u} \cdot v \in \dot{G}\Vert = \prod_{v \in B} \bb{(-v) + \Vert \check{u} \cdot \check{v} \in \dot{G}\Vert } \end{align*}$$ Since $B$ is an algebra of sets, $\check{u} \cdot \check{v} = (u \cdot v)\check{\phantom{x}}$. Thus: $$ \begin{align*} \prod_{v \in B} \bb{(-v) + \Vert \check{u} \cdot \check{v} \in \dot{G}\Vert } &= \prod_{v \in B} \bb{(-v) + u \cdot v} \\ &\geq \prod_{v \in B} \bb{u \cdot (-v) + u \cdot v} \\ &= \prod_{v \in B} u \\ &= u \end{align*}$$ Therefore: $$ \begin{align*} \prod_{u \in B} \bb{(-u) + \Vert (\forall v \in \dot{G}) \, \check{u} \cdot v \in \dot{G}\Vert } \geq \prod_{u \in B} ((-u) + u) = 1 \end{align*}$$
- We have: $$ \begin{align*} \Vert (\forall u \in \check{B})(\check{u} \in \dot{G} \vee -\check{u} \in \dot{G})\Vert &= \prod_{u \in B} ((-1) + \Vert \check{u} \in \dot{G} \vee -\check{u} \in \dot{G}\Vert ) \\ &= \prod_{u \in B} (\Vert \check{u} \in \dot{G}\Vert + \Vert {-\check{u}} \in \dot{G}\Vert ) \\ &= \prod_{u \in B} (u + (-u)) \\ &= \prod_{u \in B} 1 \\ &= 1 \end{align*}$$
$\square$
Exercise 14.14(ii)
Solution
We first note that since $B$ is complete, and $\Vert \dot{G} \text{ is an ultrafilter on } B\Vert = 1$ by Exercise 14.14(i), we have that: $$ \begin{align*} \Vert\prod X \in \dot{G}\Vert &= \Vert (\exists u \in \dot{G})(\forall x \in \check{X}) \, u \leq x\Vert \\ &= \sum_{u \in B}(\dot{G}(\check{u}) \cdot \Vert (\forall x \in \check{X}) \, \check{u} \leq x\Vert ) \\ &= \sum_{u \in B}(u \cdot \Vert (\forall x \in \check{X}) \, \check{u} \leq x\Vert ) \end{align*}$$ Now for each $u \in B$, we have $\Vert (\forall x \in \check{X}) \, \check{u} \leq x\Vert = \prod_{x \in X} \Vert \check{u} \leq \check{x}\Vert $. Observe that the RHS is $1$ iff $u \leq \prod X$, and $0$ otherwise. Thus: $$ \begin{align*} \sum_{u \in B}(u \cdot \Vert (\forall x \in \check{X}) \, \check{u} \leq x\Vert ) = \sum_{u \leq \prod X} u = \prod X \end{align*}$$ On the other hand, we have: $$ \begin{align*} \Vert \check{X} \subseteq \dot{G}\Vert &= \Vert (\forall x \in \check{X}) \, x \in \dot{G} \Vert \\ &= \prod_{x \in X} \Vert \check{x} \in \dot{G}\Vert \\ &= \prod_{x \in X} x \\ &= \prod X \end{align*}$$ Thus: $$ \begin{align*} \Vert \text{if $\check{X} \subseteq \dot{G}$ then $\prod X \in \dot{G}$}\Vert &= -\Vert \check{X} \subseteq \dot{G}\Vert + \Vert\prod X \in \dot{G}\Vert \\ &= -\prod X + \prod X \\ &= 1 \end{align*}$$
We first note that since $B$ is complete, and $\Vert \dot{G} \text{ is an ultrafilter on } B\Vert = 1$ by Exercise 14.14(i), we have that: $$ \begin{align*} \Vert\prod X \in \dot{G}\Vert &= \Vert (\exists u \in \dot{G})(\forall x \in \check{X}) \, u \leq x\Vert \\ &= \sum_{u \in B}(\dot{G}(\check{u}) \cdot \Vert (\forall x \in \check{X}) \, \check{u} \leq x\Vert ) \\ &= \sum_{u \in B}(u \cdot \Vert (\forall x \in \check{X}) \, \check{u} \leq x\Vert ) \end{align*}$$ Now for each $u \in B$, we have $\Vert (\forall x \in \check{X}) \, \check{u} \leq x\Vert = \prod_{x \in X} \Vert \check{u} \leq \check{x}\Vert $. Observe that the RHS is $1$ iff $u \leq \prod X$, and $0$ otherwise. Thus: $$ \begin{align*} \sum_{u \in B}(u \cdot \Vert (\forall x \in \check{X}) \, \check{u} \leq x\Vert ) = \sum_{u \leq \prod X} u = \prod X \end{align*}$$ On the other hand, we have: $$ \begin{align*} \Vert \check{X} \subseteq \dot{G}\Vert &= \Vert (\forall x \in \check{X}) \, x \in \dot{G} \Vert \\ &= \prod_{x \in X} \Vert \check{x} \in \dot{G}\Vert \\ &= \prod_{x \in X} x \\ &= \prod X \end{align*}$$ Thus: $$ \begin{align*} \Vert \text{if $\check{X} \subseteq \dot{G}$ then $\prod X \in \dot{G}$}\Vert &= -\Vert \check{X} \subseteq \dot{G}\Vert + \Vert\prod X \in \dot{G}\Vert \\ &= -\prod X + \prod X \\ &= 1 \end{align*}$$
$\square$
Exercise 14.15
Solution
Define the map $h : M^B/G \to M[G]$ by stipulating that $h([x]) := x^G$. This is well-defined and one-to-one by Lemma 14.28(ii), preserves the $\in$ predicate by Lemma 14.28(i), and is clearly onto by definition of $h$ and $M[G]$.
Define the map $h : M^B/G \to M[G]$ by stipulating that $h([x]) := x^G$. This is well-defined and one-to-one by Lemma 14.28(ii), preserves the $\in$ predicate by Lemma 14.28(i), and is clearly onto by definition of $h$ and $M[G]$.
$\square$
Exercise 14.16
Solution
By Exercise 14.14(i), $H$ remains an ultrafilter as $\Vert \dot{G} \text{ is an ultrafilter on } B\Vert = 1$ implies: $$ \begin{align*} \Vert \pi(\dot{G}) \text{ is an ultrafilter on } \pi(B)\Vert = \Vert \dot{H} \text{ is an ultrafilter on } B\Vert = 1 \end{align*}$$ Similarly by Exercise 14.14(ii), $H$ remains generic. $M[H] \subseteq M[G]$ as $G, \pi \in M[G]$ so $H = \pi(G) \in M[G]$. This argument is symmetric between $G$ and $H$, so $M[H] = M[G]$.
By Exercise 14.14(i), $H$ remains an ultrafilter as $\Vert \dot{G} \text{ is an ultrafilter on } B\Vert = 1$ implies: $$ \begin{align*} \Vert \pi(\dot{G}) \text{ is an ultrafilter on } \pi(B)\Vert = \Vert \dot{H} \text{ is an ultrafilter on } B\Vert = 1 \end{align*}$$ Similarly by Exercise 14.14(ii), $H$ remains generic. $M[H] \subseteq M[G]$ as $G, \pi \in M[G]$ so $H = \pi(G) \in M[G]$. This argument is symmetric between $G$ and $H$, so $M[H] = M[G]$.
$\square$