资源描述：
《m 1 2 3 n f g a1a2a3amb1b2b3bnh 1 2 3 m》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、Cardinality,Recursion,andMatricesSections4.3-4.4,5.2,5.8CardinalityItwastheworkofGeorgCantor(1845–1918)toestablishthefieldofsettheoryandtodiscoverthatinfinitesetscanhavedifferentsizes.Hisworkwascontroversialinthebeginningbutquicklybecameafoundationofmodernmathematics.Cardinalityisthegen
2、eraltermforthesizeofaset,whetherfiniteorinfinite.2/23/20042DiscreteMathematicsforTeachers,UTMath504,Lecture07DefinitionforfinitesetsThecardinalityofafinitesetissimplythenumberofelementsintheset.Forinstancethecardinalityof{a,b,c}is3andthecardinalityoftheemptysetis0.MoreformallythesetAhas
3、cardinalityn(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/20043DiscreteMathematicsforTeachers,UTMath504,Lecture0
4、7DefinitionforfinitesetsAlthoughourbooksavesthenotationforlater,wedenotethecardinalityofthesetAby
5、A
6、.Thislookslike“absolutevalue”anditmeasuresthesizeofaset,justasabsolutevaluemeasuresthemagnitudeofarealnumber.Anotherusefulnotationthatdoesnotappearinourbookistolet[n]betheset{1,2,3,…n}wit
7、h[0]=∅.Thenwecanstatethat
8、A
9、=nifthereisabijectionf:[n]→A.2/23/20044DiscreteMathematicsforTeachers,UTMath504,Lecture07DefinitionofcountableAninfinitesetAiscountablyinfiniteifthereisabijectionf:ℙ→A,whereℙisthesetofpositiveintegers.Thatisℙ={1,2,3,…}.Asetiscountableifitfiniteorcountablyinfi
10、nite.Asynonymforcountableisdenumerable.Infinitesetsthatarenotcountableareuncountableor,lessfrequently,nondenumerable.2/23/20045DiscreteMathematicsforTeachers,UTMath504,Lecture07ElementaryTheoremsThecardinalityofthedisjointunionoffinitesetsisthesumofthecardinalities(4.45a).Thatis,suppose
11、
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+n.Itistediousbutnothardtoshowthatfisabijection.Thefollowingpicturemakesthesituationclear.
