1/9数学奥赛辅导第六讲集合与映射知识、方法、技能这一讲主要介绍有限集的阶，有限集上的映射及其性质，这些在与计数有关的数学竞赛问题中应用极广，是参赛者必不可少的知识Ⅰ.有限集元素的数目1．有限集的阶有限集A的元素数目叫做这个集合的阶，记作|A|[或n(A)].2．集族的阶若M为由一些给定的集合构成的集合，则称集合M为集族.设A为有限集，由A的若干个子集构成的集合称为集合A的一个子集族，求满足一定条件的集族的阶是一类常见的问题.显然，若|A|=n，则由A的所有子集构成的子集族的阶为2n.Ⅱ.映射，映射法定义1设X和Y是两个集合（二者可以相同）.如果对于每个Xx，都有惟一确定的Yy与之对应，则称这个对应关系为X到Y的映射.记为.YyXxYX或这时,Yxfy)(称为Xx的象,而x称为y的原象,特别当X和Y都是数集时，映射f称为函数.定义2设f为从X到Y的一个映射.(1)如果对于任何x1、.),()(,,21212为单射则称都有fxfxfxxXx（2）如果对于任何Yy，都有Xx，使得f(x)=y，则称f为满射;（3）如果映射f既为单射又为满射，则称f为双射；（4）如果f为满射且对任何Yy，恰有X中的m个元素x1、x2、⋯xm，使得.)(,,,2,1,)(倍数映射的倍数为为则称mfmiyxfi定理1设X和Y都是有限集，f为从X到Y的一个映射,（1）如果f为单射，则|X|≤|Y|（2）如果f为满射，则|X|≥|Y|（3）如果f为双射，则|X|=|Y|（4）如果f为倍数为m的倍数映射，则|X|=m|Y|.这个定理的结果是显然的.定理2设有限集faaaAn},,,,{21是A到A上的映射，),()(1xfxf2/9),,)](([)(1NrAxxffxfrr则f是一一映射（即双射）的充要条件是：对任意).11,()(,)(1,,iiisiimiiimsNsaafaafnmNmAai而使得存在证明：必要性.若f是双射，则iiaaf)(1（此时mi=1）,或者.)(11iiiaaaf在后一种情形下，不可能有.)()(1112iiiaafaf否则，ai1在A中有两个原象ai和ai1，与f是双射不合，而只可能有2222)(,,)(),2()(12iiiiiiiiiaafaaaafmaaf如果或者此时，则依同样的道理，不可能有或者此时而只可能有),3()(,,)()(33212iiiiiiimaafaaafaf213,,)(3iiiiiaaaaaf.如此等等.因为A是有限集，所以经过有限次（设经过m次）后，有isiimaaifaafi)(,)(而).11,(imsNs这表明当f是双射时，对任一Aai都存在着映射圈:iimiiiaaaaai121在这个映射圈中，诸元素互异，且),1(1iiiamnm只有一个元素充分性.如果对任意iisiimiiiiaafaafnmNmAa)(,)(,1,,而使存在)1,(1imsNs，这说明从A中任一元素ai出发，都可以得到一个包含mi个互异元素的映射圈，显然f是双射.定理3在命题1的条件下，若对iimiiiaafNmAa)(,,使存在，则对任意.)(,iitmaafNti有这是明显的事实，证明从略.赛题精讲例1：设集合,30001|{},,14,20001|{yyBZkkxxxA集合||},,13BAZkky求.【解】形如4k+1的数的数可分三类：3/9)(912,512,112Zllll，其中只有形如12l+5的数是形如3k-1的数..167||},1997,,17,5{,1660),(20005121BABAlZll所以所以得令例2：有1987个集合，每个集合有45个元素，任意两个集合的并集有89个元素，问此1987个集合的并集有多少个元素.【解】显然，可以由题设找到这样的1987个集合，它们都含有一个公共元素a，而且每两个集合不含a以外的公共元素.但是，是否仅这一种可能性呢？由任意两个集合的并集有89个元素可知，1987个集合中的任意两个集合有且仅有一个公共元素，则容易证明这1987个集合中必有一个集合中的元素a出现在A以外的45个集合中，设为A1，A2，⋯，A45，其余的设为A46，A47，⋯，A1996.设B为A46，⋯，A1996中的任一个集合，且Ba，由题设B和A，A1，A2，⋯，A45都有一个公共元素，且此46个元素各不相同，故B中有46个元素，与题设矛盾，所以这1987个集合中均含有a.故所求结果为1987×44+1=87429.即这1987个集合的并集有87429个元素.例3：集合nBBBA,,,},9,2,1,0{21为A的非空子集族，并且当,2||jiBBji时求n的最大值.【解】首先考虑至多含三个元素的A的非空子集族，它们共有175310210110CCC个，这说明.175maxn下证，.175maxn事实上，设D为满足题设的子集族，若,,4||,BbBDB设且则B与B-{b}不能同时含于D，以B-{b}代B，则D中元素数目不变.仿此对D中所有元素数目多于4的集合B作相应替代后，集族D中的每个集合都是元素数目不多于3的非空集合，故.1...
