集合论

• 2022 年 8 月 22 日
• 笔记
• 数学, 数学分析

我们现在介绍集合论中的一些概念和记号，他们通常被广泛而频繁地被用到。几乎所有数学分支领域都将集合论作为其基础。因此在学习高级的数学领域之前，学习集合论中的一些基础概念是非常重要的。我们下面给出公理集合论中的部分（较为初等）的内容，可以证明，我们将要建立的集合公理体系是等价于ZF公理集合论的。

3.1 基本事项

首先，集合是一个不加定义的原始概念，这意味着我们不打算构造出集合这个概念，而是使用公理来规范化它。我们并不会知道什么是集合，我们只是列出集合可以进行的运算和性质。我们认为，一个集合始终是一个对象。

然后我们定义一个对象 \(o\) 和集合 \(A\) 之间的二元关系 \(\in\)，且称 \(o\in A\) 为 “\(o\) 属于 \(A\)” 或 “\(A\) 包含 \(o\)” 或 “\(o\) 是 \(A\) 的元素”。特别地，由于集合是对象，询问一个集合是否属于另一个集合是有意义的。

注：根据定义，“集合内不能有重复的元素” 这种说法是荒谬的。而下文中，“\(A\) 的每个元素都……” 的含义是 “对于任意的对象 \(x\) 满足 \(x\) 是 \(A\) 的元素，\(x\) 都满足……”。即，我想强调的是，“元素”描述的是一种关系，而不是一个对象。

纯粹集合论认为一切对象都是集合。从逻辑学的角度来看，纯粹集合论确实是一种更加简单的理论，人们只需要处理集合，而无需考虑其他对象。然而我们从概念角度来说，不纯粹的集合论的处理更加容易（例如，纯粹集合论可以把 \(0\) 看做 \(\varnothing\)，\(1\) 看做 \(\left\{\varnothing\right\}\)，\(2\) 看做 \(\left\{\left\{\varnothing\right\}\right\}\)，以此类推）。单纯从应用的角度来看，两种想法集合是等价的。因此，对于一切对象是否都是集合，我们采取不可知的态度。即我们既不添加公理确认这一点，也不添加公理否认这一点，而在现在的公理体系中，命题“一切对象都是集合”是未决的（不能证明也不能推翻）。

我们先在 \(\in\) 的基础之上扩展一些仅适用于集合间的二元关系。

• 定义 3.1.1（子集）：设 \(A,B\) 是集合，定义 \(A\subseteq B\)（称为 “\(A\) 是 \(B\) 的子集” 或 “\(A\) 包含于 \(B\)” 或 “\(B\) 包含 \(A\)“），当且仅当 \(A\) 的每个元素都是 \(B\) 的元素。形式化地说 \(A\subseteq B\iff\forall_{x\in A}x\in B\)。

  定义 \(A\subsetneq B\)（称为 “\(A\) 是 \(B\) 的真子集” 或 “\(A\) 真包含于 \(B\)” 或 “\(B\) 真包含 \(A\)“），当且仅当 \(A\subseteq B\) 且 \(B\nsubseteq A\)。

• 命题 3.1.2（集合的包含关系的基本性质）：设 \(A,B,C\) 为集合，那么：

  • 自反性：\(A\subseteq A\)。

    证明：根据定义可得。

  • 传递性：若 \(A\subseteq B\) 且 \(B\subseteq C\)，则 \(A\subseteq C\)。

    证明：根据定义，\(A\) 的每个元素都是 \(B\) 的元素，\(B\) 的每个元素都是 \(C\) 的元素，那么 \(A\) 的每个元素都是 \(C\) 的元素。

  • 混合传递性：若 \(A\subsetneq B\) 且 \(B\subseteq C\)，则 \(A\subsetneq C\)；若 \(A\subseteq B\) 且 \(B\subsetneq C\)，则 \(A\subsetneq C\)。

    证明：两者类似，证前面那个。首先 \(A\subseteq B\) 且 \(B\subseteq C\) 可知 \(A\subseteq C\)，然后由于 \(B\nsubseteq A\)，故存在一个对象 \(x\) 满足 \(x\) 是 \(B\) 的元素而非 \(A\) 的元素，又 \(B\) 的元素都是 \(C\) 的元素，故存在一个对象 \(x\) 满足 \(x\) 是 \(C\) 的元素而非 \(A\) 的元素，故 \(C\nsubseteq A\)，那么 \(A\subsetneq C\)。

集合的真包含关系显然是一种偏序关系，因为我们知道对于任意两个集合 \(A\) 和 \(B\)，不可能同时成立 \(A\subsetneq B\) 和 \(B\subsetneq A\)。但是真包含关系与我们定义在自然数上的小于关系 \(<\) 的不同之处在于，后者是一种全序关系。在满足偏序性质的基础上，我们还知道对于两个不相等的数 \(a\) 和 \(b\)，要么成立 \(a>b\)，要么成立 \(b>a\)。对于集合的真包含关系而言，这一条性质是不满足的。考虑集合 \(A=\left\{1,2\right\}\) 和 \(B=\left\{2,3\right\}\)，它们既不相等，也没有哪一个是另一个的真子集。

• 定义 3.1.3（集合之相等）：设 \(A,B\) 是集合，定义 \(A=B\)（称为 \(A,B\) 相等），当且即当 \(A\subseteq B\) 且 \(B\subseteq A\)。

• 命题 3.1.4（集合的相等关系的基本性质）：设 \(A,B,C\) 为集合，那么：

  • 自反性：\(A=A\)。证明：根据命题 3.1.2 可知 \(A\subseteq A\)。

  • 对称性：若 \(A=B\)，则 \(B=A\)。证明：根据定义可知。

  • 传递性：若 \(A=B,B=C\)，则 \(A=C\)。证明：根据命题 3.1.2 可知 \(A\subseteq C\) 且 \(C\subseteq A\)。

可以证明 “若 \(A=B\)，则 \(x\in A\iff x\in B\)”，即集合关于命题 “某个对象 \(x\) 是否属于该集合 ” 遵从代入公理。

• 引理 3.1.5（集合构造的唯一性）：若存在集合 \(S\)，满足 \(x\in S\iff P(x)\)，其中 \(P(x)\) 是某个关于任意对象 \(x\) 的命题，那么 \(S\) 唯一。

  证明：若存在两个集合 \(S,S’\) 都满足条件，那么 \(x\in S\iff P(x)\iff x\in S’\)，于是 \(S=S’\)。

接下来运用公理构建集合时，我们都使用该引理来说明构建的集合的唯一性。

类似自然数，我们将从空集开始，然后借助几个运算公理化更多的集合。

• 公理 3.1.6（空集）：存在一个集合 \(\varnothing\)（空集），对于任意的 \(x\)，\(x\not\in \varnothing\)。

• 公理 3.1.7（单元素集）：对于任意一个对象 \(a\)，存在一个集合 \(\{a\}\)，它唯一的元素是 \(a\)。称这样的集合为单元素集。

• 公理 3.1.8（双并）：对于两个集合 \(A,B\)，存在一个集合 \(A\cup B\)，称为 \(A\) 和 \(B\) 的并，其元素由属于 \(A\) 或属于 \(B\) 的一切元素组成。即，对于任意对象 \(x\)，

  \[x\in A\cup B\iff (x\in A \lor x\in B)
  \]

容易证明并运算满足交换律和结合律。容易证明 \(A\cup \varnothing=A\)。

根据双并公理，我们可以定义双元素集：

• 定义 3.1.9（双元素集）：若 \(a\) 和 \(b\) 是两个对象，根据双并公理，存在一个集合 \(\{a,b\}=\{a\}\cup\{b\}\)，其仅有的元素是 \(a\) 和 \(b\)。即，对于每个对象 \(y\)，有 \(y\in\{a,b\}\iff (y\in a\lor y\in b)\)。

类似地，我们可以定义三元素集、四元素集，依此类推。

但另一方面，我们还不能对于任意给定的自然数 \(n\) 定义由 \(n\) 个对象组成的集合。这将要求重复使用双并公理 \(n\) 次，然而 \(n\) 次重复的概念尚不曾被严格地定义（没有关于集合的归纳方法）。根据类似的理由，我们也还不能定义由无限多个对象组成的集合。

• 公理 3.1.10（分类公理）：设 \(A\) 是一个集合，并对于每个 \(x\in A\)，设 \(P(x)\) 是一个关于 \(x\) 的命题。那么存在一个集合 \(\{x\in A:P(x)\}\)（或 \(\{x\in A|P(x)\}\)），它的元素恰恰是 \(A\) 中使 \(P(x)\) 成立的 \(x\)。即，对于任意对象 \(y\)，

  \[y\in\{x\in A:P(x)\}\iff (y\in A\land P(y))
  \]

分类可以看成关于集合 \(A\) 和命题 \(P\) 的运算。可以证明 “若 \(A=B\)，则 \(\{x\in A:P(x)\}=\{x\in B:P(x)\}\)”，即集合关于分类运算遵从代入公理。

利用分类运算和分类公理，我们可以定义集合的其他一些运算。

• 定义 3.1.11（交）：两个集合 \(A\) 和 \(B\) 的交 \(A\cap B\) 定义为集合 \(\{x\in A:x\in B\}\)。根据分类公理，\(A\cap B\) 存在。

  定义两个集合是不交的，当且仅当 \(A\cap B=\varnothing\)。

• 定义 3.1.12（差集）：两个集合 \(A\) 和 \(B\) 的差 \(A\setminus B\) 定义为集合 \(\{x\in A:x\not\in B\}\)。根据分类公理，\(A\setminus B\) 存在。

• 命题 3.1.13（集合构成一个布尔代数）：

  设 \(A,B,C,X\) 均为集合，且满足 \(A,B,C\subseteq X\)。

  1. 最小元：\(A\cup\varnothing=A\) 以及 \(A\cap\varnothing=\varnothing\)。
  2. 最大元：\(A\cup X=X\) 以及 \(A\cap X=A\)。
  3. 恒等式：\(A\cup A=A\) 以及 \(A\cap A=A\)。
  4. 交换律：\(A\cup B=B\cup A\) 以及 \(A\cap B=B\cap A\)。
  5. 结合律：\(A\cup(B\cup C)=(A\cup B)\cup C\) 以及 \(A\cap(B\cap C)=(A\cap B)\cap C\)。
  6. 分配律：\(A\cap(B\cup C)=(A\cap B)\cup(A\cap C)\) 以及 \(A\cup(B\cap C)=(A\cup B)\cap(A\cup C)\)。
  7. 分差法则：\(A\cup(X\setminus A)=X\) 以及 \(A\cap(X\setminus A)=\varnothing\)。
  8. 摩根定律：\(X\setminus(A\cup B)=(X\setminus A)\cap(X\setminus B)\)。

这些公理还不能满足我们的要求，例如把集合中的元素每个都加上 \(1\)，把 \(\left\{1,6, 15\right\}\) 变为 \(\left\{2,7,16\right\}\)，这是我们现在有的公理无法办到的。我们需要更加强大的数学工具，因此让我们再添加一个公理：

• 公理 3.1.14（替换公理）：设 \(A\) 是一个集合，\(P(x,y)\) 是关于任意对象 \(x\in A\) 和任意对象 \(y\) 的命题，且满足对于每个 \(x\in A\) 存在至多一个 \(y\) 使得 \(P(x,y)\) 成立。那么存在一个集合 \(\{y:\exists_{x\in A},P(x,y)\}\)，使得对于任何对象 \(z\)

  \[z\in\{y:\exists_{x\in A},P(x,y)\}\iff \exists_{x\in A},P(x,z)
  \]

  我们常把形如 \(\{y:\exists_{x\in A},y=f(x)\}\) 的集合简写成 \(\{f(x):x\in A\}\)。

注意到，替换公理蕴含分类公理，我们只需令 \(P(x,y)\iff x=y\land Q(x)\) 即可构造出集合 \(\{x\in A:Q(x)\}\)。

接下来，我们将引入无限集合：

• 公理 3.1.15（无穷大）：存在一个集合 \(\mathbb{N}\)，其元素叫作自然数，满足 \(0\) 是 \(\mathbb{N}\) 中的一个对象，并且对于任意 \(n\in\mathbb{N}\)，由 \(n\) 所指定的满足皮亚诺公理的后继对象 \(n^+\) 也在 \(\mathbb{N}\) 中。

这是假设 2.1.6 的更正式的形式。自然数集引入了无限集合的一个最基本的例子。

3.2 万有分类公理

从分类公理更进一步，我们考虑拓展出一个新的公理并将其加入集合论公理之中：

• 公理 3.2.1（万有分类公理）：设 \(P(x)\) 是关于任意对象 \(x\) 的命题，那么存在一个集合 \(\{x:P(x)\}\)，使得对于任何对象 \(y\)，

  \[y\in\{x:P(x)\}\iff P(y)
  \]

该公理断言每个性质对应一个集合，这也就是朴素的集合思想。这个公理蕴含了我们已经讨论过的公理，但这个公理不能被引入集合论，因为它引出了一个逻辑上的矛盾：

罗素悖论：

根据万有分类公理，有集合：

\[\Omega:=\{x:\text{$x$是集合且$x\not\in x$}\}
\]

即一切不以自己为元素的集合的集合。那么现在问 \(\Omega\) 是否属于 \(\Omega\)，发现不管 \(\Omega\) 是否属于 \(\Omega\)，都会引出矛盾。

为了解决这个悖论，我们考虑把对象按照一定的层次结构排列。在层级结构最底层的是原始对象（不是集合的对象），在下一层次中则存在一些集合，但是这些集合的元素只能是原始对象。以此类推，一层次中存在的集合只能包含之前层次中的对象。这种想法引导出了正则公理。

• 公理 3.2.2 （正则公理） ：对于一个非空的集合 \(A\)，\(A\) 中至少存在一个元素 \(x\) 满足 \(x\) 不是集合或 \(A\cap x=\varnothing\)。

正则公理的一个重要推论是一个集合不能包含其本身，但是可以包含其他（更低层次的）集合。这使得我们排除了罗素悖论中定义的集合 \(\Omega\)。

• 命题 3.2.3（集合不能包含其本身）：设 \(A\) 为一个集合，那么 \(A\not\in A\)。

  证明：（反证法）假设存在一个集合 \(A\)，满足 \(A\in A\)。根据单元素公理，存在一个集合 \(B=\left\{A\right\}\)。\(B\) 是一个非空的集合，因此根据正则公理，应该存在 \(x\in B\)，满足 \(x\) 不是集合或 \(A\cap x=\varnothing\)，但是集合 \(B\) 作为单元素集，只有 \(A\in B\)，而 \(A\) 是一个集合，且 \(A\cap B=A\)，故 \(B\) 集合违反正则公理，矛盾，假设不成立。原命题得证。

3.3 函数

• 定义 3.3.1（函数/映射/变换）：设 \(X,Y\) 是集合，\(P(x,y)\) 是关于任意对象 \(x\in X\) 和任意对象 \(y\in Y\) 的命题，使得对于每个对象 \(x\in X\) 存在恰好一个 \(y\in Y\) 使得 \(P(x,y)\) 成立。那么我们定义由 \(P\) 在 \(X\) 和 \(Y\) 上确定的函数 \(f:X\to Y\) 是这样的对象，它对于任意的输入 \(x\in X\)，将指定一个输出 \(f(x)\in Y\)，满足

  \[y=f(x)\iff P(x,y)
  \]

  根据 \(P(x,y)\) 的定义，对于任意 \(x\in X\)，\(f(x)\) 存在且唯一。

  定义函数 \(f\) 的定义域为 \(X\)，对应域为 \(Y\)，值域为 \(f(X):=\{f(x):x\in X\}\)，那么值域为对应域的子集。

有时我们在定义函数时，为了方便，在确定完其定义域 \(X\) 后，直接指定从输入 \(x\) 得到输出 \(f(x)\) 的过程（procedure）（即如何从 \(x\) 得到 \(f(x)\)）来定义 \(f\)。其真正的过程如下：在确定完定义域 \(X\) 之后，先定义 \(P(x,y)\) 表示命题 “\(y\) 是 \(x\) 经过 procedure 过程得到的结果”，若未给出对应域，再令对应域为 \(Y:=\{y:\exists_{x\in X},P(x,y)\}\)（可以发现此时对应域和值域相等），然后再定义 \(f\) 为由 \(P\) 在 \(X\) 和 \(Y\) 上确定的函数。

易证对象关于函数遵从代入公理：如果 \(x=x’\)，那么 \(f(x)=f(x’)\)。当然前提是 \(x\) 关于 \(P(x,y)\) 遵从代入公理。

有时函数的变元用下标来表示以取代括号，如，一个自然数序列 \(a_0,a_1,\cdots\) 严格地说是一个从 \(\mathbb N\) 到 \(\mathbb N\) 的函数，而 \(a_n\) 其实就是 \(a(n)\)。

• 定义 3.3.2（函数相等）：对于两个函数 \(f\) 和 \(g\)，称它们是相等的（记为 \(f=g\)），当且仅当它们含有相同的定义域 \(X\) 和对应域 \(Y\)，且对于任意 \(x\in X\)，\(f(x)=g(x)\)。

容易验证函数相等是自反、传递、对称的。

对于函数，一个基础性的可执行的运算是复合。

• 定义 3.3.3（复合）：设 \(f:X\to Y\) 和 \(g:Y\to Z\) 是两个函数，其中 \(f\) 的对应域等于 \(g\) 的定义域。那么可以定义两个函数 \(g\) 与 \(f\) 的复合：

  \[(g\circ f)(x):=g(f(x))
  \]

  容易证明，对于任意 \(x\in X\)，\(g(f(x))\) 存在且唯一。

易证函数关于复合遵从代入公理：如果 \(f=f’\)，那么 \(g\circ f=g\circ f’\)；如果 \(g=g’\)，那么 \(g\circ f=g’\circ f\)。

• 引理 3.3.4（复合是结合的）：\(f\circ \left(g\circ h\right)=(f\circ g)\circ h\)。证明：根据定义可知。

我们再来描述其他一些有关函数的概念。

• 定义 3.3.5（单射）：一个定义域为 \(X\) 的函数 \(f\) 是单射当且仅当对于任意的 \(x\in X\) 和任意的 \(x’\in X\)，若 \(x\neq x’\)，则 \(f(x)\neq f(x’)\)。

• 定义 3.3.6（满射）：一个定义域为 \(X\) 对应域为 \(Y\) 的函数 \(f\) 是满射当且仅当 \(Y=f(X)\)。

• 定义 3.3.7（双射/一一对应）：一个函数是双射的当且仅当它既是单射的，又是满射的。

  该定义也等价于，对于每个 \(y\in Y\)，恰有一个 \(x\in X\) 使得 \(f(x)=y\)（至多一个意味着单射，至少一个意味着满射），记为 \(f^{-1}(y)\)，那么 \(f^{-1}\) 就是一个从 \(Y\) 到 \(X\) 的函数。此时称 \(f^{-1}\) 为 \(f\) 的逆。

3.4 象和逆象

• 定义 3.4.1（集合的象）：设函数 \(f:X\to Y\)，设 \(S\) 是 \(X\) 的一个子集，定义 \(S\) 在映射 \(f\) 下的象为

  \[f(S):=\{f(x):x\in S\}
  \]

• 定义 3.4.2（逆象）：设 \(T\) 是 \(Y\) 的一个子集，定义 \(T\) 在映射 \(f\) 的逆象为

  \[f^{-1}(T):=\{x\in S:f(x)\in T\}
  \]

注意函数也是对象，特别地我们可以考虑函数的集合，这里我们向考虑从一个集合 \(X\) 到一个集合 \(Y\) 的一切函数组成的集合。为此，我们引入公理：

• 公理 3.4.3（幂集公理）：设 \(X\) 和 \(Y\) 是集合，那么存在一个集合 \(Y^X\)，满足 \(f\in Y^X\) 当且仅当 \(f\) 是一个以 \(X\) 为定义域以 \(Y\) 为对应域的函数。

此公理的一个结果是：

• 引理 3.4.9（幂集存在性）：设 \(X\) 是一个集合，那么存在集合 \(\{Y:Y\subseteq X\}\)（也记作 \(2^X\)，称为 \(X\) 的幂集），使得对于任意对象 \(Z\)

  \[Z\in\{Y:Y\subseteq X\}\iff Z\subseteq X
  \]

  证明：设集合 \(Y=\{0,1\}\)。

  设 \(P(f,S)\) 是关于映射 \(f\in Y^X\) 和任意对象 \(S\) 的命题，满足 \(P(f,S)\) 为真当且仅当 \(S\) 是 \(X\) 的子集且 \(\forall_{x\in X},f(x)=1\iff x\in S\)。

  根据引理 3.1.5，容易证明，对于每个 \(f\in Y^X\)，都恰好存在唯一的 \(S:=\{x\in X:f(x)=1\}\) 使得 \(P(f,S)\) 为真。

  根据替换公理，存在集合 \(A:=\{S:\exists_{f\in Y^X},P(f,S)\}\)。那么 \(Z\in A\implies Z\subseteq X\)。

  为证 \(Z\subseteq X\implies(Z\in A\iff \exists_{f\in Y^X},P(f,Z))\)，我们构造函数 \(f(x):=[x\in Z]\) 即可。

  于是 \(Z\in A\iff Z\subseteq X\)，得证。

为了完整起见，我们现在再往集合论中添加一条公理，它扩充了双并公理而允许做出更大的并集。

• 公理 3.4.10（并）：设 \(A\) 是集类（即它的每个元素都是一个集合），那么存在一个集合 \(\bigcup A\)，使得对于任意对象 \(x\)

  \[x\in \bigcup A\iff \exists_{S\in A},x\in S
  \]

该公理的一个重要的结果是：

• 定义 3.4.11（集族的并）：设 \(I\) 为一集合，且对于任意 \(\alpha\in I\)，都映射到一个集合 \(A_{\alpha}\)。

  此时我们称 \(I\) 为指标集，称 \(I\) 的元素 \(\alpha\) 为标签，称 \(\{A_{\alpha}:\alpha\in I\}\) 为一个集族，其中的元素是贴有标签 \(\alpha\in I\) 的。

  定义集族 \(\{A_{\alpha}:\alpha\in I\}\) 的并为集合 \(\bigcup_{\alpha\in I}A_{\alpha}:=\bigcup\{A_{\alpha}:\alpha\in I\}\)。那么对于任意对象 \(y\)

  \[y\in\bigcup_{\alpha\in I}A_{\alpha}\iff \exists_{\alpha\in I},y\in A_{\alpha}
  \]

  注意到，当 \(I\) 为空集时，集族的并也为空集。

对称地，尽管不需要用到并公理，我们定义：

• 定义 3.4.12（集族的交）：设 \(I\) 为一非空集合，且对于任意 \(\alpha\in I\)，都映射到一个集合 \(A_{\alpha}\)。

  由于 \(I\) 非空，那么存在某个对象 \(\beta\in I\)。然后定义集族 \(\{A_{\alpha}:\alpha\in I\}\) 的交为集合 \(\bigcap_{\alpha\in I}A_{\alpha}:=\{x\in A_{\beta}:\forall_{\alpha\in I},x\in A_{\alpha}\}\)。那么对于任意对象 \(y\)

  \[y\in \bigcap_{\alpha\in I}A_{\alpha}\iff \forall_{\alpha\in I},x\in A_{\alpha}
  \]

  注意，该定义不依赖于 \(\beta\) 的选择。

集合论的这些我们已经引入的公理统称为ZF公理集合论（Zermelo-Fraenkel Set Theory，策梅洛-弗兰克尔集合论）。后面我们将还需要一个更进一步的公理，即著名的选择公理，它们统称为集合论的ZFC公理集合论（Zermelo-Fraenkel-Choise Set Theory，策梅洛-弗兰克尔-选择集合论）。

3.5 笛卡尔积

• 定义 3.5.1（序偶/有序对）：设 \(x\) 和 \(y\) 是两个对象（可以相等），定义序偶 \((x,y):=\{\{x\},\{x,y\}\}\)，定义 \(x\) 为它的第一个分量而 \(y\) 为它的第二个分量。

  可以证明，两个序偶 \((x,y)\) 和 \((x’,y’)\) 相等，当且仅当 \(x=x’\land y=y’\)。

• 定义 3.5.2（笛卡尔积）：设 \(X\) 和 \(Y\) 是集合，定义它们的笛卡尔积为集合 \(X\times Y\)（或记作 \(\{(x,y):x\in X,y\in Y\}\)），使得对于任意的对象 \(a\)

  \[a\in X\times Y\iff \exists_{x\in X,y \in Y},a=(x,y)
  \]

  证明：首先，对于每个 \(x\in X\)，存在一个集合 \(A_x:=\{(x,y):y\in Y\}\)。

  再构造集合 \(B=\bigcup_{x\in X}A_x\)。发现对于任意对象 \(a\)，\(a\in B\iff \exists_{x\in X,y \in Y},a=(x,y)\)，得证。

设 \(f:X\times Y\to Z\) 是一个函数。我们认为，\(f\) 即是以 \(X\times Y\) 为定义域的单变元函数，也是以 \(X\) 和 \(Y\) 同为定义域的两个变元的函数。

现在我们扩展序偶的概念。

• 定义 3.5.3（有序 \(n\) 元组/\(n\) 元序列）：设 \(n\) 是自然数，定义一个有序 \(n\) 元组为一个函数 \(x:\{i\in\mathbb{N}:1\leqslant i\leqslant n\}\to X\)，其中 \(X\) 是任意的某个集合，满足 \(x\) 是满射。我们把 \(x(i)\) 写成 \(x_i\)，称为第 \(i\) 个分量，并把 \(x\) 写成 \((x_i)_{1\leqslant i\leqslant n}\)。

  那么可以证明，两个有序 \(n\) 元组 \((x_i)_{1\leqslant i\leqslant n}\) 和 \((y_i)_{1\leqslant i\leqslant n}\) 是相等的，当且仅当对于任意自然数 \(1\leqslant i\leqslant n\)，\(x_i=y_i\)。

• 定义 3.5.4（\(n\) 重笛卡尔积）：设 \((X_i)_{1\leqslant i\leqslant n}\) 是一个集合的有序 \(n\) 元组，我们定义此组的诸分量的笛卡尔积为集合 \(\prod_{1\leqslant i\leqslant n}X_i\)（或记作 \(\prod_{i=1}^n X_i\) 或 \(X_1\times\cdots\times X_n\) 或 \(\{(x_i)_{1\leqslant i\leqslant n}:\forall_{1\leqslant i\leqslant n},x_i\in X_i\}\)），使得对于任意的对象 \(a\)

  \[a\in \prod_{1\leqslant i\leqslant n}X_i\iff \bigg(a=(x_i)_{1\leqslant i\leqslant n}\land (\forall_{1\leqslant i\leqslant n},x_i\in X_i)\bigg)
  \]

  证明：考虑集合 \(A:=\left(\bigcup_{1\leqslant i\leqslant n}X_i\right)^{\{i\in\mathbb N:1\leqslant i\leqslant n\}}\)，\(B:=\{x\in A:\forall_{1\leqslant i\leqslant n},x_i\in X_i\}\)，容易发现集合 \(B\) 即为所求。

设 \(f:X_1\times X_2\times X_3\to Y\) 是一个函数。我们认为，\(f\) 可以被看做是一个变元 \((x_1,x_2,x_3)\in X_1\times X_2\times X_3\) 的函数，或三个变元 \(x_1\in X_1,x_2\in X_2,x_3\in X_3\) 的函数，或两个变元 \(x_1\in X_1,(x_2,x_3)\in X_2\times X_3\) 的函数，诸如此类。我们将不在乎这些不同的看法，而假装它们实际上是相同的。

• 引理 3.5.5（有限选择）：设 \((X_i)_{1\leqslant i\leqslant n}\) 是一个非空集合的 \(n\) 元序列，那么 \(\prod_{1\leqslant i\leqslant n}X_i\) 也非空，即存在一个 \(n\) 元序列 \((x_i)_{1\leqslant i\leqslant n}\) 使得对于任意自然数 \(1\leqslant i\leqslant n\)，\(x_i\in X_i\)。

  证明：对 \(n\) 归纳。每次选择一个 \(a\in X_{n^+}\) 并令 \(x_{n^+}=a\)。

3.6 集合的基数

• 定义 3.6.1（相同的基数）：称两个集合 \(X\) 和 \(Y\) 具有相同基数当且仅当存在一个 \(X\) 与 \(Y\) 间的双射 \(f:X\rightarrow Y\)。

容易证明，“有相同的基数”这一概念是一个等价关系，满足自反性、对称性、传递性。对于一个有限集，我们可以用一个自然数来表示其集合的大小，即其所含元素的个数。

• 定义 3.6.2（基数）：设 \(n\) 是自然数。称一个集合 \(X\) 具有基数 \(n\)（或称 \(X\) 有 \(n\) 个元素，记作 \(\operatorname{card}X\)），当且仅当它与集合 \(\{i\in\mathbb N:1\leqslant i\leqslant n\}\) 具有相同的基数。

• 引理 3.6.3（基数的非退化性）：\(X=\varnothing\iff\operatorname{card}X=0\)，即一个集合 \(X\) 具有基数 \(0\) 当且仅当 \(X\) 为空集，且若 \(X\) 为空集，则 \(X\) 仅具有基数 \(0\)。

  证明：证明不存在空集与非空集间的双射即可。

• 引理 3.6.4（基数的可减性）：设集合 \(X\) 具有基数 \(n^+\)（则 \(X\) 非空），若 \(x\in X\)，那么 \(X\setminus \{x\}\) 有基数 \(n\)。

  证明：根据假设，存在一个 \(X\) 到 \(\{i\in\mathbb N:1\leqslant i\leqslant n^+\}\) 的双射 \(f\)。现在定义一个 \(X\setminus\{x\}\) 到 \(\{i\in \mathbb N:1\leqslant i\leqslant n\}\) 的函数 \(g\)。分两种情况讨论：

  • 若 \(f(x)=n^+\)，那么对于任意 \(y\in X\setminus\{x\}\)，定义 \(g(y):=f(y)\)。

  • 若 \(f(x)\neq n^+\)，那么对于任意 \(y\in X\setminus\{x\}\)，若 \(f(y)\neq n^+\)，则定义 \(g(y):=f(y)\)；若 \(f(y)=n^+\)，则定义 \(g(y):=f(x)\)。

  可以证明，按上述定义的函数 \(g\) 存在且唯一，且 \(g\) 是双射。

• 命题 3.6.5（基数的唯一性）：设集合 \(X\) 具有基数 \(n\)，那么对于任意 \(m\neq n\)，\(X\) 不具有基数 \(m\)。

  证明：对 \(n\) 进行归纳。当 \(n=0\) 时，根据引理 3.6.3 可知命题成立。

  归纳地假设命题对 \(n\) 成立。设集合 \(X\) 具有基数 \(n^+\)（则 \(X\) 非空），反证地设其又具有基数 \(m^+\neq n^+\)，\(X\) 非空意味着存在 \(x\in X\)，那么对于集合 \(X\setminus\{x\}\)，它既具有基数 \(n\)，有具有基数 \(m\neq n\)，矛盾，故命题对 \(n^+\) 成立。故命题对任意自然数 \(n\) 成立，得证。

• 定义 3.6.6（有限集）：称一个集合是有限的，当且仅当它具有基数 \(n\)（那么 \(n\) 唯一）；否则称该集合为无限的。

注意到，两个集合具有相同的基数，必要条件是它们同为有限集或同为无限集，而对于有限集，我们往后也不会用其他的方式来定义它另外具有的基数，所以对于有限集 \(X\)，设它具有基数 \(n\)，那么我们不妨直接称 \(X\) 的基数为 \(\operatorname{card}X=n\)。

• 定理 3.6.7：\(\mathbb N\) 是无限集。

  证明：反证法。若 \(\mathbb N\) 存在基数 \(n\)，那么存在一个 \(\{i\in\mathbb N:1\leqslant i\leqslant n\}\) 到 \(\mathbb N\) 的双射 \(f\)。

  通过对 \(n\) 归纳，可以证明序列 \(f(1),\cdots,f(n)\) 是有界的：存在一个自然数 \(M\)，使得 \(\forall_{1\leqslant i\leqslant n},f(i)\leqslant M\)。

  那么自然数 \(M+1\) 就不等于任何 \(f(i)\)，这与 \(f\) 是双射矛盾。

应用到集合论公理和定义上，我们给出关于有限集的基数的一些基本性质：

• 命题 3.6.8（基数算术）：基数满足如下性质：

  1. 设 \(X\) 是有限集，并设 \(x\) 是一个不属于 \(X\) 的对象。那么 \(X\cup\{x\}\) 为有限集且 \(\operatorname{card}X\cup\{x\}=\operatorname{card}X+1\)。

     证明：在原来映射的基础上，再将 \(x\) 映射到 \(\operatorname{card}(X)+1\) 即可。

  2. 设 \(X\) 是有限集，并设 \(Y\) 是 \(X\) 的子集。那么 \(Y\) 是有限集且 \(\operatorname{card}Y\leqslant \operatorname{card}X\)，当且仅当 \(X=Y\) 时取等号。

     证明：设 \(P(n)\) 表示对于任意有限集 \(X\) 满足 \(\operatorname{card}X=n\)，上述命题成立。我们只需证明对于任意自然数 \(n\) 有 \(P(n)\) 成立即可。对 \(n\) 进行归纳。当 \(n=0\) 时，\(X\) 为空集，命题显然成立。

     归纳地假设 \(P(n)\) 成立。对于任意有限集 \(X\) 满足 \(\operatorname{card}X=n^+\) 及任意 \(Y\subseteq X\)，

     1. 若 \(Y=X\)，则 \(Y\) 是有限集且 \(\operatorname{card}Y=\operatorname{card}X\)。

     2. 若 \(Y\neq X\) 即 \(X\not\subseteq Y\)，则存在 \(x\in X\) 满足 \(x\not\in Y\)，考虑集合 \(X\setminus\{x\}\)，根据引理 3.6.4，该集合是有限集且其基数为 \(n\)。容易证明 \(Y\subseteq X\setminus\{x\}\)，那么根据归纳，\(Y\) 是有限集且 \(\operatorname{card}Y\leqslant \operatorname{card}(X\setminus\{x\})<\operatorname{card}X\)。

     于是 \(P(n^+)\) 成立。于是对于任意自然数 \(n\) 有 \(P(n)\) 成立。

  3. 设 \(X\) 和 \(Y\) 是有限集，那么 \(X\cup Y\) 是有限集且 \(\operatorname{card}(X\cup Y)\leqslant \operatorname{card}X+\operatorname{card}Y\)，当且仅当 \(X,Y\) 不交时等号成立。

     证明：设 \(\operatorname{card}X=n\) 且 \(\operatorname{card}Y=m\)，根据定义，存在双射 \(f:X\to \{i\in\mathbb N:1\leqslant i\leqslant n\}\) 和 \(g:Y\to \{i\in\mathbb N:1\leqslant i\leqslant m\}\)。

     考虑构建双射 \(h\)，其定义域为 \(X\cup Y\)，满足对于任意 \(x\in X\cup Y\)：若 \(x\in X\)，则 \(h(x):=f(x)\)；若 \(x\not\in X\)，则 \(h(x):=n+g(x)\)。容易证明满足该定义的双射 \(h:X\cup Y\to (Z=h(X\cup Y))\) 存在，且 \(Z\subseteq \{i\in\mathbb N:1\leqslant i\leqslant n+m\}\)。

     根据 3.6.8.2，可知 \(Z\) 为有限集且 \(\operatorname{card}Z\leqslant n+m\)，当且仅当 \(Z=\{i\in\mathbb N:1\leqslant i\leqslant n+m\}\) 时取等。那么 \(X\cup Y\) 也为有限集且 \(\operatorname{card}(X\cup Y)\leqslant n+m\)，当且仅当 \(h(X\cup Y)=\{i\in\mathbb{N}:1\leqslant i\leqslant n+m\}\)，即 \(X\cap Y=\varnothing\) 时等号成立。

  4. 设 \(X\) 是有限集，且 \(f:X\to Y\) 是一个函数，那么 \(f(X)\) 是有限集且 \(\operatorname{card}f(X)\leqslant \operatorname{card}X\)，当且仅当 \(f\) 为单射时取等。

     证明：仍用与 3.6.8.2 类似的证明方法。设 \(P(n)\) 表示对于任意有限集 \(X\) 满足 \(\operatorname{card}X=n\)，上述命题成立。当 \(n=0\) 时，\(X,f(X)\) 为空集，命题显然成立。

     归纳地假设 \(P(n)\) 成立。欲对于有限集 \(X\) 满足 \(\operatorname{card}X=n^+\) 和函数 \(f:X\to Y\) 证明命题。

     一定存在一个元素 \(x\in X\)，设 \(X’=X\setminus \{x\}\)。设函数 \(f’:X’\to Y\)，使得 \(\forall_{x\in X’},f'(x):=f(x)\)。根据归纳，\(f'(X’)\) 为有限集且 \(\operatorname{card}f'(X’)\leqslant \operatorname{card}(X’)=n\)，当且仅当 \(f'(X’)\) 为单射时取等。

     • 若 \(f(x)\in f'(X’)\)，则 \(f'(X’)=f(X)\)，那么 \(f(X)\) 是有限集且 \(\operatorname{card}f(X)<n^+\)。

     • 若 \(f(x)\not\in f'(X’)\)，则 \(f(X)=f'(X’)\cup \{f(x)\}\) 为有限集，且 \(\operatorname{card}f(X)=\operatorname{card}f'(X’)+\operatorname{card}\{f(x)\}\leqslant n+1\)，当且仅当 \(f'(X’)\) 为单射时取等，结合 \(f(x)\not\in f'(X’)\)，可知等价于 \(f(X)\) 为单射。

     于是 \(P(n^+)\) 成立。于是对于任意自然数 \(n\) 有 \(P(n)\) 成立。

  5. 设 \(X\) 和 \(Y\) 是有限集，那么笛卡尔积 \(X\times Y\) 是有限的，且 \(\operatorname{card}(X\times Y)=\operatorname{card}X\times \operatorname{card}Y\)。

     证明：设 \(\operatorname{card}X=n\) 且 \(\operatorname{card}Y=m\)，根据定义，存在双射 \(f:X\to \{i\in\mathbb N:1\leqslant i\leqslant n\}\) 和 \(g:Y\to \{i\in\mathbb N:1\leqslant i\leqslant m\}\)。

     构造映射 \(h:X\times Y\to \{i\in\mathbb N:1\leqslant i\leqslant nm\}\)，满足对于任意 \((x,y)\in X\times Y\)， \(h(x,y):=(f(x)-1)m+g(y)\)。

     容易证明 \(h\) 是个双射，证毕。

  6. 设 \(X\) 和 \(Y\) 是有限集，那么集合 \(Y^X\) 是有限的，且 \(\operatorname{card}(Y^X)=(\operatorname{card}Y)^{\operatorname{card}X}\)。

     证明：设 \(\operatorname{card}X=n\) 且 \(\operatorname{card}Y=m\)，根据定义，存在双射 \(f:X\to \{i\in\mathbb N:1\leqslant i\leqslant n\}\) 和 \(g:Y\to \{i\in\mathbb N:1\leqslant i\leqslant m\}\)。

     构造映射 \(h:Y^X\to \{i\in\mathbb N:1\leqslant i\leqslant m^n\}\)，满足对于任意 \(p\in Y^X\)，\(h(f):=\sum_{i=1}^n(g\circ p\circ f^{-1})(i)\cdot Y^{i-1}\)。

     此处需先对 \(n\) 归纳证明形如 \(\sum_{i=1}^na(i)\) 的求和式存在且唯一，其中 \(a:\{i\in \mathbb{N}:1\leqslant i\leqslant n\}\to \mathbb N\)。

     容易证明 \(h\) 是个双射，证毕。

经过上述性质的证明，我们看到，通过基数和单个选取引理，我们已经能对有限集使用类似归纳的方法了。

至此，我们对于集合的讨论告一段落。