离散数学自然数和归纳法概念和例题讲解课件

离散数学自然数和归纳法概念和例题讲解主要概念：主要概念：集合的后继集合的后继主要方法：归纳原理、第一归纳法、第二归纳法主要方法：归纳原理、第一归纳法、第二归纳法 自然数的引进方法自然数的引进方法 公理化方法：皮亚诺公理（公理化方法：皮亚诺公理（G.Peano）；）；构造性方法：借助构造性方法：借助集合论集合论，具体构造出，具体构造出 N。自然数构造的出发点自然数构造的出发点1)自自然然数数的的各各种种性性质质(运运算算、大大小小次次序序 及及 基基本本定定律律),都可以从都可以从 Peano 公理一一推导出来；公理一一推导出来；2)证证明明构构造造出出来来的的“自自然然数数”满满足足Peano公公理理，因因此此具有普通自然数的一切性质。具有普通自然数的一切性质。集合的后继集合的后继定义定义8.2(后继集合后继集合)对于任意集合对于任意集合 A，其，其后继集合后继集合 A+定义为：定义为：A+=A A 。每个集合都有每个集合都有唯一的唯一的一个后继。一个后继。引理引理 1 设设 A 为任意集合，为任意集合，则则 i)=；ii)=,；iii)A A；iv)A A；v)A 。构造自然数系统构造自然数系统N，+，冯冯 诺依曼（诺依曼（Von Neumann）方案：）方案：0 =1 =0+=0 2 =1+=,=0,1 3 =2+=,=0,1,2 n+1 =n+=0,1,n 自然数集合自然数集合 N（归纳定义法）（归纳定义法）i)0N，这里这里 0=；ii)若若 n N，则，则 n N；iii)若若 S N 满足满足 （极小化极小化）1)0S 2)如果如果 nS,则则 n+S 则则 S=N。大于大于/小于、加法、乘法小于、加法、乘法对每个自然数对每个自然数 n N，皆有，皆有 nn 及及 n n，据此有据此有:定义定义 8.4 若若 m,nN 使使 mn,则称则称 m小于小于n(或或 n大于大于m),记为记为 mn(或或 nm)。“小于小于”关系关系 是自然数集是自然数集 N上的上的反自反、反对称、传反自反、反对称、传递递的二元关系的二元关系可以用可以用归纳定义法归纳定义法在在 N 上定义上定义“+”与与“”如下如下：加法加法/乘法乘法 对任意的对任意的 n,m N，令，令 i)m+0 =m，m 0 =0 ii)m+n+=(m+n)+，m n+=m n+m。引理引理 2 若若 n N，则，则 n =n。证明：令证明：令 S =nnN 且且 n=n 显然显然 S N。为证明为证明 S=N，只需，只需 验证验证 S 满足：满足：1)0S。因为。因为 0N 且且 0=0。2)若若 nS，则，则 nN 且且 n=n。因此有。因此有 nN，此外，此外 (n)=(n n )=(n)(n )=n n =n。所以所以 nS。由自然数集合由自然数集合 N 归纳定义法的归纳定义法的 iii),由由 1)和和 2)即知即知 S=N。按按上上述述方方法法构构造造出出来来的的自自然然数数系系统统 N,+,满满足足以以下下的的皮亚诺皮亚诺(Peano)公理公理：P1：0 N；P2：若：若 n N，则有唯一的后继，则有唯一的后继 n N；P3：若：若 n N，则，则 n 0；P4：若：若 n,mN 且且 n=m，则则 n=m；P5：若：若 S N 满足满足 （归纳原理归纳原理）i)0S ii)如果如果 nS，则，则 nS 则则 S=N。证明：证明：P1，P2 和和 P5 分别为自然数集分别为自然数集 N 归纳定义法的归纳定义法的 i),ii)和和 iii)。P3 可以从引理可以从引理 1 的的 v)直接推导出来。直接推导出来。P4：若：若 n,m N 且且 n+=m+，则由则由 引理引理 2 可得：可得：n =n+=m+=m。Peano公理说明：公理说明：（1）0 是自然数；是自然数；（2）每一个自然数）每一个自然数 n 都有一个确定的后继数都有一个确定的后继数 n+；（3）没有以）没有以 0 为后继的自然数；为后继的自然数；（4）每一个自然数）每一个自然数 n 的的后继后继 是唯一的；是唯一的；（5）自然数集合是）自然数集合是 满足满足 1)、2)条件的条件的极小集合极小集合。（3）良基性：不存在一个自然数的）良基性：不存在一个自然数的无穷递降序列无穷递降序列 n1,n2,n3,ni,ni+1,使得使得 ni+1 ni。由自然数的定义可知，对于每一个自然数，比它小的由自然数的定义可知，对于每一个自然数，比它小的 自然数总是自然数总是有穷个有穷个，并且，并且 0 1 2 3 0 1 2 3 性质性质 8.18.1（作为集合的自然数的性质）（作为集合的自然数的性质）:（1）传递性：若）传递性：若 n1n2 且且 n2n3,则则 n1n3。（2）三歧性：对于任何两个自然数）三歧性：对于任何两个自然数 n1，n2，下列三式，下列三式 恰有一个成立：恰有一个成立：n1n2,n1=n2 ,或或 n2n1。数学归纳法（第一数学归纳法）：数学归纳法（第一数学归纳法）：设设 P(n)是自然数集合上的是自然数集合上的性质性质(或或 谓词谓词),如果能证明如果能证明1)P(0)是真；是真；2)对任何对任何 n N,P(n)P(n+)。则对所有则对所有 n N,P(n)为真。为真。Peano公理公理(5)的的极小化极小化就是自然数集合定义中的就是自然数集合定义中的极小化极小化,是数学归纳法的基础。下面给出一个是数学归纳法的基础。下面给出一个等价等价的数学归纳法的数学归纳法:数学归纳法是数学归纳法是论域论域为自然数集合的为自然数集合的推理规则推理规则，可形式，可形式表达如下：表达如下：P(0)(n)(P(n)P(n+1)(n)P(n)设设k是某个自然数，如果要证明谓词是某个自然数，如果要证明谓词P(x)对所有对所有xk的自的自然数成立，则上述原理可写成：然数成立，则上述原理可写成：P(k)(n)(n k P(n)P(n+1)(x)(x kP(x)第一、第二归纳法第一、第二归纳法对任意 n N，令 =N Nn =n,n+1,n+2,第二数学归纳法：第二数学归纳法：第二数学归纳法是一种更强形式的数学归纳法，第二数学归纳法是一种更强形式的数学归纳法，它在证明对所有自然数它在证明对所有自然数x，P(x)为真时，使用下述步骤：为真时，使用下述步骤：假设对所有假设对所有kn，P(k)是真，推出是真，推出P(n)为真，则为真，则(x)P(x)为真。即为真。即 (n)(k)(knP(k)P(n)(x)P(x).上述推论前提中包含了上述推论前提中包含了P（0）为真。因为把）为真。因为把n=0代入上代入上式后，式后，k0P(k)为真，推出为真，推出(k)(k0P(k)为真，为真，(k)(k0P(k)P(0)等价于等价于P(0)。因此两个原理的。因此两个原理的假设是等价的。假设是等价的。证明：证明：设设P(n)：n2n（1）对于）对于n=0,P(0)：020=1,因此因此P(0)为真为真.（2）对于任意的）对于任意的m N,假定假定P(m)是真是真,即即P(m)：m2m.（3）m+1 2m+1 2m+2m=2 2m=2m+1,即即m+1 2m+1.说明说明P(m+1)为真为真.因此因此P(m)P(m+1),由数学归纳法由数学归纳法,对于所有的对于所有的n N,P(n)为真为真.例例8.1：证明：证明n2n证明证明：设：设P(n)：2nn!(1)P(4):244!,24=16，4!=24.P(4)成立成立.(2)设对于任何设对于任何m4,P(m)为真为真,即即2mm!.(3)2 2m2 m!,2m+12 m!(m+1)m!=(m+1)!,即即2m+1(m+1)!上式说明上式说明P(m+1)为真为真.因此因此,对于所有的对于所有的n N,n4 ,P(n)为真为真.例例8.2 证明对于任何证明对于任何n 4,2nn!.例例8.3 证明所有证明所有n 2的整数能写成质数的乘积的整数能写成质数的乘积.证明：证明：对任意的对任意的n作归纳假设作归纳假设,设对每个设对每个k,2 kn能写能写成质数成质数 的乘积的乘积,证明证明n也能写成质数的乘积也能写成质数的乘积.证明分两种情况：证明分两种情况：(1)若若n是质数是质数,显然它就是一个质数的乘积显然它就是一个质数的乘积.(2)若若n不是质数不是质数,则可写成则可写成n=a b,而而2 a,bn.根据假根据假设设a和和b都可写成质数的乘积都可写成质数的乘积,所以所以n也能写成质数的乘也能写成质数的乘积积.根据第二数学归纳法结论成立根据第二数学归纳法结论成立.思考题思考题证明以下的证明以下的二重归纳原理二重归纳原理的正确性：的正确性：设设 i0,j0 N。假定对任意自然数。假定对任意自然数i i0 及及 j j0皆皆有有 一个命题一个命题 P(i,j)满足：满足：1)P(i0,j0)真；真；2)对任意自然数对任意自然数 k i0 及及 l j0，若若P(k,l)真，则真，则P(k+1,l)和和 P(k,l+1)皆皆真。真。则对任意自然数则对任意自然数 i i0 及及 j j0,P(i,j)皆真。皆真。证明：用第一归纳法证明：用第一归纳法 对于每个对于每个 i i0，用，用 Q(i)表示下列命题：表示下列命题：对于任意对于任意j j0，P(i,j)皆真。皆真。下面验证：下面验证：Q(i)满足第一归纳法满足第一归纳法i)Q(i0)为真为真，为此对，为此对 j 施用第一归纳法）：施用第一归纳法）：a)P(i0,j0)为真；为真；b)若若 P(i0,j)为真，则为真，则 P(i0,j+1)为真；为真；由归纳法可知，由归纳法可知，Q(i0)为真为真。ii)假设假设Q(i)为真为真（i i0），即对于任意），即对于任意i i0，j j0，P(i,j)为为真真 则对于任意则对于任意j j0，P(i+1,j)为真，即为真，即 Q(i+1)为真为真。由由 i)和和 ii)可知，对于任意可知，对于任意i i0，Q(i)皆真。皆真。所以，对于任意所以，对于任意i i0，j j0，P(i,j)为真。为真。8.2 基基 数数本节讨论度量和比较本节讨论度量和比较 两个集合两个集合大小大小的方法。的方法。重点掌握重点掌握 等势，等势，有穷、无穷集合，可数无穷集合，有穷、无穷集合，可数无穷集合，可数、不可数集合，无穷集合的性质，可数、不可数集合，无穷集合的性质，有穷集合、有穷集合、N 与与 R 的基数，基数的比较。的基数，基数的比较。比较两个集合的大小：比较两个集合的大小：1 1 计计数数法法：先先数数出出它它们们的的元元素素个个数数，再再加加以以比比较。较。2 2 愚人比宝法：每次各取一，看哪个最后取完。愚人比宝法：每次各取一，看哪个最后取完。对无限集，方法对无限集，方法 1 1 失效。失效。什么叫做什么叫做 数一个集合中元素个数数一个集合中元素个数？在该集合与某个在该集合与某个自然数自然数 之间建立一个双射。之间建立一个双射。等势等势设设 A 和和 B 为二集合，若存在从为二集合，若存在从 A 到到 B 的的双射双射，则称则称 A 和和 B 对等对等，或称，或称 A 和和 B 等势等势，记为，记为 A B。例例 设设 N=0,1,2,E=0,2,4,令令 f:N E 为为 f(n)=2n,其中其中 nN,则则 f 为为双射双射,故故 N E。等势关系的性质：等势关系的性质：对于任何集合对于任何集合 A,B,C，均有：，均有：(1)A A；(2)若若 A B,则则 B A；(3)若若 A B,B C,则则 A C。即即 等势关系等势关系有自反性有自反性,对称性和传递性，因此等势是对称性和传递性，因此等势是集合族上的集合族上的等价等价关系。关系。定义定义8.6：集合是集合是有穷的有穷的，当且仅当，当且仅当 它与某个自然数它与某个自然数等势等势，否则就是无穷的。，否则就是无穷的。例例 8.7:单位开区间单位开区间(0,1)=x|x R 0 x 1 与与实数集合实数集合 R 等势。等势。下面是下面是 从从(0,1)到到 R 的的 一一对应的一一对应的几何结构示意图几何结构示意图 图图8.4 (0,1)R 图图还可以建立还可以建立(0,1)到到 R 的双射的双射函数如下：函数如下：0 f(x)=tg(x 0.5),由由函数函数 f 的图象可见，的图象可见，F 是从是从(0,1)到到 R 的双射的双射函数函数。0 x例：如果例：如果 a，b R，a b，则，则(a，b)R。证：定义证：定义 f：(a，b)R 如下：如下：x(a，b)，令，令 f(x)=tg (x-(a+b)2)(b-a)，若若 x(a，b)时时,则则(x-(a+b)2)(b-a)(-/2,/2)显然显然f 是双射，所以是双射，所以(a，b)R。无穷集合可以与它本身的真子集无穷集合可以与它本身的真子集 等势等势任任何何无无限限集集都都如如此此，这这正正是是无无限限集集与与有有限限集集之之间间的的本本质质区别，也可以把它作为无限集的定义。区别，也可以把它作为无限集的定义。鸽笼原理（抽屉原理）鸽笼原理（抽屉原理）任何任何有限集有限集都不能与它的都不能与它的真子集真子集 对等对等。这个定理也叫抽屉原理，可通俗表述为：这个定理也叫抽屉原理，可通俗表述为：“如如果果把把 n+1 本本书书放放进进 n 个个抽抽屉屉里里，至至少少在在一一个个抽抽屉屉里有两本或两本以上的书。里有两本或两本以上的书。”上述原理可以导出有穷集合与无穷集合的根本差别上述原理可以导出有穷集合与无穷集合的根本差别：任何与自身真子集等势的集合均是无穷集合任何与自身真子集等势的集合均是无穷集合。例子例子把把 s 个个元元素素分分成成 t 个个组组，当当不不能能均均匀匀分分放放时时，必必有有一一个个组，其元素个数要超出组，其元素个数要超出“平均数平均数”。形式地叙述为：形式地叙述为：定定理理：把把 s(s 1)个个元元素素分分成成 t 个个组组，那那么么必必存存在在 一个组，至少含有一个组，至少含有 s/t 个元素。个元素。其中，其中，为为“向上取整向上取整”记号，记号，如如 4/3 =2。例子任意任意 13 个人，至少有二人生日在同一个月；个人，至少有二人生日在同一个月；任意任意 50 个人中，至少有个人中，至少有5人生日同月。人生日同月。例例：在在 1,2,2n 中中任任取取 n+1个个互互不不相相同同的的数数中中,必必存存在两个数在两个数,其中一个数是另一个数的倍数。其中一个数是另一个数的倍数。证明：任何正整数证明：任何正整数 n 都可以表示成都可以表示成 n=2 a b （这里（这里 a=0,1,2,且且 b为奇数）为奇数）设取出的设取出的 n+1 个数为个数为 k1,k2,kn+1，且，且 ki=2 ai bi，由于由于 b1,b2,bn+1 是奇数，共有是奇数，共有 n+1个，并且个，并且 bi ki。而而在在 1,2,2n 中中只只有有 n 个个不不同同的的奇奇数数，所所以以必必存存在在 i,j(1 i j n+1)使使得得 bi=bj。不不妨妨设设 ki kj，则则有有 kj/ki =2 aj ai为正整数，因此为正整数，因此 kj是是 ki的倍数。的倍数。例例：任任给给 52 个个整整数数，证证明明其其中中必必有有两两数数之之和和（或或之之差差）能被能被100整除。整除。证明：设证明：设 r 为为任意整数任意整数 n 被被100 除的余数，则除的余数，则 r 均满足：均满足：0 r 99。这些这些余数可以构成余数可以构成 51个抽屉如下：个抽屉如下：(0,0),(1,99),(2,98),(3,97),(49,51),(50,50)任给任给 52 个整数，则必有两个整数个整数，则必有两个整数 a 和和 b 的的余数余数 ra和和 rb 落在落在同一个抽屉中，同一个抽屉中，若若 ra和和 rb落在落在(0,0)或或(50,50)中，则中，则a 和和 b之和、之差均能之和、之差均能被被100整除。整除。若若 ra和和 rb落在落在(i,100-i)(1 i 49)中中,当当 ra和和 rb 取同一个数取同一个数时，则时，则 a 和和 b之差能被之差能被100整除，否则整除，否则a 和和 b之和能被之和能被100整整除。除。定理定理8.1：任意有穷集合任意有穷集合 A 唯一地唯一地与一个自然数等势与一个自然数等势。证明证明:设对于某两个自然数设对于某两个自然数 m 和和 n,A m 且且 A n,则则 m n。根据自然数的。根据自然数的 三岐性三岐性 和和 传递性传递性,则则 m=n，或者或者 其中一个是另一个的真子集其中一个是另一个的真子集。因为因为 m n,所以所以 后一种可能后一种可能 是不存在的是不存在的,因此因此 只能是只能是 m=n。证证毕毕 定义定义8.7 (有穷集合的有穷集合的 基数基数)：对于任意有穷集合对于任意有穷集合 A,存在唯一的自然数存在唯一的自然数 n,使得使得 A n,称称 n 为为 A 的的基数基数,记为记为#A。集合的基数集合的基数我们现在拓广集合中含有的元素个数这一概念，引进我们现在拓广集合中含有的元素个数这一概念，引进集合的集合的基数基数的概念。的概念。A：(A)（card(A)或或A）显然，每个显然，每个有限集有限集都与唯一的都与唯一的自然数自然数 对等对等。设设 n N，若，若 A n，则令，则令#(A)=n。对于无限集的基数，我们规定特殊的记号，例如令对于无限集的基数，我们规定特殊的记号，例如令#(N)=0 是希伯来语的第一个字母，念作阿列夫。是希伯来语的第一个字母，念作阿列夫。基数相等和大小顺序基数相等和大小顺序定义：定义：设设 A 和和 B 为二集合。为二集合。1)如果如果 AB，就称，就称 A 和和 B 的基数的基数相等相等，记为，记为#(A)=#(B)。2)如果存在从如果存在从 A 到到 B 的的单射单射，就称就称 A 的基数的基数小于等于小于等于 B 的基数，记为的基数，记为#(A)#(B)，或称或称 B 的基数大于等于的基数大于等于 A 的基数，的基数，记为记为#(B)#(A)。3)如果如果#(A)#(B)且且#(A)#(B)，就称就称 A 的基数的基数小于小于 B 的基数，记为的基数，记为#(A)#(A)。任何两个基数都可以比较大小任何两个基数都可以比较大小设设 A 和和 B 为任意两个集合，则为任意两个集合，则#(A)#(B)，或，或#(B)#(A)，二者之中至少有一个成立。二者之中至少有一个成立。（证明要用（证明要用选择公理选择公理）基数的相等关系基数的相等关系“=”是等价关是等价关系系设设 A、B 和和 C为三集合，则有为三集合，则有1）#(A)=#(A)；2）若）若#(A)=#(B)，则，则#(B)=#(A)；3）若）若#(A)=#(B)且且#(B)=#(C)，则则#(A)=#(C)基数的小于等于关系基数的小于等于关系“”是半序是半序设设 A，B 和和 C 为三集合，则有为三集合，则有1)#(A)#(A)；2)若若#(A)#(B)且且#(B)#(A)，则，则#(A)=#(B)；3)若若#(A)#(B)且且#(B)#(C)，则，则#(A)#(C)。其中，其中，2）为著名的）为著名的 Bernstein 定理。定理。基数的相等关系基数的相等关系“=”是等价关是等价关系系设设A、B和和C为三集合，则有为三集合，则有1）#(A)=#(A)；2）若）若#(A)=#(B)，则，则#(B)=#(A)；3）若）若#(A)=#(B)且且#(B)=#(C)，则则#(A)=#(C)定义定义8.8 (基数基数)设设 F 是集合族是集合族,是是 F 上的等势关系。上的等势关系。关系关系 在在 F 上的上的等价类等价类 称为称为 基数基数。对于对于 A F,A 所属的等价类用所属的等价类用#A 表示表示,称之为称之为 A 的基数。的基数。对于对于 A,B F：#A=#B A B。定义定义8.9（可数无穷集合）：（可数无穷集合）：任何与自然数集合任何与自然数集合等势等势的集合的集合称为称为 可数无穷集合可数无穷集合。可数无穷集合的基数可数无穷集合的基数，用用 0 表示表示，读作，读作 阿列夫零阿列夫零。定义定义8.10（可数、不可数集合（可数、不可数集合）：）：如果一个集合是有穷集合如果一个集合是有穷集合或是或是 可数无穷集合可数无穷集合,就称它为就称它为 可数集合可数集合；如果一个集合是如果一个集合是无穷的，而且不是可数的无穷的，而且不是可数的，就称它为，就称它为不可数集合不可数集合。无穷集的等价条件无穷集的等价条件定理定理 以下三个条件等价：以下三个条件等价：1)A 为无穷集；为无穷集；2)A 有可数无穷子集；有可数无穷子集；3)A 有与它对等的真子集。有与它对等的真子集。定理定理8.2：任何无穷集合任何无穷集合 必含有必含有 可数无穷子集可数无穷子集。证明：设证明：设 A 是无穷集合是无穷集合,可以顺序地从可以顺序地从 A 的子集中取元素。的子集中取元素。构造一个构造一个 无穷序列无穷序列,方法如下方法如下:从从 A 中中 选选 a0 从从 A a0 中选中选 a1 从从 A a0,a1 中选中选 a2 从从 A a0,a1,an-1 中选中选 an 而集合而集合 A a0,a1,an 是是无穷集无穷集,不论取到何时不论取到何时,必有元素剩下必有元素剩下,否则否则 A 就是个有穷集合就是个有穷集合。继续上述过程。继续上述过程,可以得到一个没有重复的无穷序列可以得到一个没有重复的无穷序列,它组它组成了成了 A 的一个可数子集的一个可数子集 a0,a1,a2,。证证毕毕 证明证明：设：设 A 是可数无穷集合，是可数无穷集合，S 是是 A 的无穷子集，的无穷子集，显然显然 A N,故有双射函数故有双射函数 f:NA,f(n)=x,x A，把把A中的元素可以排列为中的元素可以排列为:f(0),f(1),f(2),把不在把不在 S 中的元素从这序列中去掉。中的元素从这序列中去掉。由于由于 S 是无穷集合，所以余下的元素仍然是无穷的，是无穷集合，所以余下的元素仍然是无穷的，用用 f(i0),f(i1),f(i2),来表示来表示余下的元素，并确定函数余下的元素，并确定函数g:N S,使得使得 g(n)=f(in)，则，则 g 是是双射函数，双射函数，因此因此 S 是可数无穷的。是可数无穷的。定理定理8.3：可数无穷集合的无穷子集可数无穷集合的无穷子集 必是必是 可数无穷的。可数无穷的。定理定理#(B)#(A)iff 存在从存在从 A 到到 B 的满射。的满射。证明：证明：i)设设 f：AB 为满射，为满射，则则 f 有右逆有右逆 g:BA 使得使得 f g=IB，因为，因为 IB 是单射，是单射，所以所以 g 是单射，故是单射，故#(B)#(A)。ii)若若#(B)#(A)，则有单射，则有单射 g:BA，g 有左逆有左逆 f:AB 使得使得 f g=IB。因为因为 IB 是是 满射，满射，所以所以 f 是满射。是满射。如图如图 8.2所示，函数所示，函数 是是 从从 N N 到到 N 的双射：的双射：(m,n)=(m+n)(m+n+1)/2+m =(m+n)2+3 m+n/2 (m,n)的值的值 写在坐标为写在坐标为(m,n)的点上。的点上。图图8.2 N N N例例8.5：集合集合 N N 与集合与集合 N 等势。等势。mn例例8.6 自然数集合自然数集合 N 与有理数集合与有理数集合 Q 等势等势,即即 N Q。图图 8.3 N Q 例例 8.8 设设 Z=,-2,-1,0,1,2,若列举若列举 Z 的元素的元素,就能建立就能建立 N 到到 Z 的一一对应如下的一一对应如下:013450-11-222-3这个对应这个对应 Z N,也可以用一个双射函数也可以用一个双射函数 f:NZ 来来表示：表示：可数无穷集合是无穷集合中十分重要的一类，可以证明可数无穷集合是无穷集合中十分重要的一类，可以证明:可数无穷集合的可数无穷集合的并集并集和可数无穷集合的和可数无穷集合的笛卡儿乘积笛卡儿乘积都仍然都仍然是可数无穷集合。是可数无穷集合。f(n)=n/2 n是偶数是偶数-(n+1)/2 n是奇数是奇数至此已证明了：偶数集至此已证明了：偶数集E N,N N N,QN,Z N,可见：偶数集合、平面上整格点的集合、有理数集合、可见：偶数集合、平面上整格点的集合、有理数集合、整数集合都是可数无穷集合。整数集合都是可数无穷集合。定理：定理：实数集合实数集合 R 是是 不可数的不可数的。基数的个数也是无限的，且无最大者基数的个数也是无限的，且无最大者对每个集合对每个集合 A，皆有，皆有#(A)#(A)。证明：证明：i)定义定义 g：A (A)为为 g(a)=a 显然显然 g 是内射，所以是内射，所以#(A)#(A)。ii)用用反证法反证法来来 证明：证明：#(A)#(A)假设假设#(A)=#(A)，则有，则有双射双射 f：A (A)。令。令 B =aa A 且且 a f(a)则则 B (A)。因。因 f 为为双射双射，故有，故有 t A 使使 f(t)=B。（1）若若 t B，按，按 B 的定义，的定义，t f(t)，即，即 t B；（2）若若 t B，即，即 t f(t)。而按。而按 B 的定义，的定义，t B。总之，总之，t B 当且仅当当且仅当 t B。这是一个矛盾。这是一个矛盾。故假设有误，所以必有故假设有误，所以必有#(A)#(A)。由由 i)和和 ii)知，知，#(A)#(A)。定理定理8.4：实数集合实数集合 R 是不可数的是不可数的。证明证明：设集合：设集合 S=x|x(0,1)假设假设 S 是可数的，于是能够把是可数的，于是能够把 S 的元素排列成无的元素排列成无穷序列穷序列S0,S1,S2,Sn,已知已知 Si 是是0和和1之间之间的实数的实数,而任何小于而任何小于 1的正数的正数 s 可以表示为可以表示为:s=0.y1y2y3 这里这里 yi 0,1,2,9 将实数集合将实数集合S 的元素的元素S1,S2,S3,Sn,表示成：表示成：S0=0.a11a12a13 S1=0.a21a22a23 Sn=0.an1an2an3 然后然后,构造一个实数构造一个实数 r=0.b1b2b3 bn ,其中其中 bj(j=1,2,3,)按下列原则选取按下列原则选取:若若 ajj 1,则取则取 bj=1;若若ajj=1,则取则取 bj=2.在位置在位置 1 上上 r 与与 S1 不同不同,在位置在位置 2上上r 与与 S2 也不同也不同,等等等等.所以所以 r 不同于不同于 S1,S2,S3,Sn,这表明这表明 r S.从而导致矛盾从而导致矛盾.因此因此 S 是不可数的是不可数的.又因为又因为实数集合实数集合 R 和集合和集合 S 是等势的是等势的,从从而而 R 也是不可数的也是不可数的.证毕证毕.与集合与集合 R 等势的集合的基数等势的集合的基数,用用 来表示来表示,并称并称为连续统的势为连续统的势.#(N)记为 例：证明#(N)=#(R)。证明证明 全体从全体从N到到N的的严格单调递增函数严格单调递增函数组成的集合的组成的集合的基数大于基数大于 0 。例：#(R R)=定义定义 8.14：若若#A=,#B=,且且 A B,则称则称 小于小于 ,记为记为 .因为自然数集合是实数集合的真子集因为自然数集合是实数集合的真子集,由定由定理理 8.4的证明的证明 可知可知,有有 N R 和和 0 C;又因为又因为任何无穷集合都包含一个可数无穷子集任何无穷集合都包含一个可数无穷子集,故故 0 是最小的无穷基数是最小的无穷基数.即对于任何无穷集合即对于任何无穷集合 A,有有 N A;对任何无穷基数对任何无穷基数 k,有有0 k.k.定理定理 8.5 对于任意集合对于任意集合 A,A (A),(A)是是 A 的幂集的幂集.