Set theory - Chapter 12: Models of Set Theory

12.1

If AaA_{a}\neq\emptyset and A=A=\emptyset, then 𝔄ax,x=x\mathfrak{A}_{a}\models\exists x,x=x but 𝔄⊧̸x,x=x\mathfrak{A}\not\models\exists x,x=x so the models are not isomorphic.

Let SS be a set, and UU a principal ultrafilter on SS. There is aSa\in S, such that U={XS:aX}U=\{X\subseteq S:a\in X\}. For all f,gxSAxf,g\in\prod_{{x\in S}}A_{x}, f=Ugf=_{U}g if and only if {xS:f(x)=g(x)}U{\{x\in S:f(x)=g(x)\}}\in U if and only if f(a)=g(a)f(a)=g(a). Hence the function ρ:AAa\rho:A\rightarrow A_{a} given by ρ([f])=f(a)\rho([f])=f(a) is well-defined (does not depend of the choice of ff). If [f][g][f]\neq[g], then f(a)g(a)f(a)\neq g(a) and so ρ([f])ρ([g])\rho([f])\neq\rho([g]) and ρ\rho is one-to-one. If Aa=A_{a}=\emptyset then A=A=\emptyset and so ρ=\rho=\emptyset is onto. If AA\neq\emptyset, then xS,Ax\forall x\in S,A_{x}\neq\emptyset. For all yAay\in A_{a} define f(a)=yf(a)=y and for all xax\neq a, take f(x)Axf(x)\in A_{x} arbitrary. Then, ρ([f])=f(a)=y\rho([f])=f(a)=y and so ρ\rho is onto.

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

12.2

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

12.3

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

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

Now suppose that κ\kappa is σ\sigma-complete. If (A, <*)(A,<^{*}) is not well-founded, then there is a sequence (fn)n(κκ){(f_{n})}_{{n\in\mathbb{N}}}\in{(\kappa^{\kappa})}^{{\mathbb{N}}} such that for all nn\in\mathbb{N}, [fn+1]<*[fn][f_{{n+1}}]<^{*}[f_{n}] that is Xn={γ<κ,fn+1(γ)<fn(γ)}UX_{n}=\{\gamma<\kappa,f_{{n+1}}(\gamma)<f_{n}(\gamma)\}\in U. So nXnU\bigcap_{{n\in\mathbb{N}}}X_{n}\in U and there is α<κ\alpha<\kappa such that n,fn+1(α)<fn(α)\forall n\in\mathbb{N},f_{{n+1}}(\alpha)<f_{n}(\alpha). A contradiction. So (A, <*)(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 jj is an isomorphism between (κ, <)(\kappa,<) and j(κ)λj(\kappa)\subseteq\lambda. We prove by induction on α<κ\alpha<\kappa that j(α)=αj(\alpha)=\alpha. Suppose that the result is true for all β<α\beta<\alpha. Let fκκf\in\kappa^{\kappa} such that β<α,[f]β=j(β)=[cβ]\forall\beta<\alpha,[f]\neq\beta=j(\beta)=[c_{\beta}]. Then Xβ={γ<κ,f(γ)cβ(γ)=β}UX_{\beta}=\{\gamma<\kappa,f(\gamma)\neq c_{\beta}(\gamma)=\beta\}\in U and so β<αXβU\bigcap_{{\beta<\alpha}}X_{\beta}\in U that is [f][cα]=j(α)[f]\geq[c_{\alpha}]=j(\alpha). Hence j(α)j(\alpha) is the next element of λ\lambda after the β\beta’s that is j(α)=αj(\alpha)=\alpha.

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

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

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

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

12.4

Let σ\sigma be the axiom of extensionality “X,Y,(xXxY)(yYyX)X=Y\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 MM be a class, then by definition σM\sigma^{M} is the formula “XM,YM,(xM,xXxY)(yM,yYyX)X=Y\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:

XM,YM,(MXY)(MYX)X=Y\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 σM\sigma^{M} holds and let X,YMX,Y\in M. If XM=YMX\cap M=Y\cap M then XM=YMYX\cap M=Y\cap M\subseteq Y and YM=XMXY\cap M=X\cap M\subseteq X and so by σM\sigma^{M} we have X=YX=Y. Hence MM is extensional.

Conversely, suppose MM extensional and let X,YMX,Y\in M. Assume MXYM\cap X\subseteq Y and MYXM\cap Y\subseteq X. A fortiori, MXMYM\cap X\subseteq M\cap Y and MYMXM\cap Y\subseteq M\cap X and so MX=MYM\cap X=M\cap Y. Because MM is extensional, this implies X=YX=Y. Hence σM\sigma^{M} holds.

12.5

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

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

xx is a partial ordering of yy” can be written “xis a relation(tdomx,ty)(tranx,ty)(tx,zy,¬(t=(z,z)))(py,qy,ry,(p<qq<rp<r))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<q\wedge q<r\implies p<r% \right)\right)” where p<qp<q is the Δ0\Delta_{0} formula “tx,t=(p,q)\exists t\in x,t=(p,q)”.

(py,qy,¬(p=q)tx,t=(p,q)t=(q,p))\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 Δ0\Delta_{0} formula and so is its conjunction with “xx is a partial ordering of yy”. This conjunction means “xx is a linear ordering of yy”.

xy=x\cap y=\emptyset” can be written zx,¬(zy)\forall z\in x,\neg(z\in y).

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

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

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

ff is a one-to-one function of XX into YY can be written “fis a functiondomf=X(zf,xX,yY,z=(x,y))(x1X,x2X,yY,y=f(x1)y=f(x2)x1=x2)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=ranfY=\operatorname{ran}f.

ff is an ordinal function” can be written (fis a function)(xdomf,xis an ordinal)(xdomf,yx,ydomf)(xranf,xis an ordinal)\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 “(x2domf,x1x2,y1ranf,y2ranf,y1=f(x1)y2=f(x2)y1y2)\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 αdomf,(¬(αis empty)(αis a limit ordinal))(xranf,x=f(α)(yx,zα,tx,t=f(z)yt))\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 MM be a transitive class.

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

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

12.7

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

Extensionality: the formula “X,Y,(xXxY)(yYyX)X=Y\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 Δ0\Delta_{0}.

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

Separation: let φ\varphi be a formula. Let X,pVαX,p\in V_{\alpha} and define Y={uX,φVα(u,p)}Y=\{u\in X,\varphi^{{V_{\alpha}}}(u,p)\}. YXY\subseteq X and XVαX\in V_{\alpha} so there is β<α\beta<\alpha such that XVβX\subseteq V_{\beta} and so YVβ+1VαY\in V_{{\beta+1}}\subseteq V_{\alpha}. For all uVαu\in V_{\alpha}, we have (uYuXφ(u,p))(u\in Y\Leftrightarrow u\in X\wedge\varphi(u,p)). Hence VαX,p,Y,u,(uYuXφ(u,p))V_{\alpha}\models\forall X,\forall p,\exists Y,\forall u,(u\in Y% \Leftrightarrow u\in X\wedge\varphi(u,p)).

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

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

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

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

fis a function(af,ba,ub,vb,a=(u,v)(uXu))(xX,xaf,ba,yb,a=(x,y)yx)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 fX×X𝒫(𝒫(XX))f\subseteq X\times\bigcup X\subseteq\operatorname{\mathcal{P}}(\operatorname{% \mathcal{P}}(X\cup\bigcup X)) so fVαf\in V_{\alpha}. Hence, VαX,f,ψ(X,f)V_{\alpha}\models\forall X,\exists f,\psi(X,f) i.e. VαACV_{\alpha}\models\textrm{AC}.

12.8

Let α>ω\alpha>\omega. We have ωVα\omega\in V_{\alpha} and ω\omega is inductice. By exercise 12.5, “xx is inductive” is Δ0\Delta_{0} so Vαx,xis inductiveV_{\alpha}\models\exists x,x\,\text{is inductive}.

12.9

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

Let SVωS\in V_{\omega} with S\notin S. Let s1,,sns_{1},...,s_{n} be the elements of SS. For each 1in1\leq i\leq n, pick xisix_{i}\in s_{i}. Then we have xi,siVωx_{i},s_{i}\in V_{\omega} so (si,xi)Vω(s_{i},x_{i})\in V_{\omega} and f={(si,xi):1in}Vωf=\{(s_{i},x_{i}):1\leq i\leq n\}\in V_{\omega}. Moreover ff satisfies φ(f)\varphi(f) where φ\varphi is the formula “f is a functionxS,yx,y=f(x)f\text{ is a function}\wedge\forall x\in S,\exists y\in x,y=f(x)”. Hence Vωf,φ(f)V_{\omega}\models\exists f,\varphi(f).

Let φ,p\varphi,p such that Vωx,y,z,(φ(x,y,p)φ(x,z,p))y=zV_{\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)Vω:φVω(x,y,p)}F=\{(x,y)\in V_{\omega}:\varphi^{{V_{\omega}}}(x,y,p)\} is a function. Let XVωX\in V_{\omega} and Y=F(X)Y=F(X). If (x,y)Vω(x,y)\in V_{\omega} then yVωy\in V_{\omega} and so YVωY\subseteq V_{\omega}. Hence YVωY\in V_{\omega}. Now, it is easy to verify that VωyYxX,ϕ(x,y,p)V_{\omega}\models y\in Y\Leftrightarrow\exists x\in X,\phi(x,y,p).

12.10

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

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

Suppose that “\infty is consistent with ZFC-\textrm{ZFC}-\infty” is provable in ZFC-\textrm{ZFC}-\infty. We work in ZFC-\textrm{ZFC}-\infty and assume that ZFC-\textrm{ZFC}-\infty is consistent. Then we conclude that ZFC is consistent. It is provable in ZFC that there is a model of ZFC-\textrm{ZFC}-\infty and so the sentence “ZFC-\textrm{ZFC}-\infty is consistent” is provable in ZFC. But “\infty is consistent with ZFC-\textrm{ZFC}-\infty” is provable in ZFC-\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κ, )(V_{\kappa},\in) is a ZFC model so there is a countable model. Let Eω×ωE\subseteq\omega\times\omega such that 𝔄=(ω,E)\mathfrak{A}=(\omega,E) is a model of ZFC. We have 𝔄Vκ\mathfrak{A}\in V_{\kappa}. If σ\sigma is a sentence then 𝔄σ\mathfrak{A}\models\sigma implies σω,E\sigma^{{\omega,E}}. Because σω,E\sigma^{{\omega,E}} is Δ0\Delta_{0} we have Vκσω,EV_{\kappa}\models\sigma^{{\omega,E}} that is Vκ(𝔄σ)V_{\kappa}\models(\mathfrak{A}\models\sigma). Similarly, if φ(p)\varphi(p) is a formula then pω,𝔄φ(p)\forall p\in\omega,\mathfrak{A}\models\varphi(p) and so the Δ0\Delta_{0} formula pω,φω,E(p)\forall p\in\omega,\varphi^{{\omega,E}}(p) is true. Hence Vκ(pω,𝔄φ(p))V_{\kappa}\models(\forall p\in\omega,\mathfrak{A}\models\varphi(p)). Finally Vκ(ω,E) is a countable model of ZFCV_{\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α|<|Vκ||V_{\alpha}|<|V_{\kappa}| and hence |Vκ|=κ|V_{\kappa}|=\kappa. Let CC be the set of α<κ\alpha<\kappa such that (Vα, )(V_{\alpha},\in) is an elementary submodel of (Vκ, )(V_{\kappa},\in). We shall prove that CC is closed unbounded in κ\kappa and in particular non empty.

First, if ωγ<κ\omega\leq\gamma<\kappa and α0<α1<αξ<<κ\alpha_{0}<\alpha_{1}<...\alpha_{\xi}<...<\kappa is a γ\gamma-sequence of elements of CC, consider α=limξαξ\alpha=\lim_{\xi}\alpha_{\xi}. Let φ(a,a1,,ak)\varphi(a,a_{1},...,a_{k}) and a1,,akVαa_{1},...,a_{k}\in V_{\alpha} such that aVκ,Vκφ(a,a1,,ak)\exists a\in V_{\kappa},V_{\kappa}\models\varphi(a,a_{1},...,a_{k}), There is ξ<γ\xi<\gamma such that a1,,akVξa_{1},...,a_{k}\in V_{\xi}. Since (Vξ, )(V_{\xi},\in) is an elementary submodel of (Vκ, )(V_{\kappa},\in), we can find aVξVαa\in V_{\xi}\subseteq V_{\alpha} such that Vκφ(a,a1,,ak)V_{\kappa}\models\varphi(a,a_{1},...,a_{k}). Hence (Vα, )(V_{\alpha},\in) is an elementary submodel of (Vκ, )(V_{\kappa},\in) that is αC\alpha\in C.

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

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

Let φ(a,a1,,ak)\varphi(a,a_{1},...,a_{k}) and a1,,akVαa_{1},...,a_{k}\in V_{\alpha} such that Vκφ(a,a1,,ak)V_{\kappa}\models\varphi(a,a_{1},...,a_{k}). There is n<ωn<\omega such that a1,,akVαna_{1},...,a_{k}\in V_{{\alpha_{n}}}. Hence a=hφ(a1,ak)Vαn+1Vαa=h_{\varphi}(a_{1},...a_{k})\in V_{{\alpha_{{n+1}}}}\subseteq V_{\alpha} satisfies Vκφ(a,a1,,ak)V_{\kappa}\models\varphi(a,a_{1},...,a_{k}). Finally, VαV_{\alpha} is an elementary model of VκV_{\kappa} and so CC is unbounded.

12.13

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

Extensionality: the formula “X,Y,(xXxY)(yYyX)X=Y\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 Δ0\Delta_{0}.

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

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

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

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

Replacement: Let φ,p\varphi,p such that Hκx,y,z,(φ(x,y,p)φ(x,z,p))y=zH_{\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)Hκ:φHκ(x,y,p)}F=\{(x,y)\in H_{\kappa}:\varphi^{{H_{\kappa}}}(x,y,p)\} is a function. Let XHκX\in H_{\kappa} and Y=F(X)Y=F(X). If (x,y)Hκ(x,y)\in H_{\kappa} then TC(y)TC((x,y))\operatorname{TC}(y)\subseteq\operatorname{TC}((x,y)) and so yHκy\in H_{\kappa}. We have |Y||X||TC(x)|<κ|Y|\leq|X|\leq|\operatorname{TC}(x)|<\kappa and TC(Y)=YyYTC(y)\operatorname{TC}(Y)=Y\cup\bigcup_{{y\in Y}}\operatorname{TC}(y). Hence YHκY\in H_{\kappa}. Now, it is easy to verify that HκyYxX,ϕ(x,y,p)H_{\kappa}\models y\in Y\Leftrightarrow\exists x\in X,\phi(x,y,p).

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

Choice: Let XHκX\in H_{\kappa} and ff a choice function on XX. We have fX×Xf\subseteq X\times\bigcup X. Hence |f||X|×|(X)||TC(X)|2<κ|f|\leq|X|\times|\bigcup(X)|\leq{|\operatorname{TC}(X)|}^{2}<\kappa and for each (x,y)f(x,y)\in f, TC((x,y))={(x,y),{x,y},{x}}TC(x)TC(y)\operatorname{TC}((x,y))=\{(x,y),\{x,y\},\{x\}\}\cup\operatorname{TC}(x)\cup% \operatorname{TC}(y) and so |TC((x,y))|<κ|\operatorname{TC}((x,y))|<\kappa. Finally TC(f)=f(x,y)fTC((x,y))\operatorname{TC}(f)=f\cup\bigcup_{{(x,y)\in f}}\operatorname{TC}((x,y)) is of size less than κ\kappa and so fHκ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αV_{\alpha} we have (xy)Vαxy{(x\in y)}^{{V_{\alpha}}}\Leftrightarrow x\in y and (x=y)Vαx=y{(x=y)}^{{V_{\alpha}}}\Leftrightarrow x=y. Hence we can take Cxy=Cx=y=OrdC_{{x\in y}}=C_{{x=y}}=\mathrm{Ord}. For all formulas φ,ψ\varphi,\psi then by definition (¬φ)Vα¬φVα{(\neg\varphi)}^{{V_{\alpha}}}\Leftrightarrow\neg\varphi^{{V_{\alpha}}} and (φψ)VαφVαψVα{(\varphi\wedge\psi)}^{{V_{\alpha}}}\Leftrightarrow\varphi^{{V_{\alpha}}}% \wedge\psi^{{V_{\alpha}}}. If αCφ\alpha\in C_{\varphi} then φVαφ\varphi^{{V_{\alpha}}}\Leftrightarrow\varphi and so ¬φVα¬φ\neg\varphi^{{V_{\alpha}}}\Leftrightarrow\neg\varphi and we can take C¬φ=CφC_{{\neg\varphi}}=C_{\varphi}. If moreover αCψ\alpha\in C_{\psi} then ψVαψ\psi^{{V_{\alpha}}}\Leftrightarrow\psi and so φVαψVαφψ\varphi^{{V_{\alpha}}}\wedge\psi^{{V_{\alpha}}}\Leftrightarrow\varphi\wedge\psi and we can take the closed unbounded set Cφψ=CφCψC_{{\varphi\wedge\psi}}=C_{\varphi}\cap C_{\psi}.

Finally, let Kφ={αOrd:x1,,xnVαx,φ(x,x1,,xn)xVα,φ(x,x1,,xn)}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 γOrd\gamma\in\mathrm{Ord} α0<<αξ<\alpha_{0}<...<\alpha_{\xi}<... is a γ\gamma sequence in KφK_{\varphi} then α=limξαξ\alpha=\lim_{\xi}\alpha_{\xi} is clearly in KφK_{\varphi}: if x1,,xnVαx_{1},...,x_{n}\in V_{\alpha} there is k<ωk<\omega such that x1,,xnVαkx_{1},...,x_{n}\in V_{{\alpha_{k}}} and so there is xVαkVαx\in V_{{\alpha_{k}}}\subseteq V_{\alpha} such that φ(x,x1,,xn)\varphi(x,x_{1},...,x_{n}). Let α0Ord\alpha_{0}\in\mathrm{Ord}. If αk\alpha_{k} is defined, then {x of minimal rank such that x1,xnVαk,φ(x,x1,,xn)}\{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αk+1V_{{\alpha_{{k+1}}}} for αk+1>αk\alpha_{{k+1}}>\alpha_{k} large enough. Then again α0<α=limkαkKφ\alpha_{0}<\alpha=\lim_{k}\alpha_{k}\in K_{\varphi}. Hence KφK_{\varphi} is closed unbounded.

Finally, if αCφKφ\alpha\in C_{\varphi}\cap K_{\varphi} then for all x1,,xnVα,x,φ(x,x1,,xn)xVα,φ(x,x1,,xn)xVα,φVα(x,x1,,xn)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 Cx,φ=CφKφC_{{\exists x,\varphi}}=C_{\varphi}\cap K_{\varphi}.

12.15

A modification of the proof of lemma 12.15 (we define C={xM,φM(u1,,un,x)}C=\{x\in M,\varphi^{M}(u_{1},...,u_{n},x)\}) gives that for any formula φ(u1,,un,x)\varphi(u_{1},...,u_{n},x), any transitive class MM and any set M0MM_{0}\subseteq M there exists a set M1M0M_{1}\subseteq M_{0} such that if xM,φM(u1,,un,x)\exists x\in M,\varphi^{M}(u_{1},...,u_{n},x) then (xM1)φM(u1,,un,x)(\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 φj\varphi_{j} then xM1φjM1(u1,,un,x)xM1φjM(u1,,un,x)\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 xM1φjM(u1,,un,x)xMφM(u1,,un,x)\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α)αOrd{(W_{\alpha})}_{{\alpha\in\mathrm{Ord}}} be a cumulative hierarchy and W=αOrdWαW=\bigcup_{{\alpha\in\mathrm{Ord}}}W_{\alpha}. Let φ\varphi be a formula and α0Ord\alpha_{0}\in\mathrm{Ord}. We use yet another variant of Theorem 12.14. We define C={xW,φW(u1,,un,x)}C=\{x\in W,\varphi^{W}(u_{1},...,u_{n},x)\} as in exercise 12.15. Then we define by induction αi+1>αi\alpha_{{i+1}}>\alpha_{i} such that Wαi+1W_{{\alpha_{{i+1}}}} contains the set of H(u1,,un);u1,unWαiH(u_{1},...,u_{n});u_{1},...u_{n}\in W_{{\alpha_{i}}}. Finally, the limit ordinal α=limiωαi>α0\alpha=\lim_{{i\rightarrow\omega}}\alpha_{i}>\alpha_{0} satisfies φW(x1,,xn)φWα(x1,,xn)\varphi^{W}(x_{1},...,x_{n})\iff\varphi^{{W_{\alpha}}}(x_{1},...,x_{n}) for all x1,,xnWαx_{1},...,x_{n}\in W_{\alpha}.

This page is W3C-compliant - Author: Frédéric WANG
Valid XHTML 1.1 Valid MathML 2.0 Valid SVG Valid CSS