定義
如果一個集合與正整數集合之間存在一一對應,則這個集合稱為可列集(或可數集); 也就是說, 存在一個從該集合到正整數集合的雙射(也稱可逆映射)。
種類
自然數集、有理數集、代數數集都是可列集。
實數集、複數集、直線點集、 平麵點集都是不可列集(或不可數集)。
可列集是最小的無限集; 它的冪集是不可數集--和實數集存在一一對應(也稱同勢)。 所謂冪集, 就是原集合中所有的子集(包括全集和空集)構成的集族。
舉例證明
證明:有理數集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個,可將它們記為xxx
於是區間(0,1]中的有理數全體可以排成
xxxxxxxxx
這就證明了有理數Q是可列集。
可以證明,可列集有下列重要性質:
1、 有限個可列集的並是可列集。
2、 可列個可列集的並是可列集。
3、 任何可列集的的無窮子集是可列集。
4、 任何無窮集都包含一個可列的真子集。
5、 一個無窮集並上一個可列集還與其自身等勢 。
6、 可列集的冪集與實數集等勢。
猜想和悖論
康托第一個認真研究了無限集合, 分清了可列集和不可數集的區別, 並用對角線法證明了實數集不是可列集。此外,康托指出了冪集的勢總是嚴格大於原集合。由此結論導致了康托猜想(即連續統假設)和康托悖論。
康托猜想
不存在一個集合, 它的勢嚴格大於可列集的勢, 同時嚴格小於實數集的勢。
邏輯學家歌德爾證明了這個連續統假設是不能被證明的,也不能被證偽--就是說不能從現有的數學公理體系推演出該結論或者否定該結論。
康托悖論
考慮所有的集合組成的最大的集族, 這個集族的冪集當然也是集合, 所以本身也是該集合的一部分, 從而它的勢應該不超過原集合的勢;但是另一方面, 冪集的勢又嚴格大於原集合的勢, 從而導致矛盾。
羅素首先意識到集合的概念存在問題。 他提出所謂的類型論, 指出有一類“集合”並不是真正的集合, 而是所謂的“類”,集合本身是不能包含自身的;“類”卻可以。 從這個角度出發,就可以解釋上述的悖論。
等勢概念
定義:集合A與集合B等勢(等基數),若且唯若,A與B之間存在雙射(一一對應、可逆映射)。
在此意義下,刻畫了兩個無窮集合比較“多少”的一種辦法。但這裡的“多少”概念只是一種直觀的解釋,已經和有限集合比較多少的情況發生了變化。
在有限集合中,一個集合不可能與其真子集等勢。但無限集合的比較,則不同。比如,整數集和偶數集之間,可以通過雙射f(n)=2n 建立一一對應的關係。所以整數集和偶數集是等勢的,雖然偶數集是整數集的真子集。集合論認為,這種與其某一真子集等勢的性質,恰好反映了無窮集合的本質,反映出了有限集和無窮集之間的一個重大區別。
康托爾對角線
證明實數區間[0,1]中所有的實數組成的集合是不可列集。
其實只要證明(0,1]區間的實數集是不可列的。反證法,如果它是可列的,說明其中所有的實數均可排列成一數列t,t,...,t,...,只有這樣,它才能一一對應於自然數集。好,這時我們將(0,1]中的實數用十進制的無限小數表示:
t=0.ttt...t...
t=0.ttt...t...
...
t=0. ttt...t...
...
其中所有的t都是0~9這十個數字中的某一個。
但是現在我們可以構造一個小數a=0.aaa...a...,任意的a也都是0~9這十個數字中的某一個,但我們讓每個a都不等於上述實數列中的t,也就是a的第i位的數字跟t的第i個數字不同。這是可行的,因為我們用的是十進制小數,不同於t的還剩9個不同的數字可供a選擇。
當我們構造好了這樣的一個小數之後,我們發現它實際上跟上述小數列中的任何一個都不相等。這就造成了邏輯上的矛盾,你說已經把所有小數都列出來了,但是我卻發現至少我構造的這個小數,你還沒有羅列出來。就算你亡羊補牢,把我這個也補充進去,但是我還是可以根據同樣規則又構造出另一個。所以,只能說明實數是無法跟可列集形成一一對應的,也就是前面的假設是錯誤的。
因此[0,1]區間的實數不是可列集。同樣,取掉0,1兩個數之後的(0,1)區間的實數也不是可列集。