抽象人的学习笔记：有限集与无限集

作为一个正在自学抽象代数的抽象人，我翻开课本看了三页，遇到一个概念——循环群。

然后我试图证明有限循环群的一个性质，证着证着遇到一个问题：什么是有限集？

emmmmm我还真不知道。

不知道的问题就要研究研究，写一篇文章作为总结。

本文的讨论都基于 ZFC 公理系统（包括选择公理）。

---

有限集

对有限集的朴素理解来自可数性：能数过来的集合就是有限集。

严谨一点说，我们可以这样定义有限集：

Def 1. 如果一个集合 $A$ 可以和集合 $A^{\ast }=\{x\in \mathbb{N}\Vert 1\le x\le n,n\ge 1,n\in \mathbb{N}\}$ 建立一一映射，称 $A$ 为有限集，同时把 $n$ 叫做 $A$ 的元素数，记作 $\Vert A\Vert =n$ 。另外规定空集 $\varnothing$ 也是有限集， $\Vert \varnothing \Vert =0$ 。

与之对应，不是有限集的集合叫做无限集。

---

无限集

如果再从朴素的理解去考虑，无限集就是数不过来的集合。

也就是说，存在一个无穷的编号序列可以给其一个子集编号。于是可以这样定义无限集：

Def 2. 如果一个集合 $A$ 存在从 $\mathbb{N}$ 到 $A$ 的单射，称 $A$ 为无限集。

刚才在有限集一节，我们说不是有限集的集合就是无限集。这两种定义方式看起来不太一样，现在我们需要证明它们的等价性。

Th 1. 按照 Def 1 和 Def 2 的定义方式，一个集合不是有限集就是无限集。

要解决这个问题其实并不容易，因为上面两个定义都涉及到自然数集，而不是纯粹的集合论问题。

---

有限集的集合论定义

我们重新用纯粹集合论的语言给出有限集的另一种定义：

Def 3. 如果集合 $A$ 满足对于任何 $A$ 的真子集 $A^{-}$ ，都不存在 $A$ 到 $A^{-}$ 的单射，则称 $A$ 为有限集。

在 Def 3 里没有特别规定空集，但是依然可以保证空集是有限集。（想一想，为什么？）

同样，我们需要证明 Def 1 与 Def 3 的等价性。

我们先引入一个引理。

Lemma 1. 对于集合 $A=\{x\in \mathbb{N}\Vert 1\le x\le n,n\ge 1,n\in \mathbb{N}\}$ ，不存在其到其真子集的单射。

证明：使用数学归纳法。当 $n=1$ 时， $A$ 的真子集只有 $\varnothing$ ，显然成立。

当 $n\ge 2$ 时，假设 Lemma 1 对 $A^{-}=\{x\in \mathbb{N}\Vert 1\le x\le n-1\}$ 成立。此时若集合 $A=\{x\in \mathbb{N}\Vert 1\le x\le n\}$ 存在一个到其真子集的单射 $f:A\to A^{\ast }$ ，那么构造映射 $f^{\prime }:A^{-}\to A^{\ast }$ ，使得 $\forall a\in A^{-},f^{\prime }(a)=f(a)$ 。记 $f$ 的像集 $f(A)$和$f^{\prime }$ 的像集 $f(A^{-})$ 。

若 $n\in f(A)$ ，不妨设 $f(n)=n$ （否则找到 $f(i)=n$ ，再交换 $f(i)$ 与 $f(n)$ 的对应关系即可），那么一定有 $n\notin f(A^{-})$ ，并且 $f(A)=f(A^{-})\cup \{n\}$ 。而 $f(A)$ 是 $A$ 的真子集，所以存在 $i<n$ 使 $i\notin f(A)$ ，进而 $i\notin f(A^{-})$ ，又 $f(A^{-})\subseteq f(A)\subseteq A$ ，因此 $f(A^{-})$ 是 $A^{-}$ 的真子集，矛盾。

若 $n\notin f(A)$ ，则 $n\notin f(A^{-})$ 。记 $f(n)=i<n$ ，那么 $i\notin f(A^{-})$ ，又 $f(A^{-})\subseteq f(A)\subseteq A$ ，这说明 $f(A^{-})$ 是 $A^{-}$ 的真子集，矛盾。

综上，由数学归纳原理，可知 Lemma 1 成立。

Th 2. Def 1 是 Def 3 的充分条件。

证明：如果存在一个 Def 1 定义的有限集 $A$ 不满足 Def 3，显然 $A$ 不为空集，那么相当于存在集合 $A^{\ast }=\{x\in \mathbb{N}\Vert 1\le x\le n,n\ge 1,n\in \mathbb{N}\}$ 有一个到真子集的单射。根据 Lemma 1，这不可能。

必要性难以直接证明，等到我们先研究完其他问题再回来讨论。

---

无限集的集合论定义

之所以采用 Def 3 的方式定义有限集，是因为它有个优点：Def 3 的否定就是无限集的定义。

Def 4. 如果集合 $A$ 存在一个 $A$ 的真子集 $A^{-}$ 和存在 $A$ 到 $A^{-}$ 的单射，则称 $A$ 为无限集。

这种定义方式最早由戴德金（R. Dedekind）给出，他证明了 Def 2 和 Def 4 的等价性。

先引入几个引理。

Lemma 2. 如果一个集合的子集是 Def 4 定义的无限集，那么这个集合也是 Def 4 定义的无限集。

证明：记集合 $A$ 的子集 $B$ 是 Def 4 定义的无限集，那么存在 $B$ 的真子集 $B^{-}$ 和其之间的单射 $f:B\to B^{-}$ 。接下来我们构造一个 $A$ 到其真子集的单射 $f^{\prime }$ 。

记 $f$ 的像集 $f(B)$ ，对于任意 $a\in A$ ，若 $a\in B$ ，令 $f^{\prime }(a)=f(a)$ ，若 $a\notin B$ ，令 $f^{\prime }(a)=a$ 。显然 $f^{\prime }$ 为单射。记 $f^{\prime }$ 的像集 $f^{\prime }(A)$ 。由 $B^{-}$ 为真子集知存在元素 $b\in B$ 但 $b\notin B^{-}$ ，于是 $b\notin f^{\prime }(A)$ ，又 $f^{\prime }(A)\subseteq B^{-}\cup A\subseteq A$ ，故 $f^{\prime }(A)$ 为 $A$ 的真子集，证毕。

Lemma 3. 对于 Def 4 定义的无限集 $A$ ，如果集合 $B$ 存在从 $A$ 到 $B$ 的一一映射，则集合 $B$ 也是 Def 4 定义的无限集。

证明：记一一映射 $f:A\to B$ 及其逆映射 $f^{-1}:B\to A$ ，由于 $A$ 存在到其真子集的单射 $g:A\to A^{-}$ ，可以找到一个 $B$ 到其真子集的单射 $g^{\prime }$ 。对于任意 $b\in B$ ，令$g^{\prime }(b)=f(g(f^{-1}(b)))$ 。不难证明 $g^{\prime }$ 为 $B$ 到其真子集的单射。

Lemma 4. 对于 Def 4 定义的无限集 $A$ ，如果集合 $B$ 存在从 $A$ 到 $B$ 的单射，则集合 $B$ 也是 Def 4 定义的无限集。

证明：由 Lemma 2 及 Lemma 3 即证。

接下来证明 Def 2 与 Def 4 的等价性。有了上面的工作，充分性就容易证明了。

Th 3. Def 2 是 Def 4 的充分条件。

证明：易知自然数集 $\mathbb{N}$ 满足 Def 4（可构造 $f(n)=2n$ ）。由 Lemma 4 可知，满足 Def 2 的集合都满足 Def 4。

接着证明必要性。

Th 4. Def 2 是 Def 4 的必要条件。

证明：记集合 $A$ 满足 Def 4。我们先证明这样一个结论：对于任意自然数 $n$ ，存在 $A$ 的非空子集 $A_n$ ，使得 $A_{n-1}$ 是 $A_n$ 的真子集（ $n\ge 2$ ），且其补集 $\overline{A_n}=\left\{a\in A\Vert a\notin A_n^{-}\right\}$ 是 Def 4 定义的无限集。

使用数学归纳法。当 $n=1$ 时，存在 $A$ 到其真子集的单射 $f:A\to A^{-}$ ，由于 $A^{-}$ 是 $A$ 的真子集，于是可令 $A_1=\overline{A^{-}}=\left\{a\in A\Vert a\notin A^{-}\right\}$ 。

当 $n\ge 2$ 时，假设命题对 $n-1$ 成立。由于 $\overline{A_{n-1}}$ 为 Def 4 定义的无限集，存在 $\overline{A_{n-1}}$ 到其真子集的单射 $f:\overline{A_{n-1}}\to A^{\ast }$ ，由 Lemma 4 知 $A^{\ast }$ 也是 Def 4 定义的无限集，同上可令 $A_n=\overline{A^{\ast }}=\left\{a\in A\Vert a\notin A^{\ast }\right\}$ ，根据 $A^{\ast }$ 是 $\overline{A_{n-1}}$ 的真子集，知 $A_{n-1}$ 是 $A_n$ 的真子集。

综上，由数学归纳原理，知命题成立。

接下来，我们记差集 $\Delta A_n=\left\{a\in A_n\Vert a\notin A_{n-1}\right\}$ （ $n\ge 2$ ）， $\Delta A_1=A_1$ ，易知 $\Delta A_n$ 非空。根据选择公理，可以在其中选出一列元素 $a_1,a_2,a_3,\cdots$ ，且显然两两不同。于是令 $f(n)=a_n$ ，就找到了 $\mathbb{N}$ 到 $A$ 的一个单射，证毕。

---

再看有限集

现在无限集的两种定义已经统一了，我们再来看 Def 1 对 Def 3 的必要性。

Th 5. Def 1 是 Def 3 的必要条件。

按照惯例，先引入几个引理。

Lemma 5. 两个非空集合之间一定存在一方到另一方的单射。

证明：我们使用有序对集合的方式来表示映射。定义 $f$ 是从非空集合 $B$ 到非空集合 $A$ 的一个映射，如果：

1. $f\subseteq B\times A$ ，其中 $B\times A$ 表示笛卡尔积 $B\times A=\left\{(b,a)\Vert b\in B,a\in A\right\}$ 。
2. $\forall (b_1,a_1),(b_2,a_2)\in f,(b_1,a_1)\ne (b_2,a_2)\Rightarrow b_1\ne b_2$ 。
3. $\forall b\in B,\exists a\in A,(b,a)\in f$ 。 如果 $f$ 还满足 $\forall (b_1,a_1),(b_2,a_2)\in f,b_1\ne b_2\Rightarrow a_1\ne a_2$ ，称 $f$ 为单射。

现在考虑两个非空集合 $A,B$ ，假设不存在单射 $f:A\to B$ ，我们要证明存在单射 $g:B\to A$ 。

考虑 $B$ 的所有非空子集到 $A$ 的单射组成的集合 $X$ ，也即 $X=\left\{f\in B\times A\Vert \forall (b_1,a_1),(b_2,a_2)\in f,(b_1,a_1)\ne (b_2,a_2)\Rightarrow b_1\ne b_2\wedge a_1\ne a_2\right\}$ ，在其上定义偏序关系为集合的包含关系。

对于 $X$ 的一个全序子集 $\mathcal{Y}$ ，可以找到一个平凡上界 $\cup Y={\bigcup }_{Y\in \mathcal{Y}}Y$ ，接下来我们证明 $\cup Y\in X$ 。任取 $(b_1,a_1),(b_2,a_2)\in \cup Y$ ，一定存在 $f_1,f_2\in \mathcal{Y}$ 使得 $(b_1,b_2)\in f_1$ ， $(b_1,b_2)\in f_2$ 。由于 $\mathcal{Y}$ 是全序的，所以 $f_1,f_2$ 间存在包含关系，不妨设 $f_1\subseteq f_2$ ，那么根据 $f_2\in X$ 可知 $(b_1,a_1)\ne (b_2,a_2)\Rightarrow b_1\ne b_2\wedge a_1\ne a_2$ ，故 $\cup Y\in X$ 。

根据佐恩引理，可知 $X$ 存在最大元。记其中一个为 $g$ ，并记 $g$ 的定义域 $B^{\prime }=\left\{b\Vert (b,a)\in g\right\}$ ，显然 $B^{\prime }\subseteq B$ 。下证： $g$ 为 $B$ 到 $A$ 的单射。

$g$ 是单射已经由 $X$ 的定义保证。只需证明 $B^{\prime }=B$ 即可。若不然，那么 $B^{\prime }$ 是 $B$ 的真子集，存在 $b\in B$ 使得 $b\notin B^{\prime }$ 。记 $g$ 的像集 $g(B^{\prime })$ ，一定存在 $a\in A$ 且 $a\notin g(B^{\prime })$ （否则考虑 $g$ 的逆映射 $g^{-1}=\left\{(a,b)\Vert (b,a)\in g\right\}$ ，它是 $A$ 到 $B$ 的单射，矛盾），此时记 $g^{\prime }=g\cup \left\{(b,a)\right\}$ ，有 $g^{\prime }\in X$ ，并且 $g\subseteq g^{\prime }$ ，而 $g\ne g^{\prime }$ ，这与 $g$ 的最大性矛盾，证毕。

（此证明的最初版本出自StackExchange的用户Mengfan Ma和Asaf Karagila，向两位表示感谢。）

Lemma 6. 自然数集的一个有上界的非空子集是 Def 1 定义的有限集。

证明：记这样的一个集合为 $A$ ，对 $A$ 的最大值 $m$ 使用数学归纳法。当 $m=0$ 时，满足条件的集合只有 $\{0\}$ ，这显然是有限集。

当 $m\ge 1$ 时，假设 Lemma 6 对 $A$ 的最大值为 $0,1,2,\cdots ,m-1$ 的情形成立，那么考虑集合 $A^{-}=\left\{a\in A\Vert a\ne m\right\}$ ，显然 $A^{-}$ 的最大值小于 $m$ ，于是 $A^{-}$ 为有限集，存在一一对应 $f:A_0^{\ast }\to A^{-}$ ，其中 $A_0^{\ast }=\{x\in \mathbb{N}\Vert 1\le x\le n,n\ge 1,n\in \mathbb{N}\}$ 。构造映射 $f^{\prime }:A_1^{\ast }\to A$ ， $A_1^{\ast }=\{x\in \mathbb{N}\Vert 1\le x\le n+1\}$ ，使 $\forall i\in A_0^{\ast },f^{\prime }(i)=f(i)$ ， $f(n+1)=m$ ，易知 $f^{\prime }$ 为一一映射，证毕。

Th 6. 不存在既不是有限集也不是无限集的集合。其中有限集按照 Def 1 定义。

证明：如果一个集合 $A$ 不是无限集，按照 Def 2，不存在从 $\mathbb{N}$ 到 $A$ 的单射，于是根据 Lemma 5，存在从 $A$ 到 $N$ 的一个单射 $f:A\to \mathbb{N}$ 。考虑 $f$ 的像集 $f(A)$ ，根据 Lemma 3，$f(A)$ 不是无限集。下证 $f(A)$ 存在上界。

若 $f(A)$ 不存在上界，也即 $\forall n\in \mathbb{N},\exists m\in f(A),m>n$ ，因此集合 $M_n=\left\{m\in f(A)\Vert m>n\right\}$ 非空，而 $M_n\subseteq \mathbb{N}$ ，因此 $M_n$ 存在最小值，记作 $\mu (n)$ 。

构造 $f(A)$ 到其子集 $X$ 的映射 $g:f(A)\to X$ ，使 $\forall n\in f(A),g(n)=\mu (n)$ ，不妨令 $X$ 为像集 $g(f(A))$ ，那么由 $M_n\subseteq f(A)$ 知 $X\subseteq f(A)$ 。记 $f(A)$ 中的最小值为 $n_0$ ，必有 $n_0\notin X$ ，否则存在 $\mu (n)=n_0$ ，故 $n<n_0$ ，与 $n_0$ 的最小性矛盾。因此 $X$ 是 $f(A)$ 的真子集。下面说明 $g$ 为单射。

若存在不同的 $a,b\in f(A)$ 使 $g(a)=g(b)=m$ ，不妨设 $a<b$ ，那么 $a<b<m$ ，与 $g(a)=\mu (a)$ 的最小性矛盾。因此 $g$ 为单射。这就找到了一个从 $f(A)$ 到其真子集的单射，于是 $f(A)$ 为无限集，矛盾。

因此， $f(A)$ 一定存在上界。根据 Lemma 6， $f(A)$ 为有限集。而 $A$ 与 $f(A)$ 之间可以建立一一映射，于是 $A$ 也为有限集，证毕。

不知大家有没有注意到，上面这个命题我写的是 Th 6 而不是 Lemma 7。事实上，在完成 Th 6 的证明后，Th 5（必要性）已经得到了证明。

我们只需要一点形式逻辑的推导：

Th 6 说明 Def 1 和 Def 2 必有一个成立，于是当 Def 1 不成立时，Def 2 成立，因此 Def 4 成立，Def 3 不成立。即 Def 1 不成立推出 Def 3 不成立，这等价于 Def 3 成立推出 Def 1 成立。

---

结语

本来以这会是一个简单的问题，没想到最后变得这么复杂……

可能是因为选择公理的使用，也可能是因为我选择的证明路径太复杂了。

如果大家有更加简单的方法，欢迎在评论区说出来。

（封面来源：BV1K5411n7Vn）