可数集与不可数集

 如同正整数的截是有限集的样本那样，所有正整数的集合\(\mathbb{Z}_+\)就是可数无限集的样板。本节将研究这种集合，还要构造一些既不是有限集也不是可数无限集的集合。这种研究将引导我们去讨论“归纳定义”过程的含义。
 定义 一个集合\(A\)称为无限的（infinite），如果它不是有限集。一个无限集\(A\)称为可数无限的（countably infinite），如果存在一个一一对应

\[f:A\longrightarrow \mathbb{Z}_+\]
 定义 一个集合称为可数的（countable），如果它是有限集或者可数无限集。一个集合不是可数的，就称为不可数的（uncountable）。
 以下定理为我们提供了一个判定集合可数性的常规方法。
 定理 7.1 设\(B\)是一个非空集，则下列条件等价：
 (1) \(B\)是可数集；
 (2) 存在一个满射\(f:\mathbb{Z}_+\rightarrow B\)；
 (3) 存在一个单射\(g:B\rightarrow\mathbb{Z}_+\)。
 证明 (1)\(\Rightarrow\)(2)。设\(B\)是一个可数集，如果\(B\)是可数无限集，则根据定义存在一个一一对应\(f:\mathbb{Z}_+\rightarrow B\)，从而结论成立。如果\(B\)是一个有限集，则对于某一个\(n\ge 1\)，存在一个一一对应\(h:\{1,\cdots,n\}\rightarrow B\)（注意\(B\ne \varnothing\)），可以把\(h\)扩张为一个满射\(f:\mathbb{Z}_+\rightarrow B\)，其定义为

\[f(i)=\begin{cases}  h(i),&1\leqslant i \leqslant n,\\  h(1),&i>n.\end{cases}\]
从而结论成立。
 (2)\(\Rightarrow\)(3)。设\(f:\mathbb{Z}_+\rightarrow B\)是一个满射。\(g:B\rightarrow \mathbb{Z}_+\)定义为：

\[g(b)=f^{-1}(\{b\})\text{的最小元}\]
因为\(f\)是一个满射，\(f^{-1}(\{b\})\)非空，所以\(g\)的定义是确切的。如果\(b\ne b'\)，集合\(f^{-1}(\{b\})\)与\(f^{-1}(\{b'\})\)无交，它们的最小元不同，因此\(g\)是一个单射。
 (3)\(\Rightarrow\)(1)。设\(g:B\rightarrow \mathbb{Z}_+\)是一个单射，我们要证明\(B\)是一个可数集。通过改变\(g\)的值域可以得到\(B\)与\(\mathbb{Z}_+\)的一个子集之间的一个一一对应。因此只要证明\(\mathbb{Z}_+\)的任意子集是可数的，便可以证明结论。令\(C\)为\(\mathbb{Z}_+\)的一个子集。
 如果\(C\)是一个有限集，根据定义它是可数的。因此，我们只需证明\(\mathbb{Z}_+\)的无限子集\(C\)是一个可数无限集。这个论断是容易理解的。事实上，我们可以将\(C\)的元素排列成一个无穷序列，这只需将\(\mathbb{Z}_+\)的元素先按通常的顺序排列，然后再“删除”\(\mathbb{Z}_+\)中所有不在\(C\)中的元素。
 以上陈述仅是对证明的轮廓的一个直观说明，严格的证明还须细致的推理分析。我们将作为一个引理予以陈述。

$\square$

 引理 7.2 设\(C\)是\(\mathbb{Z}_+\)的一个无限子集，那么\(C\)是一个可数无限集。
 证明 我们将构造一个一一对应\(h:\mathbb{Z}_+\rightarrow C\)。采用归纳法。定义\(h(1)\)为\(C\)的最小元，由于\(\mathbb{Z}_+\)的任意非空子集\(C\)有最小元，所以\(h(1)\)是存在的。假定\(h(1),\cdots,h(n-1)\)已有定义，我们定义

\[h(n)=[C-h(\{1,\cdots,n-1\})]\text{的最小元}\]
集合\(C-h(\{1,\cdots,n-1\})\)是非空的，这是因为：如果它是空集的话，\(h:\{1,\cdots,n-1\}\rightarrow C\)便是一个满射，（根据推论 6.7）\(C\)就是一个有限集了。所以\(h(n)\)的定义是确切的。根据归纳法，对于所有\(n\in\mathbb{Z}_+\)，\(h(n)\)有定义。
 容易证明\(h\)是一个单射，当\(mc\)。令\(m\)是\(\mathbb{Z}_+\)中满足\(h(m)\geqslant c\)的最小元，于是对于所有\(i1\)定义\(h(i)\)为\(A\)的这样唯一一个的元素，它仅与\(h\)在小于\(i\)的正整数时的值有关，这个公式便决定了唯一的一个函数\(h:\mathbb{Z}_+\rightarrow A\)。
 这就是我们在证明引理 7.2时实际用到的原理。如果读者愿意的话，可以直接相信它是对的。当然它也能用归纳原理加以严格证明。下节将给出精确的描述，并且指出如何予以证明。数学家们很少专门援引这个原理。他们更愿意像在引理 7.2的证明中那样，当确实要用到归纳定义原理时，再设法用“归纳原理”来定义一个函数。为了避免过于迂腐，本系列也遵从这个惯例。
 推论 7.3 可数集的子集也是可数的。
 证明 假定\(A\subset B\)，其中\(B\)是一个可数集。那么，存在一个从\(B\)到\(\mathbb{Z}_+\)的单射\(f\)，而\(f\)在\(A\)上的限制即为从\(A\)到\(\mathbb{Z}_+\)的一个单射。

$\square$

 推论 7.4 集合\(\mathbb{Z}_+\times\mathbb{Z}_+\)是可数无限的。
 证明 根据定理 7.1，只要构造一个单射\(f:\mathbb{Z}_+\times\mathbb{Z}_+\rightarrow \mathbb{Z}_+\)，将\(f\)定义为

\[f(n,m)=2^n3^m\]

容易验证\(f\)是一个单射。假定\(2^n3^m=2^p3^q\)，当\(n