有限集

 有限这个概念，读者应该从小学开始就有了直观的感受——能一个个数出来，并且数完的就是有限的。现在，我们将这个概念抽象化严谨化。
 回想一下，如果\(n\)是一个正整数，用\(S_n\)表示全体小于\(n\)的正整数集合，并称之为正整数的一个截。集合\(S_n\)就是有限集的样本。
 定义 集合\(A\)称为有限的（finite），如果\(A\)与正整数的某一个截存在一个一一对应。即：\(A\)称为有限的，如果\(A\)是空集，或者对于某个正整数\(n\)存在一个一一对应

\[f:A\longrightarrow\{1,\cdots,n\}\]
前一种情况，称\(A\)的基数（cardinality）为0；后一种情况，称\(A\)的基数为\(n\)。
 例如，\(\{1,\cdots,n\}\)的基数为\(n\)，因为恒等函数是它与自身的一个一一对应。
 特别要注意，我们并没有证明，对于有限集\(A\)，\(A\)的基数由\(A\)唯一决定。当然，空集的基数为0。但就我们目前所知道的，不能排除存在集合\(A\)与两个不同集合\(\{1,\cdots, n\}\)和\(\{1,\cdots, m\}\)之间的一一对应的可能性。这种可能性似乎是荒谬的，好像说两个人“数”一个盒子里的石子，得的结果不同，却又都是正确的一样。根据我们日常生活中“数”东西的经验，这时不可能的。而事实上，当\(n\)是1，2，3这种小数目时，也很容易验证。但是，如果\(n\)等于500万，要直接证明就难以设想了。
 对于如此大的\(n\)，凭经验来证实是很困难的，例如，可以做这样一个试验。找一辆载满石子的货车，请十个人各自独立地去“数一数”石子的数量。就这个具体问题而言，很难想象他们“数”的结果会是一样的。当然，可以断定他们中至少有一个人“数”错了。而这其实是假定了要用经验来验证前面关于基数唯一性的结果是正确的。另一种解释就是，在给定的石子集合与正整数的两个不同截之间都有一一对应。
 实际生活中人们接受第一种解释。“数”东西的经验使我们相信，对于成员个数比较少的集合所产生的结论，对于任意大的集合也应该成立。
 然而在数学中（与现实生活不一样）不难轻易相信这样的论断。只有用一一对应的存在性，而不是依靠具体地“数”，那才是有价值的数学证明。我们马上要证明，若\(n\ne m\)，则不可能存在从给定集合\(A\)到两个集合\(\{1,\cdots,n\}\)与\(\{1,\cdots, m\}\)的两个一一对应。
 关于有限集，一个简单的事实是
 引理 6.1 设\(n\)是一个正整数，\(A\)是一个集合，\(a_0\)是\(A\)的一个元素，则存在集合\(A\)与集合\(\{1,\cdots,n+1\}\)之间的一一对应\(f\)，当且仅当存在集合\(A-\{a_0\}\)与\(\{1,\cdots, n\}\)之间的一一对应\(g\)。
 证明 要证明两种蕴含关系，首先假定存在一个一一对应

\[g:A-\{a_0\}\longrightarrow \{1,\cdots,n\}\]
那么由下式

\[\begin{aligned}  &f(x)=g(x),\text{ 对于}x\in A-\{a_0\}\\  &f(a_0)=n+1\end{aligned}\]
所定义的函数\(f:A\longrightarrow \{1,\cdots,n+1\}\)就是一个一一对应。
 为了证明其逆，我们假定存在一个一一对应

\[f:A\longrightarrow \{1,\cdots,n+1\}\]
如果\(f\)恰好把\(a_0\)映成\(n+1\)，事情就容易了。那时，限制映射\(f|A-\{a_0\}\)就是\(A-\{a_0\}\)与\(\{1,\cdots,n\}\)之间的一一对应。如若不然，令\(f(a_0)=m\)，\(a_1\)是\(A\)中满足\(f(a_1)=n+1\)的点，则\(a_1\ne a_0\)。由

\[\begin{aligned}  &h(a_0)=n+1\\  &h(a_1)=m\\  &h(x)=f(x),\text{ 对于}x\in A-\{a_0,a_1\}\end{aligned}\]
定义一个新函数

\[h:A\longrightarrow \{1,\cdots,n+1\}\]
容易验证\(h\)是一个一一对应。
 这就回到的简单的情况，限制映射\(h|a-\{a_0\}\)就是\(A-\{a_0\}\)与\(\{1,\cdots,n\}\)之间的一一对应。

$\square$

 由这个引理，可得到几个有用推论。

 定律 6.2 设\(A\)是一个集合。假定对于某一个\(n\in\mathbb{Z}_+\)，存在一个一一对应\(f:A\rightarrow \{1,\cdots,n\}\)。设\(B\)为\(A\)的一个真子集，则不存在一一对应\(g:B\rightarrow \{1,\cdots,n\}\)。但是（假定\(b\ne \varnothing\)），必定有一个一一对应\(h:B\rightarrow \{1,\cdots,m\}\)对于某个\(m