不可數集

設 A 和 B 為集合，若存在 A 到 B 的雙射，則稱 A 與 B 等勢，即為

。集合A 與 B 等勢可以形象地説為“A 和 B 集合中的元素一樣多”。 ^[1] 

可以利用等勢概念來定義有限集：設

，若集合 A 與

等勢，則稱 A 為有限集，否則稱為無限集。特別的，空集稱為有限集。

（1）自然數集合 N 是無限集。

（2）任何有限集均不能與其真子集等勢。 ^[1] 

與有限集合中元素的個數的記法一樣，集合 A 的基數用

表示。顯然，每個有限集都恰與集合

等勢，其中

，

。若

，則令

；對於無限集，則用一個特殊記號表示，例如對自然數集合 N ，令

ℵ₀（讀作“阿列夫零”）。

我們希望基數像普通數一樣，也具有相等關係和大小順序。設 A 和 B 為兩個集合：

（1）若 A~B，則稱 A 的基數和 B 的基數相等，記為 | A |=| B |，否則記為| A l ≠ l B l；

（2）若存在 A 到 B 的單射，則稱 A 的基數小於或等於 B 的基數，記為l A I ≤l B l，或者稱 B 的基數大於或等於A的基數，記為l B l ≥l A |；

（3）若l A I ≤l B l，且| A l ≠ l B l，則稱A的基數小於 B 的基數，記為| A | < | B |，或者稱B的基數大於A 的基數，記為l B l > l A |。

由定義，l A I=l B I可形象地理解成，A 中的元素與 B 中的元素一樣多。顯然，上述定義是有限集合的元素個數有大小的推廣。容易驗證，集合基數的關係具有自反性和傳遞性。義由Bernstein（伯恩斯坦）定理知，集合基數的關係還具有反對稱性。因此，集合基數的關係是一個偏序關係，進一步還可以證明它是一個全序關係。於是，像實數一樣，任何兩個基數均可以比較大小，基數也有無限多個，而且無最大者。

關於基數，有如下結論：

（1）設A 和 B 為兩個集合，於是l A I ≤l B l，或者l B I ≤l A l。

（2）基數之間的相等關係“=”是一個等價關係。

（3）基數之間的小於或等於關係“≤”是一個偏序關係。 ^[1] 

不可數集是無窮集合中的一種。一個無窮集合和自然數集合之間要是不存在一個雙射（不存在一一對應關係/法則），那麼它就是一個不可數集。

設 A 是一個集合，若 A 與自然數集 N 等勢，則稱 A 為可數無限集；若 A 是有限集，則稱 A 為可數集。不是可數集的集合稱為不可數集。 ^[1] 

康托爾在1874年和1891年分別用兩種不同的方法，證明了實數集是不可數集。其中1891年所用的方法更加為人所熟知，又被稱為對角線法。證明發表之後，這種方法在數理邏輯中獲得廣泛應用。

證明過程：令

，函數

是從 R 到 S 的雙射，因此 card(R)=card(S) ，下面證明S是不可數集。

反證法，假設 S 是可數集，則 S 可以表示為

，其中

，設：

其中

。

構造實數

，其中

。

這樣，r 和 S 中的所有實數都不相同，即

，產生矛盾，故 S 是不可數集，因此也證明 R 也是不可數集。 ^[2] 

無理數集也是不可數集。事實上，反設無理數集至多是可數集，因為有理數集是可數集，實數集就是有限個至多可數集的並集，為至多可數集，與已得的結果矛盾。所以無理數集是不可數集。

區間 [0,1] 是不可數集。

證明過程：（反證法）

顯然 [0,1] 是無限集，假設它是可數集，記

。

對

，存在 [0,1] 中長度不超過

的閉區間

，使

；

對

，存在

中長度不超過

的閉區間

，使

；

如此下去，得到一列閉區間，滿足：

（1）

；

（2）

的長度不超過

，且

。

因為

，由數學分析中的閉區間套定理可知，存在唯一一點

。顯然有

，由假設

應該是

中的某一點，即存在 m 使得

。由

的取法，

，這與

相矛盾，故 [0,1] 是不可數集。 ^[3]