集合论笔记

1集论中的哲学与分体学

这里使用经典逻辑, 因为根据双重否定律 $\neg\neg A ⟹ A$ 可知归谬法 (reduction ad absurdum,RAA) 与间接证明 (indirect proof) 等价, 从而无需区别矛盾证法 (proof by contradiction) 的两种类型. 但是在 Brouwer-Heyting-Kolmogorov 直觉主义中有 Brouwer(1925) $\neg\neg\neg A ⟺ \neg A$ 但是 $\neg\neg A ⟹ A$ 不再成立, 所以尽管可以使用归谬法从假设 $A$ 导出矛盾来证明 $\neg A$ , 但由于缺乏双重否定律从假设 $\neg A$ 导出矛盾只能证明 $\neg\neg A$ .

令 $Ω = {\neg, \lor}$ 且 $α : Ω \to N$ 定义为 $α (\neg) = 1$ 且 $α (\lor) = 2$ , 令 $A$ 是命题符号的集合, 则不交并 $Ω \cup A$ 称为字符集, 而 $W (Ω, A) := ⋃_{n \in N} (Ω \cup A)^{n}$ 的元素称为词 (word) 或字符串 (string), 这是一个 $Ω$ 代数, 则 $A$ 生成的子代数 $F (Ω, A)$ 称为公式 (well-defined formula), 利用 Hall 准则可以判断一个字符串是否是公式

集论分体学

集论的分体学 (Mereology) 至少可追溯至 Shoenflies1921,Merzbach1925,Foradori1932 现代的介绍有 Hamkins2016. 拓扑分体学的想法导致了无点拓扑, 例如 Menger 关系 $A \leq B ⟺ \overline{A} \subseteq B$ 而 $A \sim B ⟺ (\overline{V} \subseteq A ⟺ \overline{V} \subseteq B)$ , 现代的介绍可看 Johnstone

令 $θ : V \to V$ 定义为 $θ (0) = 1$ 且 $θ (1) = 0$ 且 $x \in V ∖ {0, 1} ⟹ θ (x) = x$ , 则 $θ$ 是双射从而 $τ = P (θ)$ 也是双射而且是关于 $\subseteq$ 的序同构, 令 $x < y ⟺ τ (x) \in τ (y)$ 则 $τ : (V, <) \to (V, \in)$ 是同构

拓扑分体学

若 $y$ 是 ${y \in E ∣ x < y}$ 的极小元, 则称 $y$ 覆盖 $x$ , 若 $x$ 覆盖最小元则称 $x$ 是一个原子 (atom).

集合论与正则公理的哲学

直觉上, 集合或类是一些数学对象的全体. 若对集中元素无限制, 则可通过判断论域中的对象是否在给定集合中而确定集合, 然而这将导致所谓 Russell 悖论, 事实上, 令 $x \in R ⟺ x 是集合且 x \in / x$ 则 $R \in R ⟺ R 是集合且 R \in / R$ 得到矛盾!

直觉上, 从原始元素 (urelement) 或称原子元素 (atom) 开始拾级而上, 其中每一级得到的集合是原始元素或由前级形成的集. 若无原始元素则得到集合称为纯集合, 并且 Fraenkel 证明了在数学实践中我们总可以限制在仅考虑纯集合的情形. 假设 $y \in x$ , 考虑最先形成得到 $x$ 的级, 则 $y$ 必然先于 $x$ 得到, 因此 $y \cap x = \emptyset$ .

正则公理

$(\forall x \neq = \emptyset) (\exists y \in x) x \cap y = \emptyset$

拾级而上说明我们需要递归地定义集合

(i)	$V_{0} = \emptyset$ .
(ii)	$V_{i + 1} = P (V_{i})$ .
(iii)	$\dots$ .

但若无替换公理模式即使说明诸 $V_{i}$ 组成一个集合也绝非易事.

假设 ZFC 一致则可以证明正则公理相对 ZFC 其它公理的独立性 (见 Bernays1954), 且理论上可以证明正则公理相对 ZFC 其它公理一致, 因此尽管一些逻辑学家对于正则公理的直观性表示怀疑, 但接受无危害的正则公理似乎是大势所趋.

在某种程度上, 正则公理等价于不存在无穷递降链

Zermelo.

Zermelo. 见 F-H-L,p90

$□$

2ZFS 系统

Zermelo 公理系统

空集公理

空集存在 $(\exists x) (\forall y) y \in / x$

外延公理

$x \subseteq y \subseteq x ⟹ x = y$

注意若舍弃外延公理, 则公理系统应含原子 (如整数可不被视为集合).

分离子集公理模式

对每个集合 $X$ 有集合 ${x \in X ∣ P (x)}$ 存在

Mostowski 证明了 ZF 中分离子集公理模式不能用有限个公理替代 (可见 Montague57,61 特别是 Kreisel-Levy68), 但在 NBG 或 NF 中可以.

无序对公理

集 ${a, b}$ 存在

并公理

并集 $⋃ X$ 存在

幂集公理

幂集 $P (X)$ 存在

注 2.1. 上述六条公理组成的公理系统记为 $Z_{0}$ .

无穷公理

存在极限序数, 或等价地存在归纳集 (亦称后继集). Zermelo 归纳集 $Z$ 是指满足 $\emptyset \in Z$ 且 $x \in Z ⟹ {x} \in Z$ ,Whitehead-Russell 归纳集则将后者换为 $x \in Z ⟹ x \cup {x} \in Z$ , 结合二者又可换为 $x, y \in Z ⟹ x \cup {y} \in Z$ von Neumann 方式的特点是 $\in$ 与 $\subset$ 一致给出了自然的序关系, 而 Zermelo 方式灵活运用了 monad 的 $η$ 分量直接给出了一个真嵌入而且比 von Neumann 方式更简单自然. 在其它 Z 公理的帮助下可以证明存在无穷集等价于存在 Dedekind 无穷集, 但若各种无穷公理相对 Z 的其它公理一致则 von Neumann 方式和 Zermelo 方式互不蕴含 (见 Bernays37-54VI 结尾). 在 ZF 中各种无穷公理版本是等价的. 但仅就无穷公理而言,Zermelo 方式和 von Neumann 方式有些强过头了, 似乎唯一的好处就是在定义实数时会方便些.

注 2.2. $Z_{0}$ 加上无穷公理和 Mirimanoff-von Neumann 正则公理记为 $Z$ . 遗传有限集 $a$ 是指 $a$ , $⋃ a$ , $⋃⋃ a$ ,... 均是有限的集. 但若没有无穷公理则不能证明非遗传有限集存在. 若有外延公理和分离子集公理模式以及集合 $a \cup {b}$ 的存在性即使不承认无穷公理也可以讨论初等算术和有限集. 然而 Ackermann37 方法说明一些用解析数论方法的算术定理不能用初等算术证明 (可见 Kreisel-Levy68). 实数集概念必须要无穷公理.

ZFS 公理系统

ZFS 公理系统亦常简称 ZF 系统

替换公理模式

$(\forall t_{1}, \dots, t_{k}) (\forall x \exists! y A_{n} (x, y, t_{1}, \dots, t_{k}) ⟹ \forall u \exists v \forall r (r \in v ⟺ \exists s \in u A_{n} (s, r, t_{1}, \dots, t_{k})))$ 或等价地说带参数的类函数的值域是集合.

替换公理模式蕴含分离公理模式. 事实上, 若 $P (x)$ 则令 $A_{n} (x, x, t_{1}, \dots, t_{k})$ 否则令 $A_{n} (x, X, t_{1}, \dots, t_{k})$ , 这样无论 $x$ 是否满足 $P (t)$ 都定义了一个类函数 $A_{n} (x, y, t_{1}, \dots, t_{k})$ , 则其在 $X$ 上的值域为 ${r \in X ∣ P (r)} \cup {X}$

替换公理模式像是在给集论公理打补丁使得可以证明一些极端大基数集的存在性, 否则甚至无法证明集合 ${N, P (N) P (P (N)), \dots}$ 的存在性.

注 2.3. $Z$ 加上 Skolem-Fraenkel 替换公理模式记为 $ZF$ .

选择公理

$(\forall i \in I) X_{i} \neq = \emptyset ⟹ i \in I \prod X_{i} \neq = \emptyset$

Zermelo 当时没有预见到甚至可以要求诸 $X_{i}$ 互不相交, 直到两年后 (1906 年)Russell 给出了 " 乘法原理 "

Zermelo.

Zermelo. 略, 见 F-H-L p.56

$□$

引理 2.4 (Diaconescu). 选择公理蕴含排中律

证明.

证明. 令 $A = {x \in {0, 1} ∣ P \lor x = 0}$ 且 $B = {x \in {0, 1} ∣ P \lor x = 1}$ , 则 $0 \in A$ 且 $1 \in B$ , 由选择公理知存在函数 $f : {A, B} \to A \cup B$ 使得 $f (A) \in A$ 且 $f (B) \in B$ , 则有下列三种情况

1.	$f (A) = 1$
2.	$f (B) = 0$
3.	$f (A) = 0 \land f (B) = 1$

若

f (A) = 1

, 则

1 = f (A) \in A

, 从而

P \lor 1 = 0

, 即

P

. 若

f (B) = 0

, 则

0 = f (B) \in B

, 从而

P \lor 0 = 1

, 即

P

. 若

f (A) = 0 \land f (B) = 1

, 假设

P

成立, 则

A = {0, 1} = B

, 从而

0 = f (A) = f (B) = 1

矛盾! 因此

\neg P

.

$□$

注 2.5. $ZFS$ 加上选择公理记为 $ZFC$ , 而 $ZFC$ 减掉正则公理的公理系统有时称为正集合论.

定义 2.6. V 表示所有集合的类

3集论哲学

元语言取为自然语言, 这里主要是中文. 一阶谓词演算不再赘述. 仅提及非 $\neg$ , 且 $\land$ , 或 $\lor$ , 蕴含 $⟹$ 亦作 $\to$ , 等价 $⟺$ 亦作 $\leftrightarrow$ 五个逻辑连接词 (logical connective) 和两个量词 (quantifier)—全称量词 (universal quantifier) $\forall$ 和存在量词 (existence quantifier) $\exists$ . 若 $A$ 和 $B$ 是合式公式 (well-defined), 则 $\neg A$ , $A \land B$ , $A \lor B$ , $A ⟹ B$ , $A ⟺ B$ 五式及 $(\forall x) A$ , $(\exists x) A$ 两式俱是合式公式.

ZF 哲学

ZF 的原始符号 (primitive symbol) 是背景逻辑 (underlying logic) 的原始符号加集论原始符号二元谓词 $\in$ 表示成员关系 (membership relation). 原子公式 (atomic formula) 是形如 $x \in y$ 可能也有 $x = y$ . 所有其它公式可由原子公式和逻辑连接词和量词得到. 论域 (universe of discourse) 即个体变量 (individual variable) 的范围由对象 (object) 组成. 在讨论 ZF 集论时, 自然假设每个对象是某个对象集合的成员 (注意其它集论可能不满足这一点). 若一个对象是某个对象的成员, 则称为元素 (element). 在 ZF 中 " 元素 " 是 " 对象 " 的同义语并倾向于用 " 元素 " 替代 " 对象 ", 这有助于将 ZF 与并非所有对象均为元素的集论对比. 有成员的元素称为集, 没有成员的元素称为 Zermelo 的 urelement. 集合论的中心问题便是我们希望有多少 urelement? 人们希望在不导致矛盾的前提下保留 Cantor 朴素集论的想法. 一旦有一个 urelement 例如 $a$ 则可构造 $b = {a}$ , $c = {b}$ ,etc. 在实践中, 希望 urelement 存在的原因之一是当两个集合无公共元素时也可以定义交, 这样这个交就是无成员的 urelement 称为空集 (null-set), 这样集合是有成员的元素或没有成员的空集. 除了空集外还需要更多 urelement 吗? 仅从数学目的来看, 没有更多 urelement 的需要. 因此在 ZF 中所有元素都是有成员的集合或空集, 即在 ZF 中集合和元素是同义语. 事实上, 可以证明 ZF 添加任意多 urelement 相对 ZF 一致 (可见 Mostowski39 或 Levy64).

等式

公理化观点是在带有等于的一阶谓词演算背景中我们可以方便地假定等式公理, 即 $\in$ 是同余关系 (congruence). 另一种观点是在集论中定义成员同余 (membership-congruence) $x =_{m} y$ 为 $(\forall z) (x \in z ⟺ y \in z) \land (\forall u) (u \in x ⟺ u \in y)$ 然后无需任何集论公理即可验证成员同余满足等式公理. 易证 $x = y ⟺ x =_{m} y$

4NBG 系统

习惯上用小写字母表示集而大写字母表示类. 类的元素是集.

类外延公理

无序对公理

任意两个集合的无序对集合存在

全类存在公理

所有集合的类 $V$ 存在

epsilon 类公理

${(a, b) \in V \times V ∣ a \in b}$ 存在

对角线公理

对角线存在

交类公理

交类 $A \cap B$ 存在

补类公理

补类 $∁ A$ 存在

定义类公理

定义类 $dom (A)$ 存在

AV 公理 (

对于任意类 $A$ , 类 $A \times V$ 存在

逆类公理

左 coupling 公理

替换公理

若类函数的定义类是集则其值类也是集

并集公理

并集 $⋃ a$ 存在

幂集公理

幂集 $P (a)$ 存在

无穷公理

存在 Bolzano-Dedekind 无穷集

选择公理

von Neumann-Baer(1929) global choice

限制公理

即正则公理

有限序数 $n$ 意谓满足 $m \leq n ⟹ m = 0 \lor (\exists k \in On) (m = k^{+})$ Zermelo1909 不使用无穷公理建立了有限集理论

一致性与独立性

最基本的元数学问题是 ZF 的一致性和 AC 的独立性. Godel 的一致性证明说明若 ZF 一致则 ZF 的一致性不能在 ZF 中证明. 因此在 ZF 中工作的人们通常默认 ZF 的一致性. 1922 年 Fraenkel 证明了在带有无穷个 urelement 的集论中 AC 的独立性, 在 1938 年波兰学派 Mostowski 和 Lindenbaum 改进了证明. 1938 年 Godel 证明了 AC 和 GCH 的一致性,Godel 引入一种方法生成一种所谓 Godel 可构造集. 在 1951-1955 年间 Shoenfield55,Mendelson56a,Specker57 独立证明了 AC 不能在 ZF–reg 中得到, 与 Fraenkel-Mostowski 证明相比只是用特殊的 unfounded 集替换了 urelement, 这一过程在 NF 中是自然的. 在 ZF 中 AC 独立性到 1963 年 Cohen 解决

5有限集

Bolzano(1851),Dedekind(1888) 和 Pierce(1933) 介绍了 Dedekind(第一种) 无穷集 (亦称反身集), 假设无穷公理, 则一个集合是 Dedekind 无穷的当且仅当其包含一个可数无穷集. Bernays61a 和 Ackermann 集论可以证明无穷集存在. 可以不使用自然数建立有限集理论.

定义 5.1 (Tarski 有限集,1924). 若 $\emptyset \neq = F \subseteq P (E)$ 蕴含 $(F, \subseteq)$ 有极小元, 则称 $E$ 是一个 Tarski 有限集 (Tarski-finite set), 而 Janiszewski 称 élément irréductible.

定理 5.2. 集合 $E$ 是 Tarski 有限集当且仅当 $\emptyset \neq = F \subseteq P (E)$ 蕴含 $(F, \subseteq)$ 有极大元.

证明.

证明. 设

E

是 Tarski 有限集且

A \in F \subseteq P (E)

, 则

E ∖ A \in {S \in P (E) ∣ E ∖ S \in F} \subseteq P (E)

, 由假设知

{S \in P (E) ∣ E ∖ S \in F}

有极小元

S

, 则

E ∖ S \in F

, 易知

E ∖ S

是

(F, \subseteq)

的极大元. 事实上, 若

E ∖ S \subseteq B \in F

, 由

B = E ∖ (E ∖ B)

知

E ∖ B \subseteq S

且

E ∖ B \in {S \in P (E) ∣ E ∖ S \in F}

, 于是

E ∖ B = S

即

E ∖ S = B

. 同理可知反之亦然.

$□$

定理 5.3. 空集 $\emptyset$ 和单元素集 ${x}$ 是 Tarski 有限集.

证明.

证明. 因为

({\emptyset}, \subseteq)

只有唯一元素

\emptyset

, 从而是最小元, 因此空集是 Tarski 有限集. 同理可知

({{x}}, \subseteq)

有最小元

{x}

, 而

({\emptyset, {x}}, \subseteq)

有最小元

\emptyset

, 因此

{x}

是 Tarski 有限集.

$□$

定理 5.4. Tarski 有限集 $E$ 的子集 $X \subseteq E$ 是 Tarski 有限集.

证明.

证明. 设

\emptyset \neq = F \subseteq P (X)

, 则由

X \subseteq E

知

\emptyset \neq = F \subseteq P (E)

, 因此

(F, \subseteq)

有极小元.

$□$

注 5.5. 注意有限集的子集有限等价于排中律. 事实上, 考虑 $S = {x \in {0} ∣ P} \subseteq {0}$ , 则 $S = \emptyset \lor S = {0}$ , 因此 $\neg P \lor P$ .

推论 5.6. 若 $A$ 是 Tarski 有限集则 $A \cap B$ 和 $A ∖ B$ 都是 Tarski 有限集.

证明.

证明. 注意到

A \cap B \subseteq A

和

A ∖ B \subseteq A

.

$□$

定理 5.7. 若 $A$ 和 $B$ 都是 Tarski 有限集则 $A \cup B$ 是 Tarski 有限集.

证明.

证明. 设

\emptyset \neq = F \subseteq P (A \cup B)

, 令

L = {C \in P (A) ∣ (\exists D \in P (B)) C \cup D \in F}

则

\emptyset \neq = F

即存在

X \in F

, 由

X = (X ∖ A) \cup (X \cap A)

易知

X ∖ A \subseteq (A \cup B) ∖ A = B ∖ A \subseteq B

因此

X \cap A \in L

从而

L \neq = \emptyset

. 由假设知

(L, \subseteq)

有极小元

C^{m}

, 令

M = {D \in P (B) ∣ C^{m} \cup D \in F}

注意到

C^{m} \in L

即

M \neq = \emptyset

, 由假设知

(M, \subseteq)

有极小元

D^{m}

. 只需证

C^{m} \cup D^{m}

是

(F, \subseteq)

的极小元. 若

E \in F

且

E \subseteq C^{m} \cup D^{m}

, 则

E = (E \cap C^{m}) \cup (E \cap D^{m})

, 由

E \cap D^{m} \subseteq D^{m} \subseteq B

知

E \cap C^{m} \in L

, 又由

C^{m}

的极小性知

E \cap C^{m} = C^{m}

, 从而

C^{m} \cup (E \cap D^{m}) = (E \cap C^{m}) \cup (E \cap D^{m}) = E \in F

则

E \cap D^{m} \in M

, 由

D^{m}

的极小性知

E \cap D^{m} = D^{m}

, 因此

E = (E \cap C^{m}) \cap (E \cap D^{m}) = C^{m} \cap D^{m}

$□$

推论 5.8. 若 $A$ 是 Tarski 有限集则 $A \cup {x}$ 是 Tarski 有限集.

定义 5.9 (Whitehead-Russell 有限集,1911,1912). 若 $\emptyset \in K \subseteq P (A) \land (\forall x \in A) (\forall B \in K) (B \cup {x} \in K) ⟹ K = P (A)$ 则称 $A$ 是一个 Whitehead-Russell 有限集.

定义 5.10 (Sierpinski-Kuratowski 有限集,1918,1920). 若

•	$\emptyset \in K \subseteq P (A)$
•	$a \in A ⟹ {a} \in K$
•	$B \in K \land C \in K ⟹ B \cup C \in K$

蕴含 $K = P (A)$ 则称集合 $A$ 是一个 Sierpinski-Kuratowski 有限集.

定理 5.11. 设 $A$ 是集合, 则下列三个命题等价

1.	集合 $A$ 是 Tarski 有限集
2.	集合 $A$ 是 Whitehead-Russell 有限集
3.	集合 $A$ 是 Sierpinski-Kuratowski 有限集

证明(Tarski).

证明 (Tarski). 第一步, 假设 $A$ 是 Tarski 有限集且

•	$\emptyset \in K \subseteq P (A)$
•	$(\forall x \in A) (\forall B \in K) (B \cup {x} \in K)$

且 $S \in P (A)$ , 则由假设易知 $\emptyset \in K \cap P (S) \subseteq P (A)$ , 由 $A$ 是 Tarski 有限集知存在 $K \cap P (S)$ 的 $\subseteq$ 极大元 $B$ , 若 $a \in S$ , 则由假设得 $B \cup {a} \in K \cap P (S)$ , 又由 $B \subseteq B \cup {a}$ 和 $B$ 的极大性知 $B = B \cup {a}$ 即 $a \in B$ , 则 $S \subseteq B$ , 因此 $S = B \in K$ , 从而 $P (A) \subseteq K$ , 于是 $A$ 是 Whitehead-Russell 有限集. 第二步, 假设集合 $A$ 是 Whitehead-Russell 有限集且

•	$\emptyset \in K \subseteq P (A)$
•	$a \in A ⟹ {a} \in K$
•	$B \in K \land C \in K ⟹ B \cup C \in K$

则由假设知

•	$\emptyset \in K \subseteq P (A)$
•	$(\forall a \in A) (\forall B \in K) B \cup {a} \in K$

又由假设知 $K = P (A)$ , 于是 $A$ 是 Sierpinski-Kuratowski 有限集. 第三步, 假设集合 $A$ 是 Sierpinski-Kuratowski 有限集, 令 $K = {C \in P (A) ∣ C 是 Tarski 有限集}$ 为 $A$ 的 Tarski 有限子集的集族, 由 5.3 和 5.7 知

•	$\emptyset \in K \subseteq P (A)$
•	$a \in A ⟹ {a} \in K$
•	$B \in K \land C \in K ⟹ B \cup C \in K$

则由假设知

K = P (A)

, 从而

A \in P (A) = K

, 于是

A

是 Tarski 有限集.

$□$

注 5.12. 利用类的语言 (例如可见 Bernays) 可能更简洁直接, 可见 Suppes 公理集论或 Levy 基础集论. 这里依 Kuratowski 精神的处理可以规避类语言, 亦可参照 Some Notes on Finite Sets

Bolzano-Dedekind-Peirce 有限集

定义 5.13 (Bolzano-Dedekind-Peirce 有限集). 若每个 $A$ 到 $A$ 的单射都是满射, 则称 $A$ 是 Bolzano-Dedekind-Peirce 有限集, 简称 Bolzano-Dedekind 有限集或 Dedekind 有限集

引理 5.14. 设 $H : A \to B$ 是满射且 $A$ 是 Sierpinski-Kuratowski 有限集则 $B$ 也是有限集

证明.

证明. 令 $K = {C \in P (A) ∣ P (H) (C) 是 T a rs ki 有限集}$ 易证

•	$\emptyset \in K \subseteq P (A)$
•	$a \in A ⟹ {a} \in K$
•	$B \in K \land C \in K ⟹ B \cup C \in K$

则

A \in P (A) = K

于是

B = P (H) (A)

有限.

$□$

定理 5.15 (有限集基本定理). Whitehead-Russell 有限集 $A$ 是 Bolzano-Dedekind 有限集

证明.

证明. 设集 $A$ 是 Whitehead-Russell 有限集且 $f : A \to A$ 是单射, 令 $K = {B \in P (A) ∣ (\forall f \in End (B)) (f 是单射 ⟹ f 是满射)}$ 显然 $\emptyset \in K$ , 设 $a \in A$ 且 $B \in K$ 且 $g : B \cup {a} \to B \cup {a}$ 是单射, 不妨设 $a \in / B$ , 则由 $g$ 是单射知 $P (g) (B) = P (g) (B \cup {a}) ∖ {g (a)} \subseteq (B \cup {a}) ∖ {g (a)}$ 从而 $g ∣_{B}^{(B \cup {a}) ∖ {g (a)}} : B \to (B \cup {a}) ∖ {g (a)}$ 是单射. 注意到 $g (a) \in B \cup {a}$ , 分两种情况讨论.

1.

若 $g (a) \in B$ , 则由 $a \in / B$ 易知 $g (a) \neq = a$ , 则 $h := id (B ∖ {g (a)}) \cup g ∣_{{a}}^{B} : (B \cup {a}) ∖ {g (a)} = (B ∖ {g (a)}) \cup {a} \to B$ 是双射, 因此存在单射 $k := g ∣_{B}^{(B \cup {a}) ∖ {g (a)}} \circ (id (B ∖ {g (a)}) \cup g ∣_{{a}}^{B}) : (B \cup {a}) ∖ {g (a)} \to (B \cup {a}) ∖ {g (a)}$ 则 $h \circ k \circ h^{- 1} : B \to B$ 是单射, 从而由 $B \in K$ 知 $h \circ k \circ h^{- 1} : B \to B$ 是满射, 因此 $k = h^{- 1} \circ (h \circ k \circ h^{- 1}) \circ h : (B \cup {a}) ∖ {g (a)} \to (B \cup {a}) ∖ {g (a)}$ 是满射, 即 $P (g) (B) = (B \cup {a}) ∖ {g (a)}$ , 也就是说 $P (g) (B \cup {a}) ∖ {g (a)} = (B \cup {a}) ∖ {g (a)}$ , 两边并上 ${g (a)}$ 知 $g : B \cup {a} \to B \cup {a}$ 是满射,

2.

若 $g (a) = a \in / B$ , 则 $(B \cup {a}) ∖ {g (a)} = B$ , 从而 $g ∣_{B}^{B} : B \to B$ 是单射, 因此由 $B \in K$ 知 $g ∣_{B}^{B} : B \to B$ 是满射, 从而 $g : B \cup {a} \to B \cup {a}$ 是满射.

于是

B \cup {a} \in K

, 由

A

是 Whitehead-Russell 有限集知

K = P (A)

, 从而

A \in P (A) = K

, 于是由

f : A \to A

是单射知

f

也是满射.Q.E.D.

$□$

注 5.16. 有限集基本定理又称算术主定理. 一个本质上相同但使用自然数的证明可见 Kleene 的元数学导论 (对有限集 $A$ 的基数归纳), 一个更简洁而且不使用自然数的证明可见 Suppes 公理集论, 这里的证明的优点是不使用自然数且更具构造性. 证明逆命题需要 AC.

推论 5.17 (Dirichlet’s Schubfachprinzip). 若 $Card (A) < Card (B)$ 则每个映射 $f : B \to A$ 不是单射

通常的基数有限集

定义 5.18 (基数有限集). 若 $(\exists n \in N) Card (A) = n$ 则称 $A$ 是 (通常的) 基数有限集.

定理 5.19. Whitehead-Russell 有限集与基数有限集等价

证明.

证明. 设 $A$ 是基数有限集且

•	$\emptyset \in K \subseteq P (A)$
•	$(\forall a \in A) (\forall B \in K) B \cup {a} \in K$

则易证 $P (A) = ⋃_{n \in N} {S \in P (A) ∣ Card (S) = n}$ , 注意到 ${\emptyset} \subseteq K$ , 假设 ${S \in P (A) ∣ Card (S) = n} \subseteq K$ , 若 $D \in P (A)$ 且 $Card (D) = n + 1$ , 则 $D \neq = \emptyset$ 即存在 $a \in D$ , 注意到有不交并分解 $D = (D ∖ {a}) \cup {a}$ 从而 $Card ((D ∖ {a}) + 1 = Card (D) = n + 1$ , 因此 $D \in P (A)$ 且 $Card (D ∖ {a}) = n$ , 由归纳假设知 $D ∖ {a} \in K$ , 则 $D = (D ∖ {a}) \cup {a} \in K$ , 由数学归纳法知 $P (A) = n \in N ⋃ {S \in P (A) ∣ Card (S) = n} = K$ 反之, 设 $A$ 是 Whitehead-Russell 有限集, 令 $K = ⋃_{n \in N} {S \in P (A) ∣ Card (S) = n}$ 是 $A$ 的所有基数有限子集的集族, 则易证

•	$\emptyset \in K \subseteq P (A)$
•	$(\forall a \in A) (\forall B \in K) B \cup {a} \in K$

由假设

A

是 Whitehead-Russell 有限集知

A \in K

.

$□$

注 5.20. 也可直接证明基数有限集与 Tarski 有限集等价, 事实上, 由集论知识可考虑 ${Card (K) ∣ K \in K}$ 的最小元 $k = Card (K)$ 则由有限集基本定理易证 $K$ 极小, 可见 Sierpinski 的书. 关于基数有限集与 Sierpinski-Kuratowski 有限集等价的直接证明可见 Kuratowski1920

Stäckel-Zermelo 有限集,Weber-Kürschák 有限集,Weber–Stäckel 有限集

Heinrich Martin Weber(1906,1922), József Kürschák, Paul Stäckel(1907), Zermelo(1909) 利用全序给出了有限集的刻画, 中文资料有郑太朴先生译的数学全书.

定理 5.21 (Hessenberg-Hartogs-Kuratowski 定理). 集 $A$ 上的全序与 $({K \subseteq P (A) ∣ (K, \subseteq) 是全序集}, \subseteq)$ 的极大元一一对应, 其中极大的 $K$ 对应于 Kuratowski 关系 $x \leq y : ⟺ x = y \lor (\exists X \in K) (x \in X \land y \in A ∖ X)$ 反之每个全序关系 $\leq$ 对应于 $A$ 的前段集族 $L$ .

证明.

证明. 设

K

是

({K \subseteq P (A) ∣ (K, \subseteq) 是全序集}, \subseteq)

的极大元, 首先, 反身性和反对称性显然, 若

(\exists X \in K) (x \in X \land y \in A ∖ X)

且

(\exists Y \in K) (y \in Y \land z \in A ∖ Y)

, 则

Y \neq \subseteq X

, 因此

X \subset Y

, 从而

x \in Y \land z \in A ∖ Y

, 于是

x < y < z ⟹ x < z

其次, 若

y \neq \leq x

即

x \neq = y \land (\forall Y \in K) (y \in Y ⟹ x \in Y)

, 令

P_{x} = {B \in K ∣ x \in / B}

则

x \in / ⋃ P_{x}

, 由

K

的极大性知

K = {\emptyset} \cup K

即

\emptyset \in P_{x}

, 显然

(\forall X \in P_{x}) X \subseteq ⋃ P_{x}

注意到

⟹ ⟹ ⟺ (\forall X \in K ∖ P_{x}) (\forall B \in P_{x}) x \in X \land x \in / B (\forall X \in K ∖ P_{x}) (\forall B \in P_{x}) X \neq \subseteq B (\forall X \in K ∖ P_{x}) (\forall B \in P_{x}) B \subseteq X (\forall X \in K ∖ P_{x}) ⋃ P_{x} \subseteq X

因此

(\forall X \in P_{x}) (X \subseteq ⋃ P_{x}) \lor (\forall X \in K ∖ P_{x}) (⋃ P_{x} \subseteq X)

从而也有

(\forall X \in P_{x}) (X \subseteq (⋃ P_{x}) \cup {x}) \land (\forall X \in K ∖ P_{x}) ((⋃ P_{x}) \cup {x} \subseteq X)

由

K

的极大性知

⋃ P_{x} \in K

且

(⋃ P_{x}) \cup {x} \in K

, 由

x \in / ⋃ P_{x} \in K

和假设知

y \in / ⋃ P_{x}

, 由假设

x \neq = y

知

(⋃ P_{x}) \cup {x} \in K \land x \in (⋃ P_{x}) \cup {x} \land y \in / (⋃ P_{x}) \cup {x}

最后, 对每个

X \in K

, 若

x \leq y \in X

, 则

y \neq < x

即

(\forall Y \in K) (y \in Y ⟹ x \in Y)

, 因此

x \in X

, 从而

X \in L

, 于是

K \subseteq L

, 由

K

的极大性知

K = L

反之, 设

(A, \leq)

是一个全序集, 令

K

为

(A, \leq)

的前段的族, 首先证明

(K, \subseteq)

是全序族, 事实上若

X, Y \in K

且

\exists b \in Y ∖ X

且

a \in X

, 则

b \neq < a

因此

a \leq b

从而

a \in Y

. 其次, 显然

(\forall a \in A)] \leftarrow, a [\in K

, 若

E \subseteq A

且

(\forall X \in K) (X \subseteq E \lor E \subseteq X)

且

a \in E \land b \in] \leftarrow, a [

, 由

a \in /] \leftarrow, a [

知

E \neq \subseteq] \leftarrow, a [

, 则

] \leftarrow, a [\subseteq E

, 从而

b \in E

, 因此

E \in K

, 于是

K

是极大的. 最后, 若

x < y

则存在

X =] \leftarrow, y [\in K

使得

x \in X \land y \in A ∖ X

, 而若

(\exists X \in K) (x \in X \land y \in A ∖ X)

则由

K

的定义知

y \neq \leq x

, 从而

x < y

.

$□$

推论 5.22. 集 $A$ 上的良序与 $({K \subseteq P (A) ∣ (K, \subseteq) 是良序集}, \subseteq)$ 的极大元一一对应.

证明.

证明. 设

K

是

({K \subseteq P (A) ∣ (K, \subseteq) 是良序集}, \subseteq)

的极大元, 若

(\forall X \in K) (X \subseteq Y \lor Y \subseteq X)

则易证

{Y} \cup K

的每个非空子集有

\subseteq

最小元, 从而

Y \in K

, 因此

K

也是

({K \subseteq P (A) ∣ (K, \subseteq) 是全序集}, \subseteq)

的极大元. 从而由

A ≅ {] \leftarrow, x [∣ x \in A}

知

A

良序. 反之设

A

是良序集, 则

K = {] \leftarrow, x [∣ x \in A} \cup {A}

也是良序集.

$□$

注 5.23. 另一个本质上相同的证明可见 Kuratowski1921.

定义 5.24 (Stäckel-Zermelo 有限集). 若存在集合 $A$ 上的良序 $\leq$ 使得 $(A, \leq^{o p})$ 是良序集, 则称集合 $A$ 是 Stäckel–Zermelo 有限集.

注 5.25. 有些文献中 Stäckel-Zermelo 有限集依 Zermelo 称为双重良序集 (doubly well-ordered set)

定义 5.26 (Tarski-Bourbaki 有限集). 若存在集合 $A$ 上的全序且 $A$ 上每个全序都是良序, 则称 $A$ 是一个 Tarski–Bourbaki 有限集.

注 5.27. 这里归功于 Tarski 和 Bourbaki 也许并不是最合适的, 但我没有找到更合适的文献 (如有人知道更合适的名称望请告知), 为了叙述方便权且这样称呼罢.

定理 5.28. 设 $A$ 是集合, 则下列三个命题等价

1.	集合 $A$ 是 Stäckel–Zermelo 有限集
2.	集合 $A$ 是 Whitehead–Russell 有限集
3.	集合 $A$ 是 Tarski–Bourbaki 有限集

证明.

证明. 首先, 设

A

是 Stäckel–Zermelo 有限集, 即存在良序

\leq

使得

(A, \leq^{o p})

是良序集, 不妨设

A \neq = \emptyset

且

a \in A

不是最小元, 若

(\forall x < a)] \leftarrow, x [是有限集

, 则由

] \leftarrow, a [\neq = \emptyset

可令

b = max] \leftarrow, a [

, 于是

] \leftarrow, a [=] \leftarrow, b [\cup {b}

是有限集, 由超穷归纳法知每个

] \leftarrow, a [

都是有限集, 取

a = max A

则

A =] \leftarrow, a [\cup {a}

是有限集. 其次, 设

A

是 Whitehead-Russell 有限集, 令

K = {S \in P (A) ∣ S 是 T a rs ki - B o u r baki 有限集}

, 则易证

\emptyset \in K

且

(\forall B \in K) (\forall x \in A ∖ B) (B \cup {x} \in K)

因此

A \in P (A) = K

. 最后, 设

A

是 Tarski–Bourbaki 有限集, 则存在集合

A

上的全序

\leq

且它的相反序

\leq^{o p}

也是全序, 从而都是良序, 因此

A

是 Stäckel–Zermelo 有限集.

$□$

注 5.29. 另一种利用 Hessenberg-Hartogs-Kuratowski 定理的证明方法可见 Tarski1924. 事实上, 记 $F = {K \subseteq P (A) ∣ (K, \subseteq) 是全序集}$ , 则 $P (A)$ 和 $P (P (A))$ 是有限集, 由 $\emptyset \in F \subseteq P (P (A))$ 知 $F$ 有极大元 $K$ 且 $K$ 有限, 则 $(K, \subseteq)$ 有极大极小元. 这里证明的第二部分本质上与滤过范畴引理相同

推论 5.30. 集合 $A$ 是有限集当且仅当存在 $A$ 上的全序且 $A$ 上任意两个全序同构

证明.

证明. 若

A

是有限集, 则存在

A

上的全序

\leq

且

A

上任意全序都是良序, 从而由 Cantor 良序集比较定理知

A

上任意两个全序同构. 反之, 若存在

A

上的全序

\leq

且

A

上任意两个全序同构, 则

$□$

推论 5.31. 集合 $A$ 上每个全序都是良序蕴含 $A$ 有限当且仅当 $A$ 上存在全序.

证明.

证明. 用反证法. 若

A

上每个全序都是良序蕴含

A

有限且

A

上不存在全序, 则

A

上每个全序都是良序, 从而

A

有限, 与假设

A

上不存在全序矛盾. 反之亦然.

$□$

定义 5.32 (Weber–Stäckel 有限集). 若存在集合 $A$ 上全序 $\leq$ 使得 $(A, \leq)$ 和 $(A, \leq^{o p})$ 的每个非空前段都有最小元和最大元, 则称 $A$ 为 Weber–Stäckel 有限集.

注 5.33. 显然要求每个中间元素有紧接前后元是不够的, 例如 $ω + ω^{o p}$ 型集无穷.

定义 5.34 (Weber–Kürschák 有限集). 若集合 $A = \emptyset$ 或对于每个全序集 $(A, \leq)$ 有最小元, 则称 $A$ 是一个 Weber–Kürschák 有限集.

定理 5.35. 设 $A$ 是集合, 则下列三个命题等价

1.	集合 $A$ 是 Stäckel–Zermelo 有限集
2.	集合 $A$ 是 Weber–Stäckel 有限集
3.	集合 $A$ 是 Weber–Kürschák 有限集

证明.

证明. 显然 Stäckel–Zermelo 有限集是 Weber–Stäckel 有限集.

$□$