Set theory - Chapter 12: Models of Set Theory

12.1

If $A_{a}\neq\emptyset$ and $A=\emptyset$, then $\mathfrak{A}_{a}\models\exists x,x=x$ but $\mathfrak{A}\not\models\exists x,x=x$ so the models are not isomorphic.

Let $S$ be a set, and $U$ a principal ultrafilter on $S$. There is $a\in S$, such that $U=\{X\subseteq S:a\in X\}$. For all $f,g\in\prod_{{x\in S}}A_{x}$, $f=_{U}g$ if and only if ${\{x\in S:f(x)=g(x)\}}\in U$ if and only if $f(a)=g(a)$. Hence the function $\rho:A\rightarrow A_{a}$ given by $\rho([f])=f(a)$ is well-defined (does not depend of the choice of $f$). If $[f]\neq[g]$, then $f(a)\neq g(a)$ and so $\rho([f])\neq\rho([g])$ and $\rho$ is one-to-one. If $A_{a}=\emptyset$ then $A=\emptyset$ and so $\rho=\emptyset$ is onto. If $A\neq\emptyset$, then $\forall x\in S,A_{x}\neq\emptyset$. For all $y\in A_{a}$ define $f(a)=y$ and for all $x\neq a$, take $f(x)\in A_{x}$ arbitrary. Then, $\rho([f])=f(a)=y$ and so $\rho$ is onto.

For all predicate $P$, and $f_{1},f_{2},...f_{n}\in\prod_{{x\in S}}A_{x}$, we have $P^{\mathfrak{A}}([f_{1}],[f_{2}],...[f_{n}])$ if and only if $\{x,P^{{\mathfrak{A}_{x}}}(f_{1}(x),f_{2}(x),...f_{n}(x))\}\in U$ if and only if $P^{{\mathfrak{A}_{a}}}(f_{1}(a),f_{2}(a),...f_{n}(a))$ if and only if $P^{{\mathfrak{A}_{x}}}(\rho([f_{1}],\rho([f_{2}],...\rho([f_{n}])$. For all function $F$, $F^{\mathfrak{A}}([f_{1}],...,[f_{n}])=[f]$ where $\forall x\in S,f(x)=F^{{\mathfrak{A}_{x}}}(f_{1}(x),...,f_{2}(x))$. In particular, $F^{{\mathfrak{A}_{a}}}(f_{1}(a),...,f_{2}(a))=f(a)=\rho([f])$. Finally if $c$ is a constant then $c^{\mathfrak{A}}=[f]$ where $\forall x\in S,f(x)=c^{{\mathfrak{A}_{x}}}$ and so $c^{{\mathfrak{A}_{a}}}=f(a)=\rho([f])$ So $\rho$ is an isomorphism between $\mathfrak{A}$ and $\mathfrak{A}_{a}$.

12.2

Let $S$ be a set, and $U$ a principal ultrafilter on $S$. There is $a\in S$, such that $U=\{X\subseteq S:a\in X\}$. Let $j:\mathfrak{A}\rightarrow\mathrm{Ult}_{U}\mathfrak{A}$ the canonical embedding. $j$ is an isomorphism between $\mathfrak{A}$ and $j(\mathfrak{A})$. Moreover, if $[f]\in\mathrm{Ult}_{U}\mathfrak{A}$, then $f(a)=c_{{f(a)}}(a)$ and so $[f]=[c_{a}]=j(f(a))\in j(\mathfrak{A})$. Hence $j(\mathfrak{A})=\mathrm{Ult}_{U}\mathfrak{A}$.

12.3

Let $\kappa$ be a measurable cardinal and $U$ an ultrafilter on $\kappa$. Let $(A,<^{*})$ be the ultrapower of $(\kappa,<)$ by $U$ and $j:\kappa\rightarrow A$ the canonical embedding.

Let $\sigma$ be the sentence $\forall x,y,(x. Then $(\kappa,<)\models\sigma$ and so $(A,<^{*})\models\sigma$ i.e. $(A,<^{*})$ is a linear ordering.

Now suppose that $\kappa$ is $\sigma$-complete. If $(A,<^{*})$ is not well-founded, then there is a sequence ${(f_{n})}_{{n\in\mathbb{N}}}\in{(\kappa^{\kappa})}^{{\mathbb{N}}}$ such that for all $n\in\mathbb{N}$, $[f_{{n+1}}]<^{*}[f_{n}]$ that is $X_{n}=\{\gamma<\kappa,f_{{n+1}}(\gamma). So $\bigcap_{{n\in\mathbb{N}}}X_{n}\in U$ and there is $\alpha<\kappa$ such that $\forall n\in\mathbb{N},f_{{n+1}}(\alpha). A contradiction. So $(A,<^{*})$ is well-ordered and isomorphic and can be identified with $(\lambda,<)$ where $\lambda$ is an ordinal.

Suppose that $\kappa$ is $\kappa$-complete. The canonical embedding $j$ is an isomorphism between $(\kappa,<)$ and $j(\kappa)\subseteq\lambda$. We prove by induction on $\alpha<\kappa$ that $j(\alpha)=\alpha$. Suppose that the result is true for all $\beta<\alpha$. Let $f\in\kappa^{\kappa}$ such that $\forall\beta<\alpha,[f]\neq\beta=j(\beta)=[c_{\beta}]$. Then $X_{\beta}=\{\gamma<\kappa,f(\gamma)\neq c_{\beta}(\gamma)=\beta\}\in U$ and so $\bigcap_{{\beta<\alpha}}X_{\beta}\in U$ that is $[f]\geq[c_{\alpha}]=j(\alpha)$. Hence $j(\alpha)$ is the next element of $\lambda$ after the $\beta$’s that is $j(\alpha)=\alpha$.

If $U$ is principal, the previous results were actually obvious by exercise 12.2. Moreover, there is some $\alpha<\lambda=\kappa$ such that $[d]=\alpha=j(\alpha)$.

Suppose instead that $U$ nonprincipal $\kappa$-complete, then for all $\alpha<\kappa$, the set $\{\gamma<\kappa,\alpha=c_{\alpha}(\gamma) that is $\alpha=j(\alpha)<[d]$ and so $\kappa\leq[d]$. We shall prove that $[d]=\kappa$ if and only if $U$ is normal using the characterization from exercise 8.8.

Assume $[d]=\kappa$. Let $X\in U$ such that $f$ is regressive on $X\in U$. This means $\{\alpha<\kappa,f(\alpha)<\alpha=d(\alpha)\}\supseteq X$ and so $[f]<[d]=\kappa$. Consequently, $[f]=j(\alpha)=[c_{\alpha}]$ for some $\alpha<\kappa$ and $f$ is constant on a set in $U$. So $U$ is normal.

Conversely, suppose $U$ normal and let $f\in\kappa^{\kappa}$ such that $[f]<[d]$. Then $\{\alpha<\kappa,f(\alpha)<\alpha=d(\alpha)\}\in U$. Then $f$ is constant with value $\beta<\alpha$ on some set in $U$. Hence $[f]=[c_{\beta}]=j(\beta)=\beta<\kappa$. Finally, $[d]=\sup_{{[f]<[d]}}[f]\leq\sup_{{\beta<\kappa}}\beta=\kappa$.

12.4

Let $\sigma$ be the axiom of extensionality “$\forall X,\forall Y,{{\left(\forall x\in X\implies x\in Y\right)}\wedge{\left(% \forall y\in Y\implies y\in X\right)}}\implies X=Y$” Let $M$ be a class, then by definition $\sigma^{M}$ is the formula “$\forall X\in M,\forall Y\in M,{{\left(\forall x\in M,x\in X\implies x\in Y% \right)}\wedge{\left(\forall y\in M,y\in Y\implies y\in X\right)}}\implies X=Y$” or using the $\subseteq$ notation:

 $\forall X\in M,\forall Y\in M,{{\left(M\cap X\subseteq Y\right)}\wedge{\left(M% \cap Y\subseteq X\right)}}\implies X=Y$

Suppose that $\sigma^{M}$ holds and let $X,Y\in M$. If $X\cap M=Y\cap M$ then $X\cap M=Y\cap M\subseteq Y$ and $Y\cap M=X\cap M\subseteq X$ and so by $\sigma^{M}$ we have $X=Y$. Hence $M$ is extensional.

Conversely, suppose $M$ extensional and let $X,Y\in M$. Assume $M\cap X\subseteq Y$ and $M\cap Y\subseteq X$. A fortiori, $M\cap X\subseteq M\cap Y$ and $M\cap Y\subseteq M\cap X$ and so $M\cap X=M\cap Y$. Because $M$ is extensional, this implies $X=Y$. Hence $\sigma^{M}$ holds.

12.5

We use lemma 12.10 which contains $\Delta_{0}$ formulas, and the facts that “$z\in\operatorname{dom}f$” is $\Delta_{0}$ and that if $\varphi$ is $\Delta_{0}$, so is $\forall z\in\operatorname{dom}X,\varphi$ (and the variants with $\forall$ and $\operatorname{ran}$)

$x$ is an ordered pair” can be written “$\exists u\in x,\exists a\in u,\exists b\in u,x=(a,b)$”.

$x$ is a partial ordering of $y$” can be written “$x\,\text{is a relation}\wedge\left(\forall t\in\operatorname{dom}x,t\in y% \right)\wedge\left(\forall t\in\operatorname{ran}x,t\in y\right)\wedge\left(% \forall t\in x,\forall z\in y,\neg{\left(t=(z,z)\right)}\right)\wedge\left(% \forall p\in y,\forall q\in y,\forall r\in y,\left(p” where $p is the $\Delta_{0}$ formula “$\exists t\in x,t=(p,q)$”.

$\left(\forall p\in y,\forall q\in y,\neg(p=q)\implies\exists t\in x,t=(p,q)% \vee t=(q,p)\right)$ is a $\Delta_{0}$ formula and so is its conjunction with “$x$ is a partial ordering of $y$”. This conjunction means “$x$ is a linear ordering of $y$”.

$x\cap y=\emptyset$” can be written $\forall z\in x,\neg(z\in y)$.

$z=x\cup y$” can be written $\left(\forall t\in z,t\in x\vee t\in y\right)\wedge x\subseteq z\wedge y\subseteq z$”.

$y=x\cup\{x\}$” can be written $y\in x\vee y=x$.

$x$ is an inductive set” can be written $\left(\exists t\in x,t\,\text{is empty}\right)\wedge\forall t\in x,\exists y% \in x,y=t\cup\{t\}$.

$f$ is a one-to-one function of $X$ into $Y$ can be written “$f\,\text{is a function}\wedge\operatorname{dom}f=X\wedge\left(\forall z\in f,% \exists x\in X,\exists y\in Y,z=(x,y)\right)\wedge\left(\forall x_{1}\in X,% \forall x_{2}\in X,\forall y\in Y,y=f(x_{1})\wedge y=f(x_{2})\implies x_{1}=x_% {2}\right)$”. The ”onto” property can be written $Y=\operatorname{ran}f$.

$f$ is an ordinal function” can be written $\left(f\,\text{is a function}\right)\wedge\left(\forall x\in\operatorname{dom}% f,x\,\text{is an ordinal}\right)\wedge\left(\forall x\in\operatorname{dom}f,% \forall y\in x,y\in\operatorname{dom}f\right)\wedge\left(\forall x\in% \operatorname{ran}f,x\,\text{is an ordinal}\right)$” The ”increasing” property can be written “$\left(\forall x_{2}\in\operatorname{dom}f,\forall x_{1}\in x_{2},\forall y_{1}% \in\operatorname{ran}f,\forall y_{2}\in\operatorname{ran}f,y_{1}=f(x_{1})% \wedge y_{2}=f(x_{2})\implies y_{1}\in y_{2}\right)$”. The ”normal” property can be written $\forall\alpha\in\operatorname{dom}f,\left(\neg\left(\alpha\,\text{is empty}% \right)\wedge\left(\alpha\,\text{is a limit ordinal}\right)\right)\implies% \left(\forall x\in\operatorname{ran}f,x=f(\alpha)\implies\left(\forall y\in x,% \exists z\in\alpha,\exists t\in x,t=f(z)\wedge y\in t\right)\right)$.

12.6

Let $M$ be a transitive class.

$|X|\leq|Y|$ can be written $\exists f,\varphi(f,X,Y)$ where “$\varphi(f,X,Y)$” is the formula $f$ is a one-to-one function from $X$ to $Y$, which is $\Delta_{0}$ by exercise 12.5. Hence if $M\models|X|\leq|Y|$, we have $\exists f\in M,\varphi(f,X,Y)$ and so $|X|\leq|Y|$.

$\alpha\,\text{is not a cardinal}$” can be written $\exists f,\psi(f,\alpha)$ where $\psi(f,\alpha)$ is the $\Delta_{0}$ formula $\exists\beta\in\alpha,f\,\text{is one-to-one function from}\,\beta\,\text{to}\,\alpha$. Let $\alpha\in M$ and suppose that $M\not\models\alpha\,\text{is a cardinal}$ that is $M\models\alpha\,\text{is not a cardinal}$. Then $\exists f\in M,\psi(f,\alpha)$ and so $\alpha$ is not a cardinal.

12.7

Let $\alpha$ be a limit ordinal. Then $V_{\alpha}=\bigcup_{{\beta<\alpha}}V_{\beta}$ and all the $V_{\beta}$ ($\beta<\alpha$) are transitive: if $X\in V_{\beta}$ then $X\subseteq V_{\beta}$.

Extensionality: the formula “$\forall X,\forall Y,{{\left(\forall x\in X\implies x\in Y\right)}\wedge{\left(% \forall y\in Y\implies y\in X\right)}}\implies X=Y$” is $\Delta_{0}$.

Pairing: let $a,b\in V_{\alpha}$. Then there is $\beta<\alpha$ such that $a,b\in V_{\beta}$. Let $c=\{a,b\}$. Then $c\in V_{{\beta+1}}\subseteq V_{\alpha}$. Moreover, “$c=\{a,b\}$” is $\Delta_{0}$ so $V_{\alpha}\models\exists c,c=\{a,b\}$.

Separation: let $\varphi$ be a formula. Let $X,p\in V_{\alpha}$ and define $Y=\{u\in X,\varphi^{{V_{\alpha}}}(u,p)\}$. $Y\subseteq X$ and $X\in V_{\alpha}$ so there is $\beta<\alpha$ such that $X\subseteq V_{\beta}$ and so $Y\in V_{{\beta+1}}\subseteq V_{\alpha}$. For all $u\in V_{\alpha}$, we have $(u\in Y\Leftrightarrow u\in X\wedge\varphi(u,p))$. Hence $V_{\alpha}\models\forall X,\forall p,\exists Y,\forall u,(u\in Y% \Leftrightarrow u\in X\wedge\varphi(u,p))$.

Union: let $X\in V_{\alpha}$ and $Y=\bigcup X$. There is $\beta<\alpha$ such that $X\subseteq V_{\beta}$ and since $Y\subseteq X$, we have $Y\in V_{{\beta+1}}\subseteq V_{\alpha}$. Moreover, “$Y=\bigcup X$” is $\Delta_{0}$ and so $V_{\alpha}$ satisfies the axiom of union.

Powerset: let $X\in V_{\alpha}$ and $Y=\operatorname{\mathcal{P}}(X)$. There is $\beta<\alpha$ such that $X\subseteq V_{\beta}$ and so $Y\subseteq V_{{\beta+1}}$ and $Y\in V_{{\beta+2}}\subseteq V_{{\alpha}}$. Then the formula $\varphi(u)$ given by $u\in Y\Leftrightarrow u\subseteq X$ is $\Delta_{0}$. For all $u\in V_{\alpha}$, $\varphi(u)$ is true and so $V_{\alpha}\models\exists Y,\forall u\varphi(u)$.

Regularity: let $\varphi(S)$ be the formula $\neg\left(S=\emptyset\right)\implies\exists x\in S,S\cap x=\emptyset$. “$S=\emptyset$” and “$S\cap x=\emptyset$” are $\Delta_{0}$ by lemma 12.10 and exercise 12.5. Hence $\varphi$ is $\Delta_{0}$. Let $S\in V_{\alpha}$ be a nonempty set and $x\in S$ of least rank. $V_{\alpha}$ is transitive and so $x\in V_{\alpha}$. Moreover, $x\cap S=\emptyset$. Consequently, $V_{\alpha}\models\forall S,\varphi(S)$.

Finally, suppose that AC holds. Let $X\in V_{\alpha}$. Then there is $f$ such that $\psi(X,f)$ is true where $\psi(X,f)$ is the $\Delta_{0}$-formula “$f$ is a choice function on $X$”:

$f\,\text{is a function}\wedge\left(\forall a\in f,\forall b\in a,\forall u\in b% ,\forall v\in b,a=(u,v)\implies\left(u\in X\wedge u\neq\emptyset\right)\right)% \wedge\left(\forall x\in X,x\neq\emptyset\implies\exists a\in f,\forall b\in a% ,\forall y\in b,a=(x,y)\implies y\in x\right)$

We have $f\subseteq X\times\bigcup X\subseteq\operatorname{\mathcal{P}}(\operatorname{% \mathcal{P}}(X\cup\bigcup X))$ so $f\in V_{\alpha}$. Hence, $V_{\alpha}\models\forall X,\exists f,\psi(X,f)$ i.e. $V_{\alpha}\models\textrm{AC}$.

12.8

Let $\alpha>\omega$. We have $\omega\in V_{\alpha}$ and $\omega$ is inductice. By exercise 12.5, “$x$ is inductive” is $\Delta_{0}$ so $V_{\alpha}\models\exists x,x\,\text{is inductive}$.

12.9

By 12.7 it only remains to show that $V_{\omega}$ satisfies AC and Replacement.

Let $S\in V_{\omega}$ with $\notin S$. Let $s_{1},...,s_{n}$ be the elements of $S$. For each $1\leq i\leq n$, pick $x_{i}\in s_{i}$. Then we have $x_{i},s_{i}\in V_{\omega}$ so $(s_{i},x_{i})\in V_{\omega}$ and $f=\{(s_{i},x_{i}):1\leq i\leq n\}\in V_{\omega}$. Moreover $f$ satisfies $\varphi(f)$ where $\varphi$ is the formula “$f\text{ is a function}\wedge\forall x\in S,\exists y\in x,y=f(x)$”. Hence $V_{\omega}\models\exists f,\varphi(f)$.

Let $\varphi,p$ such that $V_{\omega}\models\forall x,\forall y,\forall z,\left(\varphi(x,y,p)\wedge% \varphi(x,z,p)\right)\implies y=z$. Then $F=\{(x,y)\in V_{\omega}:\varphi^{{V_{\omega}}}(x,y,p)\}$ is a function. Let $X\in V_{\omega}$ and $Y=F(X)$. If $(x,y)\in V_{\omega}$ then $y\in V_{\omega}$ and so $Y\subseteq V_{\omega}$. Hence $Y\in V_{\omega}$. Now, it is easy to verify that $V_{\omega}\models y\in Y\Leftrightarrow\exists x\in X,\phi(x,y,p)$.

12.10

Let $\varphi(S)$ be the $\Delta_{0}$ formula $\emptyset\in S\wedge\forall x\in S$ and $\infty$ be the sentence $\exists S,\varphi(S)$.

Suppose that $\infty$ is provable in $\textrm{ZFC}-\infty$. Then $V_{\omega}\models\textrm{ZFC}-\infty$ and so $V_{\omega}\models\infty$. Hence there is $S\in V_{\omega}$ such that $\phi(S)$. This is a contradiction.

Suppose that “$\infty$ is consistent with $\textrm{ZFC}-\infty$” is provable in $\textrm{ZFC}-\infty$. We work in $\textrm{ZFC}-\infty$ and assume that $\textrm{ZFC}-\infty$ is consistent. Then we conclude that ZFC is consistent. It is provable in ZFC that there is a model of $\textrm{ZFC}-\infty$ and so the sentence “$\textrm{ZFC}-\infty$ is consistent” is provable in ZFC. But “$\infty$ is consistent with $\textrm{ZFC}-\infty$” is provable in $\textrm{ZFC}-\infty$ and a fortiori in ZFC. Thus “ZFC is consistent” is provable in ZFC. This is a contradiction.

12.11

Let $\kappa$ be an inaccessible cardinal. $(V_{\kappa},\in)$ is a ZFC model so there is a countable model. Let $E\subseteq\omega\times\omega$ such that $\mathfrak{A}=(\omega,E)$ is a model of ZFC. We have $\mathfrak{A}\in V_{\kappa}$. If $\sigma$ is a sentence then $\mathfrak{A}\models\sigma$ implies $\sigma^{{\omega,E}}$. Because $\sigma^{{\omega,E}}$ is $\Delta_{0}$ we have $V_{\kappa}\models\sigma^{{\omega,E}}$ that is $V_{\kappa}\models(\mathfrak{A}\models\sigma)$. Similarly, if $\varphi(p)$ is a formula then $\forall p\in\omega,\mathfrak{A}\models\varphi(p)$ and so the $\Delta_{0}$ formula $\forall p\in\omega,\varphi^{{\omega,E}}(p)$ is true. Hence $V_{\kappa}\models(\forall p\in\omega,\mathfrak{A}\models\varphi(p))$. Finally $V_{\kappa}\models(\omega,E)\text{ is a countable model of ZFC}$.

12.12

Let $\kappa$ be an inaccessible cardinal. Let’s recall exercise 6.3: by ordinal induction we show that for each $\alpha<\kappa$, $|V_{\alpha}|<|V_{\kappa}|$ and hence $|V_{\kappa}|=\kappa$. Let $C$ be the set of $\alpha<\kappa$ such that $(V_{\alpha},\in)$ is an elementary submodel of $(V_{\kappa},\in)$. We shall prove that $C$ is closed unbounded in $\kappa$ and in particular non empty.

First, if $\omega\leq\gamma<\kappa$ and $\alpha_{0}<\alpha_{1}<...\alpha_{\xi}<...<\kappa$ is a $\gamma$-sequence of elements of $C$, consider $\alpha=\lim_{\xi}\alpha_{\xi}$. Let $\varphi(a,a_{1},...,a_{k})$ and $a_{1},...,a_{k}\in V_{\alpha}$ such that $\exists a\in V_{\kappa},V_{\kappa}\models\varphi(a,a_{1},...,a_{k})$, There is $\xi<\gamma$ such that $a_{1},...,a_{k}\in V_{\xi}$. Since $(V_{\xi},\in)$ is an elementary submodel of $(V_{\kappa},\in)$, we can find $a\in V_{\xi}\subseteq V_{\alpha}$ such that $V_{\kappa}\models\varphi(a,a_{1},...,a_{k})$. Hence $(V_{\alpha},\in)$ is an elementary submodel of $(V_{\kappa},\in)$ that is $\alpha\in C$.

For each formula $\varphi(a,a_{1},...,a_{k})$ and $a_{1},...,a_{k}\in V_{\kappa}$, if there is $a\in V_{\kappa}$ such that $\varphi(a,a_{1},...,a_{k})$ then we use the axiom of choice to pick such an element to define $h_{\varphi}(a_{1},a_{2},...,a_{n})$ (and set it to $\emptyset$ otherwise). We get Skolem functions $h_{\varphi}$.

Let $\alpha_{0}<\kappa$ arbitrary. Let $n<\omega$ such that $\alpha_{n}$ is defined. The set of all $h_{\varphi}(a_{1},...a_{k})$ such that $\varphi(a,a_{1},...a_{k})$ is a formula and $a_{1},...a_{k}\in V_{{\alpha_{n}}}$ is of size less than $\kappa$ ($\kappa$ is regular uncountable, $|V_{{\alpha_{n}}}|<\kappa=|V_{\kappa}|$ and there are countably many $\varphi$). Hence we can pick $\alpha_{n}<\alpha_{{n+1}}<\kappa$ such that $V_{{\alpha_{{n+1}}}}$ contains all these elements. Let $\alpha=\lim_{n}\alpha_{n}$. Again, because $\kappa$ is uncountable regular, $\alpha_{0}<\alpha<\kappa$.

Let $\varphi(a,a_{1},...,a_{k})$ and $a_{1},...,a_{k}\in V_{\alpha}$ such that $V_{\kappa}\models\varphi(a,a_{1},...,a_{k})$. There is $n<\omega$ such that $a_{1},...,a_{k}\in V_{{\alpha_{n}}}$. Hence $a=h_{\varphi}(a_{1},...a_{k})\in V_{{\alpha_{{n+1}}}}\subseteq V_{\alpha}$ satisfies $V_{\kappa}\models\varphi(a,a_{1},...,a_{k})$. Finally, $V_{\alpha}$ is an elementary model of $V_{\kappa}$ and so $C$ is unbounded.

12.13

Let $\kappa$ be a regular cardinal and define $H_{\kappa}=\{x:|\operatorname{TC}(x)|<\kappa\}$. Let $x$ a set of rank $\kappa$. Then for all $\alpha<\kappa$ there is $x_{\alpha}\in x$ such that $\alpha<\operatorname{rank}(x_{\alpha})+1$ and so ${(\operatorname{rank}(x_{\alpha}))}_{{\alpha<\kappa}}$ is cofinal in $\kappa$. Hence $|\operatorname{TC}(x)|\geq|\{x_{\alpha}\}|\geq\kappa$. Similarly, if $x$ is of rank more than $\kappa$, there is a set $z\in x$ such that $\operatorname{rank}(z)\geq\kappa$. If $z$ is of minimal rank, then $\operatorname{rank}(z)=\kappa$ and $|\operatorname{TC}(x)|\geq|\operatorname{TC}(z)|\geq\kappa$. Consequently, $H_{\kappa}\subseteq V_{\kappa}$. If $x\in y\in H_{\kappa}$ then $|\operatorname{TC}(x)|\leq|\operatorname{TC}(y)|<\kappa$ and so $H_{\kappa}$ is transitive. We shall prove that it is a model of ZFC minus the Power Set axiom.

Extensionality: the formula “$\forall X,\forall Y,{{\left(\forall x\in X\implies x\in Y\right)}\wedge{\left(% \forall y\in Y\implies y\in X\right)}}\implies X=Y$” is $\Delta_{0}$.

Pairing: let $a,b\in H_{\kappa}$. Let $c=\{a,b\}$. Then $\operatorname{TC}(c)=\{a,b\}\cup\operatorname{TC}(a)\cup\operatorname{TC}(b)$ and so $c\in H_{\kappa}$. Moreover, “$c=\{a,b\}$” is $\Delta_{0}$ so $H_{\kappa}\models\exists c,c=\{a,b\}$.

Separation: let $\varphi$ be a formula. Let $X,p\in H_{\kappa}$ and define $Y=\{u\in X,\varphi^{{H_{\kappa}}}(u,p)\}$. $Y\subseteq X$ and so $|\operatorname{TC}(Y)|\leq|\operatorname{TC}(X)|<\kappa$ and so $Y\in H_{\kappa}$. For all $u\in H_{\kappa}$, we have $(u\in Y\Leftrightarrow u\in X\wedge\varphi(u,p))$. Hence $H_{\kappa}\models\forall X,\forall p,\exists Y,\forall u,(u\in Y% \Leftrightarrow u\in X\wedge\varphi(u,p))$.

Union: let $X\in H_{\kappa}$ and $Y=\bigcup X$. We have $\operatorname{TC}(Y)\subseteq\operatorname{TC}(X)$ and so $Y\in H_{\kappa}$. Moreover, “$Y=\bigcup X$” is $\Delta_{0}$ and so $H_{\kappa}$ satisfies the axiom of union.

Infinity: $\kappa$ is uncountable and so $|\operatorname{TC}(\omega)|=|\omega|<\kappa$. Hence $\omega\in H_{\kappa}$ and we deduce as in theorem 12.11 that $H_{\kappa}$ satisfies the axiom of infinity.

Replacement: Let $\varphi,p$ such that $H_{\kappa}\models\forall x,\forall y,\forall z,\left(\varphi(x,y,p)\wedge% \varphi(x,z,p)\right)\implies y=z$. Then $F=\{(x,y)\in H_{\kappa}:\varphi^{{H_{\kappa}}}(x,y,p)\}$ is a function. Let $X\in H_{\kappa}$ and $Y=F(X)$. If $(x,y)\in H_{\kappa}$ then $\operatorname{TC}(y)\subseteq\operatorname{TC}((x,y))$ and so $y\in H_{\kappa}$. We have $|Y|\leq|X|\leq|\operatorname{TC}(x)|<\kappa$ and $\operatorname{TC}(Y)=Y\cup\bigcup_{{y\in Y}}\operatorname{TC}(y)$. Hence $Y\in H_{\kappa}$. Now, it is easy to verify that $H_{\kappa}\models y\in Y\Leftrightarrow\exists x\in X,\phi(x,y,p)$.

Regularity: let $\varphi(S)$ be the formula $\neg\left(S=\emptyset\right)\implies\exists x\in S,S\cap x=\emptyset$. “$S=\emptyset$” and “$S\cap x=\emptyset$” are $\Delta_{0}$ by lemma 12.10 and exercise 12.5. Hence $\varphi$ is $\Delta_{0}$. Let $S\in H_{\kappa}$ be a nonempty set and $x\in S$ of least rank. $H_{\kappa}$ is transitive and so $x\in H_{\kappa}$. Moreover, $x\cap S=\emptyset$. Consequently, $H_{\kappa}\models\forall S,\varphi(S)$.

Choice: Let $X\in H_{\kappa}$ and $f$ a choice function on $X$. We have $f\subseteq X\times\bigcup X$. Hence $|f|\leq|X|\times|\bigcup(X)|\leq{|\operatorname{TC}(X)|}^{2}<\kappa$ and for each $(x,y)\in f$, $\operatorname{TC}((x,y))=\{(x,y),\{x,y\},\{x\}\}\cup\operatorname{TC}(x)\cup% \operatorname{TC}(y)$ and so $|\operatorname{TC}((x,y))|<\kappa$. Finally $\operatorname{TC}(f)=f\cup\bigcup_{{(x,y)\in f}}\operatorname{TC}((x,y))$ is of size less than $\kappa$ and so $f\in H_{\kappa}$. Then we repeat the proof of exercise 12.7.

12.14

We show the result by induction on the complexity on $\varphi$. By definition, for any $V_{\alpha}$ we have ${(x\in y)}^{{V_{\alpha}}}\Leftrightarrow x\in y$ and ${(x=y)}^{{V_{\alpha}}}\Leftrightarrow x=y$. Hence we can take $C_{{x\in y}}=C_{{x=y}}=\mathrm{Ord}$. For all formulas $\varphi,\psi$ then by definition ${(\neg\varphi)}^{{V_{\alpha}}}\Leftrightarrow\neg\varphi^{{V_{\alpha}}}$ and ${(\varphi\wedge\psi)}^{{V_{\alpha}}}\Leftrightarrow\varphi^{{V_{\alpha}}}% \wedge\psi^{{V_{\alpha}}}$. If $\alpha\in C_{\varphi}$ then $\varphi^{{V_{\alpha}}}\Leftrightarrow\varphi$ and so $\neg\varphi^{{V_{\alpha}}}\Leftrightarrow\neg\varphi$ and we can take $C_{{\neg\varphi}}=C_{\varphi}$. If moreover $\alpha\in C_{\psi}$ then $\psi^{{V_{\alpha}}}\Leftrightarrow\psi$ and so $\varphi^{{V_{\alpha}}}\wedge\psi^{{V_{\alpha}}}\Leftrightarrow\varphi\wedge\psi$ and we can take the closed unbounded set $C_{{\varphi\wedge\psi}}=C_{\varphi}\cap C_{\psi}$.

Finally, let $K_{\varphi}=\{\alpha\in\mathrm{Ord}:\forall x_{1},...,x_{n}\in V_{\alpha}% \exists x,\varphi(x,x_{1},...,x_{n})\implies\exists x\in V_{\alpha},\varphi(x,% x_{1},...,x_{n})\}$. If $\gamma\in\mathrm{Ord}$ $\alpha_{0}<...<\alpha_{\xi}<...$ is a $\gamma$ sequence in $K_{\varphi}$ then $\alpha=\lim_{\xi}\alpha_{\xi}$ is clearly in $K_{\varphi}$: if $x_{1},...,x_{n}\in V_{\alpha}$ there is $k<\omega$ such that $x_{1},...,x_{n}\in V_{{\alpha_{k}}}$ and so there is $x\in V_{{\alpha_{k}}}\subseteq V_{\alpha}$ such that $\varphi(x,x_{1},...,x_{n})$. Let $\alpha_{0}\in\mathrm{Ord}$. If $\alpha_{k}$ is defined, then $\{x\text{ of minimal rank such that }\exists x_{1},...x_{n}\in V_{{\alpha_{k}}% },\varphi(x,x_{1},...,x_{n})\}$ is a set and so included in some $V_{{\alpha_{{k+1}}}}$ for $\alpha_{{k+1}}>\alpha_{k}$ large enough. Then again $\alpha_{0}<\alpha=\lim_{k}\alpha_{k}\in K_{\varphi}$. Hence $K_{\varphi}$ is closed unbounded.

Finally, if $\alpha\in C_{\varphi}\cap K_{\varphi}$ then for all $x_{1},...,x_{n}\in V_{\alpha},\exists x,\varphi(x,x_{1},...,x_{n})% \Leftrightarrow\exists x\in V_{\alpha},\varphi(x,x_{1},...,x_{n})% \Leftrightarrow\exists x\in V_{\alpha},\varphi^{{V_{\alpha}}}(x,x_{1},...,x_{n})$. Hence, we can take $C_{{\exists x,\varphi}}=C_{\varphi}\cap K_{\varphi}$.

12.15

A modification of the proof of lemma 12.15 (we define $C=\{x\in M,\varphi^{M}(u_{1},...,u_{n},x)\}$) gives that for any formula $\varphi(u_{1},...,u_{n},x)$, any transitive class $M$ and any set $M_{0}\subseteq M$ there exists a set $M_{1}\subseteq M_{0}$ such that if $\exists x\in M,\varphi^{M}(u_{1},...,u_{n},x)$ then $(\exists x\in M_{1})\varphi^{M}(u_{1},...,u_{n},x)$.

Then we do the proof by induction as in Theorem 12.14. If the result is true for a subformula $\varphi_{j}$ then $\exists x\in M_{1}\varphi_{j}^{{M_{1}}}(u_{1},...,u_{n},x)\iff\exists x\in M_{% 1}\varphi_{j}^{{M}}(u_{1},...,u_{n},x)$ and by the lemma $\exists x\in M_{1}\varphi_{j}^{{M}}(u_{1},...,u_{n},x)\iff\exists x\in M% \varphi^{M}(u_{1},...,u_{n},x)$.

12.16

Let ${(W_{\alpha})}_{{\alpha\in\mathrm{Ord}}}$ be a cumulative hierarchy and $W=\bigcup_{{\alpha\in\mathrm{Ord}}}W_{\alpha}$. Let $\varphi$ be a formula and $\alpha_{0}\in\mathrm{Ord}$. We use yet another variant of Theorem 12.14. We define $C=\{x\in W,\varphi^{W}(u_{1},...,u_{n},x)\}$ as in exercise 12.15. Then we define by induction $\alpha_{{i+1}}>\alpha_{i}$ such that $W_{{\alpha_{{i+1}}}}$ contains the set of $H(u_{1},...,u_{n});u_{1},...u_{n}\in W_{{\alpha_{i}}}$. Finally, the limit ordinal $\alpha=\lim_{{i\rightarrow\omega}}\alpha_{i}>\alpha_{0}$ satisfies $\varphi^{W}(x_{1},...,x_{n})\iff\varphi^{{W_{\alpha}}}(x_{1},...,x_{n})$ for all $x_{1},...,x_{n}\in W_{\alpha}$.