离散数学第一章第节.pptVIP

§1.3 映 射 映射 可数集合 不可数集合 定义1.3.1 映 射(mapping) 设A，B是两个集合，若对A的每个元素a，规定了B的一个确定元素b与之对应，则称此对应为由A到B内的一个映射。（有的书中称为函数） 将此映射记为?，于是对任意a?A，?(a)= b表示B中与a对应之元素，b称为a的映像(image)，a称为b的原像(pre-image) 。 集合A称为映射?的定义域(domain) , ?(A)={b | ?(a)=b，? a?A}，称为?的值域(range)，或像的集合。 显然, ?(A)是B的子集. 例：设 A={1,2,3,4,5,6},B={a,b,c,d}, ?：A ? B的映射 {(1,a).(2,b),(3,b),(4,d),(5,d),(6,d)} ?(1)= a, ?(2)=?(3)=b, ?(4)=?(5)= ?(6)=d ?(A)={a,b,d} ? B 映射的等价定义 设A，B是两个集合， ?是A到B的关系。如果对任意a∈A，都有B中唯一的b，满足(a,b)∈?，则?称为由A到B内的一个映射。 定义1.3.2 满射(surjection) 设?是A到B内的映射，如果B中每一个元素都一定是A中某元素的映像，就称?是A到B上的映射（满射）。 特别，A到A上的映射，称为变换。 注意：隐含着|A|≥|B|。 例： 设 A={1,2,3,4,5,6}, B={a,b,c,d}, ? ：A ? B上的映射(满射) 定义1.3.3 单射(injection) 设?是A到B内的映射，如果对任意a?A，b?A且a?b，都有?(a) ? ?(b)，就称?是A到B的单射。 注意：隐含着|A|≤|B| 。 例： 设A={1,2,3},B={a,b,c,d}, ? ：A ? B的映射(单射) 显然，单射未必满射；满射未必单射。 定义1.3.4 1-1映射 设?是集合A到集合B内的映射。如果?既是A到B的满射，又是A到B的单射，则称?为A到B的1-1映射(one-to-one correspond-ence),或双射(bijection)。 注意：有|A|=|B|。 例： 设A={1,2,3,4},B={a,b,c,d}, ? ：A ? B的映射(1-1映射) 例. （1）A={1,2},B={0}, ?={(1,0),(2,0)} （2） A={a,b},B={2,4,6}, ?={(a,2),(b,6)} 例. （1）A={1,2},B={0}, ?={(1,0),(2,0)} 满射，非单射 （2） A={a,b},B={2,4,6}, ?={(a,2),(b,6)} 单射，非满射 逆映射(inverse mapping) 定义.设A,B是两个集合， ?是A到B的1–1映射，则?的逆关系? -1称为?的逆映射.（有的书中称为反函数） 对任意a?Ａ，都有 ? -1 (?(a))＝a 逆映射(inverse mapping) 结论：设A,B是两个集合， ?是A到B的1–1映射，则?的逆关系?-1是B到A的 1-1映射。 证明： (1)首先证明?-1是B到A的映射，即证对任意b?B，在?-1下都有A的一个确定元素与之对应。　　 　　因?是A到B的1-1映射，故?是满射。即对任意b?B，有a?A，使得?(a)=b，即(a,b) ??，亦即(b,a)??-1 。 　　若存在b?B，满足(b,a１)??-1，(b,a２)??-1 ，且a１≠ a２，则(a１,b)??， (a２, b)??，说明A中两个不同元素有同一映像b，与?是单射矛盾。 (2)证明?-1是满射。即证明A中每一个元素a都一定是B中某元素在?-1下的映像。 任取A中元素a，因?是A到B的映射，因此，存在唯一的b?B，使得 (a,b) ??，亦即(b,a)??-1 。 (3)证明?-1是单射。即证明对任意b１?B，b2?B，且b１?b2，都有?-1(b1) ? ?-1(b2)。 用反证法。若?-1(b1) =?-1(b2)=a，则(b1,a)??-1， (b2,a)??-1，即 (a, b1)??， (a, b2)??，与?是映射矛盾。 综上， ?的逆关系? -1是B到A的 1-1映