证明集合可数的简便方法

在集合论中，一个重要的概念就是集合的可数性。我们说一个集合是可数的，如果这个集合内的元素能够与自然数集N建立一一对应的关系。换句话说，我们能够给这个集合里的所有元素按次序排好，能够以某种顺序为所有元素进行编号。在这里，我们看到了两个重要的结论：全体有理数集合是可数的，以及全体实数集合是不可数的。在证明全体有理数可数时，我们用到的方法通常是当年Cantor所用的对角线方法。不过，事实上我们还有一个更简便的方法。在证明一个集合可数时，我们只需要建立一个映射到自然数集N的函数，使得每个自然数的原像都只有有限个即可。这样的话，我们便可以从小到大考虑自然数集中的每个元素，列举出它所对应的原像，从而得到原集合的一种编号次序。

例如，欲证明全体整数是可数的，只需要考虑函数f(x)=|x|，这是一个从全体整数到自然数的函数，并且每个自然数最多只有两个原像。这样的话，我们便可以立即说明全体整数是可数的。类似地，为了说明全体有理数也是可数的，只需要令函数f(p/q)=|p|+|q|。显然分子分母的绝对值和为某一指定自然数的只有有限多种情况。

下面是一些更有意思的情形。怎样用这种方法来证明自然数集N的有限子集个数是可数的呢？一个容易想到的函数是f(S)=|S|，即集合S中的元素个数。不过细想一下发现不对，因为在元素个数给定的情况下，自然数子集有无穷多种取法。这告诉我们，我们还需要找到一个更巧妙的限制。想一想，用怎样的条件才能把自然数子集给限制住呢？令f(S)=max(S)，即集合S中的最大元素。由于有限集中必然存在一个最大元素，因此这个函数是有意义的。又由于最大元素为m的有限集最多有2^m个，这就立即说明了自然数有限子集的个数是可数的。

更有趣的是全体整系数多项式的可数性。受上面这一问题的启发，我们自然而然地想到函数f(P)为多项式P的最高次数。不过我们立即发现这样不行——指定次数的多项式有无穷多个。那么，定义f(P)为各项系数的绝对值之和呢？仔细一想发现也不行，例如1, x, x^2, x^3, x^4, …这无穷多个多项式对应的函数值均为1。不过，如果把上面两个条件结合在一起，我们的结论也就证到了：令f(P)为各项系数的绝对值之和加这个多项式的最高次数。这样的话，我既设定了多项式的系数上界，又设定了多项式的次数上界，有效地限定了多项式的数目。

来源：http://www.tricki.org/article/A_good_way_of_proving_that_a_set_is_countable