1.3-映 射_ou.ppt

1、1.3 映 射,映射 可数集合 不可数集合,定义1.3.1 映 射(mapping),设A，B是两个集合，若对A的每个元素a，规定了B的一个确定元素b与之对应，则称此对应为由A到B内的一个映射。（有的书中称为函数） 将此映射记为，于是对任意aA，(a)= b表示B中与a对应之元素，b称为a的映像(image)，a称为b的原像(pre-image) 。 集合A称为映射的定义域(domain) , (A)=b | (a)=b， aA，称为的值域(range)，或像的集合。 显然, (A)是B的子集.,例：设A=1,2,3,4,5,6,B=a,b,c,d, ：A B的映射 (1,a).(2,b),(

2、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的关系。如果对任意aA，都有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 单射(injectio

3、n),设是A到B内的映射，如果对任意aA，bA且ab，都有(a) (b)，就称是A到B的单射。 注意：隐含着|A|B| 。,设A=1,2,3,B=a,b,c,d, ：A B的映射(单射) 显然，单射未必满射；满射未必单射。,例：,1 2 3,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

4、,2,B=0, =(1,0),(2,0) （2） A=a,b,B=2,4,6, =(a,2),(b,6) （3）A=N,B=N, =(x,2x)|xN - (x)=2x, xN 若B=2N? （4） A=Z,B=Z, =(x,x+1)|xZ - (x)=x+1, xZ,例. （1）A=1,2,B=0, =(1,0),(2,0) 满射，非单射 （2） A=a,b,B=2,4,6, =(a,2),(b,6) 单射，非满射 （3）A=N,B=N, =(x,2x)|xN- (x)=2x, xN 单射，非满射 若B=2N，则1-1映射 （4） A=Z,B=Z, =(x,x+1)|xZ- (x)=x+1,

5、 xZ 1-1映射,逆映射(inverse mapping),结论：设A,B是两个集合， 是A到B的11映射，则的逆关系-1是B到A的 1-1映射。 证明： （1）首先证明-1是B到A的映射，即证对任意bB，在-1下都有A的一个确定元素与之对应。 因是A到B的1-1映射，故是满射。即对任意bB，有aA，使得(a)=b，即(a,b) ，亦即(b,a)-1 。 若存在bB，满足(b,a)-1，(b,a)-1 ，且a a，则(a,b)， (a, b)，说明A中两个不同元素有同一映像b，与是单射矛盾。,（）证明-1是满射。即证明A中每一个元素a都一定是B中某元素在-1下的映像。 任取A中元素a，因是A

6、到B的映射，因此，存在唯一的bB，使得 (a,b) ，亦即(b,a)-1 。 （3）证明-1是单射。即证明对任意bB，b2B，且bb2，都有-1(b1) -1(b2)。 用反证法。若-1(b1) =-1(b2)=a，则(b1,a)-1， (b2,a)-1，即 (a, b1)， (a, b2)，与是映射矛盾。 综上， 的逆关系 -1是B到A的 1-1映射。,逆映射(inverse mapping),定义.设A,B是两个集合， 是A到B的11映射，则的逆关系 -1称为的逆映射.（有的书中称为反函数） 对任意a，都有 -1 (a)a,设A=1,2,3,4,B=a,b,c,d, ：A B (1-1映射

7、),例：,1 2 3 4,a b c d,A,B,1 2 3 4,a b c d,A,B,-1,定义1.3.5映射的乘积,设是集合到集合内的映射， 是集合到集合内的映射，对任意aA，规定( )(a) ( (a)显然 是集合到集合内的映射，我们称此映射为映射与映射的乘积。 不难证明：映射的乘积满足结合律，但是不满足交换律。,映射的乘积满足结合律,需要证明：任意xA，有 ( ( )(x) = () )(x) = (x),A,B,C,D,映射的乘积不满足交换律,( )(1)=( (1)=(a)=m; ( )(1)= ( (1) 没有定义。,1 2 3,a b c,m n p,A,B,C,练习：,设A

8、=1,2,3,B=p,q,C=a,b :AB =(1,p),(2,p),(3,q) :BC =(p,b),(q,b) 则 =(1,b),(2,b),(3,b),练习：,设A=1,2,3 :AA =(1,2),(2,3),(3,1) : AA =(1,2),(2,1),(3,3) : AA =(1,1),(2,2),(3,3) 则 =(1,3),(2,2),(3,1) =(1,1),(2,3),(3,2) -1 = = = ,例：将集合M中元素映射到自身的变换称为同一变换，记为I。设，是集合M上的两个变换，如果=I，则，是11变换，并且=-1。 证明： (1)往证，是11变换。对任意x1，x2M

9、，如果(x1)= (x2)，则有x1=I(x1)= () (x1)= (x1) )= (x2) ) = () (x2) =I(x2)= x2所以是单射。同理可证是单射。 又由，是满射，知， ，是11变换。,(2)往证=-1。 由是1-1映射，知-1亦是1-1映射， 对任意x M，-1(x)= I (-1(x)= () (-1(x) = ( (-1(x)= (x)故=-1 。,1.3.1 集合的基数,基数是集合的一个重要特征，基数的研究是纯集合论研究的一个极其重要的方向，但它作为离散数学课程的一部分，只是为了使读者对基数概念有一个正确的认识，并借此加深对映射概念的理解，提高正确运用映射工具的能力

10、，获得一些特定的研究方法（如“对角线法”）。,前面两节我们把基数看成是集合元素的个数，对于有限集合没有问题，而对无限集合而言便不合适了。 著名的伽利略悖论：如一个有无限多个客房的旅店，规定每个房间住一位旅客，并已住满，又来一位旅客投宿，店主欣然接纳，他让一号房的旅客住二号房，让二号房的旅客住三号房，如此下去，腾出一号房让新来的旅客住，用集合论的观点来描述这一悖论，无疑是说集合I=1,2,3与集合N=0,1,2,具有相同多元素，即I=N。可是N明明比I多一个元素“0”！ 这表明必须给出基数的严格定义，按直观讨论的集合元素个数是行不通的，至少对于无限集合是这样。,问题的提出,无限集合的大小如何比较

11、? 例: 集合A:全体正整数做成的集合, 集合B：全体正偶数做成的集合, 这两个集合哪个包含的元素数更多?,集合C=x,y,z,集合D=1,2,3,有限集合的情形,1.3.1 集合的基数,把相当于有限集合的元素数的概念推广到一般集合，称之为集合的基数(势，浓度)。集合A的基数记为|A|。,定义1.3.6 设A，B为集合，若A与B之间存在1-1映射，则称A与B基数相同，也称A与B对等（等势，等浓），记为|A|=|B|, 或者AB。 例.正整数集合Z+与正偶数集合B对等， Z+到B的一个1-1映射为(n)=2n。 例. 区间集合A=(0, 1)与B=(0, +)等浓， A到B的一个1-1映射为(x

12、)=tan(x/2),显然，集合A为有限集当且仅当它以某一非负整数为其基数，即存在一非负整数n使得A=n。即集合A的元素个数是n。 把自然数集合的基数记为0（读作阿列夫零），于是凡是与自然数集合对等的集合A，其基数|A|=0,集合的对等关系是一个等价关系。 可以用对等关系重新来刻画什么是集合的基数：集合按照对等关系分成等价类，每个等价类的共同的数量特征，称为该等价类中集合的基数。,定义1.3.7,设A，B是任意两个集合。 (1)称A的基数小于等于B的基数，记为A B，如果有A到B单射或有B到A满射。 (2)称A的基数小于B的基数，记为AB，如果AB且AB。 换句话说，若A与B的某一子集有1-1

13、对应关系，则AB；若A与B的某一子集有1-1对应关系，且A与B不存在1-1对应关系，则AB。 集合基数的关系是部分序关系。,定理1.3.1(Bernstein定理-集合基数的关系具有反对称性) 若存在A的子集A和B的子集B，使得|A|=|B|且|B|=|A|，则|A|=|B|。即若|A|B|且|B|A|，则|A|=|B|。 证明用到基数的三歧性定理 基数的三歧性定理 对任意集合A，B，或者|A|B|，或者|A|B|，或者|B|A|，且不能有两个式子同时成立。,1.3.2 可数集合,定义1.3.8 一个集合，如果它的元素为有限个，或者它与自然数集合之间存在一个1-1映射，则称此集合为可数集合。否

14、则称该集合为不可数集合。元素个数不是有限的可数集合称为可数无穷集合。,结论 A为可数无穷集合，当且仅当 A可排列为A=a1, a2, , an, (可以把它的元素编号) 证明： （必要性）若A为可数无穷集，则A与自然数集合N之间可以建立1-1映射 ，由得到A中与n对应的元素，记为an+1,也就是说可以把A写成A =a1, a2, , an, 的形式。 （充分性）若A可排列为A =a1, a2, , an, ，则an与n-1对应，于是可得到A与自然数集N之间的1-1映射： ann-1。故A为可数无穷集合。,例：,正整数的平方数集合是可数无穷集。 证法一：可排列：B=1, 4, 9, 16, 。

15、证法二：可建立NB的映射 ： (x)=(x1)2 整数的集合Z是可数无穷集。 证法一：可排列：Z=0,1,-1,2,-2,3,-3, 证法二：可建立NZ的映射 ：,例：有理数集合Q是可数集合. 证法一：任意非零有理数均可以表示成确定的既约分数（即m/n的形式，其中m,n互质） 按如下方法排列： step 排 Step 2 对Q 中正分数p=m/n， 若m+n在未排过的数中最小，且和相同者中m最小，则排p。（按它的分子与分母的和数由小到大排列，和数相同，则分子小的先排） Step 3 排-p（对负分数，把它紧排在相应的正分数之后）。转Step 2 。 显然，任意有理数总会排入此序列中。 则Q可排

16、成0，1/1，-1/1，1/2,-1/2,2/1,-2/1,1/3, -1/3,3/1,-3/1,1/4,-1/4,2/3,-2/3,3/2,-3/2,4/1,-4/1,，因此， Q是可数集合。,定理1.3.2可数集合的子集仍为可数集合。 证明：如果此可数集合是有限集合，则它的子集也有限，当然可数。 如果此可数集合是无穷集合，则此集合的元素可写成a1, a2, , an, 的形式。它的子集可以这样得到：从左向右，第一个是子集中元素的记为ai1，第二个是子集中元素的记为ai2, ，于是，此子集的元素可排列为： ai1, ai2, , ain, 。 所以，此子集是可数集合。,定理1.3.3 设A，

17、B是可数集合， AB= ，则AB是可数集合。 证明：因为A，B是可数集合，所以可设A=a1,a2,an,，B= b1,b2,bn,。 于是AB可以写成a1,b1,a2,b2,an,bn,(A中元素与B中元素交替出现)，且由AB = 知，其中没有重复元。 因此AB是可数集合。,例.整数的集合Z是可数无穷集。 证法三：因自然数集0，1，2，3，是可数集， -1，-2，-3，亦是可数集，因此，这两个互不相交的可数集合的并集，即整数集，仍是可数集。,定理1.3.4,设A1,A2,An, 是可数无穷多个可数集合的序列，则 是可数集合。即可数无穷多个可数集合的并集是可数集合。,证明：,不失一般性，设A1,

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

19、 a23, a24, , a2n, A3=a31, a32, a33, a34, , a3n, A4=a41, a42, a43, a44, , a4n, .,定理1.3.5,设A，B是可数无穷集合，则AB是可数集合。 证明：设A= a1, a2, , an, ，B= b1, b2, , bn, 。于是AB=(ai，bj)| aiA， bjB，我们将AB的元素作如下排列：,(a1, b1), (a1, b2), (a1, b3), , (a1, bn), (a2, b1), (a2, b2), (a2, b3) , (a2, bn), (a3, b1), (a3, b2), (a3, b3),

20、 , (a3, bn), (an, b1), (an, b2), (an, b3), , (an, bn), 对上述元素按足标同定理1.3.4的证明方式进行处理排序，得AB是可数集合。,例：有理数集合是可数集合 证法二：任意有理数都可以表示成p/q形式，其中pZ(整数集合)，qZ +(正整数集合)。 集合ZZ+ =(p, q)| pZ, qZ+是可数集合， 取其一个子集 S=(0,1)(p,q)|(p,q)ZZ+,且p/q是既约分数, 显然， S是可数集合。 有理数集合可以与S建立1-1映射: 0(0,1),既约分数p/q (p, q)， 故有理数集合是可数集合。,定理,若A1, A2, ,A

21、n是可数集合，则A1 A2 An是可数集合。 用归纳法证明。 证明：当n=1时，显然成立，n=2时，也成立。 假设n=k时， 结论成立，即A1 A2 Ak是可数集合。,当n=k+1时，有(A1 A2 Ak) Ak+1 =(a1,a2,ak),ak+1)|ai Ai, for i=1,2,k+1， 由假设知A1 A2 Ak是可数集合，而Ak+1也是可数集合，所以(A1 A2 Ak) Ak+1是可数集合。 A1 A2 Ak Ak+1 =(a1,a2,ak,ak+1)|ai A i,for i=1,2,k+1，显然可以与(A1 A2 Ak) Ak+1建立1-1映射。因此A1 A2 Ak Ak+1也是

22、可数集合。 故A1 A2 An是可数集合。,小结：判断可数集合,方法一. 按照可数集合的定义， 若A为有限集，则A一定是可数集合，否则若A与自然数集之间存在一个1-1映射，则A为可数集合。 方法二. 若A与某可数集合之间存在1-1映射，则A为可数集合 方法三. 若A中所有元素可按某种规律进行排序，则A是可数集合。,判断可数集合,方法四. 若A是n( 1)个可数集合的并集，则A是可数集合。 方法五. 若A是某个已知是可数集合的子集，则A是可数集合。 方法六. 若A是可数无穷多个可数集合的并集，则A是可数集合。 方法七. 若A是n( 1)个可数集合的笛卡儿乘积，则A是可数集合。,1.3.3 不可数

23、集合,1872年Contor考虑实数集与自然数集是否有1-1对应，1873年得出否定结论,定理1.3.6 全体实数做成的集合是不可数集合。 证明：由定理1.3.2(的逆否命题)知，只要证明(0,1)区间内的实数不可数就可以了。 若不然，我们可以把(0,1)区间内的数排成一个序列： 0.a11a12a13 0.a21a22a23 0.a31a32a33 ,(2),我们考虑下面的数： 0.r1r2rk () 其中 显然，(3)是(0,1)区间内的数，但它却不是序列(2)中的任一个数。事实上，对(2)中任一个数0.ak1ak2akk，因为rkakk，故 0.ak1ak2akk0.r1r2rk 与假设

24、矛盾。故(0,1)区间内的实数不可数，所以整个实数集不可数。,推 论,实数集合R，区间(a,+)、a,b、a,b)、(a,b，其中ab，都是不可数的，且与区间(0,1)等浓。 仅看构造区间0,1与(0,1)之间1-1映射的一个例子。我们知道全体有理数的集合是可数的，于是(0,1)区间中的有理数是可数的，不妨将它们排成a1, a2, , an, 的形式。,而闭区间0,1比区间(0,1)多两个数0和1，它们是有理数，于是可建立闭区间0, 1中的有理数到区间(0,1)中的有理数的1-1映射1： 0， 1， a1， a2，an， a1，a2，a3， a4，, an+2, 令区间0,1中的无理数到区间(

25、0,1)中的无理数的1-1映射2为自己对应自己。则映射= 12为区间0, 1到区间(0,1)的1-1映射。从而区间0,1与(0,1)等浓。,我们把(0,1)区间内的实数集合的基数记为c，也记为1。即c= 1。,定理1.3.7,设A1, A2, ,An, 是互不相交的集合序列，它们的基数都是c，则 的基 数也是c。即可数(无穷多)个基数为c的集合的并集基数仍为c。 注: c是实数集合的基数。,(0, 1,(1, 2,(2, 3,(n-1, n, , ,A1,A2,A3,An, , ,(0, +),1,2,3,n,证明：,设In=(n-1, n，则当mn时，ImIn =。因为In (n=1, 2, )的基数是c，故存在1-1映射1