离散数学 实数集合与集合的基数(精品).ppt

《离散数学 实数集合与集合的基数(精品).ppt》由会员分享，可在线阅读，更多相关《离散数学 实数集合与集合的基数(精品).ppt（20页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、集合的基数集合的基数v基数基数-集合中元素的个数集合中元素的个数.v本章主要本章主要借助于函数借助于函数讨论集合的所谓讨论集合的所谓“大小大小”问题。问题。一一.自然数自然数v定义定义:对任意集合对任意集合A,定义定义vA+=A A v称称A+为为A的后继的后继,A为为A+的前驱的前驱.v例例:若若A=,则则v+=v(+)+=.v(+)+)+=一一.自然数自然数v定义定义:集合集合0=是一个自然数是一个自然数,若集合若集合n是一是一个自然数个自然数,则集合则集合n+1=n+也是一个自然数也是一个自然数.v0=v1=0+=0 0=0 v2=1+=1 1=0,1 v3=2+=2 2=0,1,2 v

2、vn+1=n+=0,1,2,3,n.v定义定义:设设F是一个函数是一个函数,A dom F,对对 x A,有有F(x)A,则称则称A在函数在函数F下是封闭的下是封闭的.vPeano系统系统是满足以下公理的有序三元组是满足以下公理的有序三元组,其中其中M为一个集合为一个集合,F为函数为函数,e为首元素为首元素.5条条公理为公理为v(1)e M.v(2)M在在F是封闭的是封闭的.v(3)e ranF.v(4)F是单射是单射.v(5)若若M的子集的子集A满足满足v e Av A在在F下是封闭的下是封闭的,则则A=Mv定理定理.设设N为自然数集合为自然数集合,:NN,且且(n)=n+,则则是是Pean

3、o系统系统.一一.自然数自然数v定义定义:对任意的自然数对任意的自然数m和和n.vmmvm nm nnmv定理定理.对任意的自然数对任意的自然数m和和n,下列三式有且仅有一下列三式有且仅有一式成立：式成立：v mn（三歧性）。（三歧性）。v注注1：任何自然数都不是自己的元素。：任何自然数都不是自己的元素。v注注2：任何自然数都是它自己的子集。：任何自然数都是它自己的子集。v注注3:mnm n.自然数的运算自然数的运算v1.加法加法v定义定义:令令+:NNN,且对且对 m,n NvAm(n)记记Am(n)=m+n.v其中其中Am(0)=m,Am(n+)=(Am(n)+,则则称称+为为N上的加法运

4、算上的加法运算.v例例:由加法定义计算由加法定义计算3+2.v定理定理.设设m,n N,则则v0+m=m+0=m (加法规则加法规则1)vm+n+=(m+n)+(加法规则加法规则2)v证明证明:m+0=Am(0)=m.(定义定义)v0+m=A0(m)=A0(m-1)+)=vm+n+=Am(n+)=(Am(n)+=(m+n)+v例例:利用加法规则计算利用加法规则计算3+2乘法乘法v定义定义:令令 :N NN,且对且对 m,n N,v Mm(n),记作记作Mm(n)=m n.v其中其中Mm(0)=0,Mm(n+)=Mm(n)+m,则称则称 为为N上的乘法运算上的乘法运算.v例例:利用定义计算利用定

5、义计算3 2.v定理定理.设设m,n N,则则 vm 0=0 (乘法规则乘法规则1)vm n+=m n+m (乘法规则乘法规则2)v例例:利用乘法规则利用乘法规则1和和2重新计算重新计算3 2.指数运算指数运算v定义定义:设设:N NN,且对且对 m,n N,Em(n),记作记作:mn.称称 为为N上的指数运算上的指数运算.其中其中Em(0)=1,Em(n+)=Em(n)m.v例例:用定义计算用定义计算32.v定理定理.对对 m,n N,有有vm0=1vmn+=mn m.性质性质v定理定理.设设m,n,k N,则则v(1)m+(n+k)=(m+n)+kv(2)m+n=n+mv(3)m(n+k)

6、=m n+m kv(4)m(n k)=(m n)kv(5)m n=n m整数集合整数集合Zv定义定义:对自然数集合对自然数集合N,令令vZ+=N-0.vZ=n Z+.vZ=Z+0 Z.v则称则称Z+的元素为正整数的元素为正整数,Z 的元素为负整数的元素为负整数,Z的元素为整数的元素为整数.集合的等势集合的等势v定义定义:设设A,B为两个集合为两个集合,如果存在如果存在A到到B的的双射函数双射函数,则称则称A和和B等势等势,记记AB.否则称否则称A和和B不等势不等势,记记(AB)或或 AB.v例例:N偶偶=nn N n为偶数为偶数.vN奇奇=nn N n为奇数为奇数.vN2n=xx=2n n N

7、.v则则N N偶偶,N N奇奇,NN2nv例例:NZ.v解解:取取f:NZ,且且 n N,v v或或,取取g:ZN,对对 n Zv 例例:NQ.因为每个有理数都可以写成一个分数形式如下：因为每个有理数都可以写成一个分数形式如下：可以从可以从0/1开始按照箭头指定次序排列开始按照箭头指定次序排列Q中元素中元素所以所以NQ。另外另外 ZZN 如右图所示。如右图所示。0/11/12/13/1-1/1-2/1-3/1-1/2-2/2-3/20/21/22/23/20/31/32/33/3-1/3-2/3-3/3-1/4-2/4-3/40/41/42/43/4.011223-1-1-2-2-3v例例:(

8、0,1)R.v解解:x(0,1),f(x)=tg .v例例:0,1(0,1)定理定理.(康托尔定理康托尔定理)(1)(NR)(2)对任意的集合对任意的集合A,(AP(A).3 有限集合与无限集合有限集合与无限集合v定义定义:集合集合A是有限集合是有限集合,当且仅当存在当且仅当存在n N,使使n A.否则否则,称称A为无限集为无限集.v定理定理1.不存在与自己的真子集等势的自然数不存在与自己的真子集等势的自然数.v推论推论1.不存在与自己的真子集等势的有限集合不存在与自己的真子集等势的有限集合.v推论推论2.任何与自己的真子集等势的集合是无限任何与自己的真子集等势的集合是无限集合集合.v推论推论

9、3.任何有限集合只与唯一的自然数等势任何有限集合只与唯一的自然数等势.4 集合的基数集合的基数v定义定义:设设A为任意一个集合为任意一个集合,用用card(A)表示表示A中的元素中的元素个数个数,并称并称card(A)为集合为集合A的基数的基数.作以下作以下5条规定条规定:v(1)对对 集合集合A,B,规定规定vcard(A)=card(B)A Bv(2)对对 有限集合有限集合A,规定与规定与A等势的自然数等势的自然数n为为A的基的基数数.记作记作:card(A)=n.v(3)对自然数集合对自然数集合N,规定规定vcard(N)=0v(4)对于实数集合对于实数集合R,规定规定vcard(R)=

10、1v(5)将将0,1,2,0,1都称作基数都称作基数.其中自然数其中自然数0,1,2,称为有限基数称为有限基数,0,1称为无限基数称为无限基数.v例例:A=a,b,c,B=a,b,c.vN偶偶=n|n Nn为偶数为偶数,vN奇奇=n|n Nn为奇数为奇数可数集合可数集合v定义定义1:对集合对集合K,如果如果card K0,则称则称K是是可数集合可数集合.v定义定义2:如果集合如果集合K是有限的或与是有限的或与N等势等势,则称则称K是可数集合是可数集合.v定理定理.集合集合A是无限可数集合是无限可数集合A可写成如下可写成如下的式的式a1,a2,an,.v定理定理(1)可数集合的任何子集是可数集可数集合的任何子集是可数集.v证证:设设A可数可数,B A,则则B A,即即 v card B card A 0.v(2)两个可数集的并集和笛卡尔积是可数集两个可数集的并集和笛卡尔积是可数集.v证证:A=a11,a12,a1n,vB=a21,a22,a2n,vAB=a11,a12,a21,a13,a22,v(3)若若K是无限集合是无限集合,则则P(K)是不可数的是不可数的.v已知的基数按从小到大的次序排列就是已知的基数按从小到大的次序排列就是v0,1,n,0,1(=20),21,连续统假设连续统假设:不存在基数不存在基数k,使得使得0 k 20.