$ \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 13.1.
Solution. Let $Z \in \cl(M)$, the transitive closure of $M$ under the Gödel operations. We induct on the complexity of $Z$ under the operations to show that:If $x \in^\ast Z$ (i.e. there's a finite sequence $x \in x_1 \in \cdots \in x_n \in Z$), then $x \in \cl(M)$.
Call this property (T). Note that if a set is transitive, then every element of this set satisfies this condition. Let $X,Y \in \cl(M)$:
- If $Z = \lbrace X,Y\rbrace$, then immediately $Z \subseteq \cl(M)$, and satisfies the property (T).
- If $Z = X \times Y \in \cl(M)$, let $z = (x,y) = \lbrace \lbrace x\rbrace,\lbrace x,y\rbrace\rbrace \in Z$. Then $x,y \in Z$ by IH on $X,Y \in \cl(M)$, so by $G_1$ we have that $\lbrace x\rbrace,\lbrace x,y\rbrace \in \cl(M)$. By $G_1$ again, $x = \lbrace \lbrace x\rbrace,\lbrace x,y\rbrace\rbrace \in \cl(M)$, so $Z \subseteq \cl(M)$. This also proves that property (T) is satisfied.
- Since $\varepsilon(X,Y) \subseteq X \times Y$, this follows from (2).
- If $X,Y \subseteq \cl(M)$ then immediately $Z = X - Y \subseteq X \subseteq \cl(M)$. Since $X$ satisfies property (T), so does $Z$.
- If $X,Y \subseteq \cl(M)$ then immediately $Z = X \cap Y \subseteq X \subseteq \cl(M)$. Since $X$ satisfies property (T), so does $Z$.
- If $Z = \bigcup X$, let $z \in^\ast Z$. Then $z \in^\ast y \in X$. By IH, $X$ satisfies the property (T), so $z \in \cl(M)$, hence $Z$ satisfies the property (T).
- If $Z = \dom(X)$, let $z \in^\ast Z$. Then $(z',y) = \lbrace \lbrace z'\rbrace,\lbrace z',y\rbrace\rbrace \in X$ for some $y$ and $z \in z'$ or $z = z'$. We see that $z' \in \lbrace z'\rbrace \in (z',y) \in X$, so by IH on $X$, $z \in \cl(M)$.
$\square$
Exercise 13.2.
Solution. Note that if $M = \emptyset$ then the assertion holds true vacuously, so assume otherwise. We induct on $\vert X\vert $. If $\vert X\vert = 0$, then trivially $X \subseteq M$. Now assume the assertion holds for $\vert X\vert = k$. Let $X = \lbrace x_1,\dots,x_{k+1}\rbrace \in M$.Now we observe that at least one of $x_i$ must be in $M$ - otherwise, we have $\func{ext}_\in(X) = \func{ext}_\in(\emptyset)$ (note that $\emptyset \in M$ necessary, as we may take any $Y \in M$ and we have $\emptyset = Y - Y \in M$). WLOG suppose $x_{k+1} \in M$, and we have that $\lbrace x_{k+1}\rbrace \in M$ by $G_1$, so $X - \lbrace x_{k+1}\rbrace = \lbrace x_1,\dots,x_n\rbrace \in M$. By IH, $x_i \in M$ for all $1 \leq i \leq n$, completing the proof.
$\square$
Exercise 13.3.
Solution. An equivalent formulation of the problem is to show that if $G$ is a composition of Gödel operations, then $\pi(G(X,Y)) = G(\pi(X),\pi(Y))$.Note that, as discussed in Theorem 13.9, closure under Gödel operations guarantees us that $\in$ is well-founded in $M$. By Mostoswki's Collapsing Theorem, $\pi$ is an isomosphism between $M$ and its transitive collapse. By Gödel's Normal Form Theorem (Theorem 13.4 and Lemma 13.7), every set in $M$ can be represented by a formula. That is, for all $X_1,\dots,X_n \in M$, there exists a $\Delta_0$ formula $\varphi$ such that:
$$ \begin{align*}
G(X_1,\dots,X_n) = \lbrace (u_1,\dots,u_n) : u_1 \in X_1,\dots,u_n \in X_n, \varphi(u_1,\dots,u_n)\rbrace
\end{align*}$$ Since $\pi$ is an isomorphism:
$$ \begin{align*}
\pi(G(X_1,\dots,X_n)) &= \lbrace (u_1,\dots,u_n) : u_1 \in \pi(X_1),\dots,u_n \in \pi(X_n), \varphi(u_1,\dots,u_n)\rbrace \\
&= G(\pi(X_1),\dots,\pi(X_n))
\end{align*}$$ as desired.
$\square$
Exercise 13.4.
Solution. $G_8$ can be represented more simply - we show that $G_8(X) = \dom(G_{10}(G_9(X \times X)))$. Note that $G_9$ applies the permutation $(2,3)$ to all triples in the set, and $G_{10}$ applies the permutation $(1,2,3)$ to all triples in the set.Note that $(u,v,w) = ((u,v),w)$ by definition of ordered pairs, and:
$$ \begin{align*}
G_8(X) = G_8(X \cap \lbrace (u,v) : u,v \in V\rbrace)
\end{align*}$$ where $V$ is the universe (or the model we're working in).
$$ \begin{align*}
&\eqbreak \dom(G_{10}(G_9(X \times X))) \\
&= \dom(G_{10}(\lbrace (u,w,v) : (u,v,w) \in X \times X\rbrace)) \\
&= \dom(\lbrace (v,u,w) : (u,v,w) \in X \times X\rbrace) \\
&= \lbrace (v,u) : (\exists w \in X) \, (u,v,w) \in X \times X\rbrace
\end{align*}$$ It suffices to show that $X \cap \lbrace (u,v) : u,v \in V\rbrace = \lbrace (v,u) : (\exists w \in X) \, (u,v,w) \in X \times X\rbrace$. $\supseteq$ is immediate. Conversely, if $(u,v) \in X$, then $(u,v,(u,v)) \in X \times X$, which maps to $(u,v) \in X$ under the operation $\dom$.
For $G_5$, we have:
$$ \begin{align*}
&\eqbreak G_5(X,Y) \\
&= X \cap Y \\
&= X \cup Y - ((X \cup Y - X) \cup (X \cup Y - Y)) \\
&= G_4(X \cup Y,G_4(X \cup Y,X) \cup G_4(X \cup Y,Y)) \\
&= G_4(G_6(G_1(X,Y)),G_6(G_1(G_4(G_6(G_1(X,Y)),X),G_4(G_6(G_1(X,Y)),Y))))
\end{align*}$$
$\square$
Exercise 13.5.
Lemma 13.5.A. The following are equivalent in $\mathsf{BG} \; - $ Comprehension:
- $\forall X_1 \, \dots \, \forall X_n \, \exists Y \, Y = \lbrace x : \varphi(x,X_1,\dots,X_n)\rbrace$, where $\varphi$ is a formula in which only set variables are quantified.
- $\forall X_1 \, \dots \, \forall X_n \, \exists Y \, Y = \lbrace (x_1,\dots,x_m) : \varphi(x_1,\dots,x_m,X_1,\dots,X_n)\rbrace$, where $\varphi$ is a formula in which only set variables are quantified.
Proof. (i) $\implies$ (ii): Let $\varphi(x_1,\dots,x_m,y_1,\dots,y_n)$ be such a formula. Define a formula $\psi(x,y_1,\dots,y_n)$ by:
$$ \begin{align*}
\psi(x,y_1,\dots,y_m) \iff \exists x_1 \, \dots \, \exists x_n \, (x = (x_1,\dots,x_n) \wedge \varphi(x_1,\dots,x_m,y_1,\dots,y_n))
\end{align*}$$ By (i), for any classes $X_1,\dots,X_n$ there exists $Y$ such that $Y = \lbrace x : \psi(x,y_1,\dots,y_n)\rbrace$. Clearly $Y = \lbrace (x_1,\dots,x_m) : \varphi(x_1,\dots,x_m,X_1,\dots,X_n)\rbrace$, as desired.
(ii) $\implies$ (i): Let $\varphi(x,y_1,\dots,y_n)$ be such a formula. By (ii) for any classes $X_1,\dots,X_n$ there exists a class $Y$ such that $Y = \lbrace (x) : \varphi(x,X_1,\dots,X_n)\rbrace$. By definition $(x) = \lbrace x\rbrace$, so $\bigcup Y = \lbrace x : \varphi(x,X_1,\dots,X_n)\rbrace$.
$\blacksquare$
Lemma 13.5.B. If $\varphi(u_1,\dots,u_n)$ is a formula with only set variables quantified, then there is a composition $G$ of the operations $G_1,\dots,G_{10}$ above such that for all classes $X_1,\dots,X_n$, there exist classes $X,Y$ such that:
$$ \begin{align*}
G_i(X,Y) = \lbrace (x_1,\dots,x_m) : \varphi(x_1,\dots,x_m,X_1,\dots,X_n)\rbrace
\end{align*}$$ where $X = G^{(1)}(X_1,\dots,X_n)$ and $X = G^{(2)}(X_1,\dots,X_n)$ for some composition $G^{(1)},G^{(2)}$.
Proof. Similar to the original Normal Form Theorem, suffices to consider only formulas of the form:
- The only logical symbols in $\varphi$ are $\neg$, $\wedge$ and $\exists$ (quantified over sets).
- $=$ does not occur.
- The only occurrence of $\in$ is $x_i \in x_j$ for $i \neq j$, $x_i \in X_j$, or $X_i \in X_j$.
- All existential formulas are of the form $\exists y \, \varphi(y,x,X_1,\dots,X_n)$.
Case I - $\varphi$ is atomic: If $\varphi$ is of the form $x_i \in x_j$ where $i \neq j$, then the proof that this can be written in terms of the $G_i$'s is very much similar to the Case I of Normal Form Theorem. For instance, in the easy case of $x_1 \in x_2$, we have:
$$ \begin{align*}
\lbrace (x_1,\dots,x_m) : \varphi(x_1,\dots,x_m,X_1,\dots,X_n)\rbrace = G_3 \times V \times \dots \times V
\end{align*}$$ The use of $G_8,G_9$ and $G_{10}$ are needed to permutate the general case. If $\varphi$ is of the form $x_i \in X_j$, then:
$$ \begin{align*}
\lbrace (x_1,\dots,x_m) : \varphi(x_1,\dots,x_m,X_1,\dots,X_n)\rbrace = V \times \dots \times X_j \times \dots \times V
\end{align*}$$ where the $X_j$ is in the $i^\text{th}$ position. Finally, if $\varphi$ is of the form $X_i \in X_j$, then since none of the $x_i$ is not a free variables inside $\varphi$ we have that the set is either $V$ or empty ($\emptyset = V - V$).
Case II - $\varphi$ is a negation: If $\varphi$ is $\neg\psi$, we have:
$$ \begin{gather*}
\lbrace (x_1,\dots,x_m) : \neg\psi(x_1,\dots,x_m,X_1,\dots,X_n)\rbrace \\
= \\
V \times \dots \times V - \lbrace (x_1,\dots,x_m) : \psi(x_1,\dots,x_m,X_1,\dots,X_n)\rbrace
\end{gather*}$$ Case III - $\varphi$ is a conjunction: If $\varphi$ is $\psi_1 \wedge \psi_2$, we have:
$$ \begin{gather*}
\lbrace (x_1,\dots,x_m) : (\psi_1 \cap \psi_2)(x_1,\dots,x_m,X_1,\dots,X_n)\rbrace \\
= \\
\lbrace (x_1,\dots,x_m) : \psi_1(x_1,\dots,x_m,X_1,\dots,X_n)\rbrace \cap \lbrace (x_1,\dots,x_m) : \psi_2(x_1,\dots,x_m,X_1,\dots,X_n)\rbrace
\end{gather*}$$ Case IV - $\varphi$ is existential: Suppose $\varphi$ is $\exists y \, \psi(x_1,\dots,x_m,y,X_1,\dots,X_n)$ (see condition (iv)). Since $(x_1,\dots,x_m,y) = ((x_1,\dots,x_m),y)$, we have that:
$$ \begin{gather*}
\lbrace (x_1,\dots,x_m) : \exists y \, \psi(x_1,\dots,x_m,y,X_1,\dots,X_n)\rbrace \\
=\\
\dom(\lbrace (x_1,\dots,x_{m+1}) : \psi(x_1,\dots,x_m,x_{m+1},X_1,\dots,X_n)\rbrace)
\end{gather*}$$
$\blacksquare$
Solution. Consider endowing $\mathsf{BG} \; - $Comprehension with the finite axiom schema:
$$ \begin{align*}
\forall X \, \forall Y \, \exists Z \, Z = G_i(X,Y)
\end{align*}$$ where the $G_i$'s are defined earlier in this exercise. Given a formula $\varphi$ in which only set variables are quantified, by Lemma 13.5.B let $G$ be a (finite) composition of operations such that:
$$ \begin{align*}
G(X,Y) = \lbrace (x_1,\dots,x_m) : \varphi(x_1,\dots,x_m,X_1,\dots,X_n)\rbrace
\end{align*}$$ We induct on the complexity of $G$. If $G = G_i$ for some $i$, then by the above axiom we immediately have $Z = G_i(X,Y)$ for some class $Z$. Otherwise, suppose $G(X,Y) = G_i(G^{(1)}(X',Y'),G^{(2)}(X",Y"))$ for some composition $G^{(1)},G^{(2)}$. By induction hypothesis, there exists classes $Z_1,Z_2$ such that $Z_1 = G^{(1)}(X',Y')$ and $Z_2 = G^{(2)}(X",Y")$. Then by the axiom again we have a class $Z$ such that $Z = G_i(Z_1,Z_2)$, which is the desired class. This implies the Axiom of Comprehension by Lemma 13.5.A.
$\square$
Exercise 13.6.
Solution. We first note that since $M$ is transitive, for all $X \in M$ we have $P^M(X) = P(X) \cap M$. Indeed:$$ \begin{align*}
x \in P^M(X) &\iff (\forall y \in M)(y \in x \to y \in X) \\
&\iff x \in M \wedge \forall y \, (y \in x \to y \in X) && \text{as $M$ is transitive} \\
&\iff x \in M \wedge x \in P(X) \\
&\iff x \in M \cap P(X)
\end{align*}$$ We now prove the exercise by induction on $\alpha \in M$. Of course $V_0 = V_0^M = \emptyset$. If $\alpha$ is limit, then:
$$ \begin{align*}
V_\alpha^M = \bigcup_{\beta < \alpha} V_\beta^M = \bigcup_{\beta < \alpha} V_\beta \cap M = V_\alpha \cap M
\end{align*}$$ We now prove for the successor case. We first observe that:
$$ \begin{align*}
V_{\alpha+1}^M = P^M(V_\alpha^M) = P(V_\alpha \cap M) \cap M
\end{align*}$$ We shall show that $P(V_\alpha \cap M) \cap M = P(V_\alpha) \cap M$. $\subseteq$ is immediate. Conversely, if $x \in P(V_\alpha) \cap M$, then $x \in M$ and $x \subseteq V_\alpha$. Since $M$ is transitive, we have $x \subseteq M$, so $x \subseteq V_\alpha \cap M$. Thus $x \in P(V_\alpha \cap M)$. Therefore:
$$ \begin{align*}
V_{\alpha+1}^M = P(V_\alpha \cap M) \cap M = P(V_\alpha) \cap M = V_{\alpha+1} \cap M
\end{align*}$$
$\square$
Exercise 13.7.
Solution. A $\Sigma_1$ formulation of "$X$ is finite" is:$$ \begin{align*}
X \text{ is finite} \iff \exists f \, (f \text{ is a one-to-one function} \wedge \dom(f) = X \wedge \ran(f) \in \omega)
\end{align*}$$ Note that all sentences in the bracket are $\Delta_0$ by Lemma 12.10.
For a $\Pi_1$ formulation, recall from Exercise 1.12 and Exercise 1.13 that a set is finite iff $T$-finite. Thus:
$$ \begin{align*}
X \text{ is finite} \iff \forall X \, (X \subseteq P(S) \to ((\exists x \in X)(\forall y \in X) \, y \subseteq x))
\end{align*}$$ Note that "$X \subseteq P(S)$" is $\Delta_0$, as:
$$ \begin{align*}
X \subseteq P(S) &\iff (\forall x \in X) \, x \subseteq S \\
&\iff (\forall x \in X)(\forall y \in x) \, y \in S
\end{align*}$$
$\square$
Exercise 13.8.
Solution. We first observe that if $(P,<)$, $(Q,<)$ are two $\Delta_0$ linear orders, then the statement "$P$ and $Q$ are order-isomorphic" is $\Sigma_1$, as it can be formulated as:$$ \begin{align*}
\exists f \, (f \text{ is a one-to-one and onto function} \wedge (\forall x \in P)(\forall y \in P)(x < y \iff f(x) < f(y)))
\end{align*}$$ Thus, given ordinals $\alpha,\beta$, we have:
$$ \begin{align*}
x = \alpha + \beta \iff x \text{ is an ordinal} \wedge \text{$(x,\in)$ is order-isomorphic to $(\alpha \times \lbrace 0\rbrace \cup \beta \times \lbrace 1\rbrace,<_\text{lex})$}
\end{align*}$$ and:
$$ \begin{align*}
x = \alpha \cdot \beta \iff x \text{ is an ordinal} \wedge \text{$(x,\in)$ is order-isomorphic to $(\alpha \times \beta,<_\text{lex})$}
\end{align*}$$ where $<_\text{lex}$ denotes the lexicographical order. This implies that $\alpha + \beta$ and $\alpha \cdot \beta$ are $\Sigma_1$. But observe that:
$$ \begin{align*}
x \in \dom(+) \iff x = (u,v) \wedge u \text{ is an ordinal} \wedge v \text{ is an ordinal}
\end{align*}$$ which is $\Delta_0$. By Lemma 13.10(vii), these two functions are in fact $\Delta_1$.
$\square$
Exercise 13.9.
Solution. Noting that $\max\lbrace \alpha,\beta\rbrace = \bigcup \lbrace \alpha,\beta\rbrace$, it's easy to see that the canonical well-ordering (3.12) is $\Delta_0$. We have:$$ \begin{align*}
x = \Gamma(\alpha,\beta) \iff & x \text{ is an ordinal} \\
&\wedge \text{$(x,\in)$ is order-isomorphic to $(\lbrace (\xi,\eta) : (\xi,\eta) < (\alpha,\beta)\rbrace,<)$}
\end{align*}$$ so as we see in the proof of Exercise 13.8, $\Gamma$ is $\Sigma_1$. Again, as we see in the proof of Exercise 13.8, $\dom(\Gamma) = \boldsymbol{\mathrm{ORD}} \times \boldsymbol{\mathrm{ORD}}$, which is $\Delta_0$, so $\Gamma$ is $\Delta_1$.
$\square$
Exercise 13.10.
Solution. Recall that (and as a result of Lemma 6.6(i).A), we have that $x \in \TC(S)$ iff there exists a sequence $x = x_0 \in x_1 \in \dots \in x_n$, and $x_n \in S$. Thus:$$ \begin{align*}
x = \TC(S) \iff (&\forall y \in x) \, \exists f \, (f \text{ is a function} \\
&\wedge \dom(f) \in \omega \\
&\wedge f(0) = y \\
&\wedge f\bb{\bigcup\dom(f)} \in S \\
&\wedge (\forall n \in \dom(f))(n + 1 \in \dom(f) \to f(n) \in f(n+1)))
\end{align*}$$ Thus the function $\TC$ is $\Sigma_1$. We have $\dom(\TC) = V$ so by Lemma 13.10(vii), $\TC$ is $\Delta_1$.
$\square$
Exercise 13.11.
Lemma 13.11.A. The function $\alpha \mapsto V_\alpha$ is $\Delta_1$.
Proof. We have:
$$ \begin{align*}
x = V_\alpha \iff &\exists f \, (f \text{ is a function} \\
&\wedge \dom(f) = \alpha + 1 \\
&\wedge f(0) = \emptyset \\
&\wedge f(\alpha) = x \\
&\wedge (\forall \alpha \in \dom(f))(\alpha + 1 \in \dom(f) \to f(\alpha+1) = P(f(\alpha))) \\
&\wedge (\forall \alpha \in \dom(f))(\alpha \text{ is a limit ordinal} \to f(\alpha) = \bigcup_{\beta \in \alpha} f(\beta)))
\end{align*}$$ Thus the function is $\Sigma_1$. The domain of the function is $\boldsymbol{\mathrm{ORD}}$, which is $\Delta_0$, so by Lemma 13.10(vii) the function is $\Delta_1$.
$\blacksquare$
Solution. We have:
$$ \begin{align*}
\alpha = \rank(x) \iff x \in V_{\alpha+1} \wedge x \notin V_\alpha
\end{align*}$$ which is $\Delta_1$ by Lemma 13.11.A.
$\square$
Exercise 13.12.
Solution. We have $X$ is countable iff:$$ \begin{align*}
\exists f \,(f \text{ is a one-to-one function} \wedge \dom(f) \in \omega \wedge \ran(f) = X)
\end{align*}$$
$\square$
Exercise 13.13.
Solution. See Exercise 12.6(i) for that $\vert X\vert \leq \vert Y\vert $ is $\Sigma_1$. Note that $\vert X\vert = \vert Y\vert \iff \vert X\vert \leq \vert Y\vert \wedge \vert Y\vert \leq \vert X\vert $, so it's also $\Sigma_1$.$\square$
Exercise 13.14.
Solution. As we see in the remark after Lemma 13.13, given a $\Delta_0$ formula $\varphi$ we have:$$ \begin{align*}
\models_0 \varphi[a_1,\dots,a_k] \iff \varphi \in \Delta_0 \wedge \exists M \, (M \text{ is transitive} \wedge (M,\in) \models \varphi[a_1,\dots,a_k])
\end{align*}$$ This is allowed as $\Delta_0$ formulas are always absolute. Note that "$M$ is transitive" is $\Delta_0$ by Lemma 12.10. Furthermore, we have $(M,\in) \models \varphi[a_1,\dots,a_k] \iff \varphi^M[a_1,\dots,a_k]$, and the latter is always $\Delta_0$ as all the quantifiers are bounded. Finally, by $\varphi \in \Delta_0$ we mean "$\varphi$ is a $\Delta_0$ formula", which is $\Delta_0$ as $\Delta_0$ is here viewed as a countable set in the universe (under suitable encoding of formulas). Hence $\models_0$ is $\Sigma_1$.
The same can also be done for $\Sigma_1$ (and hence $\Pi_1$ formulas): If $\exists y \, \varphi(x,y)$ holds, where $\varphi \in \Delta_0$, then let $M$ be a transitive set containing $x$, and we have that $(M,\in) \models \exists y \, \varphi(x,y)$. Thus $\models_1$ is also $\Sigma_1$.
Now suppose $\models_n$ is $\Sigma_n$. Then, as written in the book, we have:
$$ \begin{align*}
\models_{n+1} (\exists x \, \varphi)[x,a_1,\dots,a_k] \iff \varphi \in \Pi_n \wedge \exists a \, (\neg\models_n (\neg\varphi)[a,a_1,\dots,a_k])
\end{align*}$$ so $\models_{n+1}$ is $\Sigma_{n+1}$.
$\square$
Exercise 13.15.
Solution. This follows from that $\Sigma_0 = \Delta_0$ formulas are absolute across all transitive sets by Lemma 12.9.$\square$
Exercise 13.16.
Solution. By the Reflection Principle there exists a set $M \supseteq M_0$ that reflects $\models_n$. Then for all $\Sigma_n$ formulas $\varphi$ we have $\models_n \varphi$ iff $(\models_n \varphi)^M$ iff $(M,\in) \models_n \varphi$, so $M \prec_{\Sigma_n} V$.$\square$
Exercise 13.17.
Lemma 13.17.A. Assume $V = L$. If $\kappa$ is an infinite cardinal, then $H_\kappa = L_\kappa$ (see Exercise 12.13 for definition of $H_\kappa$).
Proof. Clearly $V_\omega = H_\omega = L_\omega$ (this does not require $V = L$). If $\kappa$ is limit, then $H_\kappa = \bigcup_{\lambda < \kappa} H_\lambda = \bigcup_{\lambda < \kappa} L_\lambda = L_\kappa$, so it remains to show the successor cardinal case.
$L_\kappa \subseteq H_\kappa$: Let $X \in L_\kappa$, so $X \in L_\alpha$ for some ordinal $\alpha < \kappa$. Since $L_\alpha$ is transitive, we have $\TC(X) \subseteq L_\alpha$. By Exercise 13.19, we have that $\vert X\vert \leq \vert L_\alpha\vert = \vert \alpha\vert < \kappa$, so $X \in H_\kappa$. We do not require $V = L$ here.
$H_\kappa \subseteq L_\kappa$: Let $X \in H_\kappa$, and suppose $\kappa = \lambda^+$. Then $\vert \TC(X)\vert \leq \lambda$. Since $V = L$, $X \in L_\delta$ for some $\delta$, so $\TC(\lbrace X\rbrace) \subseteq L_\delta$. Then $\vert \TC(\lbrace X\rbrace)\vert \leq \vert L_\delta\vert = \vert \delta\vert \leq \lambda$, so by Löwenheim-Skolem Theorem there exists an elementary submodel $M \prec (L_\delta,\in)$ of size $\lambda$ such that $\TC(\lbrace X\rbrace) \subseteq M$. Let $M'$ be the transitive collapse of $M$. Since $\TC(\lbrace X\rbrace) \subseteq M$ and $\TC(\lbrace X\rbrace)$ is transitive, $\TC(\lbrace X\rbrace) \subseteq M'$. By Gödel's Condensation Lemma, we have that $M' = L_\gamma$ for some ordinal $\gamma$. Since $\vert M\vert = \vert \gamma\vert = \lambda$, we have that $\gamma < \lambda^+$. Thus $X \in \TC(\lbrace X\rbrace) \subseteq L_\gamma \subseteq L_{\lambda^+}$.
$\blacksquare$
Lemma 13.17.B. For regular uncountable cardinals $\kappa$, we have that:
- $H_\kappa \models$ All sets are of cardinality $<\kappa$.
- $L_{\kappa^L} \models$ All sets are of cardinality $<\kappa^L$.
Proof.
- Let $X \in H_\kappa$, so $\vert \TC(X)\vert < \kappa$. Let $\lambda < \kappa$ be a cardinal such that there exists a one-to-one function $f$ on $X$ into $\lambda$. But as we saw in the proof that $H_\kappa \models \AC$ in Exercise 12.13, we in fact have $f \in H_\kappa$ (and that $\lambda \in H_\kappa$). Thus $H_\kappa \models \vert X\vert < \lambda$.
- By (i) and Lemma 13.17.A, we have that $L \models (L_{\kappa^L} \models$ All sets are of cardinality $<\kappa^L))$. But the sentence "$L_{\kappa^L} \models$ All sets are of cardinality $<\kappa^L$" is $\Delta_0$ (as all quantifiers are bounded), so it holds (in $V$).
$\blacksquare$
Solution. Let $X \in M$. Now $M \subseteq L_{\omega_1^L}$, so by Lemma 13.17.B there exists an $f \in (L_{\omega_1^L},\in)$ that is a one-to-one mapping of $\omega$ onto $X$ (note that $\omega^L = \omega$). Then $f$ is definable from $X$ in $L_{\omega_1^L}$, and since $M \prec L_{\omega_1^L}$ we have that $f$ is definable from $X$ in $M$. Thus $f \in M$, so $f(n) \in M$ for all $n$. Therefore $X \subseteq M$.
By Gödel's Condensation Lemma 13.17, $M = L_\alpha$ for some $\alpha < \omega_1$.
$\square$
Exercise 13.18.
Solution. Let $\gamma \in \omega_1^L \cap M$. Then again like the proof of Exercise 13.17, there exists an $f \in (L_{\omega_2^L},\in)$ that is a one-to-one mapping of $\omega$ onto $\gamma$. $f$ is definable from $\gamma$ in $L_{\omega_2}^L$, so it is also definable from $\gamma$ in $M$. Thus $\gamma \subseteq M$. Thus $\omega_1^L \cap M$ is a transitive set of ordinals, hence an ordinal (and of course $\alpha \leq \omega_1$, as $\omega_1^L \leq \omega_1$).$\square$
Exercise 13.19.
Lemma 13.19.A. Given an infinite set $M$, we have $\vert \func{def}(M)\vert = \vert M\vert $.
Proof. Clearly $\lbrace a\rbrace \in \func{def}(M)$ for all $a \in M$, so $\vert \func{def}(M)\vert \geq \vert M\vert $, On the other hand, consider the following map on $[M]^{<\omega} \times \mathit{Form}$ as follows:
$$ \begin{align*}
((a_1,\dots,a_n),\varphi) \mapsto \lbrace x \in M : (M,\in) \models \varphi[x,a_1,\dots,a_n]\rbrace
\end{align*}$$ This map is onto by definition, so we have $\vert \func{def}(M)\vert \leq \vert M\vert ^{<\omega} \cdot \aleph_0 = \vert M\vert $.
$\blacksquare$
Solution. Note that since $\alpha \subseteq L_\alpha$, clearly $\vert L_\alpha\vert \geq \vert \alpha\vert $. We prove the equality. We have $\vert L_\omega\vert = \vert V_\omega\vert = \omega$, and if $\alpha$ is a limit ordinal then:
$$ \begin{align*}
\vert L_\alpha\vert = \mod{\bigcup_{\beta<\alpha} L_\beta} \leq \sum_{\beta < \alpha} \vert L_\beta\vert = \vert \alpha\vert \cdot \sup_{\beta < \alpha} \vert \beta\vert = \vert \alpha\vert
\end{align*}$$ For the successor case, we have by Lemma 13.19.A that $\vert L_{\alpha+1}\vert = \vert L_\alpha\vert = \vert \alpha\vert = \vert \alpha + 1\vert $.
$\square$
Exercise 13.20.
Solution. We work in $L$. Since $X \subseteq \alpha$, we have that $\TC(X)$ is an ordinal and $\TC(X) \leq \alpha$. Let $\beta := \vert \alpha\vert ^+$, so $\vert \TC(X)\vert \leq \vert \alpha\vert < \beta$. Therefore $X \in H_\beta$, but $H_\beta = L_\beta$ by Lemma 13.17.A, so the assertion follows.$\square$
Exercise 13.21.
Solution. For $X \in L$, we let $o(X)$ denote the order-type of $X$ under the canonical well-ordering $<$.We note that $P(\omega) \cap L \subseteq L_{\omega_1^L}$ by Exercise 13.20. This implies that $P(\omega) \cap L \in L_{\omega_1^L + 1}$, as:
$$ \begin{align*}
P(\omega) \cap L = \lbrace x \in L_{\omega_1^L} : &(\exists \varphi \in \mathit{Form})(\exists \alpha < \omega_1) \\
&(\exists a_1,\dots,a_n \in L_\alpha)(y \in x \leftrightarrow (L_\alpha,\in) \models \varphi[y,a_1,\dots,a_n])\rbrace
\end{align*}$$ Note that $\mathit{Form} \in L_{\omega+1}$ as the Gödel numbering of formulas may be done without parameters.
Since there is a definable (without parameters) function from $P(\omega)$ onto $\R$, we have that $\R \cap L \in L_{\omega_1^L+1}$. By Lemma 13.19, we have that $L_{\omega_1^L+\omega}$ witnesses the order-type of $\R^L$, so $o(\R^L) \in L_{\omega_1^L+\omega}$. But since for all $\alpha < \omega_1$ there exists $x \in \R^L$ such that $x \notin L_\alpha$ (since $L$ thinks that $L_\alpha$ is countable but $P^L(x)$ is uncountable), so $o(\R^L)$ must be an unbounded subset of an ordinal of uncountable cofinality. Therefore $o(\R^L) = \omega_1^L$. necessarily.
$\square$
Exercise 13.22.
Solution. This follows from Lemma 13.17.A and Exercise 12.13.$\square$
Exercise 13.23.
Lemma 13.23.A. If $\kappa = \beth_\kappa$, then $V_\kappa = H_\kappa$.
Proof. Suppose $\rank(x) = \alpha < \kappa$. Then $\TC(\lbrace x\rbrace) \subseteq V_\alpha$, so $\vert \TC(\lbrace x\rbrace)\vert \leq \vert V_\alpha\vert = \beth_\alpha < \beth_\kappa = \kappa$. Conversely, if $\vert \TC(\lbrace x\rbrace)\vert < \kappa$, then $\vert \lbrace \rank(z) : z \in \TC(\lbrace x\rbrace)\rbrace\vert < \kappa$. But $\lbrace \rank(z) : z \in \TC(\lbrace x\rbrace)\rbrace$ is an ordinal (say $\alpha$), so $\rank(x) \leq \alpha + 1 < \kappa$. Thus $x \in V_\kappa$ (this converse direction holds for all cardinals).
$\blacksquare$
Solution. Note that $V_\kappa^L = V_\kappa \cap L$ by Exercise 13.6. By Lemma 6.3.A, Lemma 13.17.A and Lemma 13.23.A, we have that $V_\kappa^L = H_\kappa^L = L_\kappa^L = L_\kappa$.
$\square$
Exercise 13.24.
Solution. As in the hint and Lemma 13.19, we have that $h_\varphi$ is well defined for all formulas $\varphi$. Given $X \subseteq L_\delta$, let $M \prec (L_\delta,\in)$ be the Skolem hull of $X$. We shall show that if $N \prec (L_\delta,\in)$ and $X \subseteq N$, then $M \subseteq N$.Let $a \in M$. If $a \in X$, then $a \in N$ as $X \subseteq N$. Otherwise, $a = h_\varphi(x_1,\dots,x_n)$ for some $x_1,\dots,x_n \in X$. Thus:
$$ \begin{align*}
M \models \exists x \, (x \text{ is the $<_\delta$-least element such that } \varphi[x,x_1,\dots,x_n]))
\end{align*}$$ Since $M$ is elementarily equivalent to $N$, we have that $N$ satisfies the same formula. Since such an $x$ is unique, which is $a$, we have that $a \in N$.
$\square$
Exercise 13.25.
Solution. Let $\c{S_\alpha : \alpha < \omega_1}$ be a $\diamondsuit$-sequence, and define $S_X$, $\F$ as in the hint. Then $S_X$ is stationary for all $X \subseteq \omega_1$. Given $X,Y \subseteq \omega_1$, if $S_X \cap S_Y$ is unbounded, then in particular we have $\lbrace \alpha : X \cap \alpha = Y \cap \alpha\rbrace$ is unbounded, so $X = Y$. Therefore, if $S_X \neq S_Y$ (so $X \neq Y$), we have that $S_X \cap S_Y$ is a bounded subset of $\omega_1$, therefore at most countable. This also implies that $\vert \F\vert = 2^{\aleph_1}$.$\square$
Exercise 13.26.
Lemma 13.26.A. Suppose $V = L[A]$ and $\kappa$ is the least cardinal such that $A \subseteq L_\kappa[A]$. Then for cardinals $\lambda$, we have $2^\lambda = \lambda^+$.
Proof. We first note that the proof for Lemma 13.19.A can be repeated with $\func{def}(M)$ replaced with $\func{def}_A(M)$. Thus, Exercise 13.19 holds for $L[A]$. Note also that $L_\alpha[A]$ is transitive for all $\alpha$ - $L_0[A]$ is trivially transitive, and if $L_\alpha[A]$ is transitive then given $X \in L_{\alpha+1}[A]$ and $x \in X$ (note that $x \in L_\alpha[A]$), we have $x = \lbrace y \in L_{\alpha+1}[A] : y \in x\rbrace \in L_{\alpha+1}[A]$.
Let $X \in P(\lambda) \cap L[A]$, so $X \in L_\alpha[A]$ for some ordinal $\alpha \geq \lambda$. By Löwenheim Skolem Theorem we obtain an elementary submodel $M \prec L[A]$ such that $\lambda \subseteq M$, $A \subseteq M$, $\vert M\vert = \lambda$. By the relativised version of Condensation Lemma, if $M'$ is the transitive collapse of $M$ then $M'= L_\gamma[\pi(A \cap M)]$ for some $\gamma$. But $\TC(\lbrace A\rbrace) \subseteq M$ so $\pi(A \cap M) = A$. Thus $A \in L_\gamma[A] \subseteq L_{\lambda^+}[A]$ (note that $\vert \gamma\vert = \lambda$), so $P(\lambda) \cap L[A] \subseteq L_{\lambda^+}[A]$.
$\blacksquare$
Solution. We note that since $\omega_1 \subseteq L_{\omega_1}$, by Lemma 13.26.A we have that $2^\lambda = \lambda^+$ for $\lambda \geq \aleph_1$. Thus, to show that $\GCH$ holds it remains to show that $\CH$ holds.
Let $X \subseteq \omega$, so $X \in L_{\omega+1}[A]$. Let $M \prec L_{\omega_1}[A]$ such that $\TC(\lbrace X\rbrace) \subseteq M$ and $M$ is countable. Then its transitive collapse $M' = L_\alpha[A \cap M]$, but since $A \cap M$ is a countable subset of ordinals $< \omega_1$, there exists a countable ordinal $\xi$ such that $M' = L_\alpha[A \cap \xi]$. We have $X \in M'$, and since $A \cap \xi \in L[A]$ we have that $L_\alpha[A \cap \xi] \subseteq L_\alpha[A] \subseteq L_{\omega_1}[A]$. Thus $P(\omega) \subseteq L_{\omega_1}[A]$ so $\CH$ holds.
$\square$
Exercise 13.27.
Lemma 13.27.A. If $B \in L[A]$ then $L[B] \subseteq L[A]$.
Proof. Let $\alpha$ be the least ordinal such that $B \in L_\alpha[A]$. Then by transfinite induction, we see that $L_{\omega+\beta}[B] \subseteq L_{\alpha+\beta}[A]$ for all ordinals $\beta$, so $L[B] \subseteq L[A]$.
$\blacksquare$
Solution. Assume $V = L[X]$ and $X \in L[X]$. Let $(\theta,E)$, where $\theta$ is an ordinal and $E \subseteq \theta \times \theta$ is a relation such that $(\theta,E)$ is isomorphic to $\TC(\lbrace X\rbrace)$. Let $A = \Gamma"(E) \subseteq \boldsymbol{\mathrm{ORD}}$. We note that $\Gamma$ is a mapping definable without parameters, so $\Gamma \in L$.
We now show that $L[A] = L[X]$. We see that $\theta,E \in L[X]$, $\Gamma \in L \subseteq L[X]$ so $A = \Gamma"(E) \in L[X]$. Therefore $L[A] \subseteq L[X]$ by \ref{lem13.27.A}. Conversely, since $E = \Gamma_{-1}(A) \in L[A]$, we have $\theta = \dom(E) \cup \ran(E) \in L[A]$. Since $E$ is a well-founded relation, in $L[A]$ there exists a transitive set $Y$ such that $(\theta,E)$ is isomorphic to $(Y,\in)$.
Claim.. The transitive set $Y$ is unique.
Proof. Suppose $Y'$ is another transitive set such that $(\theta,E)$ is isomorphic to $(Y',\in)$. Let $f : Y \to \theta$ and $g : Y' \to \theta$ be the isomorphisms. For each ordinal $\alpha$, let $Y_\alpha := \lbrace x \in Y : \rank(x) = \alpha\rbrace$, and similarly for $Y_\alpha'$. We shall induct on $\alpha$ that $Y_\alpha = Y_\alpha'$, and $f\restrictedto Y_\alpha = g\restrictedto Y_\alpha'$.
- $Y_0 = \emptyset = Y_0'$, and trivially $f\restrictedto Y_0 = g\restrictedto Y_0'$.
- Suppose $Y_\alpha = Y_\alpha'$ and $f\restrictedto Y_\alpha = g\restrictedto Y_\alpha'$. Let $x \in Y_{\alpha+1}$, and since $Y$ is transitive we have $x \subseteq Y_\alpha$ (since $y \in x \implies \rank(y) < \rank(x) = \alpha$). Let:
$$ \begin{align*}
x' := \lbrace (g \circ f^{-1})(y) : y \in x\rbrace \in Y'
\end{align*}$$ But since $\rank(y) = \alpha$ for all $y \in x$, and rank is preserved between isomorphisms, we have that $(g \circ f^{-1})(y) = y$ for all $y \in x$. Thus $x' = x$, and since $\rank(x) = \alpha + 1$ we have $x \in Y_{\alpha+1}$. Therefore $Y_{\alpha+1} \subseteq Y_{\alpha+1}$, and by symmetry of argument we have that equality holds. - If $\alpha$ is limit, we have $Y_\alpha = \bigcup_{\beta<\alpha} Y_\beta = \bigcup_{\beta<\alpha} Y_\beta' = Y_\alpha'$.
$\blacksquare$
Note that the claim above is a theorem in $L[X]$ (recall we assume $V = L[X]$), not $L[A]$. But in $L[X]$ we already know that $(\TC(\lbrace X\rbrace),\in)$ is isomorphic to $(\theta,E)$, so we must have $\TC(\lbrace X\rbrace) = Y \in L[A]$. Finally, since $X$ is the element of $\TC(\lbrace X\rbrace)$ of the largest rank, we have that $X \in L[A]$. Therefore $L[X] \subseteq L[A]$.
We have thus proved that $L[X] \models (L[X] = L[A])$. But since relative constructibility is $\Delta_1$ and hence absolute we have:
$$ \begin{align*}
L[X] = L^{L[X]}[X] = L^{L[X]}[A] = L[A]
\end{align*}$$
$\square$
Exercise 13.28.
Solution. Let $f : \omega \to \alpha$ be one-to-one and onto. Define $W \subseteq \omega \times \omega$ by stipulating that $n \, W \, m$ iff $f(n) \in f(m)$. Then $W$ is a well-ordering of order-type $\alpha$. Since "$W$ is a well-ordering of order-type $\alpha$" is $\Delta_0$ relative to $\alpha$, we have that $L[W] \models$ "$W$ is a well-ordering of order-type $\alpha$", so $L[W] \models \alpha$ is countable.Let $A = \Gamma(W) \subseteq \omega$, where $\Gamma$ is the canonical well-ordering of $\boldsymbol{\mathrm{ORD}}^2$ (recall that $\Gamma(\omega_\alpha \times \omega_\alpha) = \omega_\alpha$ for all ordinals $\alpha$). Since $\Gamma$ is definable without parameters, we have that $A \in L[W]$ and $W \in L[A]$. Thus $L[A] = L[W]$. Note that $\AC$ is not used in this proof.
$\square$
Exercise 13.29.
Solution. By Exercise 13.28 we may let $A \subseteq \omega$ be such that $\alpha$ is countable in $L[A]$. For $\alpha \leq \beta < \omega_1$, $L \models$ there exists a one-to-one function $f$ from $\beta$ onto $\alpha$. Since $L \subseteq L[A]$, it follows that $\beta$ is countable in $L[A]$ for all $\alpha \leq \beta < \omega_1$. Of course if $\beta < \alpha$ then $\beta$ is countable in $L[A]$, so $\omega_1^{L[A]} \leq \sup_{\alpha<\omega_1} \alpha = \omega_1$. Note that $\AC$ is not used in this proof.$\square$
Exercise 13.30.
Solution. By Exercise 13.28, for each $\alpha < \omega_1$ there exists $A_\alpha \subseteq \omega$ such that $\alpha$ is countable in $L[A_\alpha]$. Let $F$ be the function $\alpha \mapsto A_\alpha$ (this is a choice function, so $\AC$ is required), and let $A = \bigcup_{\alpha < \omega_1} \lbrace \alpha\rbrace \times F(\alpha) \subseteq \omega_1 \times \omega_1$. Then $L[A_\alpha] \subset L[A]$, and since "$X$ is countable" is $\Sigma_1$ (see Exercise 13.12) hence upward absolute, $\alpha$ is countable in $L[A]$. Thus $\omega_1^{L[A]} = \omega_1$.To ensure that $A \subseteq \omega_1$, we simply consider the canonical well-ordering $\Gamma$ on $\omega_1 \times \omega_1$. Then $L[\Gamma(A)] = L[A]$, as we argued in Exercise 13.29.
$\square$
Exercise 13.31.
Solution. Since $L \models \GCH$, we have that in $L$, $\omega_2$ is inaccessible iff it is a regular limit cardinal (weakly inaccessible). By Lemma 13.13, "$\alpha$ is a regular cardinal" is $\Pi_1$, so we have that $\omega_2$ is a regular cardinal in $L$. Therefore, if $\omega_2$ is not inaccessible in $L$, then $\omega_2$ is a successor cardinal in $L$.Let $\alpha < \omega_2$ be an ordinal such that $\omega_2 = \alpha^+$ in $L$. By repeating the proof in Exercise 13.28, one may obtain an $A \subseteq \omega_1$ such that $\vert \alpha\vert = \omega_1^{L[A]}$ in $L[A]$. By Exercise 13.30, one obtain another $B \subseteq \omega_1$ such that $\omega_1 = \omega_1^{L[B]}$ ($\AC$ is used here). Thus we have that $\omega_1^{L[A \times B]} = \omega_1$ and $\omega_2^{L[A \times B]} = \omega_2$. Now convert $A \times B \subseteq \omega_1 \times \omega_1$ to a subset of $\omega_1$ using the canonical well-ordering $\Gamma$.
$\square$
Exercise 13.32.
Solution. Given a fixed ordinal $\alpha$, for $\beta \leq \alpha$ we observe that $\func{def}_A(L_\beta[A]) = \func{def}_{A \cap L_\alpha[A]}(L_\beta[A])$, so we have that $L_\beta[A] = L_\beta[A \cap L_\alpha[A]]$ (see also the proof of Lemma 13.23). Thus for any ordinal $\alpha$ we have:$$ \begin{align*}
L[A] &= \bigcup_{\alpha \in \boldsymbol{\mathrm{ORD}}} L_\alpha[A] \\
&= \bigcup_{\alpha \in \boldsymbol{\mathrm{ORD}}} L_\alpha[A \cap L_\alpha[A]] \\
&= \bigcup_{\alpha \in \boldsymbol{\mathrm{ORD}}} L_\alpha[\bar{A} \cap L_\alpha[A]] \\
&= \bigcup_{\alpha \in \boldsymbol{\mathrm{ORD}}} L_\alpha[\bar{A}] \\
&= L[\bar{A}]
\end{align*}$$ We first show that $L[A]$ is an inner model of $\ZF$. By Theorem 13.9, it suffices to show that it is closed under Gödel operations and is almost universal. Closure under Gödel operations follow immediately from the way $L[A]$ is constructed (see (13.20), (13.21) and (13.22)). For almost universality, given a set $X \subseteq M$ let $\alpha := \sup\lbrace \min\lbrace \beta \in \boldsymbol{\mathrm{ORD}} : x \in L_\beta[A]\rbrace : x \in X\rbrace$. Then clearly $X \subseteq L_{\alpha+1}[A]$ and $L_{\alpha+1}[A] \in L[A]$.
$L[A]$ satisfies $\AC$ because we may define a global well-ordering $<_{L[A]}$ similar to $<_L$ in Theorem 13.18. Indeed, for ordinals $\alpha$ we let:
$$ \begin{gather*}
W_0^\alpha := L_\alpha[A] \cup \lbrace L_\alpha[A]\rbrace \cup \lbrace A \cap L_\alpha[A]\rbrace \\
W_{n+1}^\alpha := \lbrace G_i(X,Y) : X,Y \in W_n^\alpha, i = 1,\dots,10\rbrace
\end{gather*}$$ and the remaining steps are verbatim to that of $<_L$.
Finally, suppose $M$ is another inner model of $\ZF$ such that $V_\alpha^M \cap A \in M$ for all $\alpha$. Of course $L[A]$ is one such model as $A \cap L[A] \in L[A]$. We show inductively that $L_\alpha[A] \in M$ for all $\alpha \geq \omega$. Since all finite sets are $\Delta_0$ and $M$ is an inner model, we have $L_\omega[A] = V_\omega = V_\omega^M \in M$. If $\alpha$ is a limit ordinal, then we have that $L_\alpha^M[A] \in M$ and $L_\alpha^M[A] = \bigcup_{\beta<\alpha} L_\beta^M[A] = \bigcup_{\beta<\alpha} L_\beta[A] = L_\alpha[A]$. Now suppose $L_\alpha[A] \in M$. By Theorem 13.9, $M$ is closed under Gödel operations. Since $A \cap V_\alpha^M \in M$ and clearly $L_\alpha[A] \subseteq V_\alpha^M$, we have that $A \cap L_\alpha[A] \in M$. Thus:
$$ \begin{align*}
L_{\alpha+1}[A] = \func{def}_A(L_\alpha[A]) = \cl(L_\alpha[A] \cup \lbrace L_\alpha[A]\rbrace \cup \lbrace A \cap L_\alpha[A]\rbrace) \cap P(L_\alpha[A]) \in M
\end{align*}$$ Therefore $L[A] \subseteq M$ by transitivity of $M$.
$\square$
Exercise 13.33.
Solution. By Lemma 13.33.A, there exists a global well-order on $V$. This yields a one-to-one correspondence between $V$ and $\boldsymbol{\mathrm{ORD}}$, so there exists a class relation $E$ such that $(V,\in)$ is isomorphic to $(\boldsymbol{\mathrm{ORD}},E)$. Let $A := \Gamma"(E)$. Following the same argument in Exercise 13.27, we observe that $V = L[A]$ - indeed, since $L[A]$ witnesses the class $A$ (as $L[A]$ contains all the ordinals) and $\Gamma$ is definable without parameters, we obtain a transitive class $W \subseteq L[A]$ such that $(W,\in)$ is isomorphic to $(\boldsymbol{\mathrm{ORD}},E)$ in $L[A]$. But the uniqueness of $W$ (witnessed in $V$) implies that we must have $V = W$, so $V = L[A]$ necessarily.$\square$
Exercise 13.34.
Solution. Define a cumulative hierarchy as follows:- $L_0(M,X) := \emptyset$.
- $L_{\alpha+1}(M,X) := \func{def}_{M \cup \lbrace X\rbrace}(L_\alpha(M,X)) \cup ((M \cup \lbrace X\rbrace) \cap V_\alpha)$.
- $L_\alpha(M,X) := \bigcup_{\beta<\alpha} L_\beta(M,X)$, if $\alpha$ is limit.
- $L(M,X) := \bigcup_{\alpha \in \boldsymbol{\mathrm{ORD}}} L_\alpha(M,X)$.
Now suppose further that $M \models \AC$. We shall show that $L_\alpha(M,X)$ has a well-ordering $<_\alpha$ for all $\alpha$, so since $L(M,X)$ is transitive it implies that every set is well-orderable. $L_0(M,X) = \emptyset$ is no problem, and if $\alpha$ is limit we let $<_\alpha \; := \bigcup_{\beta<\alpha} <_\beta$. Now suppose $<_\alpha$ is well-defined. Let:
$$ \begin{gather*}
W_0^\alpha := L_\alpha(M,X) \cup \lbrace L_\alpha(M,X)\rbrace \cup \lbrace (M \cap \lbrace X\rbrace) \cap L_\alpha(M,X)\rbrace \\
W_{n+1}^\alpha := \lbrace G_i(X,Y) : X,Y \in W_n^\alpha, i = 1,\dots,10\rbrace
\end{gather*}$$ We define $<_{\alpha+1}'$ in the same way as (13.15) (which is an end-extension of $<_\alpha$). Now since $M \cap V_\alpha = V_\alpha^M \in M$ and $M \models \AC$, there exists a well-order in $M \subseteq L(M,X)$, $<_\alpha"$, on $M \cap V_\alpha$. Thus, we may define $<_{\alpha+1}$ by having $<_\alpha"$ end-extending $v_{\alpha+1}'$, then setting $X$ as the last element if $X \in L_{\alpha+1}(M,X) - L_\alpha(M,X)$. Then $<_{\alpha+1}$ is easily seen to be a well-order of $L_{\alpha+1}(M,X)$. Note that this does not imply that $L(M,X)$ satisfies Axiom of Global Choice, but if we further assume that $M$ satisfies Axiom of Global Choice, then so does $L(M,X)$.
$\square$
Exercise 13.35.
Solution. We first note that if $X$ is a set and $X \in \OD$, then $X \subseteq V_\beta$ for some $\beta$. Thus we may write $X = \lbrace u \in V_\beta : \varphi^{V_\beta}(u,\alpha)\rbrace$ (note that using the canonical well-ordering, we may replace $\varphi(u,\alpha_1,\dots,\alpha_n)$ with just $\varphi(u,\alpha)$ - see also Lemma 3.6.A). Let $\gamma := \Gamma(\beta,\alpha)$. Now $X \in V_{\gamma+1}$, and so we have that $X = \lbrace u \in V_{\gamma+1} : \psi(u,\gamma)\rbrace$ for some formulas $\psi$, as $\alpha,\beta$ may be obtained from $\gamma$ using $\Gamma$, which is definable without parameters. But observe further that $\gamma$ is the largest ordinal in $V_{\gamma+1}$, so $\gamma \in V_{\gamma+1}$ is also definable without parameters in $V_{\gamma+1}$. Thus $X$ is definable in $V_{\gamma+1}$ without parameters.Conversely, suppose $X$ is definable in some $V_\gamma$, so $X = \lbrace u \in V_\gamma : \varphi(u)\rbrace$ for some formula $\varphi$. Let $\psi(u,\gamma)$ denote the formula that $\varphi(u)$ and $\rank(u) < \gamma$. Then $X = \lbrace u : \psi(u,\gamma)\rbrace$, so $X \in OD$.
$\square$
Exercise 13.36.
Solution. Suppose $F = \lbrace (\alpha,x) : \varphi(\alpha,x)\rbrace$ for some formula $\varphi$. Let $x \in \ran(F)$. If $x = F(\alpha)$, we shall show that:$$ \begin{align*}
x = \lbrace y : \exists z \, (\varphi(\alpha,z) \wedge y \in z)\rbrace
\end{align*}$$ If $y \in x$, then since $\varphi[\alpha,x]$ we have in particular that $\exists z \, (\varphi(\alpha,z) \wedge y \in z)$. Conversely, suppose $y \in z$ for some $z$ such that $\varphi[\alpha,z]$. But since $F$ is a function, there exists a unique set $z$ such that $y \in z and$ $\varphi[\alpha,z]$. Since we know that $\varphi[\alpha,x]$, we have that $z = x$ necessarily. Thus $y \in x$. Therefore $x$ is ordinal definable (with parameter $\alpha$).
The latter assertion follows immediately: If $M$ is a class with a definable one-to-one correspondence $F : \boldsymbol{\mathrm{ORD}} \to M$, then $M = \ran(F) \subseteq OD$.
$\square$
Exercise 13.37.
Solution. Let $M$ be a transitive model of $\ZF$ such that there exists a definable one-to-one correspondence with the class of all ordinals. By Exercise 13.36, we have $M \subseteq OD$. But since $M$ is transitive, for all $x \in M$ we have $\TC(\lbrace x\rbrace) \subseteq M \subseteq OD$. Thus $x \in HOD$, so we have in fact that $M \subseteq HOD$.$\square$