可數集

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

「可數集」這個術語有時也指代可數無窮集，即僅代表能和自然數集本身一一對應的集合^[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) harv模板錯誤: 無指向目標: CITEREFApostol1969 (幫助).
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