可数集
在数学上,可数集,或称可列集,是与自然数集的某个子集具有相同基数(等势)的集合。在这个意义下,可数集由有限可数集和无限可数集组成。不是可数集的无穷集称为不可数集。这个术语是康托尔创造的。可数集的元素,正如其名,是“可以计数”的:尽管计数有可能永远无法终止,集合中每一个特定的元素都将对应一个自然数。
“可数集”这个术语有时也指代可数无穷集,即仅代表能和自然数集本身一一对应的集合[1]。两个定义的差别在于有限集合在前者中算作可数集,而在后者中不算作可数集。
定义
换句话说,一个集合要想是无限可数集,它要和自然数集 有一一对应关系。
如上所述,这个术语不普遍:一些作者在这里使用可数来表示被称为“无限可数”,并没有包括有限集。
介绍
由定义易知所有偶数所构成的集合为可列的,因为我们可以将所有的 都对应到 ,如此就完成了一一对应。类似地,不难证明所有整数构成的集合 、所有有理数构成的集合 、甚至所有代数数构成的集合都是可列的。
并非所有的无穷集都可数。乔治·康托首先指出存在有不可列的无穷集合。他利用他发明的对角论证法证明了由所有实数构成的集合 是不可列的,即 与 之间不可能存在一种一一对应。这同时也表示实数当中存在有一些数不是代数数,因为刚才已经说过代数数是可列的;于是这就给出了一种超越数存在的非构造性证明。
正规定义和性质
由定义,如果存在从 到自然数集合 存在单射函数 ,则 称为可数集。
这似乎自然地把集合划分为不同类别:把所有包含一个元素的集合放在一起;包含两个元素的集合在一起......最后,把所有无限集合放在一起,并认为它们具有相同的大小。然而,在大小的自然定义下,这种观点是不确切的。
为了阐述这一点,我们需要一个双射的概念。虽然双射看起来比数更加高深,但原本数学发展中集论定义函数要先于数字。因为它们都是基于更简单的集合。这就引出了双射的概念:
由于 的每个元素都可以和 中准确的一个配对,并且反过来也同样,这就定义了一个双射。
我们将这个情境一般化,定义当且仅当它们之间存在双射,两个集合的大小相同。对于有限集,这里给出了“大小相同”的常用定义。那么对于无限集呢?
考虑集合 (正整数集),和 (正偶数集)。我们说,在我们的定义下,这些集合有相同的大小,并且因此B是无限可数集。我们需要证明它们之间存在双射。但这是很简单的,运用 ,那么
正如前面的例子, 的每个元素都已和 中准确的一个配对,并且反过来也同样。因而它们大小相同。这给出了一个集合与其一个合适的子集大小相同的例子,这种情形在有限集中是不可能的。
同样,自然数的有序对的集合,也就是自然数集合的笛卡尔积 ,是无限可数集,可以沿着图中的一种路径:
配对结果就像这样:
显然这个映射可以覆盖所有这些有序对。另一个证明方法是可以定义一个从自然数集合的笛卡尔积 到自然数集合 的单射函数 。
利用数学归纳法,可知在n是个有限的自然数时,自然数集合的n-元笛卡尔积 是可数的。利用自然数集的笛卡尔积是可数的这点,可以证明整数集和有理数集是可数集,这是因为整数可以视为自然数的有序对(可将正整数 给视为 ,将负整数 给视为 ),而以最简分数形式表示的有理数 也可视为整数的有序对 所致。
另外,可数无限多个可数集的并集是可数的,这是因为可以定义一个单射函数,将可数无限多个可数集的并集给映至自然数集合的笛卡尔积 之故。
不过可数无限多个自然数集合的笛卡尔积不是可数的,这可以透过康托的对角论证法证明。
参见
注解
- ^ 例子参见(Rudin 1976,Chapter 2)
- ^ 参见(Lang 1993,§2 of Chapter I).
- ^ 参见(Apostol 1969,Chapter 13.19) .
- ^ 因为显然N和N* = {1, 2, 3, ...}之间显然存在双射,无所谓是否把0算作自然数。在任何情况,这篇文章都遵循ISO 31-11和数学逻辑中的标准传统,将0作为自然数。
参考资料
- Lang, Serge, Real and Functional Analysis, Berlin, New York: Springer-Verlag, 1993, ISBN 0-387-94001-4
- Rudin, Walter, Principles of Mathematical Analysis, New York: McGraw-Hill, 1976, ISBN 0-07-054235-X