《离散数学》课件：1-3-映射(简)

1、1.3 映映 射射 映射映射可数集合可数集合不可数集合不可数集合定义定义1.3.1 映映 射射(mapping)v设设A，B是两个集合，若对是两个集合，若对A的的每个每个元素元素a，规定了规定了B的一个确定元素的一个确定元素b与之对应，则与之对应，则称此对应为由称此对应为由A到到B内内的一个映射。的一个映射。 v将此映射记为将此映射记为 ，于是对任意于是对任意a A， (a)= b表示表示B中与中与a对应之元素，称为对应之元素，称为a的映象的映象( (imageimage) )，a称为称为b的原象的原象( (pre-imagepre-image) ) 。集合集合A称为映射称为映射 的定义域的定

2、义域( (domaindomain) ) 。 (A)=b | (a)=b，a A，称为称为 的值域的值域(range)，或象的集合。或象的集合。 映射图示a1a2a3b1b2b3GGKv设设A=1,2,3,4,5,6,B=a,b,c,d, ：A B的映射的映射例：例：123456abcdABv对于对于映射映射 ：A B， (a)= b可以表示成可以表示成(a,b) 。并且对于任意的。并且对于任意的x A，都存在都存在唯一的唯一的y B，满足满足(x,y) 。v若若A为有限集合，则为有限集合，则 也为有限集合，也为有限集合，且且| |=| A |映射是一种特殊的二元关系映射是一种特殊的二元关系

3、定义定义1.3.2 满射满射( (surjection) )v设设 是是A到到B内的映射，如果内的映射，如果B中每一个元中每一个元素都一定是素都一定是A中某元素的映象，就称中某元素的映象，就称 是是A到到B上上的映射（满射）。特别，的映射（满射）。特别，A到到A上的上的映射，称为变换。映射，称为变换。 v设设A=1,2,3,4,5,6,B=a,b,c,d, ：A B的映射的映射(满射满射)例：例：123456abcdAB定义定义1.3.3 单射单射( (injection) )v设设 是是A到到B内的映射，如果对任意内的映射，如果对任意a A，b A且且a b，都有都有 (a) (b)，就称就

4、称 是是A到到B的单射。的单射。 v设设A=1,2,3,B=a,b,c,d, ：A B的映射的映射(单射单射)例：例：123abcdAB定义定义1.3.4 1-1映射映射v设设 是集合是集合A到集合到集合B内的映射。如果内的映射。如果 既既是是A到到B的满射，又是的满射，又是A到到B的单射，则称的单射，则称 为为A到到B的的1- -1映射映射( (one-to-one correspond-ence),),或双射或双射( (bijection)。 1-1映射示意图a1a2a3Gb1b2b3Gv设设A=1,2,3,4,B=a,b,c,d, ：A B的映射的映射(1- -1映射映射)例：例：123

5、4abcdAB同态映射实例CatalogPartAttributeSchemaManagercategoryProperty1*1111111*Belong toBelong tosubpartsubcategory逆映射逆映射( (inverse mapping) ) v若若 是集合是集合A到集合到集合B的的11映射，则对于映射，则对于B中每个元素中每个元素b都对应着都对应着A中以中以b为映象（在为映象（在 下）的那个元素，这个对应显然是集合下）的那个元素，这个对应显然是集合B到到A上的映射，我们称这个映射为上的映射，我们称这个映射为 的逆映的逆映射，记为射，记为 -1 。显然，显然， -1

6、也是也是1-1映射，并映射，并且对任意且对任意a ，都有，都有 -1 ( (a)a定义定义1.3.5映射的乘积映射的乘积v设设 是集合到集合内的映射，是集合到集合内的映射， 是集是集合到集合内的映射，对任意合到集合内的映射，对任意a A，规规定定( )(a) ( (a)显然显然 是集合到集合内的映射，我们是集合到集合内的映射，我们称此映射为映射称此映射为映射 与映射与映射 的乘积。的乘积。v不难证明：映射的乘积满足结合律，但是不难证明：映射的乘积满足结合律，但是不满足交换律。不满足交换律。 v设设A=1,2,3,4,B=a,b,c,d, ：A B (1- -1映射映射)例：例：1234abcd

7、AB1234abcdAB -11.3.1 集合的基数集合的基数 基数是集合的一个重要特征，基数的研究是纯集合论研究的一基数是集合的一个重要特征，基数的研究是纯集合论研究的一个及其重要的方向，但它作为离散数学课程的一部分，只是为了使个及其重要的方向，但它作为离散数学课程的一部分，只是为了使读者对基数概念有一个正确的认识，并借此加深对映射概念的理解，读者对基数概念有一个正确的认识，并借此加深对映射概念的理解，提高正确运用映射工具的能力，获得一些特定的研究方法（如提高正确运用映射工具的能力，获得一些特定的研究方法（如“对角线法对角线法”）。前面两节我们把基数看成是集合元素的个数，对）。前面两节我们把

8、基数看成是集合元素的个数，对于有限集合没有问题，而对无限集合而言便不合适了。于有限集合没有问题，而对无限集合而言便不合适了。著名的伽利著名的伽利略悖论：如一个有无限多个客房的旅店，规定每个房间住一位旅客，略悖论：如一个有无限多个客房的旅店，规定每个房间住一位旅客，并已住满，又来一位旅客投宿，店主欣然接纳，他让一号房的旅客并已住满，又来一位旅客投宿，店主欣然接纳，他让一号房的旅客住二号房，让二号房的旅客住三号房，如此下去，腾出一号房让新住二号房，让二号房的旅客住三号房，如此下去，腾出一号房让新来的旅客住，用集合论的观点来描述这一悖论，无疑是说集合来的旅客住，用集合论的观点来描述这一悖论，无疑是说

9、集合I=1,2,3与集合与集合S=0,1,2,具有相同多元素，即具有相同多元素，即I=S。可是可是S明明比明明比I多一个元素多一个元素“0”！这表明必须给出基数的严格定义，！这表明必须给出基数的严格定义，按直观讨论的集合元素个数是行不通的，至少对于无限集合是这样。按直观讨论的集合元素个数是行不通的，至少对于无限集合是这样。1.3.1 集合的基数集合的基数 v我们把相当于有限集合的元素数的概我们把相当于有限集合的元素数的概念推广到一般集合，称之为集合的基念推广到一般集合，称之为集合的基数数( (势，浓度势，浓度) )。集合。集合A的基数记为的基数记为|A|。 定义定义1.3.6 v设设A，B为集

10、合，若为集合，若A与与B之间存在之间存在1-1映射，映射，则称则称A与与B基数相同，也称基数相同，也称A与与B对等（等势，对等（等势，等浓），记为等浓），记为|A|=|B|。v例如，自然数集合例如，自然数集合N与正偶数集合与正偶数集合B对等，对等，N到到B的一个的一个1-1映射为映射为 (n)=2n。v再如，区间集合再如，区间集合A=(0, 1)与与B=(0, + )等浓，等浓，A到到B的一个的一个1-1映射为映射为 (x)=tg( x/2) v显然，集合显然，集合A为有限集当且仅当它以某一为有限集当且仅当它以某一非负整数为其基数，即存在一非负整数非负整数为其基数，即存在一非负整数n使使得得

11、A=n。即集合即集合A的元素个数是的元素个数是n。我们把我们把自然数集合的基数记为自然数集合的基数记为0，于是凡是与自，于是凡是与自然数集合对等的集合然数集合对等的集合A，其基数其基数|A|= 0。 v容易验证集合的对等关系是一个等价关系。容易验证集合的对等关系是一个等价关系。v我们可以用对等关系重新来刻画什么是集我们可以用对等关系重新来刻画什么是集合的基数：集合按照对等关系分成等价类，合的基数：集合按照对等关系分成等价类，每个等价类的共同的数量特征，称为该等每个等价类的共同的数量特征，称为该等价类中集合的基数。价类中集合的基数。 定义定义1.3.7 v设设A，B是任意两个集合。是任意两个集合

12、。(1)称称A的基数小于等于的基数小于等于B的基数，记为的基数，记为 A B ，如果有如果有A到到B单射单射 或有或有B到到A满射满射 。(2) 称称A的基数小于的基数小于B的基数，记为的基数，记为 AB ，如果如果AB且且AB 。v换句话说，若换句话说，若A与与B的某一子集有的某一子集有1-1对应对应关系，则关系，则AB ；若若A与与B的某一子集有的某一子集有1-1对应关系，且对应关系，且A与与B不存在不存在1-1对应关系，则对应关系，则 AB。 定理定理1.3.1 v若存在若存在A的子集的子集A 和和B的子集的子集B ，使使得得|A|=|B |且且|B|=|A |，则则|A|=|B|。即若

13、即若|A|B|且且|B|A|，则则|A|=|B|。 基数的三歧性定理基数的三歧性定理 v对任意集合对任意集合A，B，或者或者|A| |B|，或者或者|A|B|，或者或者|B| |A|，且不能有两个且不能有两个式子同时成立。式子同时成立。 1.3.2 可数集合可数集合 定义定义1.3.8 v一个集合，如果它的元素为有限个，一个集合，如果它的元素为有限个，或者它与自然数集合之间存在一个或者它与自然数集合之间存在一个1-1映射，则称此集合为可数集合。否则映射，则称此集合为可数集合。否则称该集合为不可数集合。称该集合为不可数集合。v元素个数不是有限的可数集合称为可元素个数不是有限的可数集合称为可数无穷

14、集合，对于可数无穷集合，可数无穷集合，对于可数无穷集合，可以把它的元素编号：以把它的元素编号： a1, a2, , an, 例：例： v正整数的平方数集合正整数的平方数集合B=1,4,9,16,是可是可数无穷集，作数无穷集，作 : NB， (x)=x2v整数的集合整数的集合Z是可数无穷集，作是可数无穷集，作 : NZ，为奇数为偶数xxxxx212)(定理定理1.3.2v可数集合的子集仍为可数集合。可数集合的子集仍为可数集合。证明：证明：如果此可数集合是有限集合，则它如果此可数集合是有限集合，则它的子集也有限，当然可数。的子集也有限，当然可数。如果此可数集合是无穷集合，则此集合的如果此可数集合是

15、无穷集合，则此集合的元素可写成元素可写成a1, a2, , an, 的形式。它的子的形式。它的子集可以这样得到：从左向右，第一个是子集可以这样得到：从左向右，第一个是子集中元素的记为集中元素的记为ai1，第二个是子集中元素第二个是子集中元素的记为的记为ai2, ，于是，此子集的元素可排列于是，此子集的元素可排列为：为： ai1, ai2, , ain, 。所以，此子集是可数集合。所以，此子集是可数集合。 定理定理1.3.3v设设A，B是可数集合，是可数集合，AB= ，则则AB是可数集合。是可数集合。v证明：证明：因为因为A，B是可数集合，所以可设是可数集合，所以可设A=a1, ,a2, , ,

16、an, ,，B= b1, ,b2, , ,bn, ,。于是于是AB可以写成可以写成a1,b1,a2,b2,an,bn,，且由且由AB=知，其中没有重复元素。因此知，其中没有重复元素。因此AB是可数集合。是可数集合。定理定理1.3.4v设设A1, ,A2, , ,An, , 是可数无穷多个是可数无穷多个可数集合的序列，则可数集合的序列，则 是可数集合。是可数集合。即可数无穷多个可数集合的并集是可即可数无穷多个可数集合的并集是可数集合。数集合。 1Aii证明：证明：v不失一般性，设不失一般性，设A1, A2, , An,都是都是可数无穷集合，且为可数无穷集合，且为A1=a11, a12, , a1

17、n, A2=a21, a22, , a2n, A3=a31, a32, , a3n, An=an1, an2, ann, 证明：证明：v对于任意的对于任意的aij，规定按各元素规定按各元素(i+j)之和的之和的大小排序，相同者按大小排序，相同者按i的大小排序，如果当的大小排序，如果当前排序者与前面已排好序的某元素相同则前排序者与前面已排好序的某元素相同则删去该当前元素，如此排下去，最后得删去该当前元素，如此排下去，最后得由定义由定义1.3.8可知可知, 是可数集合。是可数集合。1iiA=a11, a12, a21, a13, a22, a31, , a1n, a2(n-1), an1,。1ii

18、A证明：证明：A1=a11, a12, a13, a14, , a1n, A2=a21, a22, a23, a24, , a2n, A3=a31, a32, a33, a34, , a3n, A4=a41, a42, a43, a44, , a4n, .定理定理1.3.5v设设A，B是可数无穷集合，则是可数无穷集合，则A B是是可数集合。可数集合。v证明：设证明：设A= a1, a2, , an, ，B= b1, b2, , bn, 。于是于是A B=(ai，bj)| ai A， bj B，我们将我们将A B的元素的元素作如下排列：作如下排列：(a1, b1), (a1, b2), (a1,

19、 b3), , (a1, bn), (a2, b1), (a2, b2), (a2, b3) , (a2, bn), (a3, b1), (a3, b2), (a3, b3), , (a3, bn), (an, b1), (an, b2), (an, b3), , (an, bn), 对上述元素按足标同定理对上述元素按足标同定理1.3.4的证明方式的证明方式进行处理排序，得进行处理排序，得A B是可数集合。是可数集合。 定理定理v有理数集合是可数集合有理数集合是可数集合定理定理v若若A1, , A2, , , ,An是可数集合，则是可数集合，则A1 A2 An是可数集合。是可数集合。用归纳法证

20、明。用归纳法证明。1.3.3 不可数集合不可数集合 定理定理1.3.6 v全体实数做成的集合是不可数集合。全体实数做成的集合是不可数集合。 证明：证明：由定理由定理1.3.2知，只要证明知，只要证明(0,1)区间内的实区间内的实数不可数就可以了。数不可数就可以了。若不然，我们可以把若不然，我们可以把(0,1)区间内的数排成一个序区间内的数排成一个序列：列：0.a11a12a13a14 0.a21a22a23a240.a31a32a33a34 (2)显然，显然，(3)是是(0,1)区间内的数，但它却不是序列区间内的数，但它却不是序列(2)中的任一个数。事实上，对中的任一个数。事实上，对(2)中任

21、一个数中任一个数0.ak1ak2akk，因为因为rkakk，故故0.ak1ak2akk0.r1r2rk 与假设矛盾。故与假设矛盾。故(0,1)区间内的实数不可数，所以区间内的实数不可数，所以整个实数集不可数。整个实数集不可数。 , 3 , 2 , 1, 1a21a1rkkkkkk当当我们考虑下面的数：我们考虑下面的数： 0.r1r2rk ()其中其中推推 论论 v实数集合实数集合R，区间区间(a,+ )、a,b、a,b)、(a,b，其中其中ab，都是不可数的，且与区间都是不可数的，且与区间(0,1)等浓。等浓。 证明：证明：我们仅看构造区间我们仅看构造区间0,1与与(0,1)之间之间1-1映射

22、的一个例子。我们知道全体有理数的映射的一个例子。我们知道全体有理数的集合是可数的，于是集合是可数的，于是(0,1)区间中的有理数区间中的有理数是可数的，不妨将它们排成是可数的，不妨将它们排成a1, a2, , an, 的形式。的形式。令区间令区间0,1中的无理数到区间中的无理数到区间(0,1)中的无理中的无理数的数的1-1映射映射 2为自己对应自己。则映射为自己对应自己。则映射 = 1 2为区间为区间0, 1到区间到区间(0,1)的的1-1映射。映射。从而区间从而区间0,1与与(0,1)等浓。等浓。 0， 1， a1， a2，an， a1，a2，a3， a4，, an+2, 而闭区间而闭区间0

23、,1比区间比区间(0,1)多两个数多两个数0和和1，它，它们是有理数，于是可建立闭区间们是有理数，于是可建立闭区间0, 1中的中的有理数到区间有理数到区间(0,1)中的有理数的中的有理数的1-1映射映射 1：v我们把我们把(0,1)区间内的实数集合区间内的实数集合的基数记的基数记为为c，也记为也记为1。即即c= 1。 定理定理1.3.7 v设设A1, A2, ,An, 是互不相交的集合是互不相交的集合序列，它们的基数都是序列，它们的基数都是c，则则 的基的基数也是数也是c。即可数个基数为即可数个基数为c的集合的并的集合的并集基数仍为集基数仍为c。 1iiA证明：证明： v设设I1=(0, 1)

24、, Ik=k-1, k) (k=2,3,4, ) ，则则当当mn时，时，ImIn =。因为因为Ik (k=1, 2, )的的基数是基数是c，故存在故存在1-1映射映射 1, 2 ,，使得使得 k(Ik)= Ak。令令 = ，则则 是是 =(0, + )到到 的的1-1映射。从而映射。从而 与与(0, + )等浓，等浓，由推论知其基数为由推论知其基数为c。 1kkA1kk1kkI1kkA定理定理1.3.8 v集合不能与集合不能与2建立建立1-1映射。映射。 证明：证明：反证法反证法；假设；假设 为为A到到2A的的1-1映射。令映射。令= x|x A并且并且x(x) 于是，存在唯一一个元素于是，存在唯一一个元素b A，使得使得 (b) =;若若b B，则由，则由B的定义知，的定义知，b(b)=B，即即b B，矛盾。矛盾。若若b , 因为因为 (b) =, 所以所以b(b)，于是由的于是由的定义知，定义知，b B，矛盾。矛盾。故集合不能与故集合不能与2建立建立1-1映射。映射。这个结论说明无穷有无穷多层次，没有最大无穷这个结论说明无穷有无穷多层次，没有