可列集

定義

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

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

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

證明：有理數集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、可列集的冪集與實數集等勢。

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

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

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

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