关系与映射学习指导学习目标理解笛卡尔积、二元关系、运算关系等概念，理解映射、满射、单射、双射等概念，理解有关定理，掌握有关定理的证明方法和有关的例题的处理方法。

内容提要(一)笛卡尔积： A ×B ={(a ,b )｜a ∈A , b ∈B }，注意(a ,b )为有次序的元素偶.从集合A 到B 中的关系： A ×B 中的每一子集R 称为从A 到B 中的关系. 若(a ,b )∈R ，则称a 与b 是R -相关的，记作aRb .关系R 的定义域： Dom (R )={a ｜存在b ∈B ，使aRb }(⊂A ). 关系R 的值域： Ran (R )={ b ｜存在a ∈A ，使aRb }(⊂B ).关系R 的象集： R (A ~)={b ｜存在a ∈A ~，使得aRb }(⊂B ). 其中集合A ~⊂A .关系R 的逆： 设R ⊂A ×B ，则B ×A 的子集1-R ={(b ,a )｜aRb }称为R 的逆.关系的复合: S R ={(a ,c )｜存在b ∈B ，使得aRb ，bSc }，其中R ⊂A ×B ，S ⊂B ×C . 设A ，B ，C ，D 为集合；R ⊂A ×B ，S ⊂B ×C ，T ⊂C ×D ，则有关系的逆与复合运算满足：(1) 11)(--R =R ；(2) 1)(-R S =1-R 1-S ； (3) T (S R )=(T S ) R .(二)映射： F ∶X →Y ，即∀x ∈X ，有唯一y ∈Y ，使得xFy .映射F 的象： y =F (x )，即对于每一x ∈X ，使得xFy 成立的y .映射F 的原象： )(1y F -，即对于y ∈Y ，使得xFy 成立的x (x ∈X ). 映射的复合： (G F )(x )=G (F (x ))，其中F ∶X →Y ，G ∶Y →Z . 满射： 若f (X )=Y ，则称f 为从X 到Y 上的满射.单射： 若∀1x ,2x ∈X , 1x ≠2x ，有f (1x )≠f (2x )，则称f 为从X 到Y 上的单射. 双射： 若f 即是单射又是满射的. 逆映射： 由y =f (x )确定的从Y 到X 的映射1-f ：Y →X ，其中f ∶X →Y 是双射.1： 设f ∶X →Y ，A ，B ⊂Y ，则逆映射1-f 满足(1)1-f (A ∪B )=1-f (A )∪1-f (B )； (2)1-f(A ∩B )=1-f(A )∩1-f(B )；(3)1-f (A -B )=1-f (A )-1-f (B ).结论2： 设f ∶X →Y(1) 若f 是单射，则对于X 的任意子集A ，有1-f(f (A ))=A .(2) 若f 是满射，则对于Y 的任意子集B ，有f (1-f (B ))=B .(三) 运算运算： 映射f : A ×B →C 是一个从A ×B 到C 中的运算.特别的，映射f : A ×A →A 是A 上的一个运算，并且称运算f 在A 上封闭.若f (a ,b )=f (b ,a ), 则称运算f 满足交换律；若f (f (a ,b ),c )=f (a ,f (b ,c )), 则称运算f 满足结合律.f 的右零元e ： ∀a ∈A , 使f (a ,e )= a ； f 的左零元e ： ∀a ∈A , 使f (e ,a )= a ；f 的零元e ： 既是f 的左零元，又是f 的右零元.a 的右逆元a '： 对于a ∈A ，若∃a '∈A ，使f (a , a ')= e ； a 的左逆元a '： 对于a ∈A ，若∃a '∈A ，使f (a '，a )= e ；a 的逆元a '： 既是a 的左逆元，又是a 的右逆元.重难点解析(二) 关于关系与映射世界上存在各种各样的事物，这些事物之间的相互联系，我们称之为“关系”. 本节用统一的数学语言来描述这些表面看起来似乎无关的，但本质上却有其共性的“关系”. 本节介绍的二元关系、运算和映射等概念也是本课程的基础，它们在后续各章节中都有应用. 因此，我们在学习本节内容时应该理解笛卡尔积、二元关系、运算关系等概念，理解映射、满射、单射、双射等概念，掌握有关定理的证明方法和有关的例题的处理方法。

1．笛卡尔积是一种集合的二元运算，是本节最基本的概念之一. 集合A 与B 的笛卡尔积A ⨯B = {(a , b )│a ∈A , b ∈B }是一个集合，这个集合的元素都是一些有序对，这些有序对中的第一个成员都是取自集合A ，第二个成员都是取自集合B ，不能随意取出写之.集合A ，B 的笛卡尔积与这两个集合的次序有关. 一般地，若A 与B 非空，只要A ≠B ，则有A ×B ≠B ×A . 也就是说交换律不成立. 例如，集合A ={a , b , c }，B ={1, 2}，则A ⨯B = {a , b , c }⨯{1, 2} = {(a , 1)，(a , 2)，(b , 1)，(b , 2)，(c , 1)，(c , 2)} A ⨯B = {1, 2}⨯{a , b , c } = {(1 , a )，(1 , b )，(1 , c )，(2 , a )，(2 , b )，(2 , c )} 所以A ×B ≠B ×A .2. 二元关系R 是一个有序对组成的集合. 因此，一个二元关系是一个集合，可以用集合形式表示. 但是任意一个集合就不一定是一个二元关系了，只有当这个集合是由有序对组成的，才能称为二元关系.例如，1R ={(a , 1)，(b , 2)}，2R ={a ，(b , 2)}，那么1R 是二元关系，而2R 不是二元关系，仅仅是一个集合二元关系R 也可以用关系图表示. 设集合A ={a 1 , a 2 , … , a m }，B ={b 1 , b 2 , … , b n }，若R 是从A 到B 的一个关系，则用m 空心点表示a 1 , a 2 , … , a m ，用n 空心点表示b 1 , b 2 , … , b n ，这些空心点统称为结点. 如果a i Rb j ，那么由结点a i 到结点b j 作一条有向弧，箭头指向b j ；如果(a i , b j )∈R ，那么结点a i 与b j 之间没有弧连结，这样的图形称为R 的关系图.若R 是A 上一个关系，如果a i Ra j (i ≠j )，有向弧的画 法与上面相同；如果a i Ra i ，则画一条从结点a i 到结点a i 的带箭头的封闭弧，称为自回路例如，集合A ={1，2，3，4}上的关系 R ={(1 , 1)，(1 ,2)，(2 , 3)，(2 , 4)，(3 , 3)，(4 , 2)}，则R 的关系图如图1-6 所示.3．关系R 的定义域是指R 中有序对的第一元素所允许选取对象的集合，关系R 的值域是指R 中有序对的第二元素所允许选取对象的集合.例如，集合A ={a , b , c }，B ={1, 2, 3}，从A 到B 的关系 R = { (a , 2)，(b , 1)，(b , 3)} 那么，Dom(R ) = {a , b }，Ran(R ) = {1, 2, 3}.4．在映射的定义(定义2.5)中，条件“如果∀x ∈X ，有唯一y ∈Y ，使得xFy ，”表示映射是单值的，也就是说，定义域中的任意一个x 与值域中唯一的y 有关系，所以用y =F (x )表示. 另外，该条件还指出，集合X 就是映射F 的定义域，即Dom(F ) =X .因此，从集合X 到Y 的映射F 是一个二元关系，但是从X 到Y 的二元关系R 不一定是一个映射. 例如，实数集R 上的二元关系f ={(a , b )|a =2b }不是映射，因为(4, -2)∈f ，(4, 2)∈f ，不满足映射的单值性.由此可知，若映射F 是双射，则存在逆映射1-F ；若映射F 不是双射，则不存在逆映射1-F，或者说1-F不是映射.图1 –6对于从集合X 到Z 中复合关系G F ，因为F 是从X 到Y 的映射，G 是从Y 到Z 的映射，由映射的定义可知，映射F 的值域是映射G 的定义域的子集，即 Ran(F )⊂Dom(G )，它保证了复合映射G F 是非空的.典型例题解析例1 设集合A = {1, 2, 3, 4}上的二元关系R = {(1, 1), (1, 2), (2, 4), (3, 1), (3, 3)}，S = {(1, 3), (2, 2), (3, 2), (4, 4)}，用定义求11112,,,,,----R S S R R S R R S .[思路] 求复合关系R S ，就是要分别将R 中有序对(a , b )的第2个元素b 与S 中的每个有序对(c , d )的第1个元素进行比较，若它们相同（即b =c ），则可组成R S 中的1个元素(a , d )，否则不能. 幂关系的求法与复合关系类似.求关系R 的逆关系，只要把R 中的每个有序对的两个元素交换位置，就能得到1-R 中的所有有序对.解 R S = {(1, 1), (1, 2), (2, 4), (3, 1), (3, 3)} {(1, 3), (2, 2), (3, 2), (4, 4)} = {(1, 3), (1, 2), (2, 4), (3, 3), (3, 2)}S R ={(1, 3), (2, 2), (3, 2), (4, 4)} {(1, 1), (1, 2), (2, 4), (3, 1), (3, 3)} ={(1, 1), (1, 3), (2, 4), (3, 4)}2R =R R = {(1, 1), (1, 2), (2, 4), (3, 1), (3, 3)} {(1, 1), (1, 2), (2, 4), (3, 1), (3, 3)} ={(1, 1), (1, 2), (1, 4), (3, 1), (3, 2), (3, 3)}1-R ={(1, 1), (1, 2), (2, 4), (3, 1), (3, 3)}1- ={(1, 1), (1, 3), (2, 1), (3, 3), (4, 2)}1-S ={(1, 3), (2, 2), (3, 2), (4, 4)}1- = {(2, 2), (2, 3), (3, 1), (4, 4)}1-S 1-R ={(1, 1), (1, 3), (2, 1), (3, 3), (4, 2)} {(2, 2), (2, 3), (3, 1), (4, 4)} ={(1, 1), (3, 1), (4, 2), (4, 3)}注：由例1可知，关系的复合运算不满足交换率，即R S ≠S R .例2 对于以下给定的集合A 、B 和关系f ，判断是否构成映射f ：B A →. 如果是，试说明f ：B A →是否为单射、满射或双射的.（1）A ={1, 2, 3, 4, 5}，B ={6, 7, 8, 9, 10}，f ={(1, 8), (3, 9), (4, 10), (2, 6), (5, 9)}； （2）A ={1, 2, 3, 4, 5}，B ={6, 7, 8, 9, 10}，f ={(1, 7), (2, 6), (4, 5), (1, 9), (5, 10)}； （3）A ={1, 2, 3, 4, 5}，B ={6, 7, 8, 9, 10}，f ={(1, 8), (3, 10), (2, 6), (4, 9)} （4）A =B =R ，f (x ) = x 3，（∈∀x R ）； （5）A =B =R ，11)(2+=x x f ，（∈∀x R ）； [思路] 首先按照1.2节的定义2.5，判断A 、B 和f 是否构成映射，即判断f 是否具有单值性以及Dom(f )是否等于A . 然后再按照定义2.6，说明f ：B A →具有的性质. 解 （1）因为Dom(f ) = A ，且对任意A i ∈（i =1, 2, 3, 4, 5），都有唯一的B j ∈，使(i , j )f ∈. 所以A 、B 和f 能构成函数f ：B A →.因为存在3, 5∈A ，且3≠5，但映射f (3)= f (5) = 9，所以f ：B A →不是单射的； 又因为集合B 中的元素7不属于f 的值域，即f (A )≠B ，所以f ：B A →不是满射的. （2）因为对1∈A ，存在7, 9∈B ，有f (1)= 7，f (1)= 9，即f 不满足映射定义的单值性条件. 所以A 、B 和f 不能构成映射f ：B A →.（3）因为Dom f ={1, 2, 3, 4}≠A ，所以A 、B 和f 不能构成映射f ：B A →. （4）因为对∈∀x R ，都有唯一的∈3x R ，使 (x , 3x )f ∈. 所以A 、B 和f 能构成映射f ：B A →.由图1-12可知，f ：B A →，f (x )= x 3是双射的.（5）因为对∈∀x R ，都有唯一的∈+112x R ， 使f x x ∈+)11,(2. 所以A 、B 和f 能构成映射 f ：B A →.因为该映射在x ≠ 0处，f (-x )= f (x )，且f (R ) ≠R ，所以映射f ：B A →不是单射的，也不是满射的.例3 证明：若f ：X →Y ，A ，B ⊂Y ，则1-f (A - B ) =1-f (A )-1-f (B )证明 ∀x ∈1-f (A - B )，∃y ∈(A - B )，即y ∈A 但y ∈B ，使得y = f (x )，从而有 x ∈1-f (A )但x ∈1-f(B )，故x ∈(1-f(A )-1-f(B ))．∴ 1-f(A -B )⊂1-f (A ) -1-f(B )．又 ∀x ∈(1-f (A )-1-f(B ))，由于x ∈1-f(A )但x ∈1-f (B )，从而f (x )∈A 但f (x )∈B ，即f (x )∈(A -B )，故x ∈1-f(A - B )．∴ 1-f (A ) -1-f (B )⊂1-f (A -B )．因此，1-f(A - B ) =1-f(A )-1-f(B )．例4 设有映射f :A →A . 若∈a ∈A , f (a )=a , 则称映射f 是恒等映射，表示为A I . 设有两个映射f :A →B , g :B →A . 若g f =A I , 则f 是单射，g 是满射. 证明 (1) 证明映射f 是单射.对任意的b ∈B ，如果存在a 1，a 2∈A ，使f (a 1) = b ，f (a 2) = b ，即f (a 1) = b = f (a 2).因为 a 1=A I (a 1)=(g f )(a 1)= g (f (a 1)) = g (f (a 2)) =(g f )(a 2) =A I (a 2)= a 2 . 所以f 是单射的.(2) 证明映射g 是满射.因为(g f )(A )=A I (A )= A ，所以g f 是满射的.又对任意的c ∈A ，由g f 是满射的可知，存在a ∈A ，使(g f )(a ) = c . 那么存在b ∈B ，使f (a ) = b ，g (b ) = c .所以存在b ∈B ，使g (b ) = c ，即g 是满射的.例5 设函数f ：A →B ，g ：B →C ，且g f ：A →C ，证明：若f 和g 都是单射的，则g f 也是单射的.证明 因为对任意的a 1，a 2∈A ，如果a 1≠a 2，那么由f 是单射的可知，f (a 1)≠ f (a 2). 而由g 是单射的可知，g (f (a 1))≠g ( f (a 2)).所以，由a 1≠a 2可得 (g f ) (a 1)≠( g f ) (a 2) ，即g f 是单射的.例6 设f ：R →R ，⎩⎨⎧<-≥=323,)(2a a a a f ，；g ：R →R ，2)(+=a a g . 求g f ，fg . 如果f 和g 存在逆映射，求它们的逆映射. 解：（1）求g f 和f g(g f )(a )= g (f (a ))⎩⎨⎧<-≥=3,23,2a a a +2 =⎩⎨⎧<-≥+3,23,22a a a ；(f g )(a )= f (g (a )) = f (a +2) =⎩⎨⎧<≥+1,01,)2(2a a a（2）求逆映射.因为映射f ：R →R ，⎩⎨⎧<-≥=3,23,)(2a a a a f 不是满射的. 所以f ：R →R 不是双射，由1.2节注2.1可知，f 不存在逆映射.又因为g ：R →R ，g (a ) = a +2即是满射的，又是单射的. 所以g ：R →R 是双射，因此g 存在逆映射，其逆映射为1-g ：R →R ，2)(1-=-a a g .。