可數集

在數學上，可數集，或稱可列集，是與自然數集的某個子集具有相同基數（等勢）的集合。在這個意義下，可數集由有限可數集和無限可數集組成。不是可數集的無窮集稱為不可數集。這個術語是康托爾創造的。可數集的元素，正如其名，是「可以計數」的：儘管計數有可能永遠無法終止，集合中每一個特定的元素都將對應一個自然數。

「可數集」這個術語有時也指代可數無窮集，即僅代表能和自然數集本身一一對應的集合。兩個定義的差別在於有限集合在前者中算作可數集，而在後者中不算作可數集。

為了避免歧義，前一種意義上的可數有時稱為至多可數，後一種可數集則稱為無限可數集。

定義

如果從$S$到自然數集合$\mathbb {N} =\left\{1,2,3,\ldots \right\}$存在單射函數，則$S$稱為可數集。

如果$S$還是滿射，則同樣是對射，則稱$S$是無限可數集。

換句話說，一個集合要想是無限可數集，它要和自然數集$\mathbb {N}$有一一對應關係。

如上所述，這個術語不普遍：一些作者在這裡使用可數來表示被稱為「無限可數」，並沒有包括有限集。

介紹

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

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

正規定義和性質

由定義，如果存在從$S$到自然數集合$\mathbb {N} =\left\{0,1,2,3,\ldots \right\}$存在單射函數$f:S\rightarrow \mathbb {N}$，則$S$稱為可數集。

這似乎自然地把集合劃分為不同類別：把所有包含一個元素的集合放在一起；包含兩個元素的集合在一起......最後，把所有無限集合放在一起，並認為它們具有相同的大小。然而，在大小的自然定義下，這種觀點是不確切的。

為了闡述這一點，我們需要一個對射的概念。雖然對射看起來比數更加高深，但原本數學發展中集論定義函數要先於數字。因為它們都是基於更簡單的集合。這就引出了對射的概念：

$a\leftrightarrow 1,b\leftrightarrow 2,c\leftrightarrow 3$

由於$\left\{a,b,c\right\}$的每個元素都可以和$\left\{1,2,3\right\}$中準確的一個配對，並且反過來也同樣，這就定義了一個對射。

我們將這個情境一般化，定義若且唯若它們之間存在對射，兩個集合的大小相同。對於有限集，這裡給出了「大小相同」的常用定義。那麼對於無限集呢？

考慮集合$A=\left\{1,2,3,\ldots \right\}$（正整數集），和$B=\left\{2,4,6,\ldots \right\}$（正偶數集）。我們說，在我們的定義下，這些集合有相同的大小，並且因此B是無限可數集。我們需要證明它們之間存在對射。但這是很簡單的，運用$n\leftrightarrow 2n$，那麼

$1\leftrightarrow 2,2\leftrightarrow 4,3\leftrightarrow 6,4\leftrightarrow 8,\ldots$

正如前面的例子，$A$的每個元素都已和$B$中準確的一個配對，並且反過來也同樣。因而它們大小相同。這給出了一個集合與其一個合適的子集大小相同的例子，這種情形在有限集中是不可能的。

同樣，自然數的有序對的集合，也就是自然數集合的笛卡兒積 $\mathbb {N} \times \mathbb {N}$，是無限可數集，可以沿著圖中的一種路徑：

康拖爾配對函數給每一對自然數分配了一個自然數

配對結果就像這樣：

$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$

顯然這個映射可以覆蓋所有這些有序對。另一個證明方法是可以定義一個從自然數集合的笛卡兒積 $\mathbb {N} \times \mathbb {N}$到自然數集合$\mathbb {N}$的單射函數$f(p,q)=2^{p}3^{q}$。

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

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

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

參見

• Aleph數
• 計數
• 希爾伯特旅館悖論
• 不可數集
• 有限集合

參考資料

• 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