ZF 集合论 I —— 外延公理、分离公理模式、替换公理

本章主要讨论 ZF 公理下的集合论，提到的 ZFC 实际上就是 ZF+C ，其中 C 为选择公理.

符号约定

为尊重 Kunen 教材的符号，我们这里写明符号约定.

符号	含义
$0$	空集（也就是说在这个部分我们不采用 $\varnothing$）
$\cong$	同构
$\models$	后承符号
$\vdash$	推演

Intro

非正式集合论

在其他的数学分支当中，我们并不需要特别深入的集合论知识，即使是在代数当中，我们常用的概念一般也就是：

集合的基本运算（子交并补）
映射与函数（像、单射、双射）
关系（序关系、等价关系）

在这些分支当中，我们学习的集合论被称为非正式集合论 (Informal Set Theory, IST)

接下来我们的首要目标，就是建立一个一阶公理化集合论 (Axiomatic Set Theory, AST) .

集合论的发展

ZF 的核心思想

罗素悖论的出现，主要还是 Cantor 提出的概括原则过于大了，把一些本不应该为集合的东西概括了进来，所以后续的公理化集合论思想主要还是限制集合的全域.

但是太大这个说法没有明确的界限，所以也就出现了不同的公理化，ZFC 只是其中的一个常用的公理.

为什么需要形式逻辑 (Why formal logic?)

(选自 Kunen)
我们之后的学习需要使用我们先前学习的数理逻辑，也就是说我们在研究公理集合论时，需要形式逻辑语言而非自然语言.

为什么我们需要它？Kunen 给出了两个原因：

第一，对于 Cantor 的概括原则：

\[ \left\lbrace x\in A : P(x) \right\rbrace \]

我们说 $P$ 是“性质”，但是“性质”依旧是一个模糊的语言，例如说“ $x$ 是开心的”是不是一个性质？这个又好像超出了我们理解的范围. 这个时候，我们如果使用形式逻辑，就可以精确化“性质”为可以用逻辑语言表达的性质.

第二，即使我们定义了 ZFC ，如何说明：从 ZFC 出发无法证明 CH （连续统假设）？

当然，这并不意味着我们接下来每个地方都使用逻辑语言，因为“存在 $x,y,z$ 使得 $x\in y\land y\in z$ ”的可读性起码比

\[ \exists x(\exists y (\exists z(x\in y \land y\in z))) \]

要更好.

ZF 公理

(以下定义取 Kunen 定义)
我们接下来逐一介绍 ZF 公理的 0~9 ，但是每介绍一个公理，我们就会引入一些新的内容，从而能理解这些公理为我们带来了什么.

存在性、外延公理、分离公理模式

下面的公理属于 ZF 公理系统：

公理 0 ： 集合的存在性

\[ \exists x (x=x) \]

这个公理保证了我们讨论的全域是非空的.

公理 1 ： 外延公理

\[ \forall x\forall y (\forall z(z\in x \leftrightarrow z\in y)\to x=y). \]

这个公理说明，集合是由它包含的元素确定的，包含元素完全相同的集合是相等的.

公理 3 ： 分离公理模式（概括公理）
令 $\varphi(u)$ 为公式，对任意集合 $x$ ，存在一个集合： $y = \left\lbrace u\in x| \varphi(u) \right\rbrace$ ：

\[ \forall x\exists y \forall u (u\in y \leftrightarrow u\in x\land \varphi(u)) \]

对于每一个公式 $\varphi$ ，都存在一个相应的分离公理. 因此分离公理我们称之为模式——它指代一个无穷的公理集合.

为了规避罗素悖论，$\varphi$ 的自由变量不能有 $Y$ .

在现有的三条公理下，我们已经可以定义空集 $\varnothing$ .

定义：空集

空集 $\varnothing$ 是满足如下性质的集合 $y$ ：
$$ \forall x(x\not\in y). $$

例题

证明：空集 $\varnothing$ 是唯一的.

根据外延公理可以证明. $\square$

定理：不存在包含所有集合的集合

\[ \neg \exists z \forall x (x\in z) \]

利用分离公理模式，如果存在这样的集合 $z$ ，那么以下的集合是存在的：

\[ \left\lbrace x\in z : x\notin x \right\rbrace = \left\lbrace x: x\notin x \right\rbrace \]

考虑设这个集合为 $a$ ，在考虑 $a\in a$ 和 $a\notin a$ 的时候就会出现 Russell 悖论. $\square$

定义：类

令 $\varphi(u)$ 为一个性质，根据自由变量的一个限制，$\left\lbrace u\mid\varphi(u) \right\rbrace$ 并不一定是一个集合，这样的对象称之为类 (class). 特别的，不是集合的类称为真类.

无序对、并集、替换公理

公理 4 ： 无序对公理

\[ \forall x\forall y \exists z(x\in z\land y\in z). \]

即：存在集合同时包含 $x,y$ .

公理 5 ： 并集公理

\[ \forall \mathscr{F} \exists A \forall Y \forall x (x\in Y\land Y \in \mathscr{F}\to x\in A). \]

这个语句中的 $\mathscr{F}$ 刻画了一个集合族，其中的 $Y$ 就是每个做并运算的集合. 那么这个语句实际上就刻画了一个集合 $A$ ，它就是 $\mathscr{F}$ 中所有集合的并.

用数学表达式有：

\[ \bigcup \mathscr{F} = \left\lbrace x : \exists Y \in \mathscr{F} (x\in Y) \right\rbrace ; \]

公理 6 ： 替换公理模式
对于每个不以 $Y$ 为自由变量的公式 $\varphi$ ，以下为替换公理：

\[ \forall x\in A \exists !y \varphi(x,y) \to \exists Y \forall x\in A \exists y \in Y \varphi(x,y). \]

其中的公式 $\varphi(x,y)$ 确定了一个类 $F$ ，替换公理实际上就反映了这个事情：若 $F$ 是 $A$ 上的函数，$A$ 是集合，那么 $A$ 在 $F$ 下的象 $F(A)$ 也是集合.

有序对和 Cartesian 积

定义：有序对

\[ \left\langle x,y \right\rangle = \left\lbrace \left\lbrace x \right\rbrace \left\lbrace x,y \right\rbrace \right\rbrace \]

例题

写出公式表达 $z=\left\langle x,y \right\rangle$ ，只使用 $\in$ 和 $=$ .

$z= \left\langle x,y \right\rangle$ 等价于 $z = \left\lbrace u,v \right\rbrace$ ，其中 $u=\left\lbrace x \right\rbrace, v = \left\lbrace x,y \right\rbrace$ .

首先先写出 $z=\left\lbrace u,v \right\rbrace$ ：

\[ \varphi_1 = \forall t (t\in z\leftrightarrow (t=u)\lor (t=v)) \]

也就是属于 $z$ 的元素仅有可能是 $u,v$ .

然后写清楚 $u=\left\lbrace x \right\rbrace$ ：

\[ \varphi_2 = \forall t (t\in u \leftrightarrow t=x) \]

最后表达 $v=\left\lbrace x,y \right\rbrace$ ：

\[ \varphi_3 = \forall t (t\in v\leftrightarrow (t=x)\lor (t=y)) \]

最终的语句就是：

\[ \exists u\exists y (\varphi_1\land \varphi_2 \land \varphi_3) \]

$\square$

定义：Cartesian 积

\[ A\times B = \left\lbrace \left\langle x,y \right\rangle : x\in A \land x\in B \right\rbrace \]

定义一个新的集合运算带来的麻烦就是我们需要证明它生成的对象是一个集合。

考虑证明 Cartesian 积的结果为一个集合：
首先考虑替换公理证明对于任意 $y\in B$ ，有 $A\times \left\lbrace y \right\rbrace$ 是集合：从 $y$ 出发可以构造 $z=\left\lbrace y \right\rbrace$ 是集合，利用如下的公式：

\[ y\in z \land \neg(x\in z \land \neg(x=y)) \]

然后 $A\times \left\lbrace y \right\rbrace = \left\lbrace \left\langle a_1,y \right\rangle,\cdots \right\rbrace$ ，其中的 $a \in A$ 都能定义 $\left\lbrace a \right\rbrace$ ，从而能定义 $\left\lbrace \left\lbrace a \right\rbrace \right\rbrace$ ，同时根据并集公理有 $\left\lbrace a,y \right\rbrace$ 是集合，从而

\[ \left\lbrace \left\lbrace a \right\rbrace , \left\lbrace a,y\right\rbrace\right\rbrace \]

是集合，那么我们就能证明 $A\times \left\lbrace y \right\rbrace$ 是集合. （在教材上写为 $\mathrm{prod}(A,y)$）.

再利用替换公理，可以得到

\[ \left\lbrace A \times \left\lbrace y \right\rbrace : y\in B \right\rbrace \]

是一个集合.

最后利用并集公理，有

\[ A\times B = \bigcup \left\lbrace A \times \left\lbrace y \right\rbrace : y\in B\right\rbrace \]

是一个集合. $\square$

关系与函数

关系

定义：关系

一个关系就是一个集合 $R$ ，它的元素均为有序对.

定义如下的符号：

\[ \mathrm{dom} (R) = \left\lbrace x: \exists y ( \left\langle x,y \right\rangle) \in R\right\rbrace \]

以及

\[ \mathrm{ran} (R) = \left\lbrace y: \exists x ( \left\langle x,y \right\rangle) \in R\right\rbrace \]

从实际意义上来看，$\mathrm{dom}(R)$ 表示可以在关系 $R$ 中作为有序对左侧元素的元素集合. 另一个则刚好相反.

此时 $R \subset \mathrm{dom}(R)\times \mathrm{ran}(R)$ . 逆关系定义为

\[ R^{-1} = \left\lbrace \left\langle x,y \right\rangle : \left\langle y,x \right\rangle\in R \right\rbrace \]

函数

定义：函数

函数是一个特殊的关系，这个关系满足
$$ \forall x\in \mathrm{dom}(f)\exists ! y \in \mathrm{ran}(f)(\left\langle x,y \right\rangle\in f). $$

在关系的部分，$\mathrm{dom}(f)$ 实际上不好给一个确切的名字，但是在函数部分，我们实际上已经可以将其与以前学的定义域联系了，事实上，$\mathrm{dom}(f)$ 就是函数的定义域 (domain)，$\mathrm{ran}(f)$ 自然就是值域 (range).

全序集与良序集

全序集

定义：全序集

全序是一个有序对：$\left\langle A,R \right\rangle$ ，称 $A$ 在 $R$ 的意义下全序，如果满足如下的三个条件：

$\forall x,y,z \in A (x R y \land y R z \to x R z)$ （transitive, 传递性）
$\forall x,y \in A (x=y\lor x R y \lor yRx)$（trichotomy, 三分性）
$\forall x \in A (\neg (x Rx))$ （irreflexive, 非自反性）

我们记 $x R y$ 来表示 $\left\langle x,y \right\rangle \in R$ . 如果 $\left\langle A,R \right\rangle$ 是全序，那么对于子集 $B \subset A$ ，$\left\langle B,R \right\rangle$ 也是全序.

良序集

定义：良序集

$\left\langle A,R \right\rangle$ 是良序的，如果 $\left\langle A,R \right\rangle$ 是全序的且对于每个 $A$ 的非空子集，它们都有 $R$-最小元素.

全序、良序集的同构

定义：全序集的同构

设 $A,B$ 均为集合，$R,S$ 均为关系，我们称 $\left\langle A,R \right\rangle \cong \left\langle B,S \right\rangle$ ，如果存在 $f: A\to B$ 是一个双射且满足
$$ \forall x,y \in A (x R y \leftrightarrow f(x)S f(y)) $$
$f$ 即为同构.

如果 $x\in A$ ，记

\[ \mathrm{pred}(A,x,R) = \left\lbrace y\in A: yRx \right\rbrace \]

这个记号通常用于解决序关系的问题. 它表示集合 $A$ 在序关系 $R$ 下，所有“小于” $x$ 的元素的子集. 也称为前段.

引理：良序集不可能同构于其前段

如果 $\left\langle A,R \right\rangle$ 为一个良序集，那么对于所有的 $x\in A$ ，$\left\langle A,R \right\rangle\not\cong \left\langle \mathrm{pred}(A,x,R),R \right\rangle$ .

利用反证：假如这样的同构存在，设为 $f$ ，那么有

\[ \forall x\forall y ((x\in A)\land (y\in A)\land xR y \leftrightarrow f(x)Rf(y)) \]

那么利用分离公理模式，取如下的集合：

\[ S = \left\lbrace a\in A : f(a) \neq a \right\rbrace \]

容易知道 $S$ 是 $A$ 的非空子集，于是 $S$ 有 $R$ 最小元 $\alpha$ . 这说明 $xR \alpha$ 时，有 $f(x)=x$ ，而由于 $f(\alpha) \neq \alpha$ ，因此 $\alpha R f(\alpha)$ 成立，由于 $f$ 为同构，则存在 $f(\beta)= \alpha$ 的 $\beta$ .

此时必须有 $\alpha R \beta$ ，而根据 $\alpha R f(\alpha)$ 可知 $f(\beta)R f(\alpha)$ ，这就出现了矛盾！ $\square$

定理

令 $\left\langle A,R \right\rangle, \left\langle B,S \right\rangle$ 是两个良序，那么下面的结论恰有一个成立：

$\left\langle A,R \right\rangle \cong \left\langle B,S \right\rangle$ ；
$\exists y\in B (\left\langle A,R \right\rangle \cong \left\langle \mathrm{pred}(B,y,S),S \right\rangle)$ ；
$\exists x\in A (\left\langle \mathrm{pred}(A,x,R) , R \right\rangle \cong \left\langle B,S \right\rangle)$ .

Remark.

这个定理的结果很重要，它表明任意两个良序集是可以比较大小的. 小的良序集同构于大的良序集的前段.

选择公理

公理 9 ： 选择公理 (Choice)

\[ \forall A \exists R (R \text{ well-orders } A) \]

在 Kunen 的书当中，上式是选择公理，但是实际上，对于多数的集合论书，它是良序定理. 事实上两者是等价的。

符号	含义
\(0\)	空集（也就是说在这个部分我们不采用 \(\varnothing\)）
\(\cong\)	同构
\(\models\)	后承符号
\(\vdash\)	推演