离散数学_李舟军第八章

《离散数学_李舟军第八章》由会员分享，可在线阅读，更多相关《离散数学_李舟军第八章（39页珍藏版）》请在金锄头文库上搜索。

1、第八章 自然数和基数,8.1 自然数及数学归纳法 8.2 基数,自然数和归纳法,主要概念： 集合的后继 主要方法：归纳原理、第一归纳法、第二归纳法,自然数的引进方法, 公理化方法：皮亚诺公理（G. Peano）； 构造性方法：借助集合论，具体构造出 N。,自然数构造的出发点,1) 自然数的各种性质 ( 运算、大小次序 及 基本定律 ) , 都可以从 Peano 公理一一推导出来； 证明构造出来的 “自然数” 满足Peano公理，因此具有普通自然数的一切性质。,集合的后继,定义8.2 (后继集合) 对于任意集合 A，其后继集合 A+ 定义为：A+ = A A 。 每个集合都有唯一的一个后继。,引

2、理 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

3、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 满足

4、： 0S。因为 0N 且 0 = = = = 0。 若 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)

5、如果 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

6、, , ni , ni+1 , 使得 ni+1 ni 。 由自然数的定义可知，对于每一个自然数，比它小的 自然数总是有穷个，并且 0 1 2 3 0 1 2 3 ,性质 8.1（作为集合的自然数的性质）:,（1）传递性：若 n1n2 且 n2n3 , 则 n1n3 。,（2）三歧性：对于任何两个自然数 n1，n2，下列三式 恰有一个成立：n1n2 , n1 = n2 , 或 n2n1 。,数学归纳法（第一数学归纳法）： 设 P (n) 是自然数集合上的性质(或 谓词), 如果能证明 1) P(0) 是真； 2) 对任何 nN, P (n) P (n+ )。 则对所有 nN, P (n) 为真。

7、,Peano公理(5)的极小化就是自然数集合定义中的极小化, 是数学归纳法的基础。下面给出一个等价的数学归纳法:,数学归纳法是论域为自然数集合的推理规则，可形式表达如下： P(0) (n) ( P(n) P(n+1) ) (n) P(n),设k是某个自然数，如果要证明谓词P(x)对所有xk的自然数成立，则上述原理可写成： P(k) (n)(nk P(n)P(n+1) (x)(xkP(x),第二数学归纳法： 第二数学归纳法是一种更强形式的数学归纳法， 它在证明对所有自然数x ，P(x)为真时，使用下述步骤： 假设对所有kn， P(k)是真，推出P(n)为真，则 (x)P(x)为真。即 (n)(k

8、)(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）对于任意的mN,假定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),由数学归纳法,对于所有的nN, P(n)为真.,例8.1：证明n2n,证

9、明 ：设P(n)：2nn! (1) P(4) : 244!, 24=16，4!=24. P(4)成立 . (2) 设对于任何m4, P(m)为真,即2mm!. (3) 22m2 m!, 2m+12 m!(m+1) m!=(m+1)!, 即2m+1(m+1) ! 上式说明P(m+1)为真. 因此,对于所有的nN , n4 , P(n)为真.,例8.2 证明对于任何n4,2nn! .,例8.3 证明所有n2的整数能写成质数的乘积 .,证明： 对任意的n作归纳假设,设对每个k,2kn能写成质数 的乘积, 证明n也能写成质数的乘积. 证明分两种情况： (1) 若n是质数,显然它就是一个质数的乘积. (

10、2) 若n不是质数,则可写成n=ab,而2a,bn.根据假设a和b都可写成质数的乘积,所以n也能写成质数的乘积. 根据第二数学归纳法结论成立., 8.2 基 数,本节讨论度量和比较集合大小的方法。重点掌握等势，有穷、无穷集合，可数无穷集合，可数、不可数集合，无穷集合的性质，有穷集合、N、R的基数，基数的比较。,定义8.5 ： 两个集合A和B是等势的，当且仅当A和B的元素是一一对应的， 记作AB .,证明：设 f:NE，f(n)=2n，nN. 对于任意n1，n2 N，若f（n1 )= f(n2) ，即2n1 = 2 n2 ，则n1=n2 ，故f是单射函数；对于任意m E，存在n= m/2N，使得

11、f(n)=m，故f又是满射函数，因此f是双射函数，由集合等势定义可知， NE.,例8.4 设：N=0 , 1 , 2 , 及E=0 , 2 , 4 , 求证:NE.,如图8.2所示，存在函数 f是 N N 到 N 的一一对应： f (m,n) = (m + n)2 + 3m + n/2 f (m,n) 的值写在坐标为 (m,n) 的点上.,图8.2 N N N,例8.5： 集合 N N 与集合 N 等势。,m,n,例8.6 自然数集合 N 与有理数集合 Q等势 . 即NQ .,图8.3 NQ 图,例8.7 : 单位开区间 (0,1) = x| xR 0x1与实数集合R等势. 下面是(0,1)

12、到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 , C : (1) AA (2) 若 AB , 则 BA (3) 若 AB , BC , 则 AC 即等势关系有自反性 , 对称性和传递性，因此等势是集合族上的等价关系.,定义8.6：集合是有穷的，当且仅当它与某个自然数等势 . 否则就是无穷的.,鸽巢原理 ：若 A 和 B 是有穷集合 , #A = m , #B = n ,且 m n , 则不

13、存在从 A 到 B 的单射函数 .,上述原理可以导出有穷集合与无穷集合的根本差别 . 任何有穷集合都不会与它本身的真子集等势 . 从而可以得出任何与自身真子集等势的集合是无穷集合 .,定理8.1：任意有穷集合 A 唯一地与一个自然数等势 .,证明 : 设对于某两个自然数 m 和 n , Am 且 An 则 mn . 根据自然数三岐性和传递性 , 或者 m = n或者一个是另一个的真子集 , 因为 mn , 所以后一种选择是不可能的 , 因此 m = n .证毕 .,定义8.7(有穷集合的基数)：对于任意有穷集合 A ，存在唯一的自然数 n ，使得 A n ， 称 n 为 A 的基数 ，记为 #

14、A .,定义8.8（基数）：设 F 是集合族 , 是 F 上的等势关系 . 关系 在 F 上的等价类称为基数 . 对于任何 A F , A 所属的等价类用 #A 表示 , 称之为 A 的基数 . 对于 A , B F , #A = #B A B .,定义8.9（可数无穷集合）：任何与自然数集合等势的集合称为可数无穷集合 .,可数无穷集合的基数 ， 用0表示 ，读作阿列夫零 .,定义8.10（可数、不可数集合 ）：如果一个集合是有穷集合或是可数无穷集合 , 就称它为可数集合 ； 如果一个集合是无穷的而且不是可数的 ,就称它为不可数集合 .,可数集合的性质,定理8.2：任何无穷集合必含有可数无穷子集 .,证明 ：设 A 是无穷集合 ，可以顺序地从 A 的子集中取元素 . 构造一个无穷序列 方法如下 :,从 A 中选 a0 从 A a0中选 a1 从 A a0 , a1中选 a2 从 A a0 , a1 , , an-1中选 an