康托尔定理指的是在集合论中,任何集合A的幂集P(A)的势严格大于A的势.康托尔定理对于有限集合成立,对于无限集合也同样成立.

　　下面给出由集合论的创始人康托尔于1891年所做的康托尔定理的证明:

　　设f是从A到A的幂集P(A)的任何函数.必须证明这个f必定不是满射的.要如此,展示一个A的子集不在f的像中就足够了.这个子集是:

　　B={x∈A:x/∈f(x)}(注:符号:/∈代表的是不属于)

　　要证明B不在f的像中,假设B在f的像中.那么对于某个y∈A,我们有f(y)=B.现在考虑y∈B还是y/∈B?如果y∈B,则y∈f(y),但是通过B的定义,这蕴涵了y/∈B.在另一方面,如果y/∈B,则y/∈f(y)并因此y∈B.任何方式下都是矛盾.因为x在表达式"x/∈f(x)"中重复出现,这是对角论证法.

　　下面通过一个实例来详细的讲解一下康托尔定理的证明过程:设自然数集合N={0,1,2,3,4.n.},自然数集合的幂集合P(N)={{1},{1,2},{2,4,6},{1,3,5,8,9}.},P(N)中包含所有的的N的子集,比如所有偶数的集合{2,4,6,...},还有空集.

　　假设N与P(N)之间是存在双射的,我们将尝试对N的每个元素都配对上P(N)的元素,使得这两个集合中没有元素是未配对的.配对元素的尝试将是如下样子的:

　　1------>{4,5,8}

　　2------>{1,2,6,8}

　　3------>{1,3,5}

　　4------>{2,3,7,9}

　　5------->{5}

　　.

　　在上述对应中,某些自然数被配对上P(N)中不包含它们的子集.例如,数1被配对上{4,5,8},数4被配对上{2,3,7,9}.其他自然被配对上包含它们的子集.比如数2被配对上{1,2,6,8},数3被配对上{1,3,5},数5被配对上{5}.

　　使用这个想法,让我们建造一个自然数的特殊集合:设D是被配对上不包含它们的子集的所有自然数的集合.通过定义,则幂集P(N)必定包含这个集合D作为元素.所以D必定被配对上某个自然数.但是这导致了一个问题:哪个自然数和D配对呢?它不能是D的成员,因为D被特殊构造为只包含那些不配对上包含它们的子集的自然数.在另一方面如果配对于D的自然数不包含在D中,则再次通过D的定义,它必定包含在D中.

　　这个矛盾是因为这个自然数不能同时出现在D的内部和外部.所以,没有自然数可以配对于D,而我们的最初假定在N和P(N)之间存在双射是有矛盾的.所以N与P(N)之间不存在双射,而N的势不能大于P(N)的势,所以P(N)的势必大于N的势.

　　根据上述康托尔定理的证明思路,下面我们来考虑一下这个命题:康托尔运用一一对应的方法证明了全体偶数集合与全体自然数集合等势,则根据康托尔定理,偶数集合的幂集合P（M）与自然数集的幂集合P（N）也应该是等势的.

　　既然N与P（N）之间不存在双射,则N与偶数集合的幂集合P（M）之间同样不能存在双射,否则就会有矛盾,但事实的确是这样的吗?

　　首先我们来假设N到偶数集合的幂集合P(M)之间是存在双射的,也许你会说,那样也可以同样运用康托尔的对角论证法来从中推导出来矛盾,但这是不可能的,原因是:如果同样是按照康托尔的方法,设D是所有不配对上包含于它们所对应的象的自然数的集合,那么这个集合之中会包含有所有的奇数或一部分偶数,而这个集合不是P(M)中的元素(P(M)之中的元素全都是偶数集合的子集),所以康托尔无法用同样的反证法来从中推导矛盾.

　　接下来我们尝试一下做N到P(M)之间的一一对应:

　　设N={1,2,3,4,5.n.}

　　设P(M)={{2},{2,4,6},{4,8,18,28},{6,22}.},P(M)之中包含所有偶数集合的子集.

　　首先,我们将N中的所有偶数与P(M)之中的所有单元素子集做一一对应,P(M)之中的所有单元素子集是:{{2},{4},{6},{8}.},这样,N中所有的偶数全部与P(M)之中的单元素子集一一对应,则N中余下来的是全体奇数.

　　接下来的第二步,我们将全体奇数排成一个数列:1,3,5,7,9,11.,运用ZFC之中的选择公理,从这个数列中每相隔一个数取出来一个数重新排成为一个数列,它是:1,5,9,13,17,21.,这个数列与奇数集合等势,也与N等势,我们将其中的一个数列定义为a1,另一个数列定义为a2,接着我们仍然运用选择公理从a2数列中每相隔一个数取出来一个数重新组成一个数列,将它定义为a3,这个a3同样与N等势,然后再从a3数列中每相隔一个数取出来一个数组成一个新的数列a4,接着从a4数列之中再取出来一个数列a5.,根据ZFC之中的无穷公理,我们可以从整个奇数集合之中取出来无穷个无穷数列:a1,a2,a3,a4.an.,这无穷个数列合并在一起就是整个的奇数集合.(而且每一个数列皆与N等势).

　　接下来的第三步,我们来分析P(M)之中的所有元素,我们可以将P(M)之中的所有元素分为单元素子集,双元素子集,三元素子集.n元素子集.,首先,我们运用先选择公理将P(M)之中所有包含有无穷个元素的子集全部找出来,定义为是b1,如:b1之中的所有元素为:

　　b11:{2,4,6,8,.2n.}

　　b12:{4,6,12,18,24,.}

　　b13:{2,24,32,48,58.}

　　.

　　接下来,运用选择公理将所有P(M)之中的双元素找出来组成P(M)的一个子集,定义为b2,然后再运用选择公理将所有三元素全部找出来组成P(M)的子集定义为b3,再将所有四元素全部找出来组成P(M)的子集定义为b4.,这样,P(M)之中的所有元素就全部的化分成为无穷个子集:b1,b2,b3,b4,b5.bn.

　　最后做N到P(M)之间的一一对应:

　　令a1对应b1,a2对应b2,a3对应b3,a4对应b4.an对应bn.

　　因为a1与b1皆为无穷数列,再将两个数列之中的数做一一对应:a11对应b11,a12对应b12,a13对应b13,a14对应b14.,其余的所有数列也是如此对应,则:最终的结果就是:N中的所有的元素在P(M)之中都有唯一的一个对应的象,所以它是一个双射,从而证明自然数集合与偶数集合的幂集合之间存在双射,两集合等势.

　　但是接下来出现了一个问题:既然康托尔证明了偶数集合与自然数集合等势,那么偶数集合的幂集合的基数必大于自然数集合的基数,两集合之间必不能存在双射,现在的的确确是证明了N到P(M)之间存在双射,究竟是哪里出错了?

　　唯一的可能就只能是:偶数集合与自然数集合不等势,即