集合基数[通俗易懂]

集合基数[通俗易懂]通俗的说,集合的势是量度集合所含元素多少的量。集合的势越大,所含的元素越多。定理9.1设A,B,C是任意集合,(1)A≈A。(2)若A≈B,则B≈A。(3)若A≈B,B≈C,则A≈C。定义9.2(1)设A,B是集合,如果存在从A到B的单射函数,就称B优势于A,记作A·B。如果B不是优势于A,则记作A·B。(2)设A,B是集合,若A·B且AB,则称B真优势于A,记作A·B。如果B不是真优势于A,则记作A·B。关于DiscreteMathematics更多讨论与交流,敬请关注本博客和新浪微博s

大家好,又见面了,我是你们的朋友全栈君。

主要内容

1. 集合的等势与优势 
2. 集合的基数 

学习要求


1. 掌握:集合之间等势与优势的概念,等势的性质(自反性,对称性,传递性) 
2. 掌握:证明集合等势的方法,康托定理的内容及证明方法 
3. 掌握:自然数、自然数集、有穷集、无穷集的定义与主要性质 
4.

掌握:集合基数的定义、基数的比较、可数集的定义与主要性质

集合的等势与优势

集合的等势


  通俗的说,集合的势是量度集合所含元素多少的量。集合的势越大,所含的元素越多。
定义9.1设A,B是集合,如果存在着从A到B的双射函数,就称A和B是等势的,记作A≈B。如果A不与B等势,则记作A集合基数[通俗易懂]B。
  下面给出一些集合等势的例子。

例9.1 (1) Z≈N。回顾上一章例8.6(3),令

    f:ZN,集合基数[通俗易懂]

则f是Z到N的双射函数。从而证明了Z≈N。

  (2) N×N≈N. 为建立N×N到N的双射函数,只需把中所有的元素排成一个有序图形,如图9.1所示。N×N中的元素恰好是坐标平面上第一象限(含坐标轴在内)中所有整数坐标的点。如果能够找到“数遍”这些点的方法,这个计数过程就是建立N×N到N的双射函数的过程。按照图中箭头所标明的顺序,从<0,0>开始数起,依次得到下面的序列:

    <0,0>,<0,1>,<1,0>,<0,2>,<1,1>,<2,0>,…
     ↓   ↓    ↓   ↓   ↓   ↓
     0    1    2    3    4    5

  设<m,n>是图上的一个点,并且它所对应的自然数是k。考察m,n,k之间的关系。首先计数<m,n>点所在斜线下方的平面上所有的点数,是


集合基数[通俗易懂]

    1+2+…+(m+n)=
集合基数[通俗易懂]



然后计数<m,n>所在的斜线上按照箭头标明的顺序位于<m,n>点之前的点数,是m.因此<m,n>点是第集合基数[通俗易懂]+m+1个点。这就得到
    k=集合基数[通俗易懂]+m
根据上面的分析,不难给出N×N到N的双射函数f,即

    f:N×N→N
    f(<m,n>)=集合基数[通俗易懂]+m

等势的性质


  以上已经给出了若干等势的集合。一般说来,等势具有下面的性质:自反性,对称性和传递性。
  定理9.1 设A,B,C是任意集合,

  (1) A≈A。

  (2) 若A≈B,则B≈A。

  (3) 若A≈B,B≈C,则A≈C。

  证明:
根据前面的分析和这个定理可以得到下面的结果:

    N≈Z≈Q≈N×N

    R≈[0,1]≈(0,1)

  而后一个结果可以进一步强化成:任何的实数区间(包括开区间,闭区间以及半开半闭的区间)都与实数集合R等势。那么N与R是否等势呢?如果有N≈R,上面列出的所有集合彼此都是等势的;如果N集合基数[通俗易懂]R,与N等势的那些集合也不会与R等势。下面证明N集合基数[通俗易懂]R。

定理9.2 (康托定理)

  (1) N集合基数[通俗易懂]R

  (2) 对任意集合A都有A集合基数[通俗易懂]P(A)。

   (1)如果能证明N集合基数[通俗易懂][0,1],就可以断定N集合基数[通俗易懂]R.为此只需证明任何函数f:N→[0,1]都不是满射的。

  首先规定[0,1]中数的表示。对任意的x∈[0,1],令

    x=0.x1x2…,0≤xi≤9

考察下述两个表示式:

    0.24999… 和 0.25000…

显然它们是同一个x的表示。为了保证表示式的唯一性,如果遇到上述情况,则将x表示为0.25000…。根据这种表示法,任何函数f: N→[0,1]的值都可以用这种表示式给出。

  设f: N→[0,1]是从N到[0,1]的任何一个函数。如下列出f的所有函数值:

    f(0)=0.a1(1)a2(1)

    f(1)=0.a1(2)a2(2)

    …

    f(n-1)=0.a1(n)a2(n)

     …

设y是[0,1]之中的一个小数,y的表示式为0.b1b2…,并且满足bi≠ai(i),i=1,2,….显然y是可以构造出来的,且y与上面列出的任何一个函数值都不相等。这就推出y集合基数[通俗易懂]ranf,即f不是满射的。

  (2)和(1)的证明类似,我们将证明任何函数g:A→P(A)都不是满射的。

  设g: A→P(A)是从A到P(A)的函数,如下构造集合B:

    B={x|x∈A∧x集合基数[通俗易懂]g(x)}

则B∈P(A),但对任意x∈A都有

    x∈B集合基数[通俗易懂]x集合基数[通俗易懂]g(x)

从而证明了对任意的x∈A都有B≠g(x)。即B集合基数[通俗易懂]rang。

优势


  根据这个定理可以知道N
集合基数[通俗易懂]P(N)。再综合前边的结果不难断定N
集合基数[通俗易懂]{0,1}
N。实际上P(N),{0,1}
N和R都是比N“更大”的集合。这里的“大”加了引号,因为至今为止我们还没有给出“大小”的严格定义。下面就来进行这个工作。

定义9.2
  (1) 设A,B是集合,如果存在从A到B的单射函数,就称B优势于A,记作A集合基数[通俗易懂]·B。如果B不是优势于A,则记作A集合基数[通俗易懂]·B。
  (2) 设A,B是集合,若A集合基数[通俗易懂]·B且A集合基数[通俗易懂]B,则称B真优势于A,记作A集合基数[通俗易懂]·B。如果B不是真优势于A,则记作A集合基数[通俗易懂]·B。
  例如N集合基数[通俗易懂]·N,N集合基数[通俗易懂]·R,A集合基数[通俗易懂]·P(A),R集合基数[通俗易懂]·N。 又如N集合基数[通俗易懂]·R,A集合基数[通俗易懂]·P(A),但N集合基数[通俗易懂]·N。
  优势具有下述的性质。
定理9.3 设A,B,C是任意的集合,则

  (1)A集合基数[通俗易懂]·A。

  (2)若A集合基数[通俗易懂]·B且B集合基数[通俗易懂]·A,则A≈B。

  (3)若A集合基数[通俗易懂]·B且B集合基数[通俗易懂]·C,则A集合基数[通俗易懂]·C。

  定理9.3(2)部分的证明比较复杂,已经超过本书范围,故而略去。(1)和(3)的证明留作练习。

9.2 集合的基数

一.后继与归纳集


  上一节我们只是抽象地讨论了集合的等势与优势。下面将进一步研究度量集合的势的方法。最简单的集合是有穷集。尽管前面已经多次用到“有穷集”这一概念,当时只是只管地理解成含有有限多个元素的集合,但一直没有精确地给出有穷集的定义。为解决这个问题我们需要先定义自然数和自然数集合。
 
定义9.3 设a为集合,称a∪{a}为a的后继,记作a+,即 a+=a∪{a}。

例9.3 考虑空集的一系列后继。

    集合基数[通俗易懂]+=集合基数[通俗易懂]∪{
集合基数[通俗易懂]}={
集合基数[通俗易懂]}

    集合基数[通俗易懂]++={
集合基数[通俗易懂]}+={
集合基数[通俗易懂]}∪{
{
集合基数[通俗易懂]}}={
集合基数[通俗易懂],{
集合基数[通俗易懂]}}={
集合基数[通俗易懂]集合基数[通俗易懂]+}

    集合基数[通俗易懂]+++={
集合基数[通俗易懂],{
集合基数[通俗易懂]}}+={
集合基数[通俗易懂],{
集合基数[通俗易懂]}}∪{
{
集合基数[通俗易懂],{
集合基数[通俗易懂]}}}

        ={
集合基数[通俗易懂],{
集合基数[通俗易懂]},{
集合基数[通俗易懂],{
集合基数[通俗易懂]}}}

        ={
集合基数[通俗易懂]集合基数[通俗易懂]+集合基数[通俗易懂]++}

        …

  由于对任何集合a都有a集合基数[通俗易懂]a。在空集的一系列后继中,任何两个集合都不相等。且满足下面的两个条件:

  1.前边的集合都是后边集合的元素。

  2.前边的集合都是后边集合的子集。

利用这些性质,可以考虑以构造性的方法用集合来给出自然数的定义,即

    0=集合基数[通俗易懂]

    1=0+=集合基数[通俗易懂]+={
集合基数[通俗易懂]}={0}

    2=1+={
集合基数[通俗易懂]}+={
集合基数[通俗易懂],{
集合基数[通俗易懂]}}={0,1}

    …

    n={0,1,…,n-1}

但这种定义没有概括出自然数的共同特征。下面我们采用另一种方法刻划自然数。

自然数,有穷集,无穷集


 定义9.4 设A为集合,如果满足下面的两个条件:
  (1)集合基数[通俗易懂]∈A
  (2)集合基数[通俗易懂]a(a∈A→a+∈A)
则称A是归纳集
  例如下面的集合
    {
集合基数[通俗易懂],集合基数[通俗易懂]+,集合基数[通俗易懂]++,集合基数[通俗易懂]+++,…}
    {
集合基数[通俗易懂],集合基数[通俗易懂]+,集合基数[通俗易懂]++,集合基数[通俗易懂]+++,…,a,a+,a++,a+++,…}
都是归纳集。
定义9.5
  (1)一个自然数n是属于每一个归纳集的集合。
  (2)自然数集N是所有归纳集的交集。
  不难看出,根据定义9.5得到的自然数集N恰好由集合基数[通俗易懂],集合基数[通俗易懂]+,集合基数[通俗易懂]++,集合基数[通俗易懂]+++,…等集合构成。而这些集合正是构造行所定义的全体自然数。
  鉴于自然数都是集合,有关集合的运算对自然数都是适用的,例如:
    2∪5={0,1}∪{0,1,2,3,4}={0,1,2,3,4}=5
    3∩4={0,1,2}∩{0,1,2,3}={0,1,2}=3
    4-2={0,1,2,3}-{0,1}={2,3}
    2×3={0,1}×{0,1,2}={<0,0>,<0,1>,<0,2>,<1,0>,<1,1>,<1,2>}
    P(1)=P({0})={
集合基数[通俗易懂],{0}}={0,1}
    23={0,1}{0,1,2}={f|f:{0,1,2}→{0,1}}={f0,f1,…,f7}
  其中
    f0={<0,0>,<1,0>,<2,0>}
    f1={<0,0>,<1,0>,<2,1>}
    f2={<0,0>,<1,1>,<2,0>}
    f3={<0,0>,<1,1>,<2,1>}
    f4={<0,1>,<1,0>,<2,0>}
    f5={<0,1>,<1,0>,<2,1>}
    f6={<0,1>,<1,1>,<2,0>}
    f7={<0,1>,<1,1>,<2,1>}

基数


  下面给出基数的定义。
定义9.7
  (1)对于有穷集合A,称与A等势的那个唯一的自然数为A的基数,记作cardA,即
    cardA=n集合基数[通俗易懂]A≈n (对于有穷集A,cardA也可以记作|A|)
  (2)自然数集合N的基数记作,即
    cardN=集合基数[通俗易懂]0
  (3)实数集R的基数记作集合基数[通俗易懂](读作阿列夫),即
    cardR=集合基数[通俗易懂]
  下面定义基数的相等和大小。

定义9.8 设A,B为集合,则
  (1)cardA=cardB集合基数[通俗易懂]A≈B
  (2)cardA≤cardB集合基数[通俗易懂]A集合基数[通俗易懂]·B
  (3)card<cardB集合基数[通俗易懂]cardA≤cardB∧cardA≠cardB
  根据上一节关于势的讨论不难得到:
    cardZ=cardQ=cardN×N=集合基数[通俗易懂]0
    cardP(N)=card2N=card[a,b]=card(c,d)=集合基数[通俗易懂]
    集合基数[通俗易懂]0<集合基数[通俗易懂]
其中2N={0,1}N。从这里可以看出,集合的基数是集合的势的大小的度量。基数越大,势就越大。


  由于对任何集合A都满足A集合基数[通俗易懂]·P(A),所以有
    cardA<cardP(A)


这说明不存在最大的基数。将已知的基数按从小到大的顺序排列就得到:
    0,1,2,…,n,…,集合基数[通俗易懂]0集合基数[通俗易懂]
其中0,1,2…,n,…,恰好是全体自然数,是有穷集合的基数,也叫有穷基数。而集合基数[通俗易懂]0集合基数[通俗易懂],…,是无穷集合的基数,也叫做无穷基数集合基数[通俗易懂]0是最小的无穷基数,而后面还有更大的基数,如cardP(R)等。

可数集


定义9.9 设A为集合,若cardA≤集合基数[通俗易懂]0,则称A为可数集可列集

  例如{a,b,c},5,整数集Z,有理数集Q,以及N×N等都是可数集,但实数集R不是可数集,与R等势的集合也不是可数集。对于任何的可数集,它的元素都可以排列成一个有序图形。换句话说,都可以找到一个“数遍”集合中全体元素的顺序。回顾前边的可数集,特别是无穷可数集,都是用这种方法来证明的。

  关于可数集有下面的命题:

  1.可数集的任何子集都是可数集。

  2.两个可数集的并是可数集。

  3.两个可数集的笛卡尔积是可数集。

  4.可数个可数集的笛卡尔积仍是可数集。

  5.无穷集A的幂集P(A)不是可数集。

例9.4 求下列集合的基数。

  (1)T={x|x是单词“BASEBALL”中的字母}

  (2)B={x|x∈R∧x2=9∧2x=8}

  (3)C=P(A),A={1,3,7,11}

   (1)由T={B,A,S,E,L}知cardT=5。

  (2)由B=集合基数[通俗易懂],可知cardB=0。

  (3)由|A|=4可知cardP(A)=|P(A)|=24=16。

例9.5 设A,B为集合,且

    cardA=集合基数[通俗易懂]0,cardB=n,n是自然数,n≠0。

求cardA×B。

   由cardA=集合基数[通俗易懂]0,cardB=n,可知A,B都是可数集。令

    A={a0,a1,a2,…}

    B={b0,b1,b2,…,bn-1}

对任意的<ai,bj>,<ak,bl>∈A×B有

    <ai,bj>=<ak,bl>集合基数[通俗易懂]i=k∧j=l

定义函数

    f:A×B→N

    f(<ai,bj>)=in+j,i=0,1,…,j=0,1,…,n-1

易见f是A×B到N的双射函数,所以

   cardA×B=cardN=集合基数[通俗易懂]0

  如果直接使用可数集的性质,本题的求解更为简单。因为cardA=集合基数[通俗易懂]0,cardB=n,所以A,B都是可数集。根据性质3可知A×B也是可数集,所以cardA×B≤集合基数[通俗易懂]0。显然当B≠集合基数[通俗易懂]时,cardA≤cardA×B,这就推出cardA×B=集合基数[通俗易懂]0

习题

1.设A={a,b,c},B=2A,由定义证明P(A)≈2A
2.设[1,2]和[0,1]是实数区间,由定义证明[1,2]≈[0,1]。
3.设A={2x|x∈N},证明A≈N。
4.证明定理9.1。
5.证明定理9.3的(1),(3)。
6.设A,B,C,D是集合,且A≈C,B≈D,证明A×B≈C×D。
7.找出三个不同的N的真子集,使得他们都与N等势。
8.找出三个不同的N的真子集A,B,C,使得A集合基数[通俗易懂]·N,B集合基数[通俗易懂]·N,C集合基数[通俗易懂]·N。
9.根据自然数的集合定义计算:
 (1)3∪6,2∩5
 (2)4-3,3集合基数[通俗易懂]1
 (3)∪4,∩1
 (4)1×4,22

10.设A,B为可数集,证明 (1)A∪B是可数集。 (2)A×B是可数集。


关于Discrete Mathematics更多讨论与交流,敬请关注本博客和新浪微博songzi_tea.

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/148976.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • 有哪些让程序员受益终生的建议

    有哪些让程序员受益终生的建议从业五年多,辗转两个大厂,出过书,创过业,从技术小白成长为基层管理,联合几个业内大牛回答下这个问题,希望能帮到大家,记得帮我点赞哦。敲黑板!!!读了这篇文章,你将知道如何才能进大厂,如何实现财务自由,如何在工作中游刃有余,这篇文章很长,但绝对是精品,记得帮我点赞哦!!!!一腔肺腑之言,能看进去多少,就看你自己了!!!目录:在校生篇:为什么要尽量进大厂? 如何选择语言及方…

  • html图片自适应div大小_未知宽高的div元素垂直水平居中

    html图片自适应div大小_未知宽高的div元素垂直水平居中1.设置label的html图片-(NSMutableAttributedString*)setAttributedString:(NSString*)str{//如果有换行,把\n替换成<br/>//如果有需要把换行加上str=[strstringByReplacingOccurrencesOfString:@”\n”withString:@”<br/>”];//设置HTML图片的宽度str=[NSString

  • Django抛错不存在(DoesNotExist)

    fromdjango.core.exceptionsimportObjectDoesNotExisttry:disabledusers.objects.get(sAMAccountName=’liu’)exceptObjectDoesNotExist:print’a’exceptmodelname.DoesNotExist:转载…

  • 随机森林(原理/样例实现/参数调优)

    决策树决策树与随机森林都属于机器学习中监督学习的范畴,主要用于分类问题。决策树算法有这几种:ID3、C4.5、CART,基于决策树的算法有bagging、随机森林、GBDT等。决策树是一种利用树形结构进行决策的算法,对于样本数据根据已知条件或叫特征进行分叉,最终建立一棵树,树的叶子结节标识最终决策。新来的数据便可以根据这棵树进行判断。随机森林是一种通过多棵决策树进行优化决策的算法。案例:

  • hadoop核心模块_ERP核心模块

    hadoop核心模块_ERP核心模块转载地址:https://www.amobbs.com/thread-5531817-1-1.html 最近,利用uip搞了小东西,要想利用好uip,最好彻底搞清楚其关键函数uip_process.当网卡接收到数据之后,均需要通过该函数来处理.  下面是对uip1.0中的uip_process函数解读.//要点:网卡收到数据时,uip_process会遍历uip_udp_conn…

  • 从入门到精通,Java学习路线导航(附学习资源)

    引言最近也有很多人来向我”请教”,他们大都是一些刚入门的新手,还不了解这个行业,也不知道从何学起,开始的时候非常迷茫,实在是每天回复很多人也很麻烦,所以在这里统一作个回复吧。Java学习路线当然,这里我只是说Java学习路线,因为自己就是学Java的,对Java理当很熟悉,对于其它方面,我也不是很了解。基础阶段首先是基础阶段,在基础阶段,我们必须掌握Java基础,Mysql数据库,Ora…

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号