资源描述：
《m 1 2 3 n f g a1a2a3amb1b2b3bnh 1 2 3 m【精品-ppt】》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、Cardinality,Recursion,andMatricesSections4.3-4.4,5.2,5.8CardinalityItwastheworkofGeorgCantor(1845–1918)toestablishthefieldofsettheoryandtodiscoverthatinfinitesetscanhavedifferentsizes.Hisworkwascontroversialinthebeginningbutquicklybecameafoundationofmodernmathematics.Cardi
2、nalityisthegeneraltermforthesizeofaset,whetherfiniteorinfinite.2/23/20042DiscreteMathematicsforTeachers,UTMath504,Lecture07DefinitionforfinitesetsThecardinalityofafinitesetissimplythenumberofelementsintheset.Forinstancethecardinalityof{a,b,c}is3andthecardinalityoftheemptys
3、etis0.MoreformallythesetAhascardinalityn(fornonnegativeintegern)ifthereisabijection(one-to-onecorrespondence)betweentheset{1,2,3,…,n}andthesetA.Formallythenwedefinethebijectionf:{1,2,3}→{a,b,c}byf(1)=a,f(2)=b,andf(3)=c,therebyproving{a,b,c}hascardinality3.2/23/20043Discret
4、eMathematicsforTeachers,UTMath504,Lecture07DefinitionforfinitesetsAlthoughourbooksavesthenotationforlater,wedenotethecardinalityofthesetAby
5、A
6、.Thislookslike“absolutevalue”anditmeasuresthesizeofaset,justasabsolutevaluemeasuresthemagnitudeofarealnumber.Anotherusefulnotationt
7、hatdoesnotappearinourbookistolet[n]betheset{1,2,3,…n}with[0]=∅.Thenwecanstatethat
8、A
9、=nifthereisabijectionf:[n]→A.2/23/20044DiscreteMathematicsforTeachers,UTMath504,Lecture07DefinitionofcountableAninfinitesetAiscountablyinfiniteifthereisabijectionf:ℙ→A,whereℙisthesetofposit
10、iveintegers.Thatisℙ={1,2,3,…}.Asetiscountableifitfiniteorcountablyinfinite.Asynonymforcountableisdenumerable.Infinitesetsthatarenotcountableareuncountableor,lessfrequently,nondenumerable.2/23/20045DiscreteMathematicsforTeachers,UTMath504,Lecture07ElementaryTheoremsThecardi
11、nalityofthedisjointunionoffinitesetsisthesumofthecardinalities(4.45a).Thatis,suppose
12、A
13、=mand
14、B
15、=nfornonnegativeintegersmandnanddisjointsetsAandB.Then
16、A∪B
17、=m+n.Proof.Thereexistbijectionsf:[m]→Aandg:[n]→B.Defineafunctionh:[m+n]→(A∪B)byh(x)=f(x)if1≤x≤mandh(x)=g(x–m)ifm+1≤x≤m+
18、n.Itistediousbutnothardtoshowthatfisabijection.Thefollowingpicturemakesthesituationclear.
