我做的集合论习题（第二卷）

关于\(V_\omega\)的两个命题

页数：71页(书52页)

定理1.16

命题

在理论KP基础上,集合 \(V_{\omega}\) 恰好就是所有彻底有限集合之集合:

\(\mathrm{KP} \vdash \forall x \left( \begin{array}{l}x \in V_{\omega} \leftrightarrow \\ (\exists n \in \omega \exists f \left( \begin{array}{l}\mathbf{H}\mathbf{S}(f) \land \mathrm{dom}(f) = \mathcal{T}\mathcal{C}(x) \land n = \mathrm{rng}(f) \land \\ (\forall u \in \mathcal{T}\mathcal{C}(x) \forall v \in \mathcal{T}\mathcal{C}(x)(u \neq v \rightarrow f(u) \neq f(v))) \end{array} \right)) \end{array} \right).\)

证明

\(\rightarrow\):
因为\(\exists n\in\mathbb N(x\subseteq V_n)\)，而\(V_n\)是一个传递集合（即\(\mathbf{CDJ}(V_n)\)），所以\(\mathcal{TC}(x)\subseteq V_n\)。又考虑到\(V_n\)是有限的，所以\(\mathcal{TC}(x)\)也必须是有限的，从而\(x\)是彻底有限的。

如果要证明有限集合的子集也都是有限的，可以使用如下方法：
首先，递归假设对于任意自然数\(n\)，其子集都是有限的，对于自然数\(n+1\)，很明显地，其子集也必须是有限的，这样，对于所有自然数其子集都必须有限了。然后，对于任意一个集合\(A\)，如果它是有限的，也就是说存在\(A\)到某个自然数\(n\)的双射\(f\)。而对\(B\subset A\)，\(f\)将\(B\)映射到\(n\)的某个子集，而这个子集也存在某个双射\(g\)映射到自然数\(m\)，所以\(B\)就能双射地映射到\(m\)，从而是有限的。

\(\leftarrow\):
我们取\(x\)是所有彻底有限集合的集合（假设我们称之为集合\(A\)）中的任意一个集合。使用第二\(\in-\)归纳原理证明\(x\)一定属于某个\(V_n\)。首先，归纳基础自然是成立的。归纳假设为：\(\forall y\in x(\exists m\in\mathbb N,y\in V_m)\)，那么\(x\subset\bigcup V_m\)，如果我们记\(V_n=\mathfrak P(\bigcup V_m)\)（因为\(x\)是有限的，所以\(V_m\)们的并是一个\(V_?\)），那么\(x\in V_n\)。

定理1.15

这个定理本来在定理1.16前面，但是我觉得使用定理1.16的证明方法会更简单，所以我就把它放在了定理1.16后面来证明。

命题

在理论KP基础上,常元符号\(V_{\omega}\)可以依照\(\Sigma-\)定义引入:

\[y = \mathrm{V}_{\omega} \leftrightarrow \left( \begin{array}{l}\mathbf{C}\mathbf{D}\mathbf{J}(y) \wedge \varnothing \in y \wedge (\forall a \in y \exists b \in y (b = a \cup \{a\})) \wedge \\ (\forall x \in [y]^{< \omega} (x \in y)) \wedge (\forall x \in y \exists n \in \omega \exists f \mathbf{S}\mathbf{h}\mathbf{S}(f, x, n)) \wedge \\ (\forall x \in y \exists a \in y (x \subseteq a \wedge \mathbf{C}\mathbf{D}\mathbf{J}(a))) \end{array} \right).\]

证明

\(\rightarrow\)是显然的，\(\leftarrow\)证明如下：
任意取\(x\in y\)，根据条件，\(\exists a\in y(x\subset a\wedge\mathbf{CDJ}(a))\)，可是还有\(\mathcal{TC}(x)\subseteq a\)并且\(a\)是有限集合（条件），所以\(\mathcal{TC}(x)\)也得是有限集合。从而任意\(x\in y\)都是彻底有限集合，故而\(x\in V_\omega\)。

疑问

证明到此完成，可是还有一些问题需要回答，定理右边的条件我们证明并没有用完，比如\(\forall a \in y \exists b \in y (b = a \cup \{a\})\)对我们根本没有用（\(\forall x \in [y]^{< \omega} (x \in y)\)在从左到右的证明中用到了，最前面两个基础条件不说了）。可是仔细检查我们的证明过程也没什么问题，从左到右，的确只用了条件\(\forall x \in [y]^{< \omega} (x \in y)\)；从右到左，的确两个条件就能得到\(x\)是彻底有限的。那这个语句真的是多余的吗？我认为就是多余的，因为这个条件可以由后面三个条件推出，如下：
对于\(a\)，我们可以知道\(a\)是有限的，而且\(a\subset y\)（\(y\)传递），所以\(a\cup\{a\}\in \[y\]^{<\omega}\)，从而属于\(y\)。

例1.4(1)

页数：78页(书59页)

命题

\((\mathrm{KP}) (V_{\omega},\in)\vDash \mathrm{KP}^{- }\)

证明

关于\(\mathrm{KP}^-\)中的公理，请见此文。关于\(\vDash\)的定义则请详见书中对应页数

\(\in-\)极小原理 首先根据定义拆解第一个\(\to\)，假设前半句确实在我们的\((V_\omega,\in)\)中，那么我们需要第二条是成立的，它也在我们的结构当中。这意味着如下语句必须在结构中

\[\exists v_{n+1}(\phi(v_1,\cdots,v_n,v_{n+1})\land\forall v_{n+2}\in v_{n+1}(\neg\phi(v_1,\cdots,v_n,v_{n+2}))\]

从而要求

\[\exists\tau_{n+1}\in(A)^{<\omega}\left( \begin{array}l \varnothing\subset_{n+1}\tau_{n+1}\wedge\\ (((V_\omega,\in),\tau_{n+1})\vDash \forall v_{n+2}((v_{n+2}\in v_{n+1})\to \neg\phi(v_1,\cdots,v_n,v_{n+2}))) \end{array} \right)\]

我们现在考虑前提条件，确实存在有限序列\(\tau_{n+1}\)。然后我们还考虑到我们的\(V_\omega\)集合是在\(\mathrm{KP}\)中的集合，所以我们可以使用\(\mathrm{KP}\)中的定理，自然地，我们期望使用极小原理，不过这里最适合结合使用\(\Delta-\)分解原理。首先，我们注意到\(\vDash\)加上后面一大坨关于\(\phi\)的表达式都可以递归地写成\(\Delta-\)表达式（这其实就是书中的定理1.12），应用分解原理找到全部的\(v_{n+1}\)，然后再使用最小原理找到最小的\(v\)和对应的\(\tau\)。而\(v,\tau\)的存在就说明第二条是成立的，其命题是在我们的模型中的。

值得注意的是，我们此处的证明并没有证明分解原理在模型中是正确的。因为对于任意模型，这些命题在不在我们的理论中并不影响其是不是真的，我们要说明的是其属不属于我们的理论，而至于其真实性，则要由公理来做出保证。

其余公理证明类似，同样想办法根据集合\(V_\omega\)存在所依赖的\(\mathrm{KP}\)公理体系尝试证明即可，此处不再赘述

理解

整个的证明过程需要基于对\(\vDash\)的理解，整个定义式中每一个都是有用的：

\[((A,E),\tau)\vDash\phi\]

其中，\(A\)自不必说，代表模型本身；\(E\)提供了某种关系，或者说将\(\in\)映射到某种\(A\)中的关系（所以如果\(E\)还是\(\in\)关系值得单独拿出来定义为传递模型）；而\(\sigma\)相当于某种记录，其记录了当前已经出现的变量\(v_i\)们的“值”，这个“值”是\(A\)中映射到的一个集合。而对\(\vDash\)的递归定义中我们可以看到在\(\in,=\)两处定义的基石上，\(\{i,j\}\in dom(\sigma)\)是在检查变量有没有被记录（防止自由变元），\((\sigma(i),\sigma(j))\in E\)则是在观察模型中是不是有对应的关系\(\in\)

不可达基数

页数：104页(书85页)
其余关于不可达基数的习题，见第一卷

原命题

例1.9(ZF)设\(\kappa\)是一个不可数的正则基数。那么

(1) \(\mathcal H_\kappa\vDash\mathrm{ZF}_2\),其中\(\mathrm{ZF}_2\)是从\(\mathrm{ZF}\)中减掉幂集公理得到的集合理论

(2)下述命题等价:
(a) \(\kappa\)是一个不可达基数;
(b) \(\mathcal H_\kappa=V_\kappa\)
(c) \(\mathcal H_\kappa\vDash\mathrm{ZF}\)

\(\mathcal H_\kappa\)是全体彻底\(\kappa-\)有限集合的集合

(3)若选择公理在 \(V\) 中成立,则 \(\mathcal{H}_{\kappa} \vDash \mathrm{AC}\)

此处主要针对(2)展开证明，其余两条可参看书前面部分，很容易证明。

证明

(a)证(b)

首先，\(\forall\mathrm{Ord}\alpha\)我们都有\(\vert V_\alpha\vert<\kappa\)，所以\(V_\alpha\in\mathcal H_\kappa\)，再根据\(V_\kappa\)定义知道\(V_\kappa\subset\mathcal H_\kappa\)

根据第二归纳原理，对全部传递集合\(x\in\mathcal H_\kappa\)，施行归纳，因为\(\forall a\in x(a\in V_\alpha\wedge\alpha<\kappa)\)，取\(\gamma=\bigcup\limits_\alpha\alpha\)，那么显然\(\gamma<\kappa\wedge\forall a\in x(a\in V_\gamma)\)，从而\(x\in V_{\gamma+1}\)，最终\(x\in V_\kappa\)，这导致\(\mathcal H_\kappa\subset V_\kappa\)

(b)证(c)

在(1)的基础上验证幂集公理即可。

(c)证(a)

考虑幂集公理，任取序数\(\alpha\)都有\(\alpha\in\mathcal H_\kappa\)，那么通过幂集公理我们就有\(\mathfrak P(\alpha)\in\mathcal H_\kappa\)，而且因为整个\(\mathrm{ZF}\)都在\(\mathcal H_\kappa\)中是成立的，所以也就有\(\vert\mathfrak P(\alpha)\vert=2^\alpha<\kappa\)，根据强极限基数的定义，\(\kappa\)是强极限基数，从而是不可达基数。

定理1.30

页数：113页(94页)

原命题

定理1.30(ZFC)设 \(\kappa\) 是一个不可数的正则基数, 设 \(\langle U_{\alpha}\mid \alpha \leqslant \kappa \rangle\) 是一个满足下述要求的序列:

(1)如果 \(\alpha < \beta \leqslant \kappa\) , 那么 \(U_{\alpha}\subseteq U_{\beta}\)

(2)如果 \(\delta \leqslant \kappa\) 是一个极限序数, 那么 \(U_{\delta} = \bigcup_{\alpha < \delta}U_{\alpha}\)

(3)$$

U_{\kappa}

= \kappa\(,以及\)\forall \alpha < \kappa

U_{\alpha}

< \kappa$$。那么

\(\forall \alpha < \kappa \exists \beta (\alpha \in \beta \in \kappa \land \beta \in \mathrm{LimOrd}\land U_{\beta}\neq \varnothing \land \bigwedge\limits_{i<k}(U_{\beta}\prec U_{\kappa}))\)

证明

\(ZFC\)中全部表达式列成序列（因为表达式只有可列个），如下：\(\langle \varphi_0,\varphi_1,\cdots\rangle\)，对于每一个\(k\in\mathbb N\)，做截断\(\langle \varphi_0,\varphi_1,\cdots,\varphi_k\rangle\)，参考广义镜像原理的证明，不妨认为这个截断彰显全部子表达式（加进去就好了）且没有\(\forall\)（用\(\exists\)等价替换即可）

对于每一个形如\(\exists v_{n+1}\varphi_j(v_1,\dots,v_n,v_{n+1})\) 的表达式 \(\varphi_i(v_1,\dots,v_n)\)定义

\[F_i: U_\kappa^n\to \kappa\]

如果\(\neg\varphi_i{U_\kappa}^(x_1,\dots ,x_n)\),那么令\(F_i(x_1,\dots ,x_n)=0\);如果\(\varphi_i^{U_\kappa}(x_1,\dots,x_n)\),那么令

\[F_i(x_1,\dots,x_n)=\min\left\{\xi\in\kappa\mid\exists x_{n+1}\in U_i\varphi_j^{U_\kappa}(x_1,\dots,x_n,x_{n+1})\right\}\]

以及如下定义\(G_i:\kappa\to\kappa\):对于\(\gamma\in\kappa\)

\[G_i(\gamma)=\bigcup\left\{F_i(x_1,\dots,x_n)\mid(x_1,\dots,x_n)\in U_\gamma^n\right\}\]

当\(\varphi_i\)并非存在型表达式时,令\(G_i:\kappa\to \{0\}\)

最后,对\(\gamma\in\kappa\),令

\[E(\gamma)=\max\{\gamma+1,\max\{G_i(\gamma)\mid i< k\}\}\]

任意固定一个序数\(\alpha\)。欲得一个满足后述要求的极限序数\(\beta >\alpha :U_{\beta}\neq\varnothing\)。为此, 令

\[\beta_0 = \min \{\xi \mid \xi >\alpha \wedge U_{\xi}\neq \varnothing \} .\]

因为 \(U_\kappa\neq \varnothing\) 是这些 \(U_\gamma\) 的并, 这样的\(\xi\)一定存在。再令 \(\beta_{j + 1} = E(\beta_j)\)。这样,

\[\alpha < \beta_0< \beta_1< \dots .\]

令\(\beta = \bigcup \{\beta_j\mid j< \omega \}<\kappa\)。此\(\beta\)即可以保证\(\bigwedge\limits_{i<k}(U_{\beta}\prec U_{\kappa})\)。

根据上述证明记映射\(H(\alpha,k)=\beta<\kappa\)，然后令\(\mu_0=\bigcup\limits_{k\in\mathbb N}\{H(\alpha+1,k)\}<\kappa\)，\(\mu_{j+1}=\bigcup\limits_{k\in\mathbb N}\{H(\mu_j+1,k)\}<\kappa\)。

最后令\(\mu=\bigcup\{\mu_i\}<\kappa\)即为我们所求的“\(\beta\)”

疑问

证明中并没有使用到选择公理吧，难道对\(ZF\)也成立？