4. 基数

在定义了序数之后, 我们将定义基数为一类特殊的序数, 作为衡量集合的 “大小” 的度量.

4.1基数

定义 4.1.1 (等势). 集合 $X$ 和 $Y$ 称为有相同的基数或者等势的, 如果存在双射 $X\to Y$, 记作 $\text{\#}X=\text{\#}Y$.

称 $\text{\#}X\le \text{\#}Y$ 如果存在单射 $X\to Y$; $\text{\#}X<\text{\#}Y$ 如果 $\text{\#}X<\text{\#}Y$ 且 $\text{\#}X\ne \text{\#}Y$.

注 4.1.2. 使用选择公理可以说明 $\text{\#}X\le \text{\#}Y$ 当且仅当存在满射 $Y\to X$.

下面的定理说明等势的定义是不平凡的:

定理 4.1.3 (Cantor). $X$ 是集合, 那么 $\text{\#}X<\text{\#}P(X)$.

证明. 假设存在双射$$f:X\to P(X).$$定义$$S=\{x\in X:x\notin f(x)\}.$$考虑 $s=f^{-1}(S)$, 若 $s\in S$, 则由定义 $s\notin f(s)=S$. 但若 $s\notin S$, 则由定义 $s\in S$, 矛盾. 这说明 $\text{\#}X\ne \text{\#}P(X)$, 显然存在单射 $f:X\to P(X),x\mapsto \left\{x\right\}$, 故 $\text{\#}X<\text{\#}P(X)$.

$\square$

我们可以说明这在全体集合的等势类上定义了全序:

定理 4.1.4 (Cantor–Bernstein). 如果 $\text{\#}X\le \text{\#}Y$ 且 $\text{\#}Y\le \text{\#}X$, 那么 $\text{\#}X=\text{\#}Y$.

证明. 设 $f:A\to B,g:B\to A$ 是单射, 令 $B^{\prime }=g(B),A_1=g(f(A))$, 于是 $A_1\subset B^{\prime }\subset A$ 且 $\text{\#}A=\text{\#}{A}_1$. 于是可以不妨设 $A_1\subset B\subset A$ 且 $f:A\to A_1$ 是双射, 下面证明 $\text{\#}A=\text{\#}B$.
归纳定义$$\begin{array}{rlrl}& A_0=A,& & A_{n+1}=f(A_n)\\ & B_0=B,& & B_{n+1}=f(B_n).\end{array}$$按照如下方式定义函数 $g$: $$g(x)=\{\begin{array}{ll}f(x),& \text{如果存在 }n\text{使得 }x\in A_n\setminus B_n\\ x,& \text{否则}.\end{array}$$容易验证 $g$ 是 $A,B$ 间的双射, 于是 $\text{\#}A=\text{\#}B$.

$\square$

定义 4.1.5 (基数). 等势在 $Ord$ 上构成一个等价关系, 每个等价类中都存在最小元, 称这些序数为基数.
我们将在选择公理一节证明良序定理: 任何集合上都存在良序. 于是每个集合都与某个序数等势, 因此每个集合都有基数.
容易证明每个自然数都是基数, 我们将无穷基数称为 $\aleph$ 数. 自然数集 $\omega$ 是最小的 $\aleph$ 数, 记作 ${\aleph }_0$, 比 ${\aleph }_0$ 大的最小基数记作 ${\aleph }_1$.

在完成了基数的定义后, 我们可以定义一些基本运算:

定义 4.1.6. 设 $\kappa ,\lambda$ 分别是 $A,B$ 的基数, 那么
(1) $\kappa +\lambda =\text{\#}(A\bigsqcup B)$;
(2) $\kappa \cdot \lambda =\text{\#}(A\times B)$;
(3) ${\kappa }^{\lambda }=\text{\#}{A}^B$, 其中 $A^B=\left\{f:B\to A\right\}$.

自然的, 我们需要验证这些运算的定义不依赖于 $A,B$ 的选取, 比如需要证明$$\text{如果 }\text{\#}A=\text{\#}{A}^{\prime },\text{\#}B=\text{\#}{B}^{\prime },\text{那么 }\text{\#}(A\times B)=\text{\#}(A^{\prime }\times B^{\prime }).$$

引理 4.1.7. 如果 $\text{\#}A=\kappa$, 那么 $\text{\#}P(A)=2^{\kappa }$.

证明. 对任意的 $S\subset A$, 定义$${\chi }_S(x)=\{\begin{array}{l}1,x\in S;\\ 0,x\in X\setminus S.\end{array}$$那么 $S\mapsto {\chi }_S$ 是 $P(X)$ 到 $2^X={\left\{0,1\right\}}^X$ 的双射.

$\square$

于是定理 4.1.3 可以重新叙述为: 对任意的基数 $\kappa$, $\kappa <2^{\kappa }$.

关于基数的运算有如下简单的事实:

命题 4.1.8.
(1) 加法和乘法满足交换律、结合律;
(2) 乘法对加法, 幂运算对乘法分别具有分配律;
(3) $(\kappa \cdot \lambda {)}^{\mu }={\kappa }^{\mu }\cdot {\lambda }^{\mu }$;
(4) $({\kappa }^{\lambda }{)}^{\mu }={\kappa }^{\lambda \cdot \mu }$;
(5) $\kappa \le \lambda ⟹{\kappa }^{\mu }\le {\lambda }^{\mu }$;
(6) $0<\lambda \le \mu ⟹{\kappa }^{\lambda }\le {\kappa }^{\mu }$;
(7) ${\kappa }^0=1$; $1^{\kappa }=1$; 如果 $\kappa >0$, 那么 $0^{\kappa }=0$.

注 4.1.9. 基数的算数和序数的算数是完全不同的两种运算, 读者不妨停下来想一想, 以免混淆它们的性质.

引理 4.1.10.
(1) 对任意的序数 $\alpha$ 存在基数 $\kappa >\alpha$;
(2) 如果 $X$ 是基数的集合, 那么 $\sup X$ 是基数.
比 $\alpha$ 大的最小基数称为 $\alpha$ 的后继基数, 记作 ${\alpha }^{+}$.

证明. (1) 对任意的集合 $Y$, 定义$$h(Y)=\text{最小的序数 }\alpha \text{使得不存在}\alpha \text{到 }Y\text{的单射}.$$由于每个 $Y$ 的子集上的全体良序都构成集合, 于是使得存在到 $Y$ 的单射的序数 $\alpha$ 构成集合, 因此 $h(Y)$ 存在.
根据定义有 $\text{\#}\alpha <\text{\#}h(\alpha )$, 因此 (1) 成立.
(2) 设 $\alpha =\sup X$, 反设 $f:\alpha \to \beta <\alpha$ 是双射, 取 $\kappa \in X$ 使得 $\beta <\kappa <\alpha$, 那么 $\text{\#}\kappa =\text{\#}\left\{f(\xi ):\xi <\kappa \right\}\le \text{\#}\beta$, 这与 $\kappa$ 是基数矛盾.

$\square$

使用引理 4.1.10 , 我们可以用序数来枚举全体基数, 我们通常用 ${\aleph }_{\alpha }$ 来表示基数, 并用 ${\omega }_{\alpha }$ 表示它的序型: $$\begin{array}{rl}& {\aleph }_0={\omega }_0=\omega ;\\ & {\aleph }_{{\alpha }^{\ast }}={\omega }_{{\alpha }^{\ast }}={\aleph }_{\alpha }^{+};\\ & {\aleph }_{\alpha }={\omega }_{\alpha }=\sup \left\{{\omega }_{\beta }:\beta <\alpha \right\},\text{对于极限序数 }\alpha .\end{array}$$

基数等于 ${\aleph }_0$ 的集合称为可数集, 可以表示为 ${\aleph }_{{\alpha }^{\ast }}$ 的基数称为后继基数, 否则称为极限基数.

基数之间的加法和乘法几乎是平凡的, 由如下定理:

定理 4.1.11. ${\aleph }_{\alpha }\cdot {\aleph }_{\alpha }={\aleph }_{\alpha }$.

为了证明这个定理, 我们需要在序数的二元组上定义良序:

4.2$Ord\times Ord$ 上的典范良序

我们将在类 $Ord\times Ord$ 上定义良序, 并使得每个 $\alpha \times \alpha$ (作为序数的序对的集合) 都是 $Or{d}^2$ 的一个前段, 诱导的 ${\alpha }^2$ 上的良序称为它的典范良序. 进一步, 我们将说明这个良序给出了 $Or{d}^2\to Ord$ 的同构, 并且说明对许多的 $\alpha$, ${\alpha }^2$ 的序型是 $\alpha$, 特别的, 这对全体 $\aleph$ 数成立.

如下定义 $Ord\times Ord$ 上的全序: $$\begin{array}{rl}(\alpha ,\beta )<(\gamma ,\delta )⟺& \max \left\{\alpha ,\beta \right\}<\max \left\{\gamma ,\delta \right\},\\ & \text{或 }\max \left\{\alpha ,\beta \right\}=\max \left\{\gamma ,\delta \right\},\alpha <\gamma ,\\ & \text{或 }\max \left\{\alpha ,\beta \right\}=\max \left\{\gamma ,\delta \right\},\alpha =\gamma ,\beta <\delta .\end{array}$$容易看出在这个序下每个非空子集都有最小元, 因此这是一个良序. 并且 $\alpha \times \alpha$ 是由 $(0,\alpha )$ 给出的前段.
定义$$\Gamma (\alpha ,\beta )=\left\{(\xi ,\eta ):(\xi ,\eta )<(\alpha ,\beta )\right\}\text{的序型}.$$于是 $\Gamma :Or{d}^2\to Ord$ 是保序单射.
注意到 $\Gamma (\omega \times \omega )=\Gamma (0,\omega )=\omega$ (这里的记号是将 $\Gamma$ 作用在 $\omega \times \omega$ 的每一个元素上); 并且 $\gamma (\alpha )=\Gamma (\alpha \times \alpha )$ 是单调函数, 于是对任意 $\alpha ,\gamma (\alpha )\ge \alpha$. 再根据定义可以说明, 对任意的 $\alpha$ 都存在 $(\beta ,\delta )<(0,\alpha )$ 使得 $\Gamma (\beta ,\delta )=\alpha$.

定理 4.1.11 的证明. 考虑如上定义的典范良序 $\Gamma$, 我们证明对任意的序数 $\alpha$ 都有 $\Gamma ({\omega }_{\alpha }\times {\omega }_{\alpha })={\omega }_{\alpha }$. 这对 $\alpha =0$ 显然是对的, 设 $\alpha$ 是最小的使得命题不成立的序数, 设 $\beta ,\gamma <{\omega }_{\alpha }$ 使得 $\Gamma (\beta ,\gamma )={\omega }_{\alpha }$. 取 $\beta ,\gamma <\delta <{\omega }_{\alpha }$, 因为 $\delta \times \delta$ 是包含 $(\beta ,\gamma )$ 的一个前段, 于是 $\Gamma (\delta \times \delta )\supset {\omega }_{\alpha }$, 因此 $\text{\#}(\delta \times \delta )\ge \text{\#}{\aleph }_{\alpha }$. 令一方面, 由 $\alpha$ 的最小性, $\text{\#}(\delta \times \delta )=\text{\#}\delta \cdot \text{\#}\delta =\text{\#}\delta <{\aleph }_{\alpha }$, 矛盾.

$\square$

作为定理的推论, 我们有: $${\aleph }_{\alpha }+{\aleph }_{\beta }={\aleph }_{\alpha }\cdot {\aleph }_{\beta }=\max \left\{{\aleph }_{\alpha },{\aleph }_{\beta }\right\}.$$基数的幂运算将在第六节中介绍, 选择公理在其中是必要的.

4.3共尾性

定义 4.3.1. 设 $\alpha ,\beta$ 是极限序数, 称一个递增 $\beta$-序列 $⟨{\alpha }_{\xi }:\xi <\beta ⟩$ 共尾于 $\alpha$, 如果 ${\lim }_{\xi \to \beta }{\alpha }_{\xi }=\alpha$. 类似的, 称 $A\subset \alpha$ 共尾于 $\alpha$, 如果 $\sup A=\alpha$. 如果 $\alpha$ 是无穷序数, 它的共尾性定义为$$\text{cf}\alpha =\text{最小的极限序数 }\beta \text{使得存在 }\beta \text{-序列共尾于 }\alpha .$$

显然 $\text{cf}\alpha <\alpha$, 容易验证 $\text{cf}(\omega +\omega )=\text{cf}{\aleph }_{\omega }=\omega$.

引理 4.3.2. $\text{cf}(\text{cf}\alpha )=\text{cf}\alpha$

证明. 注意到, 若 $⟨{\alpha }_{\xi }:\xi <\beta ⟩$ 共尾于 $\alpha$, 且 $⟨{\xi }_{\nu }:\nu <\eta ⟩$ 共尾于 $\beta$, 那么 $⟨{\alpha }_{{\xi }_{\nu }}:\nu <\eta ⟩$ 共尾于 $\alpha$.

$\square$

共尾性的两个有用的性质:

引理 4.3.3. 设 $\alpha >0$ 是极限序数,
(1) 如果 $A\subset \alpha$ 共尾于 $\alpha$, 那么 $A$ 的序型至少是 $\text{cf}\alpha$.
(2) 如果递增 $\beta$-序列共尾于 $\alpha$, 那么 $\text{cf}\beta =\text{cf}\alpha$.

证明. a.

$\square$

称无穷基数 ${\aleph }_{\alpha }$ 是正则基数, 如果 $\text{cf}{\aleph }_{\alpha }={\aleph }_{\alpha }$.

引理 4.3.4. 对每个极限序数 $\alpha$, $\text{cf}\alpha$ 是正则基数.

设 $\kappa$ 是极限序数, 子集 $X\subset \kappa$ 称为有界的, 如果 $\sup X<\kappa$, 反之称 $X$ 是无界的.

引理 4.3.5. 设 $\kappa$ 是极限序数: (1) 如果 $X\subset \kappa$ 且 $\text{\#}X<\text{cf}\kappa$, 那么 $X$ 有界. (2) 如果 $f:\lambda \to \kappa$ 是函数且 $\lambda <\text{cf}\kappa$, 那么 $\text{ran}f$ 有界.

存在任意大的非正则基数, 如对每个 $\alpha$, ${\aleph }_{\alpha +\omega }$ 的共尾性都是 $\omega$. 我们将在第六节中使用选择公理证明每个后继基数都是正则的.

引理 4.3.6. 无穷基数 $\kappa$ 不是正则的, 当且仅当存在基数 $\lambda <\kappa$ 以及一族 $\kappa$ 的子集 $\left\{S_{\xi }:\xi <\lambda \right\}$ 使得 $\forall \xi <\lambda ,\text{\#}{S}_{\xi }<\kappa$ 且 ${\bigcup }_{\xi <\lambda }{S}_{\xi }=\kappa$. 满足这个条件的最小的 $\lambda$ 就是 $\text{cf}\kappa$

证明. a.

$\square$

如果不使用选择公理, 我们无法证明 ${\omega }_1$ 不是可数集的可数并, 读者可以对比习题??.

迄今为止我们唯一证明的基数不等式就是 $\kappa <2^{\kappa }$, 特别的当 $\kappa \ne 1$ 时我们有 $\kappa <{\kappa }^{\kappa }$. 下一个命题是它更精细的版本, 更多的不等关系将作为 König 定理?? 的推论给出.

定理 4.3.7. $\kappa$ 是无穷基数, 那么 $\kappa <{\kappa }^{\text{cf}\kappa }$

证明. a.

$\square$

4.4习题