前面说了奇数集、偶数集、自然数集、有理数集都是可数集。是否存在不可数的集合，或者说存在比自然数集大的集合呢？

德国数学家康托尔首先解决了这个问题，答案是肯定的。下面就来证明自然数的幂集是不可数的。先解释一下什么是幂集。一个集合的所有子集所组成的集合就是它的幂集，比如{1,2,3}的幂集是{∅，{1}，{2}，{3}，{1,2}，{2,3}，{1,3}，{1,2,3}}。

定理：自然数的幂集是不可数的。

证明：假设它是可数的，它的元素按顺序排列：S1、S2、S3、S4、S5……。这里的每个元素都是集合。可以构造出一个元素D，D也是自然数的子集，但它不在这个序列中。这样构造集合D：k属于Sk当且仅当k不属于D。具体来说，如果1属于S1，则1不属于D。如果1不属于S1，则1属于D。对2、3、4等所有其他数字也这样。（举个例子。考虑有限集{{1,3}，{2,4}，{1,4}，{1,2}}，它的元素排列如下：{1,3}，{2,4}，{1,4}，{1,2}，则构造出来的集合D为{3,4}，它和这个集合中的任一个元素不同。）

接着证明D和序列中的任一个元素都不同。假设D和某个元素Sk相同，即D=Sk。按照D的构造方法，k属于Sk当且仅当k不属于D，即k属于D当且仅当k不属于D。而这是不可能的。所以D不在序列中。这是自然数幂集是可数的相矛盾。因为如果它是可数的，自然数的所有子集都在这个序列中。

实际上，上面的证明可以推广：任一集合都小于它的幂集。

反对角线方法

康托尔构造集合D的方法叫做反对角线方法。为了使这个方法更清晰，从不同的角度再次分析一下上面的证明。

自然数的任一子集可以用一串0和1表示。如果n属于这个集合，则在第n个位置是1，反之则是0。比如集合A={2,3,5}，则可表示成0110100000000……。

为了简单，仅考虑上面的集合{{1,3}，{2,4}，{1,4}，{1,2}}的例子。

这个表格对角线上的元素为1100，取相反的值为0011，则集合D={3,4}。采用反对角线方法可构造出原来序列中不存在的元素。

下面用反对角线方法证明实数集是不可数的。

定理：实数集是不可数的

只要证明[0,1)之间的实数不可数就行了。

假设它是可数的。它的元素排列如下：a₀、a₁、a₂、a₃、a₄、a₅……。

每个小数都可以用无穷小数表示，比如0.1=0.100000……，后面全是0。所以序列中的每个数可以展开如下（下面的每一个a_mn都是0到9中的一个数）：

这样构造小数D，它D_m≠a_mm，这样得到的D不同于序列中的任一个小数a_m，所以[0,1)是不可数的。所以实数集是不可数的。

（这里的证明是不严格的。因为同一个小数有不同的表示方法，比如0.100000……=0.099999……。用反对角线方法构造出来的D，在表示上虽然和序列中的任一个小数不同，但不能保证它们就不是相同的小数。不过对上面的证明稍作修改，就可以弥补这个漏洞。）

连续统假设

康托尔提出问题：是否存在这样一个集合，它的元素数量大于自然数个数而小于实数的个数。康托尔猜测不存在这样的集合，这个猜测又叫做连续统假设。哥德尔和柯恩证明了，这个问题是不可解决的。即既不可能证明这样的集合存在，也不可能证明这样的集合不存在。用严格的术语说，连续统假设在集合论ZFC系统中是不可判定的。