6. 选择公理

6.1选择公理

选择函数与构造性

定理 6.1.1 (选择公理,AC). 对于一个由非空集合构成的集族 $S$, 一个选择函数 $f$ 指的是满足 $f(X)\in X,\forall X\in S$ 的函数 $f$. 那么对于任何一个由非空集合组成的集族, 都存在这样的选择函数.

选择公理与其他 ZF 中的公理是有所不同的, 原因在于其他 ZF 中的公理都是构造性地说明集合存在性, 而选择公理则是非构造性地保证选择函数存在 (回忆: 选择函数本身是个集合).

选择公理的非构造性让人们本能地不喜欢, 于是一些数学家希望能够不用选择公理来做事. 经过亿点点研究, 数学家们发现 AC 与 ZF 是彼此独立的, 有许多数学命题必须要 AC 才能够证明.

在一些简单的情况下, 选择函数的存在性是可以直接通过构造来证明的.

例 6.1.2.

1.	每一个集合 $X\in S$ 都是单元素集.
2.	$S$ 是有限的, 根据数学归纳法可以归纳构造选择函数的存在性.
3.	每个 $X\in S$ 是 $\mathbb{R}$ 的有限子集, 可以选择 $\min$ 作为选择函数.

但是大部分 $S$ 是无限集的情况下, 选择函数都不能够被构造出来, 即使简单到 $S$ 的每一个元素都是二元集, 我们也不能构造出选择函数的存在性.

注 6.1.3. 有趣的是,(通俗地说), 对于无穷双袜子, 我们没有办法给出一个选择函数, 但是对于无穷双鞋子, 我们可以给出一个选择函数, 即选出左脚的鞋子.

Zermelo 良序定理

定理 6.1.4 (Zermelo 良序定理). 任何一个集合都可以良序化.

这个定理是非常强大的, 利用这个定理就可以说明任何一个集合都和一个序数等势, 也说明任何两个集合之间的势存在大小关系, 且我们可以知道所有基数构成良序.

证明. 定理的证明思路是: 既然要证明良序化, 那么就只需要证明和某个序数一一对应, 那我们就利用选择公理 " 一个一个 " 地选.

我们构造以序数作为下标的序列$$a_{\alpha }=f(A-a_{\xi }:\xi <\alpha )$$很显然, 在 $A-a_{\xi }:\xi <\alpha$ 非空的时候可以构造. 令 $\theta$ 是最小的满足 $A=\left\{a_{\xi }:\xi <\theta \right\}$ 的序数, 那么就给出了一个 $A$ 与比 $\theta$ 小的序数的一一对应. (为什么存在这样的序数 $\theta$ ? $♠$)

$\square$

事实上, 良序定理和选择公理是等价的: 在我们假定每个集合都可良序化的情况下, 对于集族 $S$, 我们可以对于 $\bigcup S$ 给出一个良序, 对于 $X$, 只要指定 $f(X)=\min X$ 即可.

有了良序定理, 那么实数集也可以良序化, 于是就知道 $2^{{\aleph }_0}$ 也是一个无穷基数, 并且 $2^{{\aleph }_0}\ge {\aleph }_1$.

对于实数集的良序化是有许多用处的, 我们可以用它来构造不少反例, 比如 Vitali 的不可测集的构造, 和一个没有完美子集 (5.4) 的不可数集的构造.(6.9.1)

处理基数问题

选择公理处理基数问题有许多方便, 我们有许多常用的处理基数的结论其实都是选择公理的推论.

定理 6.1.5. 若存在 $f:A\to B$ 是满射, 那么 $\text{\#}B\le \text{\#}A$.

定理 6.1.6. 可数个可数集的并还是可数集.

前者的证明中其实用到的是从每个 $f^{-1}(b)$ 中选取一个元素, 而后者则是要对于每一个 $A_n$, 选择一种与 $\mathbb{N}$ 的同构, 从而才能有对角线排列.

我们还可以处理更加一般的情况:

引理 6.1.7. $\text{\#}(\bigcup S)\le \text{\#}S\cdot \sup \left\{\text{\#}X:X\in S\right\}$

这是有限的显然结论到无限的一个推广, 证明与上类似是利用选择公理对于每个集合选择一种与它等势的序数的同构.

证明. 令 $\kappa =\text{\#}S,\lambda =\sup \left\{\text{\#}X:X\in S\right\}$, 自然有 $S=\left\{X_{\alpha }:\alpha <\kappa \right\}$. 对于每个 $\alpha <\kappa$, 我们选取一个编号方式 $X_{\alpha }=\left\{a_{\alpha ,\beta }:\beta <{\lambda }_{\alpha }\right\}$ 于是我们有了一个满射 $(\alpha ,\beta )\mapsto a_{\alpha ,\beta }$ 从 $\kappa \times \lambda$ 到 $\bigcup S$.

$\square$

特别地来说, 一个由 ${\aleph }_{\alpha }$ 个势为 ${\aleph }_{\alpha }$ 的集合组成的集族, 所有元素的并, 依旧具有势 ${\aleph }_{\alpha }$.

推论 6.1.8. 每一个 ${\aleph }_{\alpha +1}$ 都是正则基数.

证明. 否则 ${\omega }_{\alpha +1}$ 会是至多 ${\aleph }_{\alpha }$ 个势不超过 ${\aleph }_{\alpha }$ 的集合的并.

$\square$

6.2在数学中应用 AC

以上都是在纯粹的集合论之中的讨论, 下面的内容我们将目光放到数学中来.

Zorn 引理

在代数与点集拓扑里面, 我们经常采用另一与 AC 等价的命题: Zorn 引理. 先给出 (回顾) 一些概念:

定义 6.2.1. 对于一个偏序集 $(P,<)$,

•	对 $a\in P$, 如果不存在 $x\in P,a<x$, 就称它是极大元.
•	对于 $P$ 的非空子集 $X$, 如果 $c\in P$ 满足 $\forall x\in X,x\le c$, 就称它是 $X$ 的上界.
•	一个子集 $C\subset P$ 如果是全序的, 就称它是一条链.

定理 6.2.2 (Zorn 引理). 如果 (P,<) 是一个非空的偏序集, 并且满足每条链都有上界, 那么它就有极大元.

证明. 我们尝试归纳构造出一个链包含极大元. 即取 $a_{\alpha }$ 为比此前的所有序数的项都大的元素, 如果存在那么就取出.

如果不存在, 注意到编号为极限序数的链的上界一定不在链中, 一定存在这一元素, 因而 $\alpha$ 是一个后继序数, 于是存在 $\theta$ 是 $\alpha$ 的前序, 就不存在任何一个元素比 $a_{\theta }$ 大了.

$\square$

Zorn 定理在 ZF 下也和 AC 是等价的, 等价性见 6.9.2.Zorn 引理在数学中也有大量的应用, 比如:

•	任何向量空间有一组基;
•	任何域存在唯一代数闭包;
•	Hahn–Banach 扩张定理;
•	任意环存在极大理想;
•	Tikhonov 定理 (关于紧空间的乘积; 由于名称转写, 常被称为 Tychonoff 定理).

6.3弱选择公理

一如之前所说, 选择公理的非构造性让人很不喜欢, 而且就像良序定理这样看上去就很反直觉的东西居然是 AC 的推论, 很多人就不愿意承认这一点. 但是我们也知道, ZF 的强度不太够, 所有有些人就退而求其次, 希望在 ZF + 可数选择公理下做证明.

定理 6.3.1 (可数选择公理). 含可数个非空集的集族有选择函数.

在可数选择公理之下, 我们依旧可以证明可数个可数集合的并是可数的. 马上就可以推出 ${\aleph }_1$ 是一个正则基数. 然而, 可数选择公理可不能保证所有的实数可以良序化. 一些关于 Borel 集和 Lebesgue 测度的基本理论都可以仅用可数选择公理, 比如要证明可数个 $F_{\sigma }$ 集的并是 $F_{\sigma }$ 的.

在现代描述集合论中, 人们大多用可数选择公理而非选择公理. 有时也用如下的加强版命题:

定理 6.3.2 (相依选择公理,DC). 对于一个有一个关系 $E$ 的非空集合 $A$, 如果对于每一个元素 $a$, 都存在 $b\in A$ 满足 $bEa$, 那么就存在序列 $a_0,a_1,\dots ,a_n,\dots$ , 满足$$a_{n+1}E{a}_n,\forall n\in \mathbb{N}$$

相依选择公理是比可数选择公理要强的, 证明见习题 6.9.3.

DC 的一个应用是可以给出扎实关系 (2.5.1) 和良序的等价条件:

引理 6.3.3.

1.	集合 $P$ 的一个全序是良序当且仅当没有无穷递降序列.
2.	一个 $P$ 上的关系 $E$ 是扎实关系当且仅当没有无穷序列 $⟨a_n:n\in \mathbb{N}⟩$ , 满足$$a_{n+1}E{a}_n,\forall n\in \mathbb{N}$$

证明. 前者是后者的直接推论, 所以只需要证明后者.

" $\Rightarrow$ " 方向, 利用反证法就是扎实关系的定义.

" $\leftarrow$ " 方向, 如果 $E$ 不扎实, 那么就存在一个 $A\subset P$, 没有 $E$ -极小元, 于是满足 DC 的条件, 就可以找到这样的序列了.

$\square$

6.4基数算术

选择公理告诉我们每一个无穷基数都是某个 ${\aleph }_{\alpha }$ , 我们就可以放心大胆地进行基数算术, 算出来肯定还是某个 ${\aleph }_{\alpha }$ . 基数的加法和乘法都是比较容易的:$$\kappa +\lambda =\kappa \cdot \lambda =\max \left\{\kappa ,\lambda \right\}.$$接下来考虑乘方运算:

引理 6.4.1. 如果 $2\le \kappa \le \lambda$, $\lambda$ 是无穷基数, 那么 ${\kappa }^{\lambda }=2^{\lambda }$.

证明. $$2^{\lambda }\le {\kappa }^{\lambda }\le (2^{\kappa }{)}^{\lambda }=2^{\kappa \cdot \lambda }=2^{\lambda }$$

$\square$

另一种情况是如果二者都是无穷基数但是 $\lambda <\kappa$, 那么这个运算就变得麻烦许多了.

如果 $2^{\lambda }\ge \kappa$, 那么根据 ${\kappa }^{\lambda }\le (2^{\lambda }{)}^{\lambda }=2^{\lambda }$, 我们还是可以有 ${\kappa }^{\lambda }=2^{\lambda }$. 但如果 $2^{\lambda }<\kappa$, 就只能得到$$\kappa \le {\kappa }^{\lambda }\le 2^{\kappa }$$不过我们根据 4.3.7($\kappa <{\kappa }^{\text{cf}\kappa }$), 我们可以得到$$\kappa <{\kappa }^{\lambda }当\lambda \ge \text{cf}\kappa 时成立$$如果 $\lambda$ 是一个基数, 并且 $\text{\#}A\ge \lambda$,$${\left[A\right]}^{\lambda }=\left\{X\subset A\mid \text{\#}X=\lambda \right\}$$

引理 6.4.2 (基数为 $\lambda$ 的子集的个数). 如果 $\text{\#}A=\kappa \ge \lambda$, 那么集合 ${\left[A\right]}^{\lambda }$ 的基数为 ${\kappa }^{\lambda }$.

证明. 一个方面, 每一个 $f:\lambda \to A$ 都是一个 $\lambda \times A$ 的势为 $\lambda$ 的子集, 所以 ${\kappa }^{\lambda }\le \text{\#}{\left[\lambda \times A\right]}^{\lambda }=\text{\#}{\left[A\right]}^{\lambda }$ 另一方面, 我们可以构造一个单射 $F:[A{]}^{\lambda }\to A^{\lambda }$ 如下: 对于势为 $\lambda$ 的子集 $X$, 取 $F(X)$ 是某个 $\lambda$ 上值域为 $X$ 的函数即可.

$\square$

若 $\lambda$ 是一个极限基数, 令 ${\kappa }^{<\lambda }=\sup \left\{{\kappa }^{\mu }\mid \mu 是小于\lambda 的基数\right\}$.

6.5无穷和与无穷乘积

$♠$

6.6连续统方程

我们已经说明了 $2^{{\aleph }_{\alpha }}>{\aleph }_{\alpha }$ , 因此有 $2^{{\aleph }_{\alpha }}\ge {\aleph }_{\alpha +1}$. 广义连续统假设 (GCH) 说的是这个等号取等, 即:$$2^{{\aleph }_{\alpha }}={\aleph }_{\alpha +1}$$在 GCH 之下, 基数的幂次运算可以记为:

定理 6.6.1.

1.	如果 $\kappa \le \lambda$, 那么 ${\kappa }^{\lambda }={\lambda }^{+}$.
2.	如果 $\mathrm{cf}\kappa \le \lambda <\kappa$, 那么 ${\kappa }^{\lambda }={\kappa }^{+}$.
3.	如果 $\lambda <\mathrm{cf}\kappa$, 那么 ${\kappa }^{\lambda }=\kappa$.

证明.

1.	6.4.1
2.	$♠$
3.	$♠$

$\square$

$♠$

6.7基数的指数运算

$♠$

6.8奇异基数假设

$♠$

6.9习题

6.9.1. 存在 $\mathbb{R}$ 的子集, 具有基数 $2^{{\aleph }_0}$, 并且没有完美子集.

证明. 根据已经证过的 5.4.1, 可以令 $⟨P_{\alpha }:\alpha <2^{{\aleph }_0}⟩$ 是所有完美集的一个编号, 我们对于它们进行分划为 $A=\left\{a_{\alpha }:\alpha <2^{{\aleph }_0}\right\}$,$B=\left\{b_{\alpha }:\alpha <2^{{\aleph }_0}\right\}$. 分划方式为: 选出 $a_{\alpha }\notin \left\{a_{\xi }:\xi <\alpha \right\}\cup \left\{b_{\xi }:\xi <\alpha \right\}$, 再选出 $b_{\alpha }\in P_{\alpha }=\left\{a_{\xi }:\xi \le \alpha \right\}$. 那么容易验证 $A$ 就满足我们的构造.

我们对于这个证明作出一些解释: 证明思路在于我们在构造时, 要每个完美集里面取一个元素丢一个元素, 前者用来保证集合的大小, 后者则保证和所有完美集都不交.

因为每个完美集的势都是 $2^{{\aleph }_0}$, 在每一步都是从非空集合中选, 而选择的合理性正是来自于良序原理可以取出实数编号下的最小元这一点, 这就是良序定理在其中的作用.

$\square$

6.9.2. Zorn 引理可以推出 AC.

证明. 这个证明也是 Zorn 引理的经典用法, 考虑所有可行的集合及其上的偏序关系 (结构相同的包含关系), 验证 Zorn 引理条件即可.

假设 $S$ 是一族非空集, 考虑$$P=\left\{(f,Z):Z\subset S,f\mathrm{是}Z\mathrm{上}\mathrm{的}\mathrm{选}\mathrm{择}\mathrm{函}\mathrm{数}\right\}$$$P$ 上自然有序关系:$(f,X)\prec (g,Y)$ 当 $X\subset Y$ 且 $f$ 和 $g$ 在 $X$ 上的限制一样.

显然这个集合非空. 这个偏序集的任何一个链都有上界: 考虑把链里面的集合并起来就得到上界.Zorn 引理条件验证完毕.

$\square$

6.9.3. 可以用相依选择公理推出可数选择公理.

证明. 对于 $S=\left\{A_n:n\in \mathbb{N}\right\}$, 我们考虑所有的在 $S_n=\left\{A_i:i\le n\right\}$ 上的选择函数, 并且考虑定义域包含所生成的二元关系, 在这一二元关系下, 根据相依选择公理就可以得到定义域不断变大的选择函数无穷序列, 将这个序列取并即可.

$\square$

6.9.4. $X$ 是无限集, $S$ 是 $X$ 的所有有限子集构成的集合, 求证 $\text{\#}S=\text{\#}X$.

证明. 假设 $\text{\#}X={\aleph }_{\alpha }$, 那么 $n$ 元的子集个数总共就不超过 ${\aleph }_{\alpha }^n={\aleph }_{\alpha }$ 个. 总共的有限子集个数也就 ${\aleph }_0\times {\aleph }_{\alpha }={\aleph }_{\alpha }$ 个.

$\square$

6.9.5. 令 $(P,<)$ 是一个全序集, $\kappa$ 是一个基数. 如果每个前段 (2.1.10) 的基数都 $<\kappa$ , 那么 $\text{\#}P\le \kappa$.

证明. $♠$

$\square$

6.9.6. 可数选择公理能够推出任何无限集有可数子集.

证明. 假设 $A$ 是无限集, 令 $A_n$ 是所有长度为 $n$ 的双射序列 (元素不重复的序列) 所构成的集合, 我们对于 $S=\left\{A_n:n\in \mathbb{N}\right\}$ 使用可数选择公理, 得到一列序列 ${⟨{⟨b_{i,j}⟩}_{j\ge 1}⟩}_{i\ge 1}$ . 然后我们可以构造新序列 ${⟨a_i⟩}_{i\ge 1}$ , 令 $a_i$ 为序列 $b_i$ 中在 $\left\{a_k:1\le k\le i\right\}$ 中没有出现过的第一项, 即可得到一个双射序列.

$\square$