在数学上，可数集，或称可列集，是与自然数集的某个子集具有相同基數（等势）的集合。在这个意义下，可数集由有限可数集和無限可數集组成。不是可数集的无穷集称为不可数集。这个术语是康托尔创造的。可数集的元素，正如其名，是「可以计数」的：尽管计数有可能永远无法终止，集合中每一个特定的元素都将对应一个自然数。

「可数集」这个术语有时也指代可数无穷集，即仅代表能和自然数集本身一一对应的集合^[1]。两个定义的差别在于有限集合在前者中算作可数集，而在后者中不算作可数集。

为了避免歧义，前一种意义上的可数有时称为至多可数^[2]，后一种可数集则称为无限可数集^[3]。

定义

如果从${\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 

查 论 编 集合论 公理 选择 可数 依賴 外延 无穷 配对 幂集 正则性 并集 马丁公理 公理模式 替代 分类 运算 笛卡儿积 德摩根定律 交集 冪集 补集 对称差 并集 概念 方法 势 基数（大基数） 类 可构造全集（英语：Constructible universe） 连续统假设 對角論證法 元素 有序对 多元组 集合族 力迫 一一对应 序数 超限归纳法 文氏图 集合类型 可數集 空集 有限集合（继承有限集合） 模糊集 无限集合 递归集合 子集 传递集合 不可數集 泛集（英语：Universal set） 理论 可替代的集合论 集合论 朴素集合论 康托尔定理 策梅洛 广义（英语：General set theory） 《数学原理》 新基础 策梅洛-弗兰克 冯诺伊曼-博内斯-哥德尔 Morse–Kelley（英语：Morse–Kelley set theory） 克里普克–普拉特克（英语：Kripke–Platek set theory） 塔斯基–格罗滕迪克（英语：Tarski–Grothendieck set theory） 悖论（英语：Paradoxes of set theory） 问题 罗素悖论 蘇斯林問題 ZFC系統無法確定的命題列表 集合論者 亚伯拉罕·弗兰克尔 伯特兰·罗素 恩斯特·策梅洛 格奥尔格·康托尔 约翰·冯·诺伊曼 库尔特·哥德尔 盧菲特·澤德 保罗·贝尔奈斯（英语：Paul Bernays） 保罗·寇恩 理查德·戴德金 托马什·耶赫 威拉德·蒯因