1

Let \(\overline{y}\) abbreviate \(y_1,\dots,y_n\) where how many variables there are doesn’t matter.

Let \(\phi(\overline{y})\) be a formula with free variables as shown. Show that \[ C_\phi = \left\{\alpha<\omega_1: \left(\forall\overline{y}\in L_\alpha\right)\left[\phi^{L_\alpha}(\overline{y}) \iff \phi^{L_{\omega_1}}(\overline{y})\right]\right\} \] is closed and unbounded in \({\omega_1}\).

We proceed just like the reflection theorem. When \(\phi\) is atomic it is absolute, so we can take the set to be \(\omega_1\). When \(\phi = \lnot \theta\) we just reuse \(C_\theta\). When \(\phi = \psi \land \theta\) we let \(C_\phi = C_\psi \cap C_\theta\) which is still closed unbounded, and an easy check shows that \(C_\phi\) agrees with the condition.

When \(\phi = \left(\exists x\right)\psi(x,\overline{y})\) let \(C_\psi\) be the club given by induction hypothesis. Define \(F:L_{\omega_1}^n \to \omega_1\) as follows. In the case that \(\left(\exists x\in L_{\omega_1}\right) \psi^{L_{\omega_1}}(x,\overline{y})\), define \(F(\overline{y})\) to be the least \(\alpha\in\omega_1\) such that \(\left(\exists x\in L_\alpha\right) \psi^{L_{\omega_1}}(x,\overline{y})\), and let \(F(\overline{y}) = 0\) otherwise. Next define \(G:\omega_1\to \omega_1\) as \(G(\alpha) = \sup_{\overline{y}\in L_{\alpha}} F(\overline{y})\), note that \(G(\alpha)\) exists as \(\left\lvert L_\alpha\right\rvert = \left\lvert\alpha\right\rvert < \omega_1\). Now let \[C_\phi = C_\psi \cap \operatorname{Lim}(\omega_1) \cap \left\{\alpha \in \omega_1: \alpha\text{ is closed under }G\right\} \] which is the intersection of 3 clubs, and therefore a club.

It remains to show that for every \(\alpha \in C_\phi, \overline{y}\in L_\alpha\) \[ \left(\exists x\in L_\alpha\right) \psi^{L_\alpha}(x,\overline{y}) \iff \left(\exists x\in L_{\omega_1}\right) \psi^{L_{\omega_1}}(x,\overline{y}) \]

Suppose there is \(x\in L_\alpha\) satisfying \(\psi^{L_\alpha}(x,\overline{y})\), then as \(\alpha \in C_\psi\), it follows that \(\psi^{L_{\omega_1}}(x,\overline{y})\) holds, and since \(L_\alpha \subseteq L_{\omega_1}\) we complete the proof.

Conversely suppose there exists \(x\in L_{\omega_1}\) such that \(\psi^{L_{\omega_1}}(x,\overline{y})\), we need to produce an \(x'\in L_\alpha\) such that \(\psi^{L_\alpha}(x',\overline{y})\). First find \(\beta < \alpha\) such that all \(\overline{y}\in L_\beta\), which we can since \(\overline{y}\) is finite and \(\alpha\) is limit. Note that from definition \(0 < F(\overline{y}) \leq G(\beta)\), and closure gives \(G(\beta) < \alpha\). So there exists \(x' \in L_{F(\overline{y})} \subseteq L_\alpha\) satisfying \(\psi^{L_{\omega_1}}(x',\overline{y})\). Since \(\alpha \in C_\psi\) this means that \(\psi^{L_\alpha}(x',\overline{y})\) holds as well.

2

Find a sentence \(\psi\) such that \(\psi^{V_{\omega_1}}\) holds but at every \(\alpha < \omega_1\), \(\psi^{V_\alpha}\) fails.

This sentence holds in \(V_{\omega_1}\) but fails when relativised to \(V_\alpha\) whenever \(\alpha < \omega_1\) is a successor, \[ \psi_1 \equiv \left(\forall x\right)\left(\exists y\right)\left(x\in y\right). \] Also, the axiom of infinity holds in \(V_{\omega_1}\) but fails for all \(\alpha \leq \omega\). It remains to produce a sentence which fails for all stages \(\alpha \in (\omega,\omega_1) \cap \operatorname{Lim}(\omega_1)\) but holds at stage \(\omega_1\). We claim that this sentence works \[ \psi_2 \equiv \left(\forall X,R\right) \left(\exists \gamma, g\right) \left( \begin{aligned} &\left\lvert X\right\rvert \leq \omega \land R \text{ well-orders } X \\&\qquad \implies \gamma\in\mathbf{ORD} \land g \text{ witnesses } (X,R) \cong (\gamma, \in) \end{aligned} \right). \]

Claim. \(\left\lvert X\right\rvert \leq \omega\) is absolute between \(V_\alpha\) and \(\mathbf{V}\) whenever \(\alpha > \omega\) is a limit ordinal.

First note that \(\omega\) is absolute for \(V_\alpha\), and \(\left\lvert X\right\rvert \leq \omega\) is \(\Sigma_1\). So by the Tarski-Vaught criterion we just have to show that for any \(X\in V_{\alpha}\), \[ \left(\exists f\right)\left(f: X \to \omega \text{ is injective}\right) \implies \left(\exists f\in V_\alpha\right)\left(f: X \to \omega \text{ is injective}\right) \] and this holds because all functions \(f: X\to \omega\) are enumerated finitely many stages after \(X\), that is if \(X\in V_\beta\) for some \(\beta < \alpha\), the witness \(f\) still remains in \(V_\alpha\).

Claim. “\(R\) well-orders \(X\)” is absolute between \(V_\alpha\) and \(\mathbf{V}\) whenever \(\alpha > \omega\) is a limit ordinal.

“\(R\) well-orders \(X\)” is \(\Pi_1\), so we only need to show that for any \(X,R\in V_\alpha\), \[\begin{align*} &\left(\forall Y\in V_\alpha\right)\left(Y\subseteq X \implies Y \text{ has an } R\text{-minimal element}\right) \\ &\qquad\implies \left(\forall Y\right)\left(Y\subseteq X \implies Y \text{ has an } R\text{-minimal element}\right). \end{align*}\] as the other clauses that form “\(R\) well-orders \(X\)” are all \(\Delta_0\). This statement also holds since \(\alpha\) is limit, and when \(X\in V_\alpha\), all \(Y\) satisfying \(Y\subseteq X\) are also in \(V_\alpha\).

Also note that \(\gamma \in \mathbf{ORD}\) and “\(g\) witnesses \((X,R) \cong (\gamma, \in)\)” are \(\Delta_0\).

\(\psi_2^{V_{\omega_1}}\) holds.

Let \(X,R\in V_{\omega_1}\) with \(\left\lvert X\right\rvert \leq \omega\) and \(R\) a well ordering on \(X\), then let \(\gamma = \operatorname{type}(X,R) < \omega_1\) so \(\gamma \in V_{\omega_1}\). In addition the (unique) witness \(g: X\to \gamma\) has rank below \(\max(\operatorname{rank}(X),\gamma) + \omega < \omega_1\), as similar to argument above all functions \(X\to\gamma\) are enumerated in finitely many stages after \(\beta < \omega_1\) where both \(\gamma, X \in V_\beta\).

Let \(\alpha<\omega_1\) be a limit ordinal greater than \(\omega\), then \(\psi_2^{V_\alpha}\) fails.

Fix \(X\in V_\alpha\) a countably infinite set (\(\omega\) will do), all possible relations on \(X\) are enumerated in finitely many stages after \(X\). Since all well orderings of \(X\) are in \(V_\alpha\), let \(R \in V_\alpha\) well order \(X\) such that \(\gamma = \operatorname{type}(X,R) > \alpha\), then we can see that \(\gamma \notin V_\alpha\), and it follows from the uniqueness of \(\operatorname{type}\) that no \(\gamma, g\) can exist in \(V_\alpha\).

Finally, let \(\psi = \psi_1 \land \psi_2 \land \text{Inf}\) and \(\psi^{V_\alpha}\) will fail for all \(\alpha < \omega_1\) but \(\psi^{V_{\omega_1}}\) will hold.

3

Assume \(\mathbf{V} = \mathbf{L}\). Show that for every infinite \(\kappa\), \(L_\kappa = H_\kappa\).

It is known that \(L_\omega = V_\omega = H_\omega\), so assume \(\kappa > \omega\).

We first show that \(L_\kappa \subseteq H_\kappa\). Let \(x\in L_\kappa\), so \(x\in L_\alpha\) for some \(\alpha <\kappa\), then \(x\subseteq \operatorname{trcl}(x)\subseteq L_\alpha\), therefore \(\left\lvert\operatorname{trcl}(x)\right\rvert\leq \left\lvert L_\alpha\right\rvert \leq \left\lvert\alpha\right\rvert < \kappa\).

Before we show \(H_\kappa \subseteq L_\kappa\), we cite the following results.

Lemma 14.7. There is a finite conjunction \(\psi\) of axioms of ZF such that for every transitive \(M\), \[\psi^M \land \left(\mathbf{V} = \mathbf{L}\right)^M \implies M = L_{o(M)}. \]

Downward Löwenheim-Skolem (Kunen IV 7.10). Let \(\mathbf{Z}\) be any transitive class and \(\phi\) a sentence, then \[ \left(\forall X\subseteq \mathbf{Z}\right)\left[ X\text{ is transitive} \Rightarrow \left(\exists M\right)\left( X\subseteq M \land \phi^M\Leftrightarrow\phi \land M\text{ is transitive} \land \left\lvert M\right\rvert \leq \max\left(\omega,\left\lvert X\right\rvert\right) \right) \right]. \] This statement can be proven by applying the standard Löwenheim-Skolem theorem followed by Mostowski collapse.

Now assume \(\mathbf{V} = \mathbf{L}\) and let \(x \in H_\kappa\), define \(X = \left\{x\right\}\cup \operatorname{trcl}(x)\) which is transitive and \(\left\lvert X\right\rvert = \left\lvert\operatorname{trcl}(x)\right\rvert + 1 < \kappa\). In the case that \(X\) is finite we have \(x\in X\in L_\omega\subseteq L_\kappa\) and we are done. So assume \(\left\lvert X\right\rvert \geq \omega\) and let \(\psi\) be given by Lemma 14.7. By downward Löwenheim-Skolem theorem there exists transitive \(M\supseteq X\) with \(\left\lvert M\right\rvert = \left\lvert X\right\rvert < \kappa\) such that \[ \psi \land \left(\mathbf{V} = \mathbf{L}\right) \iff \psi^M\land\left(\mathbf{V} = \mathbf{L}\right)^M \] and so \(M = L_{o(M)}\). Now \(\left\lvert o(M)\right\rvert = \left\lvert L_{o(M)}\right\rvert = \left\lvert M\right\rvert = \left\lvert X\right\rvert <\kappa\) which gives \(o(M) < \kappa\), this means that \(x\in X\subseteq M = L_{o(M)} \subseteq L_\kappa\).

4

Let \(S\) be any set of axioms extending ZF. Suppose \(\phi_1,\dots,\phi_n\in S\). Show that, if \(\phi_1,\dots,\phi_n\vdash \phi\) for each \(\phi\in S\), then \(S\) is inconsistent. Conclude that ZF is not finitely axiomatizable.

Let \(\chi = \phi_1\land\cdots\land\phi_n\), and we know that for every statement \(\phi\) of \(S\), the statement \(\chi\Rightarrow\phi\) is logically valid, then for every transitive class \(\mathbf{M}\), by Fact 10.2 \(\chi^\mathbf{M}\Rightarrow\phi^\mathbf{M}\) is also logically valid. We reflect on \(\chi\) and let \(\alpha\) be the smallest such that \(\chi^{V_\alpha} \Leftrightarrow \chi\). Then since \(\chi\) are axioms, \(\chi^{V_\alpha}\) holds and for each statement \(\phi\) in \(S\), \(\phi^{V_\alpha}\) holds too. As \(S\) extends ZF, all the basic absoluteness results hold for \(V_\alpha\) and \((\)Reflection theorem\()^{V_\alpha}\) holds too, so in particular \[ \left(\exists \beta \in V_\alpha\right)\left(\chi^{V_\beta} \iff \chi^{V_\alpha}\right) \] as by Lemma 11.12, \(\left(V_\beta\right)^{V_\alpha} = V_\beta\cap V_\alpha = V_\beta\). This means \(\chi^{V_\beta}\) also holds which contradicts minimality of \(\alpha\), therefore \(S\) is inconsistent. This means that if any finite collection of statements \(S\) proves ZF, then \(\text{ZF}\cup S\) is inconsistent, so any attempt to axiomatize ZF in a finite manner gives rise to an inconsistent theory.

5

Show that there is a finite conjunction \(\phi\) of axioms of ZF, such that whenever \(\mathbf{M}\) is a transitive proper class satisfying \(\phi\), \(\mathbf{M}\) satisfies all the axioms of ZF.

The only axiom schemes in ZF are replacement and comprehension. We first let \(\phi\) be a conjunction of all the other axioms, plus whatever instances of replacement and comprehension needed to prove all the absoluteness results I invoke below.

For any \(s\in B^m, t\in B^n\), we let \(s*t\) denote \(\left\langle s(0),\dots,s(m-1),t(0),\dots,t(n-1)\right\rangle\in B^{m+n}\). Using \(\operatorname{En}(m,A,n)\) as in Definition 14.1, we add to \(\phi\) the following statements, \[ \texttt{C} \equiv \left(\forall m,n\in\omega\right) \left(\forall B\right) \left(\forall A\in B, s\in B^n\right) \left(\exists y\right) \left(\forall t\right) \left[ t\in y \Leftrightarrow t\in B\land \left\langle t,A\right\rangle*s \in \operatorname{En}(m,B,n+2) \right] \] and \[ \texttt{R} \equiv \left(\forall m,n\in\omega\right) \left(\forall B\right) \left(\forall A\in B, s\in B^n\right) \left[ \left(\forall t\in A\right) \left(\exists ! y\right) \left(y\in B \land \left\langle t,y,A\right\rangle \in \operatorname{En}(m,B,n+3)\right) \\ \Rightarrow \left(\exists Y\right) \left(\forall t\in A\right) \left(\exists y\in Y\right) \left(y\in B \land \left\langle t,y,A\right\rangle \in \operatorname{En}(m,B,n+3)\right) \right] \]

Let \(\mathbf{M}\) be a transitive proper class satisfying \(\phi\), we only need to check instances of Comprehension and Replacement. Let \(M_\alpha = \mathbf{M} \cap V_\alpha\) and note that \(\mathbf{M} = \bigcup_{\alpha\in \mathbf{ORD}} M_\alpha\) is a continuous hierarchy.

Let \(\theta(t,A,\overline{v})\) be a formula with free variables as shown. Let \(\overline{v}, A\in \mathbf{M}\) and we want \[ X = \left\{t\in A: \theta^\mathbf{M}(t,A,\overline{v})\right\} \in \mathbf{M}. \] First note that \(\mathbf{M}\) satisfies enough of ZF for tuples to exist, so \(\left\langle v_1,\dots,v_n\right\rangle\in \mathbf{M}\) too. Reflect on \(\theta\land\phi\) to find \(\beta\) above the ranks of \(X,A,s,\omega\) such that \(\theta\) and \(\phi\) are absolute between \(M_\beta\) and \(\mathbf{M}\). Now \(M_\beta\) is a transitive set and \(\phi^{M_\beta}\) holds, also note that \(A,s,\overline{v},\omega \in M_\beta\), \(X\subseteq M_\beta\) and \(M_\beta = \left(V_\beta\right)^\mathbf{M} \in \mathbf{M}\). Appealing to Gödel’s construction there is a number \(q\in \omega\) such that \(\operatorname{En}(q,M_\beta,n+2)\) is precisely the set of all \((n+2)\)-tuples over \(M_\beta\) where \(\theta^{M_\beta}\) holds. Then applying \(\texttt{C}\) with \(m = q\) and \(B = M_\beta\) gives a \(y\in M\) containing precisely the members \(t\in M_\beta\) satisfying \(t\in A\) and \(\theta^{M_\beta}(t,A,\overline{v})\), but \(\theta\) is absolute between \(M_\beta\) and \(\mathbf{M}\) so \(y = X \in \mathbf{M}\) as desired.

The proof for any instance of foundation uses exactly the same reflection argument, just that we invoke \(\texttt{R}\).