可数集

如果存在从${\displaystyle S}$ 到自然数集合${\displaystyle \mathbb {N} =\left\{1,2,3,\ldots \right\}}$ 存在单射函数，则${\displaystyle S}$ 称为可数集。^[4]

如果${\displaystyle S}$ 还是满射，则同样是双射，则称${\displaystyle S}$ 是无限可数集。

换句话说，一个集合要想是无限可数集，它要和自然数集${\displaystyle \mathbb {N} }$ 有一一对应关系。

如上所述，这个术语不普遍：一些作者在这里使用可数来表示被称为“无限可数”，并没有包括有限集。

由定义易知所有偶数所构成的集合为可列的，因为我们可以将所有的${\displaystyle n}$ 都对应到${\displaystyle 2n}$ ，如此就完成了一一对应。类似地，不难证明所有整数构成的集合${\displaystyle \mathbb {Z} }$ 、所有有理数构成的集合${\displaystyle \mathbb {Q} }$ 、甚至所有代数数构成的集合都是可列的。

并非所有的无穷集都可数。乔治·康托首先指出存在有不可列的无穷集合。他利用他发明的对角论证法证明了由所有实数构成的集合${\displaystyle \mathbb {R} }$ 是不可列的，即${\displaystyle \mathbb {R} }$ 与${\displaystyle \mathbb {N} }$ 之间不可能存在一种一一对应。这同时也表示实数当中存在有一些数不是代数数，因为刚才已经说过代数数是可列的；于是这就给出了一种超越数存在的非构造性证明。

由定义，如果存在从${\displaystyle S}$ 到自然数集合${\displaystyle \mathbb {N} =\left\{0,1,2,3,\ldots \right\}}$ 存在单射函数${\displaystyle f:S\rightarrow \mathbb {N} }$ ，则${\displaystyle S}$ 称为可数集。

这似乎自然地把集合划分为不同类别：把所有包含一个元素的集合放在一起；包含两个元素的集合在一起......最后，把所有无限集合放在一起，并认为它们具有相同的大小。然而，在大小的自然定义下，这种观点是不确切的。

为了阐述这一点，我们需要一个双射的概念。虽然双射看起来比数更加高深，但原本数学发展中集论定义函数要先于数字。因为它们都是基于更简单的集合。这就引出了双射的概念：

${\displaystyle a\leftrightarrow 1,b\leftrightarrow 2,c\leftrightarrow 3}$ 

由于${\displaystyle \left\{a,b,c\right\}}$ 的每个元素都可以和${\displaystyle \left\{1,2,3\right\}}$ 中准确的一个配对，并且反过来也同样，这就定义了一个双射。

我们将这个情境一般化，定义当且仅当它们之间存在双射，两个集合的大小相同。对于有限集，这里给出了“大小相同”的常用定义。那么对于无限集呢？

考虑集合${\displaystyle A=\left\{1,2,3,\ldots \right\}}$ （正整数集），和${\displaystyle B=\left\{2,4,6,\ldots \right\}}$ （正偶数集）。我们说，在我们的定义下，这些集合有相同的大小，并且因此B是无限可数集。我们需要证明它们之间存在双射。但这是很简单的，运用${\displaystyle n\leftrightarrow 2n}$ ，那么

${\displaystyle 1\leftrightarrow 2,2\leftrightarrow 4,3\leftrightarrow 6,4\leftrightarrow 8,\ldots }$ 

正如前面的例子，${\displaystyle A}$ 的每个元素都已和${\displaystyle B}$ 中准确的一个配对，并且反过来也同样。因而它们大小相同。这给出了一个集合与其一个合适的子集大小相同的例子，这种情形在有限集中是不可能的。

同样，自然数的有序对的集合，也就是自然数集合的笛卡尔积 ${\displaystyle \mathbb {N} \times \mathbb {N} }$ ，是无限可数集，可以沿着图中的一种路径：

配对结果就像这样：

${\displaystyle 0\leftrightarrow (0,0),1\leftrightarrow (1,0),2\leftrightarrow (0,1),3\leftrightarrow (2,0),4\leftrightarrow (1,1),5\leftrightarrow (0,2),6\leftrightarrow (3,0),\ldots }$ 

显然这个映射可以覆盖所有这些有序对。另一个证明方法是可以定义一个从自然数集合的笛卡尔积 ${\displaystyle \mathbb {N} \times \mathbb {N} }$ 到自然数集合${\displaystyle \mathbb {N} }$ 的单射函数${\displaystyle f(p,q)=2^{p}3^{q}}$ 。

利用数学归纳法，可知在n是个有限的自然数时，自然数集合的n-元笛卡尔积 ${\displaystyle \prod _{i=1}^{n}\mathbb {N} =\{(x_{1},\ldots ,x_{n})\ |\ x_{1}\land \;\ldots \;\land \;x_{n}\in \mathbb {N} \}}$ 是可数的。利用自然数集的笛卡尔积是可数的这点，可以证明整数集和有理数集是可数集，这是因为整数可以视为自然数的有序对（可将正整数${\displaystyle n}$ 给视为${\displaystyle (n,0)}$ ，将负整数${\displaystyle -n}$ 给视为${\displaystyle (0,n)}$ ），而以最简分数形式表示的有理数${\displaystyle p/q}$ 也可视为整数的有序对${\displaystyle (p,q)}$ 所致。

另外，可数无限多个可数集的联集是可数的，这是因为可以定义一个单射函数，将可数无限多个可数集的联集给映至自然数集合的笛卡尔积 ${\displaystyle \mathbb {N} \times \mathbb {N} }$ 之故。

不过可数无限多个自然数集合的笛卡尔积不是可数的，这可以透过康托的对角论证法证明。

• Aleph数
• 计数
• 希尔伯特旅馆悖论
• 不可数集
• 有限集合

1. ^ 例子参见（Rudin 1976，Chapter 2）
2. ^ 参见（Lang 1993，§2 of Chapter I）.
3. ^ 参见（Apostol 1969，Chapter 13.19）.
4. ^ 因为显然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