离散数学实数集合与集合的基数

《离散数学实数集合与集合的基数》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、集合的基数基数----集合中元素的个数.本章主要借助于函数讨论集合的所谓“大小”问题。一.自然数定义:对任意集合A,定义A+=A∪A称A+为A的后继,A为A+的前驱.例:若A=Ф,则Ф+=(Ф+)+=.((Ф+)+)+=一.自然数定义:集合0=Ф是一个自然数,若集合n是一个自然数,则集合n+1=n+也是一个自然数.0=Φ1=0+=0∪0=02=1+=1∪1=0,13=2+=2∪2=0,1,2…n+1=n+=0,1,2,3,…,n.定义:设F是一个函数,AdomF,对xA,有F(x)

2、A,则称A在函数F下是封闭的.Peano系统是满足以下公理的有序三元组,其中M为一个集合,F为函数,e为首元素.5条公理为(1)eM.(2)M在F是封闭的.(3)eranF.(4)F是单射.(5)若M的子集A满足①eA②A在F下是封闭的,则A=M定理.设N为自然数集合,σ:N→N,且σ(n)=n+,则是Peano系统.一.自然数定义:对任意的自然数m和n.mmmnmnn≥m定理.对任意的自然数m和n,下列三式有且仅有一式成立：mn（三歧性）。注

3、1：任何自然数都不是自己的元素。注2：任何自然数都是它自己的子集。注3:mAm(n)记Am(n)=m+n.其中Am(0)=m,Am(n+)=(Am(n))+,则称+为N上的加法运算.例:由加法定义计算3+2.定理.设m,nN,则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)+例:利

4、用加法规则计算3+2乘法定义:令:NNN,且对m,nN,Mm(n),记作Mm(n)=mn.其中Mm(0)=0,Mm(n+)=Mm(n)+m,则称为N上的乘法运算.例:利用定义计算32.定理.设m,nN,则m0=0(乘法规则1)mn+=mn+m(乘法规则2)例:利用乘法规则1和2重新计算32.指数运算定义:设⊙:NNN,且对m,nN,Em(n),记作:mn.称⊙为N上的指数运算.其中Em(0)=1,Em(n+)=Em(n)m.例:用定义计算32.定理.对m,n

5、N,有m0=1mn+=mnm.性质定理.设m,n,kN,则(1)m+(n+k)=(m+n)+k(2)m+n=n+m(3)m(n+k)=mn+mk(4)m(nk)=(mn)k(5)mn=nm整数集合Z定义:对自然数集合N,令Z+=N-0.Z=<0,n>nZ+.Z=Z+∪0∪Z.则称Z+的元素为正整数,Z的元素为负整数,Z的元素为整数.集合的等势定义:设A,B为两个集合,如果存在A到B的双射函数,则称A和B等势,记A≈B.否则称A和B不等势,记(A≈B)或A≈B.例:N偶=n

6、nNn为偶数.N奇=nnNn为奇数.N2n=xx=2nnN.则N≈N偶,N≈N奇,N≈N2n例:N≈Z.解:取f:NZ,且nN,或,取g:ZN,对nZ例:N≈Q.因为每个有理数都可以写成一个分数形式如下：可以从0/1开始按照箭头指定次序排列Q中元素所以N≈Q。另外Z×Z≈N如右图所示。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....

7、.........................................011223-1-1-2-2-3例:(0,1)≈R.解:x(0,1),f(x)=tgπ.例:[0,1]≈(0,1)定理.(康托尔定理)(1)(N≈R)(2)对任意的集合A,(A≈P(A)).§3有限集合与无限集合定义:集合A是有限集合,当且仅当存在nN,使nA.否则,称A为无限集.定理1.不存在与自己的真子集等势的自然数.推论1.不存在与自己的真子集等势的有限集合.推论2.任何与自己的真子集等势的集合是无限集合.推论3.任何有限

8、集合只与唯一的自然数等势.§4集合的基数定义:设A为任意一个集合,用card(A)表示A中的元素个数,并称card(A)为集合A的基数.作以下5条规定:(1)对集合A,B,规定card(A)=card(B)AB(2)对有限集合A,规定与A等势的自然数n为A的基数.记作:card(A)=n.(3)对自然数集合N