可數集（英文名：Countable set），凡是與自然數所成之集N對等的集合，稱為可數集合或可列集合。可數集的基數為自然數集的基數，記作???（讀作“阿列夫零”）。
格奧爾格·康托爾在1874年提出了集合的定義，此后進一步定義了集合的子集、交集、并集、映射等一系列概念。康托爾提出了通過一一對應的方法對無限集合的大小進行比較，并將能夠彼此建立一一對應的集合稱為等勢，即可以被認為是“一樣大”的。他引入了可數無窮的概念，用來指與自然數集合等勢的集合，并證明了有理數集合是可數無窮。
可數集在計算機科學、算法設計、計算水力學中有著廣泛的應用。在這些應用中，可數集合也是構建和分析相關模型的重要工具，對于科學研究和實際問題的解決起到了至關重要的作用。
定義
設是一個集合，如果是空集或者存在正整數使得集合和集合之間有一個一一映射，則稱集合是一個有限集。不是有限集的集合稱為無限集；如果存在一個從集合到正整數集的單射，則稱集合是一個可數集，不是可數集的集合稱為不可數集。有限集的任何一個子集都是有限集。因此，有一個無限子集的集合必為無限集。凡有限集皆是可數集，但可數集可為無限集。例如，正整數集便是一個無限的可數集.的單射像集也是無限的可數集。
凡是與自然數所成之集對等的集合，稱為可數集合或可列集合。可數集的基數為自然數集的基數，記作（讀作“阿列夫零”）。
簡史
格奧爾格·康托爾（Cantor，Georg Ferdinand Ludwig Philipp，1845.3.3-1918.1.6）德國數學家，集合論的創始人。康托爾在1874年提出了集合的定義：“一個集合就是我們的直觀或我們的思想上那些確定的、能區分的對象（它們稱為集合的元素）匯集在一起，作為一個整體來考慮的結果。”這里用匯集來定義集合是同義語反復。之后人們認識到集合是一個原始的概念，不能用其他概念來定義，而只能加以描述或說明。在集合概念產生后，進一步定義了集合的可數集、不可數集、子集、交集、并集、映射等系列概念。
格奧爾格·康托爾提出了通過一一對應的方法對無限集合的大小進行比較，并將能夠彼此建立一一對應的集合稱為等勢，即可以被認為是“一樣大”的。他引入了可數無窮的概念，用來指與自然數集合等勢的集合，并證明了有理數集合是可數無窮，而實數集合不是可數無窮（即實數集與自然數集有不同的基數），這表明無窮集合的確存在著不同的大小，他稱與實數等勢(從而不是可數無窮)的集合為不可數無窮。原始證明發表于1874年，這個證明使用了較為復雜的歸納反證法。1891年他用對角線法重新證明了這個定理。另外，他證明了代數數集合是可數集，以及n維空間與一維空間之間存在一一對應。
性質
（1）可數集的子集至多可數。
（2）若為可數集，為有限集或可數集，則是可數集。
（3）有限或可數個可數集的并任是可數集。
（4）有限個可數集的直積是可數集。
（5）任一無限集都包含可數子集。
相關定理
定理1
任何無限集合都至少包含一個可數子集。
證明 設是一個無限集，因為，可以從中取一個元素，記作。由于是無限集，則，于是又可以從中取一個元素，記為，顯然，且。設已從中取出個這樣的互異元素，由于是無限集，故，于是又可以從中取一個元素，記作，顯然且與都不相同。這樣，由歸納法，就可以找到的一個無限子集，它是一個可數集合。
定理2
可數集合的任何無限子集必為可數集合，從而可數集合的任何子集或者是有限集，或者是可數集。
證明 設是可數集，是的一個無限子集，那么，所以。由定理1可知有可數子集，這樣，所以。由Bernstein定理可知，即也是可數集。
由可數集的定義，一個集合是可數集，當且僅當的元素能排列成無窮序列（時）的形式。
定理3
設為可數集，為至多可數集，則為可數集。
證明 （1）先設，因為是可數集，設，若是有限集，設，此時
其中，這是一個可數集。
若是無限集，設，此時
其中，這是一個可數集。
（2）一般情形，即，此時，令，則，并且，因為，是至多可數集，由（1）可知，是可數集，于是是可數集。
定理4
有理數全體成一可數集合
證明 設（），則是可數集，全體正有理數成一可數集，因正負有理數通過，成為對應，故全體有理數成一可數集，但有理數全體所成之集合，故可知為可數集，證畢。
定理5
設，都是可數集，則也是可數集。
證明 （1）先設。因都是可數集，故可置
。
照箭頭順序可將排成：
因此，是可數集。
（2）一般情形
令，則（當時），且。
今都是都是有限集或可數集（定理2），如果只有有限個不為空集，則由定理3的推論，為可數集（因至少為可數集），如果有無限多個（必為可數個）不為空集，則由（1）末之注意，也是可數集，故在任何場合都是可數集。
定理6
若中每個元素可由個互相獨立的記號一對一的加以決定，各記號跑遍一個可數集。
，則為可數集。
證明 用數學歸納法予以證明。
若則定理為真，假設當時定理是真的，由此證明當時定理也是真的。
設 ，中滿足的元素，記全體為，則由假定為一個可數集，而，所以是可數集。
定理7
代數數的代數數的全體成一可數集。(所謂代數數，乃是整系數多項式的根)。
例如，設是一個無窮集合，則必有，使，而可數。
證明 由于是一個無窮集合，所以含有一個可數子集。
設令，則，且，均為可數集。令，，則且是可數集。又因為也是可數集，所以，由，，所以。
相關推論
推論1
中的有理數是可數集。中的有理點集是可數集。
證 對每一個，令，顯然有，所以是可數集，從而知是可數集。
推論2
可數個兩兩不交的可數集的并集，仍然是可數集。
證明 設集合是可數集。
由題設知道時，有，則有：
得到
它與自然數集是一一對應的，所以是可數集。
這種得到并集的排列的方法叫做對角線排列法。在數學的證明中，和計算機科學的某些理論中經常會用到。
相關概念
整數集
全體整數的集合稱為整數集，記作，即。
自然數集
全體非負整數即自然數組成的集合稱為自然數集（或非負整數集），記作，即
非負奇數
由所有正奇數組成的集合稱為非負奇數集。可以用列舉法表示為
非負偶數
由所有正偶數組成的集合稱為非負偶數集。可以用列舉法表示為
不可數集
可數集的基數我們記作，讀作“阿列夫零”。若集合的勢大于可數集的勢，則稱它為不可數集。區間便是一個不可數集。我們稱這樣的集合為不可數集或不可列集，它是具有連續統的勢的集合。我們記不可數集的勢為，讀作“阿列夫”。
有理數集
一般地，把研究對象統稱為元素（element），把一些元素組成的總體叫做集合（set）（簡稱為集）。所有有理數構成的集合為有理數集，用符號表示。
等勢
若集合和之間存在雙射，則稱它們有相同的基數，也稱兩個集合等勢。如果與不對等，但存在的真子集和對等，則稱比有較小的基數。
子集
設是兩個集合。若，則稱是的子集。
推廣
可數集合的每一個無窮子集合都是可數的。集合，由它的可數性，可以寫為下面的形狀
設是屬于的第一個元素，是有同一性質的第二個元素，以此類推。
設，我們得出，子集合的元素是由序列
所構成的，這就是說這一個子集合是可數的。
應用
算法設計
在算法設計中，可數集也發揮著重要的作用。在編寫算法時，我們需要確定如何處理不同的輸入。如果輸入數據是可數集，那么可以設計一些有效的算法來解決問題，如排序、搜索等。如果輸入數據是不可數集，則可能需要使用不同的算法來解決。
計算機科學
可數集在計算機科學中有著廣泛的應用。其中一個重要應用是分治算法，它通過將一個復雜的問題分成兩個或更多的子問題來解決。在這個過程中，需要對一個可數集進行處理，以計算出需要將問題分割成多少個子問題。例如，確定四個男孩可以用多少種方式分享三個獎品，這可以通過二進制表示來表示不同的組合方式，從而幫助計算機快速地找到最優的分割方案。
計算水力學
計算水力學，正如其它許多自然科學學科，是一種描述和理解水力現象的學科。它通常使用可數集合，如有限可數集合和無限可數集合來研究水力現象。可數集合在這一過程中扮演了關鍵角色，它們可以有效地描述和分類各種不同的水力現象，并幫助科學家和工程師更好地理解和預測這些現象的發生。此外，可數集合的基數也可以用來比較無限集合的大小，這種方式對于研究和解決實際問題有很大的幫助。
參考資料 >