查看“︁可數集”︁的源代码

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

「可数集」这个术语有时也指代'''可数无穷集'''，即仅代表能和自然数集本身一一对应的集合<ref name="Rudin">例子参见{{Harv|Rudin|1976|loc=Chapter 2}}</ref>。两个定义的差别在于[[有限集合]]在前者中算作可数集，而在后者中不算作可数集。

为了避免歧义，前一种意义上的'''可数'''有时称为'''至多可数'''<ref name="Lang">参见{{Harv|Lang|1993|loc=§2 of Chapter I}}.</ref>，后一种'''可数集'''则称为'''无限可数集'''<ref name="Apostol">参见{{Harv|Apostol|1969|loc=Chapter 13.19}}.</ref>。

==定义==
如果从<math>S</math>到[[自然數]]集合<math>\mathbb{N}=\left \{ 1,2,3,\ldots \right \}</math>存在[[单射]]函数，则''<math>S</math>''称为可数集。<ref>因为显然'''N'''和'''N'''* = {1, 2, 3, ...}之间显然存在[[双射]]，无所谓是否把0算作自然数。在任何情况，这篇文章都遵循[[ISO 31-11]]和[[数学逻辑]]中的标准传统，将0作为自然数。</ref>

如果''<math>S</math>''还是[[满射]]，则同样是[[双射]]，则称<math>S</math>是'''[[无限集|无限]]可数集'''。

换句话说，一个集合要想是'''无限可数集'''，它要和自然数集<math>\mathbb{N}</math>有[[一一对应]]关系。

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

==介绍==
由定義易知所有[[偶數]]所構成的集合為可列的，因為我們可以將所有的<math>n</math>都對應到<math>2n</math>，如此就完成了一一對應。類似地，不難證明所有[[整數]]構成的集合<math>\mathbb{Z}</math>、所有[[有理數]]構成的集合<math>\mathbb{Q}</math>、甚至所有[[代數數]]構成的集合都是可列的。

並非所有的無窮集都可數。[[康托爾|喬治·康托]]首先指出存在有不可列的無窮集合。他利用他發明的[[對角論證法]]證明了由所有[[實數]]構成的集合<math>\mathbb{R}</math>是不可列的，即<math>\mathbb{R}</math>與<math>\mathbb{N}</math>之間不可能存在一種一一對應。這同時也表示實數當中存在有一些數不是代數數，因為剛才已經說過代數數是可列的；於是這就給出了一種[[超越數]]存在的[[非構造性證明]]。

==正规定义和性质==
由定义，如果存在从''<math>S</math>''到[[自然數]]集合<math>\mathbb{N}=\left \{ 0,1,2,3,\ldots \right \}</math>存在单射函数<math>f:S\rightarrow \mathbb{N}</math>，则''<math>S</math>''称为可数集。

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

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

:<math>a\leftrightarrow 1,b\leftrightarrow 2,c\leftrightarrow 3</math>

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

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

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

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

同样，自然数的[[有序对]]的集合，也就是自然數集合的[[笛卡爾積]] <math>\mathbb{N} \times \mathbb{N}</math>，是无限可数集，可以沿着图中的一种路径：[[File:Pairing natural.svg|thumb|300px|[[康拖尔配对函数]]给每一对自然数分配了一个自然数]]配对结果就像这样：
:<math>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</math>

显然这个映射可以覆盖所有这些有序对。另一個證明方法是可以定義一個從自然數集合的[[笛卡爾積]] <math>\mathbb{N} \times \mathbb{N}</math>到自然數集合<math>\mathbb{N}</math>的[[單射]]函數<math>f(p,q) = 2^p3^q</math>。

利用[[數學歸納法]]，可知在n是個有限的自然數時，自然數集合的n-元[[笛卡爾積]] <math>\prod_{i =1}^{n} \mathbb{N} = \{(x_1, \ldots, x_n) \ | \ x_1\land\;\ldots\;\land\;x_n\in \mathbb{N}\}</math>是可數的。利用自然數集的笛卡爾積是可數的這點，可以證明[[整數]]集和[[有理數]]集是可數集，這是因為整數可以視為自然數的有序對（可將正整數<math>n</math>給視為<math>(n,0)</math>，將負整數<math>-n</math>給視為<math>(0,n)</math>），而以[[最簡分數]]形式表示的有理數<math>p/q</math>也可視為整數的有序對<math>(p,q)</math>所致。

另外，可數無限多個可數集的聯集是可數的，這是因為可以定義一個單射函數，將可數無限多個可數集的聯集給映至自然數集合的[[笛卡爾積]] <math>\mathbb{N} \times \mathbb{N}</math>之故。

不過可數無限多個自然數集合的[[笛卡爾積]]不是可數的，這可以透過康托的對角論證法證明。

== 参见 ==
* [[艾禮富數|Aleph数]]
* [[计数]]
* [[希尔伯特旅馆悖论]]
* [[不可数集]]
* [[有限集合]]
==注解==
<references/>
==参考资料==
* {{Citation | last1=Lang | first1=Serge | author1-link=Serge Lang | title=Real and Functional Analysis | publisher=[[Springer-Verlag]] | location=Berlin, New York | isbn=0-387-94001-4 | year=1993}}
* {{Citation | last1=Rudin | first1=Walter | author1-link=Walter Rudin | title=Principles of Mathematical Analysis | publisher=[[McGraw-Hill]]| location=New York | isbn=0-07-054235-X | year=1976}}

{{点集拓扑}}
{{集合论}}
{{數的系統}}

[[Category:无穷集合论基本概念]]
[[Category:基数|K]]
[[Category:无穷]]