1

Suppose \(X_1,X_2\) are transitive sets and \(f:X_1\to X_2\) is a bijection that satisfies \[\left(\forall x,y\in X_1\right)\left(x\in y \iff f(x)\in f(y)\right).\] Show that \(X_1 = X_2\) and \(f\) is the identity function on \(X_1\).

Case when \(X_1 = X_2 = 0\) is trivial, suppose \(X_1, X_2\) are nonempty.

We first show that \(0 \in X_1\), \(0 \in X_2\) and \(f(0) = 0\). By foundation there exists \(x\in X_1\) with \(x\cap X_1 = 0\), then as \(x\subseteq X_1\) due to transitivity \(x \cap X_1 = x = 0\). Same argument shows \(0 \in X_2\). Now \(f(0) = 0\), because if \(f(0) \ne 0\), then let \(y \in f(0)\) which by bijectivity means \(f^{-1}(y) \in 0\) which can never happen.

Suppose for all \(x\in X_1\) with \(\operatorname{rank}(x) < \alpha\), \(f(x) = x\). Let \(y\in X_1\) with \(\operatorname{rank}(y) = \alpha\), we show that \(y = f(y)\). Let \(x\in y\), then as \(\operatorname{rank}(x) < \operatorname{rank}(y) = \alpha\) it follows that \(f(x) = x \in f(y)\). Suppose the inclusion is proper, that is \(y \subsetneq f(y)\), then let \(z \in f(y)\) but \(z\notin y\), then \(f^{-1}(z) \in y\) so \(\operatorname{rank}(f^{-1}(z) < \alpha\), which means \(f(f^{-1}(z)) = z = f^{-1}(z)\), so \(z\in y\) which contradicts.

By letting the induction run vacuously past \(\operatorname{rank}(X_1)\) we can see that \(f\) is identity function, then bijectivity of \(f\) gives us that \(X_1 = X_2\).

2

Write a \(\Delta_0\)-formula \(\phi(X,R)\) equivalent (over BST) to “\((X,R)\) is a linear ordering”.

We use the result that \(z = \left\langle x,y\right\rangle\) is equivalent to a \(\Delta_0\) formula over BST (Lemma 11.7).

“\(R\) is a relation on \(X\)” is equivalent to \[\left(\forall r\in R\right)\left(\exists a\in X\right)\left(\exists b\in X\right)\left(r = \left\langle a,b\right\rangle\right) \] “\((X,R)\) is irreflexive” is equivalent to \[\left(\forall x\in X\right)\left(\forall z\in R\right)\left(\lnot \left\langle x,x\right\rangle = z\right)\] “\((X,R)\) is a total ordering” is equivalent to \[ \left(\forall x\in X\right)\left(\forall y\in X\right)\left(\exists z\in R\right)\left(x = y \lor z = \left\langle x,y\right\rangle \lor z = \left\langle y,x\right\rangle\right) \] “\((X,R)\) is transitive” is equivalent to \[ \left(\forall x\in X\right)\left(\forall y\in X\right)\left(\forall z\in X\right) \left( \left(\exists a\in R\right)\left(a = \left\langle x,y\right\rangle\right) \land \left(\exists b\in R\right)\left(b = \left\langle y,z\right\rangle\right) \to \left(\exists c\in R\right)\left(c = \left\langle x,z\right\rangle\right) \right) \] and “\((X,R)\) is a linear ordering” is the conjunction of everything above, all of which are \(\Delta_0\).

3

Let \(H_\kappa = \left\{x: \left\lvert\operatorname{trcl}(x)\right\rvert <\kappa\right\}\).

1. For every infinite cardinal \(\kappa\), \(H_\kappa\) is transitive.

Let \(x\in H_\kappa\), then \(\left\lvert\operatorname{trcl}(x)\right\rvert < \kappa\). Let \(y\in x\) and we want to show that \(y\in H_\kappa\). Since \(y\in x \subseteq \operatorname{trcl}(x)\) and \(\operatorname{trcl}(x)\) is transitive \(y\subseteq\operatorname{trcl}(x)\), then by Lemma 9.6 \(\operatorname{trcl}(y)\subseteq\operatorname{trcl}(x)\) which gives \(\left\lvert\operatorname{trcl}(y)\right\rvert <\kappa\) also.

2. For every infinite cardinal \(\kappa\), \(H_\kappa\cap\mathbf{ORD} = \kappa\).

Let \(\alpha < \kappa\), then as \(\alpha \in \mathbf{ORD}\) and \(\alpha\) is transitive \(\left\lvert\operatorname{trcl}(\alpha)\right\rvert = \left\lvert\alpha\right\rvert < \kappa\), so \(\alpha \in H_\kappa\).

Conversely let \(\alpha \in H_\kappa\) be an ordinal, we want to show that \(\alpha < \kappa\). This is also clear as \(\alpha = \operatorname{trcl}(\alpha)\) and \(\kappa\) is a cardinal.

3. For every infinite cardinal \(\kappa\), \(H_\kappa \subseteq V_\kappa\).

Observation. For all \(\alpha\), \(V_\alpha\) is transitive.

\(V_0 = 0\) is trivially transitive. Suppose \(V_\alpha\) is transitive, let \(x\in V_{\alpha+1}\), then \(x\subseteq V_\alpha\), so let \(y\in x\subseteq V_\alpha\), by transitivity of \(V_\alpha\) \(y\subseteq V_\alpha\) therefore \(y\in V_{\alpha+1}\) which completes the proof for successor case. The limit case trivially follows from definition.

Observation. For all \(\alpha\) for all \(x\), \(x\in V_{\alpha+1}\) iff \(\operatorname{trcl}(x)\in V_{\alpha+1}\).

Let \(x\subseteq V_\alpha\), use transitivity of \(V_\alpha\) and Lemma 9.6 to get \(\operatorname{trcl}(x) \subseteq V_\alpha\). Conversely \(x\subseteq \operatorname{trcl}(x) \subseteq V_{\alpha}\). This result tells us that for all \(x\), \(\operatorname{rank}(x) = \operatorname{rank}(\operatorname{trcl}(x))\).

Now let \(x\in H_\kappa\), it suffices to show \(\operatorname{rank}(\operatorname{trcl}(x)) < \kappa\). Let \(t = \operatorname{trcl}(x)\) and \(S = \left\{\operatorname{rank}(y): y\in t\right\}\) which is a set of ordinals. Let \(\alpha = \min \mathbf{ORD}\setminus S\), then \(\alpha \subseteq S\). We claim that \(\alpha = S\), then \(\alpha = \operatorname{rank}(t) < \kappa\) and we will be done.

To prove the claim suppose the inclusion is proper, let \(\beta >\alpha\) be minimum such that \(\beta\in S\), then \(\beta = \operatorname{rank}(y)\) for some \(y \in t\), which means \[ \beta = \sup_{z\in y} \left(\operatorname{rank}(z) + 1\right) \leq \alpha \] by transitivity \(z\in t\) so \(\operatorname{rank}(z) \in S\), and \(\operatorname{rank}(z) < \operatorname{rank}(y) = \beta\) which by our choice of \(\beta\) means \(\operatorname{rank}(z) < \alpha\), so the upper bound holds, this contradicts \(\beta > \alpha\).

4. For every regular uncountable cardinal \(\kappa\), \(H_\kappa = V_\kappa\) iff \(\kappa\) is strongly inaccessible.

Suppose \(\left(\exists \lambda<\kappa\right)\left(2^\lambda \geq \kappa\right)\), Assume for simplicity that \(\lambda\) is an infinite cardinal, then we know that \(\lambda \subseteq H_\lambda \subseteq V_\lambda\), then \(\left\lvert V_{\lambda+1}\right\rvert \geq 2^{\left\lvert V_\lambda\right\rvert} \geq 2^\lambda \geq \kappa\). Let \(y\subseteq V_{\lambda+1}\) such that \(\left\lvert y\right\rvert = \kappa\), then \(y \in V_{\lambda+2} \subseteq V_\kappa\), but \(\left\lvert\operatorname{trcl}(y)\right\rvert \geq \left\lvert y\right\rvert \geq \kappa\) which means \(y\notin H_\kappa\).

Conversely suppose \(\left(\forall \lambda<\kappa\right)\left(2^\lambda < \kappa\right)\). First we induct on \(\kappa\) to show that \(\left(\forall \alpha<\kappa\right)\left(\beth_\alpha <\kappa\right)\). The case when \(\alpha=0\) trivially holds as we assume \(\kappa>\beth_0=\omega\). Assume \(\beth_\alpha < \kappa\), then \(\beth_{\alpha+1} = 2^{\beth_\alpha} < \kappa\) by strong inaccessibility. When \(\alpha\) is a limit and result holds for all \(\beta<\alpha\), \[\left\lvert\beth_\alpha\right\rvert = \left\lvert\bigcup_{\beta<\alpha} \beth_\beta\right\rvert <\kappa \] as each \(\beth_\beta < \kappa\), \(\alpha < \kappa\) and \(\kappa\) is regular.

By part (c) we only need to show that \(V_\kappa\subseteq H_\kappa\). Let \(x\in V_\kappa\), then \(x\in V_\alpha\) for some \(\alpha < \kappa\). Since \(V_\alpha\) is transitive, \(x\subseteq \operatorname{trcl}(x)\subseteq V_\alpha\), then \(\left\lvert\operatorname{trcl}(x)\right\rvert \leq \left\lvert V_\alpha\right\rvert \leq \beth_\alpha < \kappa\). Where the inequality \(\left\lvert V_\alpha\right\rvert\leq \beth_\alpha\) is a weak form of \(\left\lvert V_{\omega+\alpha}\right\rvert = \beth_\alpha\), which follows from induction.