solnpdf1

MATH 4181 001 Fall 1999 Problem Set 1 Solutions 1. (Exercise 2, page 11) Prove that if Ahas precisely ndistinct elements and Bhas preciselymdistinct elements, where mandnare positive integers, then ABhas preciselymndistinct elements. We can prove this by appealing to a counting argument and showing that the product set is in one-to-one correspondence with an mnmatrix, which we know has mn elements. 2. (Exercise 3, page 11) LetAandBbe sets, both of which have at least two distinct members. Prove that there is a subset WABthat is not the product of a subset ofAwith a subset of B. LetA=B=fa;bg. ThenABconsists of 4 elements: f(a;a);(a;b);(b;a);(b;b)g. The subsetf(a;a);(b;b)gis not the product of a subset of Aand a subset of B, because the subset of Awould have to contain both aandb, as would the subset of B. Then, the product of those two subsets would be all of AB. 3. (Exercise 1, page 14) Letf:A!Bbe given. Prove the following: (a)For each subset XA,Xf1(f(X)). Leta2X. Thenf(a)2f(X) by denition. Thus, a2fx2Xjf(x)2f(X)g. This is just the set f1(f(X)). Thus,Xf1(f(X)). (b)For each subset YB,f(f1(Y))Y. Lety2f(f1(Y)). Thus, there is an element x2Xso thaty=f(x). What is more,x2f1(Y), which means that f(x)2Y. Thus,y2Yandf(f1(Y))Y. (c)Iffis injective, then for each subset XA, f1(f(X)) =X: We have shown that Xf1(f(X)), so it only remains to show that f1(f(X)) X. Lety2f(X). Then there is an x2Xso thatf(x) =y. Leta2f1(f(x)), i.e.,f(a) =f(x) =y. Sincefis one-to-one a=x2X. Thus, any element of f1(f(X)) is inXand hencef1(f(X))X. It then follows that f1(f(X)) = X. (d)Iffis surjective, then for each subset YB, f(f1(Y)) =Y: Again, we only need to show that Yf(f1(Y)). Lety2Y. We need to nd an element x2Aso thaty=f(x). What is more, we would like to show that thisxactually belongs to f1(Y). Sincefis surjective, there is an element x2A so thaty=f(x), by the denition of surjectivity. Also, by denition of the set, x2f1(Y) sincef(x) =y2Y. Thus,y2f(f1(Y)) and we are done. MATH 4181 Problem Set 1 Solutions 2 4. (Exercise 4, page 14) Letf:A!Bbe given. (c)IfYis a subset of Bthenf1(BnY) =An(f1(Y)). We have to show the two set containments: f1(BnY)An(f1(Y)) and An(f1(Y))f1(BnY). Letx2f1(BnY). Thenf(x)2BnYorf(x)62Y. This means that x62f1(Y) orx2An(f1(Y)). Thus,f1(BnY)An(f1(Y)). Letx2An(f1(Y)). Thus,x62f1(Y) andf(x)62Y. Thus,f(x)2Bnf(Y), makingx2f1(BnY). Thus,f1(BnY)An(f1(Y)) and we are done. (d)IfXAandYB, then f(X\f1(Y)) =f(X)\Y: Again, we have two set containments to show. Letv2f(X\f1(Y)). Then we know that v=f(u) whereu2X\f1(Y). Thus,u2Xandu2f1(Y). It then easily follows that f(u)2f(X) and f(u)2Y. Thus,v=f(u)2f(X)\Y. Therefore f(X\f1(Y))f(X)\Y. Now, letv2f(X)\Y. Thenv2Yandv2f(X). Thus, there is a u2Xso thatf(u) =v. Now,f(u)2Y, which places u2f1(Y). Thus,u2X\f1(Y) and this places v2f(X\f1(Y)) andf(X)\Yf(X\f1(Y)). Thus the two sets are equal. 5. (Exercise 7, page 15) LetXbe a set and A;B;CX. The function A:X!f0;1g dened by A(x) =( 1 ifx2A 0 ifx62A is called the characteristic function of A. Show (a)A\B=A
B,whereA
B(x) =A(x)B(x). Ifx2A\Bthenx2Aandx2B. Thus,A\B(x) = 1,A(x) = 1 and B(x) = 1. In this case, A\B=A
B. Ifx62A\B, then there are three cases: (1) x2Aandx62B; (2)x62Aand x2B; and (3)x62Aandx62B. The proof for cases (1) and (2) are similar. (1) Ifx2Aandx62B, thenA(x) = 1 andB(x) = 0 andA\B(x) = 0. Thus, in this case A\B=A
B. (3) Ifx62Aandx62B, thenA(x) = 0 andB(x) = 0 andA\B(x) = 0. Thus, in this case A\B=A
B. Therefore,A\B=A
B. (b)A[B=A+BA\Band nd a similar expression for A[B[C. Ifx2A[B, thenx2A,x2B, orxlies in both. Assume that x2Aand x62B. ThenA[B(x) = 1 andA(x) = 1,B(x) = 0, and A\B(x) = 0. Thus, c David Royster Introduction to Topology For Classroom Use Only MATH 4181 Problem Set 1 Solutions 3 in this case A[B=A+BA\B. Ifx2Bandx62A, then we have a similar computation. If x2Aandx2B, thenA(x) =B(x) =A\B(x) = A[B(x) = 1. Then, A[B(x) =A(x) +B(x)A\B(x) = 1 + 11. Therefore A[B=A+BA\B. What we do in this case is we see how many times each point is counted. The points inA\Bare counted twice, once in Aand once in B. Thus, for A[B[C the points in A\B,A\CandB\Care counted twice. When we pull them out though, we pull out the points in A\B\Cthree times { one for each of the intersections. Thus, A[B[C=A+B+CA\BA\CB\C+A\B\C: 6.Prove that;B=;for each set B. Assume not, that is assume that there is a point in ;B. Then this point is an ordered pair (x;y) wherex2;andy2B. However, the empty set contains no elements, thus x62;. Thus, there is no point in ;B. Thus,;B=;. 7.Give an example to show that f(A\B)may not equal f(A)\f(B). Show that equality holds iffis injective. Letf:R!Rbyf(x) =x2. LetA= [2;1] andB= [1;2]. Then,f(A) = [0;4] andf(B) = [0;4] andf(A)\f(B) = [0;4]. Now,A\B= [1;1] andf(A\B) = [0;1]. Thus, in this case, f(A\B)6=f(A)\f(B). Clearly, we have that f(A\B)f(A)\f(B) since it is contained in each. If fis injective, we need to show the opposite inclusion. Let x2f(A)\f(B). Then there is ana2Aandb2Bso thatf(a) =xandf(b) =x. Thus,f(a) =f(b). Since fis injective, this implies that a=b. Hence,a2A\Bandx2f(A\B). Thus, f(A)\f(B)f(A\B) and we have that f(A)\f(B) =f(A\B). c David Royster Introduction to Topology For Classroom Use Only