《离散数学实数集合与集合的基数.ppt》由会员分享，可在线阅读，更多相关《离散数学实数集合与集合的基数.ppt（20页珍藏版）》请在三一办公上搜索。
1、集合的基数,基数-集合中元素的个数.本章主要借助于函数讨论集合的所谓“大小”问题。,一.自然数,定义:对任意集合A,定义A+=AA称A+为A的后继,A为A+的前驱.例:若A=,则+=(+)+=.(+)+)+=,一.自然数,定义:集合0=是一个自然数,若集合n是一个自然数,则集合n+1=n+也是一个自然数.0=1=0+=00=02=1+=11=0,13=2+=22=0,1,2n+1=n+=0,1,2,3,n.,定义:设F是一个函数,Adom F,对xA,有F(x)A,则称A在函数F下是封闭的.Peano系统是满足以下公理的有序三元组,其中M为一个集合,F为函数,e为首元素.5条公理为(1)eM.
2、(2)M在F是封闭的.(3)eranF.(4)F是单射.(5)若M的子集A满足 eA A在F下是封闭的,则A=M定理.设N为自然数集合,:NN,且(n)=n+,则是Peano系统.,一.自然数,定义:对任意的自然数m和n.mmmnmnnm定理.对任意的自然数m和n,下列三式有且仅有一式成立：mn（三歧性）。注1：任何自然数都不是自己的元素。注2：任何自然数都是它自己的子集。注3:mnmn.,自然数的运算,1.加法定义:令+:NNN,且对m,nNAm(n)记Am(n)=m+n.其中Am(0)=m,Am(n+)=(Am(n)+,则称+为N上的加法运算.例:由加法定义计算3+2.,定理.设m,nN,
3、则0+m=m+0=m(加法规则1)m+n+=(m+n)+(加法规则2)证明:m+0=Am(0)=m.(定义)0+m=A0(m)=A0(m-1)+)=m+n+=Am(n+)=(Am(n)+=(m+n)+例:利用加法规则计算3+2,乘法,定义:令:NNN,且对m,nN,Mm(n),记作Mm(n)=mn.其中Mm(0)=0,Mm(n+)=Mm(n)+m,则称 为N上的乘法运算.例:利用定义计算32.定理.设m,nN,则 m0=0(乘法规则1)mn+=mn+m(乘法规则2)例:利用乘法规则1和2重新计算32.,指数运算,定义:设:NNN,且对m,nN,Em(n),记作:mn.称为N上的指数运算.其中E
4、m(0)=1,Em(n+)=Em(n)m.例:用定义计算32.定理.对m,nN,有m0=1mn+=mnm.,性质,定理.设m,n,kN,则(1)m+(n+k)=(m+n)+k(2)m+n=n+m(3)m(n+k)=mn+mk(4)m(nk)=(mn)k(5)mn=nm,整数集合Z,定义:对自然数集合N,令Z+=N-0.Z=n Z+.Z=Z+0Z.则称Z+的元素为正整数,Z的元素为负整数,Z的元素为整数.,集合的等势,定义:设A,B为两个集合,如果存在A到B的双射函数,则称A和B等势,记AB.否则称A和B不等势,记(AB)或AB.例:N偶=nnNn为偶数.N奇=nnNn为奇数.N2n=xx=2n
5、 nN.则N N偶,N N奇,NN2n,例:NZ.解:取f:NZ,且nN,或,取g:ZN,对nZ,例:NQ.因为每个有理数都可以写成一个分数形式如下：可以从0/1开始按照箭头指定次序排列Q中元素所以NQ。另外 ZZN 如右图所示。,例:(0,1)R.解:x(0,1),f(x)=tg.例:0,1(0,1),定理.(康托尔定理)(1)(NR)(2)对任意的集合A,(AP(A).,3 有限集合与无限集合,定义:集合A是有限集合,当且仅当存在nN,使nA.否则,称A为无限集.定理1.不存在与自己的真子集等势的自然数.推论1.不存在与自己的真子集等势的有限集合.推论2.任何与自己的真子集等势的集合是无限
6、集合.推论3.任何有限集合只与唯一的自然数等势.,4 集合的基数,定义:设A为任意一个集合,用card(A)表示A中的元素个数,并称card(A)为集合A的基数.作以下5条规定:(1)对集合A,B,规定card(A)=card(B)AB(2)对有限集合A,规定与A等势的自然数n为A的基数.记作:card(A)=n.(3)对自然数集合N,规定card(N)=0(4)对于实数集合R,规定card(R)=1(5)将0,1,2,0,1都称作基数.其中自然数0,1,2,称为有限基数,0,1称为无限基数.,例:A=a,b,c,B=a,b,c.N偶=n|nNn为偶数,N奇=n|nNn为奇数,可数集合,定义1:对集合K,如果card K0,则称K是可数集合.定义2:如果集合K是有限的或与N等势,则称K是可数集合.定理.集合A是无限可数集合A可写成如下的式a1,a2,an,.,定理(1)可数集合的任何子集是可数集.证:设A可数,BA,则BA,即 card B card A 0.(2)两个可数集的并集和笛卡尔积是可数集.证:A=a11,a12,a1n,B=a21,a22,a2n,AB=a11,a12,a21,a13,a22,(3)若K是无限集合,则P(K)是不可数的.已知的基数按从小到大的次序排列就是0,1,n,0,1(=20),21,连续统假设:不存在基数k,使得0 k 20.,
