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

《《离散数学》课件：1-3-映射(简)》由会员分享，可在线阅读，更多相关《《离散数学》课件：1-3-映射(简)（48页珍藏版）》请在文档大全上搜索。

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是任意两个集合。是任意两个集合