这篇文章上次修改于 723 天前,可能其部分内容已经发生变化,如有疑问可询问作者。
作为一个正在自学抽象代数的抽象人,我翻开课本看了三页,遇到一个概念——循环群。
然后我试图证明有限循环群的一个性质,证着证着遇到一个问题:什么是有限集?
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$ 的一个映射,如果:
- $f \subseteq B \times A$ ,其中 $B \times A$ 表示笛卡尔积 $B \times A=\left\{(b,a)\|b \in B, a \in A\right\}$ 。
- $\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$ 。
- $\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)
没有评论