在上节中，我们提到自然数集N是无限的，但是并非所有无限集都可与自然数集建立一一对应。
定义1 与自然数集合等势的任意集合称为可数的，可数集合的基数用Ψ0表示。
例如，
均为可数集。
我们把有限集和可数集统称为至多可数集。
定理1 A为可数集的充分必要条件是可以排列成
A={a1,a2,…,an,…}
的形式。
证明 若A可排成上述形式，那么将A的元素an与足码n对应，就得到A与N之间的一一对应，故A是可数集。
反之，若A为可数集，那么在A与N之间存在一种一一对应的关系f，由f得到n的对应元素an，即A可写为{a1，a2，…，an，…}和形式。证毕。
定理2 任一无限集，必含有可数子集。
证明 设A为无限集合，从A中取出一个元素a1，因为A是无限的，它不因取出a1而耗尽，所以从A-{a1}中可取元素a2，所以A-{a1，a2}也是非空集，所以又可取一元素a3，如此继续下去，就得到A的可数子集。证毕。
定理3 任一无限集合必与其某一真子集等势。
证明 设无限集合M，按定理2，必含有可数子集A={a1，a2，…，an，…}，设M-A=B，我们定义集合M到其自身的映象，f：M→M-{a1}，使得f（an）=an+1（n=1，2，…）且对于任何b∈B，有f（b）=b，这个f是双射的。证毕。
这个定理亦可用图1表示。
设线段AB，其上有线段CD，则线段AB与CD上所有的点，可作成一一对应。其作法是：把CD移出与AB平行，连AC、BD延长交于G，则AB上任意点E与G的连线EG必与CD交于F。
反之，CD上任意点F与G的连线FG延长必交AB于E，上述E，F的对应作法，即说明AB～CD。
定理4 可数集的任何无限子集是可数的。
证明 设A为可数集合，B⊆A为一无限子集，如将A的元素排成a1，a2，…，an，…，从a1开始，向后检查，不断地删去不在B中的元素，则得到新的一列ai1，ai2，…，ain，…，它与自然数一一对应，所以B是可数的。证毕。
定理5 可数个两两不相交的可数集合的并集，仍然是一可数集。
证明 设可数个可数集分别表示为：
令S=S1∪S2∪S3∪…，即
，对S的元素作如下排列：
在上述元素的排列中，由左上端开始，其每一斜线上的每一元素的两足码之和都相同，依次为2，3，4，…，各斜线上元素的个数依次为1，2，3，4，…，故
的元素可排列为：a11，a21，a12，a31，a22，a13，…，证毕。
定理6 设自然数集合N，则N×N是可数集。(www.xing528.com)
证明 首先我们把N×N的元素足码按表1的次序排列，并对表中每个序偶注以标号。我们可以作f：N×N→N如下：
若把f（m，n）看作表1中序偶〈m，n〉的标号，则
f:N×N→N
是个双射函数。这是因为：
①[x]表示x的整数部分。
由（1），（2）可知N×N是可数的。证毕。
定理7 有理数的全体组成的集合是可数集。
证明 由定理6中可知N×N是可数的，在N×N集合中删除所有m和n不是互为质数的序偶（m，n），得集合S⊆N×N，S={（m，n）|m∈N，n∈N且m和n互质}。因为S是N×N的无限子集，故据定理4可知，S是可数的。
令g：S→Q+即g：（m，
（ 其中m，n互质），因为g是双射，故Q+是可数集。又因为Q+～Q-，故
Q=Q+∪{0}∪Q-
是可数集。证毕。
定理8 全体实数构成的集合R是不可数的。
证明 因为（0，1）～R，令
S={x|x∈R∧(0＜x＜1)}
若能证S是不可数集，则R也为不可数集。
用反证法。
假设S是可数的，则S必可表示为：S={S1，S2，…}，其中Si是（0，1）间的任一实数。
设Si=0.ai1ai2ai3…，其中aij∈{0，1，2，…，9}（如0.2和0.123可记为0.1999…和0.12299…），
设 S1=0.a11a12a13…a1n…
S2=0.a21a22a23…a2n…
S3=0.a31a32a33…a3n……
其次，我们构造一个实数r=0.b1b2b3…使
这样，r与所有实数S1，S2，…，Sn，…不同，因为它与S1在位置1不同，与S2在位置2不同，等等。这证明了r∉S，产生矛盾，因此S是不可数的，即R是不可数集。证毕。
我们把集合（0，1）的基数记为“Ψ”，因为（0，1）～R，故K[R]=Ψ，“Ψ”也称作连续统的势。
免责声明：以上内容源自网络，版权归原作者所有，如有侵犯您的原创版权请告知，我们将尽快删除相关内容。
