可列集

如果一個集合與正整數集合之間存在一一對應，則這個集合稱為可列集（或可數集）； 也就是説， 存在一個從該集合到正整數集合的雙射（也稱可逆映射）。

自然數集、有理數集、代數數集都是可列集。

實數集、複數集、直線點集、 平面點集都是不可列集（或不可數集）。

可列集是最小的無限集； 它的冪集是不可數集--和實數集存在一一對應（也稱同勢）。 所謂冪集， 就是原集合中所有的子集（包括全集和空集）構成的集族。

證明：有理數集Q是可列集

證 由於區間（−∞,+∞）可以表示為可列個區間（n,n+1](n∈Z)的並，我們只須證明區間（0,1]中的有理數是可列集即可。

由於區間（0,1]中的有理數可惟一地表示為既約分數q/p，其中p∈N+，q∈N+，q≤p，並且p，q互質。我們按下列方式排列這些有理數：

分母p=1的既約分數只有一個： x₁₁=1;

分母p=2的既約分數也只有一個：x₂₁ =1/2；

分母p=3的既約分數有兩個： x₃₁=1/3, x₃₂ =2/3；

分母p=4的既約分數也只有兩個：x₄₁=1/4，x₄₂=3/4；

... ...

一般地，分母p=n的既約分數至多不超過n-1個，可將它們記為x_n1，x_{n2，... ，}x_{nk(n)，其中k（n）≤n。}

於是區間（0,1]中的有理數全體可以排成

x_11，x_21，x_31，x_32，x_41，x_{42，... ，}x_n1，x_{n2，... ，}x_{nk(n)，... 。}

這就證明了有理數Q是可列集。

可以證明，可列集有下列重要性質：

1、 有限個可列集的並是可列集。

2、 可列個可列集的並是可列集。

3、 任何可列集的的無窮子集是可列集。

4、 任何無窮集都包含一個可列的真子集。

5、 一個無窮集並上一個可列集還與其自身等勢 。

6、 可列集的冪集與實數集等勢。 ^[1] 

康託第一個認真研究了無限集合， 分清了可列集和不可數集的區別， 並用對角線法證明了實數集不是可列集。此外，康託指出了冪集的勢總是嚴格大於原集合。由此結論導致了康託猜想（即連續統假設）和康託悖論。

不存在一個集合， 它的勢嚴格大於可列集的勢， 同時嚴格小於實數集的勢。

邏輯學家歌德爾證明了這個連續統假設是不能被證明的，也不能被證偽--就是説不能從現有的數學公理體系推演出該結論或者否定該結論。

考慮所有的集合組成的最大的集族， 這個集族的冪集當然也是集合， 所以本身也是該集合的一部分， 從而它的勢應該不超過原集合的勢；但是另一方面， 冪集的勢又嚴格大於原集合的勢， 從而導致矛盾。

羅素首先意識到集合的概念存在問題。 他提出所謂的類型論， 指出有一類“集合”並不是真正的集合， 而是所謂的“類”，集合本身是不能包含自身的；“類”卻可以。 從這個角度出發，就可以解釋上述的悖論。

定義：集合A與集合B等勢(等基數)，當且僅當，A與B之間存在雙射（一一對應、可逆映射）。

在此意義下，刻畫了兩個無窮集合比較“多少”的一種辦法。但這裏的“多少”概念只是一種直觀的解釋，已經和有限集合比較多少的情況發生了變化。

在有限集合中，一個集合不可能與其真子集等勢。但無限集合的比較，則不同。比如，整數集和偶數集之間，可以通過雙射f(n)=2n 建立一一對應的關係。所以整數集和偶數集是等勢的，雖然偶數集是整數集的真子集。集合論認為，這種與其某一真子集等勢的性質，恰好反映了無窮集合的本質，反映出了有限集和無窮集之間的一個重大區別。

證明實數區間[0,1]中所有的實數組成的集合是不可列集。

其實只要證明(0,1]區間的實數集是不可列的。反證法，如果它是可列的，説明其中所有的實數均可排列成一數列t₁,t₂,...,t_n,...，只有這樣，它才能一一對應於自然數集。好，這時我們將(0,1]中的實數用十進制的無限小數表示：

t₁=0.t₁₁t₁₂t₁₃...t_1n...

t₂=0.t₂₁t₂₂t₂₃...t_2n...

...

t_m=0. t_m1t_m2t_m3...t_mn...

...

其中所有的t_ij都是0～9這十個數字中的某一個。

但是我們可以構造一個小數a=0.a₁a₂a₃...a_k...，任意的a_i也都是0～9這十個數字中的某一個，但我們讓每個a_i都不等於上述實數列中的t_ii，也就是a的第i位的數字跟t_i的第i個數字不同。這是可行的，因為我們用的是十進制小數，不同於t_ii的還剩9個不同的數字可供a_i選擇。

當我們構造好了這樣的一個小數之後，我們發現它實際上跟上述小數列中的任何一個都不相等。這就造成了邏輯上的矛盾，你説已經把所有小數都列出來了，但是我卻發現至少我構造的這個小數，你還沒有羅列出來。就算你亡羊補牢，把我這個也補充進去，但是我還是可以根據同樣規則又構造出另一個。所以，只能説明實數是無法跟可列集形成一一對應的，也就是前面的假設是錯誤的。

因此[0,1]區間的實數不是可列集。同樣，取掉0，1兩個數之後的(0,1)區間的實數也不是可列集。