介绍 ZF 和 ZFC 集合论的由来。

罗素悖论

在朴素集合论中，将“集合的元素”也视为集合。

可以得到概括公理：

1	exists s: forall x, (x in s <-> P(x))

概括公理说，对于任意的 Prop P，存在集合 s，它里面是所有满足性质 P(x) 的 x。

罗素提出一个悖论，考虑 S = {x | x notin x}，S in S 是否成立？S notin S 是否成立？如果 S in S 成立，则根据定义应该有 S notin S，和假设矛盾。如果 S notin S 成立，则能推出 S in S，有矛盾。

哥德尔不完备定理

定理1

任何自洽的形式系统，只要蕴涵皮亚诺算术公理，就可以在其中构造在体系中不能被证明的真命题，因此通过推理演绎不能得到所有真命题。也就是说体系不完备。

定理2

任何逻辑自洽的形式系统，只要蕴涵皮亚诺算术公理，它就不能用于证明其本身的自洽性。

ZF 和 ZFC 集合论

几个公理

外延公理

1
2
3

forall x,
    forall y,
        {forall z | z in x <-> z in y} -> x = y

正规公理

每个非空集合 x 都包含一个成员 y，使得 x 和 y 不相交。这里 exists a (a in x) 是非空集合的条件，

forall x,
    exists a (a in x) -> exists y
        y in x /\ not (exists z)
            z in y /\ z in x

正则公理可以用来防止罗素悖论。

证明如果 A 是集合，则 A not in A。不妨假定 A in A，则有 A in {A}，所以有 A intersect {A} = {A}。根据正规公理，可以得到 {A} 是空集，这是矛盾的。

替代公理

如果给定任何集合 x，有一个唯一的集合 y 使得 P 对 x 和 y 成立，那么给定任何集合 A，有着一个集合 B 使得，给定任何集合 y，y 是 B 的一个成员，当且仅当有是 A 的成员的一个集合 x 使得 P 对于 x 和 y 成立。

因为在一阶逻辑中无法 quantify 可定义的函数，one instance of the schema is included for each formula f in the language of set theory with free variables among w1, …, wn, A, x, y; but B is not free in f.

简单的形式如下，可以看出这里的 f 指定了一个从 x 到 y 的对应关系，类似 F 在 A 上的应用。所有由此得到的 y 可以被定义为集合 B，类似于 F(A)。

这里有个简单记法。唯一性可以写为 !x, P(x)。它被定义为: forall x, forall y, P(x) /\ P(y) -> x = y。

概括公理模式、分类公理模式、分离公理模式

这个公理类似于弱化版的概括公理。因为它实际上只允许 {a in s: P(x)} 这样的集合，不允许 {a: P(x)} 这样的集合。

forall x,
    exists s,
        forall a,
            a in s <-> a in x /\ P

这个公理可以被用来证明空集的存在。我们可以去找一个所有集合都没有的性质，比如

1	forall w, {u in w \| (u in u) /\ not (u in u)}

配对公理

如果 x 和 y 是集合，则存在一个集合包含 x 和 y。

1	forall x, forall y, exists (x in z /\ y in z)

并集公理

对任一个集合 F 总存在一个集合 A 包含每个为 F 的某个成员的成员的集合。

无穷公理

存在一个有无限多成员的集合 X。
形式化来说，令 S(x) 为 x union {x}，其中 x 为某个集合。存在一个集合 X 使得空集 ∅ 为 X 的成员，且当一个集合 y 为 X 的成员时，S(y) 也是 X 的成员。

幂集公理

对于任意的集合 x，都存在一个集合 y 为 x 的幂集的父集。
这里的 forall z [...] 实际上定义了幂集。

选择公理

良序定理，等价于选择公理，声称所有集合都可以被良序排序。

良序定理形式。

势和序数

集合的势

任何势小于自然数集的集合称为有限集合。
任何势和自然数集一样的集合称为可数无限集合。
任何势大于自然数集的集合称为不可数集合。

对角论证法

假设实数区间 [0,1] 是可数无穷大的，那么就可以将其组成排列 r1, r2, ...。比如如下

r1 = 0 . 5 1 0 5 1 1 0 ...
r2 = 0 . 4 1 3 2 0 4 3 ...
r3 = 0 . 8 2 4 5 0 2 6 ...
r4 = 0 . 2 3 3 0 1 2 6 ...
r5 = 0 . 4 1 0 7 2 4 6 ...
r6 = 0 . 9 9 3 7 8 3 8 ...
r7 = 0 . 0 1 0 5 1 3 5 ...
...

现在如果能构造出一个 x，它一定不等于所有的 r[k]，那么就可以通过反证法证明了实数区间 [0,1] 不是可数无穷大的。
构造方法就是 x 的第 k 位，让它和 r[k] 的第 k 位不同。这是肯定能做到的。
这样的话 x 就会和所有的 r[k] 至少有一位不同。

连续统假设

自然数集的势标记为 N0，实数集的势则被标记为 c。可以证明 c = 2^N0 > N0。连续统假设断言不存在介于实数集的势和自然数集的势之间的基数，亦即 c = N1。

ZFC 公理系统