这篇文章上次修改于 612 天前，可能其部分内容已经发生变化，如有疑问可询问作者。

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

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

emmmmm我还真不知道。

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

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

有限集

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

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

Def 1. 如果一个集合 $A$ 可以和集合 $A^*=\{x\in \mathbb{N}\|1\le x\le n,n\ge 1, n\in \mathbb{N}\}$ 建立一一映射，称 $A$ 为有限集，同时把 $n$ 叫做 $A$ 的元素数，记作 $\|A\|=n$ 。另外规定空集 $\varnothing$ 也是有限集， $\|\varnothing\|=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}\|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}\|1\le x\le n-1\}$ 成立。此时若集合 $A=\{x\in \mathbb{N}\|1\le x\le n\}$ 存在一个到其真子集的单射 $f:A\to A^*$ ，那么构造映射 $f':A^-\to A^*$ ，使得 $\forall a\in A^-,f'(a)=f(a)$ 。记 $f$ 的像集 $f(A)$和$f'$ 的像集 $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^*=\{x\in \mathbb{N}\|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'$ 。

记 $f $ 的像集 $f(B)$ ，对于任意 $a\in A$ ，若 $a \in B$ ，令 $f'(a)=f(a)$ ，若 $a \notin B$ ，令 $f'(a)=a$ 。显然 $f'$ 为单射。记 $f'$ 的像集 $f'(A)$ 。由 $B^-$ 为真子集知存在元素 $b\in B$ 但 $b \notin B^-$ ，于是 $b \notin f'(A)$ ，又 $f'(A)\subseteq B^-\cup A \subseteq A$ ，故 $f'(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'$ 。对于任意 $b\in B$ ，令$g'(b)=f(g(f^{-1}(b)))$ 。不难证明 $g'$ 为 $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\|a\notin A_n^-\right\}$ 是 Def 4 定义的无限集。

使用数学归纳法。当 $n=1$ 时，存在 $A$ 到其真子集的单射 $f:A\to A^-$ ，由于 $A^-$ 是 $A$ 的真子集，于是可令 $A_1=\overline{A^-}=\left\{a\in A\|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^*$ ，由 Lemma 4 知 $A^*$ 也是 Def 4 定义的无限集，同上可令 $A_n=\overline{A^*}=\left\{a\in A\|a\notin A^*\right\}$ ，根据 $A^*$ 是 $\overline{A_{n-1}}$ 的真子集，知 $A_{n-1}$ 是 $A_{n}$ 的真子集。

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

接下来，我们记差集 $\Delta A_n=\left\{a\in A_n\|a\notin A_{n-1}\right\}$ （ $n\ge2$ ）， $\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)\|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\|\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$ 的一个全序子集 $\mathscr{Y}$ ，可以找到一个平凡上界 $\cup Y=\bigcup_{Y\in\mathscr{Y}} Y$ ，接下来我们证明 $\cup Y \in X$ 。任取 $(b_1,a_1),(b_2,a_2) \in \cup Y$ ，一定存在 $f_1,f_2 \in \mathscr{Y}$ 使得 $(b_1,b_2)\in f_1$ ， $(b_1,b_2)\in f_2$ 。由于 $\mathscr{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'=\left\{b\|(b,a) \in g\right\}$ ，显然 $B'\subseteq B$ 。下证： $g$ 为 $B$ 到 $A$ 的单射。

$g$ 是单射已经由 $X$ 的定义保证。只需证明 $B'=B$ 即可。若不然，那么 $B'$ 是 $B$ 的真子集，存在 $b\in B$ 使得 $b \notin B'$ 。记 $g$ 的像集 $g(B')$ ，一定存在 $a\in A$ 且 $a \notin g(B')$ （否则考虑 $g$ 的逆映射 $g^{-1}=\left\{(a,b)\|(b,a)\in g\right\}$ ，它是 $A$ 到 $B$ 的单射，矛盾），此时记 $g'=g\cup \left\{(b,a)\right\}$ ，有 $g'\in X$ ，并且 $g \subseteq g'$ ，而 $g \ne g'$ ，这与 $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\|a\ne m\right\}$ ，显然 $A^-$ 的最大值小于 $m$ ，于是 $A^-$ 为有限集，存在一一对应 $f:A_0^*\to A^-$ ，其中 $A_0^*=\{x\in \mathbb{N}\|1\le x\le n,n\ge 1, n\in \mathbb{N}\}$ 。构造映射 $f':A_1^*\to A$ ， $A_1^*=\{x\in \mathbb{N}\|1\le x\le n+1\}$ ，使 $\forall i \in A_0^*, f'(i)=f(i)$ ， $f(n+1)=m$ ，易知 $f'$ 为一一映射，证毕。

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)\| 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）