3. (10 pts.) Let A be a set with at least two elements, and let a...

Transcribed Image Text:

3. (10 pts.) Let A be a set with at least two elements, and let a and b be two distinct elements of A. Define P, as the set consisting of all the subsets of that contain a, while P, is the set consisting of all subsets of A that contain b. Our goal is to define a bljection from P. to Pu. A candidate for the bljection is f: Pa> P, where f(S) = (S- {a}) U (b}. The function f seems intuitive (all the subsets In Pa contain a so replace a with b), but is f a bijection? (1) (2 pts.) Let A = {a,b,c,d). List all the subsets of that contain a. Then for each one of them, write down its image under f. (ii) (2 pts.) Using your answer from (i), explain why f is not one-to-one and why fis not onto. (Note: you must provide two explanations!) So f is not a bijection. But it turns out that we just have to tweak it to make it into a bijection. Here's a new function based on f: Let g: Pa > P, where S 9(S) = { {g (S if bes 5-{a}) U {b} if by S. That is, g replaces a with b in Sonly when b is not in S; otherwise, g does not modify S at all. 1 (iii) (3 pts.) When A = {a, b, c, d), write down the images of all the subsets of A under g. Explain why the answers imply that g is a bijection. Now let's generalize. That is, for any set A that contains a and b, let's argue why the function g described above is a bijection. (iv) (2 pts.) Suppose Sand Sare two subsets of A that contain a. Argue why if S #S" then g(S)g(S'). Consider three cases: when both subsets contain b, when both subsets do not contain b, and when one contains b but the other doesn't contain b. (v) (1 pt.) Let T be a subset of A that contains b. Define the pre-image of T under g. 3. (10 pts.) Let A be a set with at least two elements, and let a and b be two distinct elements of A. Define P, as the set consisting of all the subsets of that contain a, while P, is the set consisting of all subsets of A that contain b. Our goal is to define a bljection from P. to Pu. A candidate for the bljection is f: Pa> P, where f(S) = (S- {a}) U (b}. The function f seems intuitive (all the subsets In Pa contain a so replace a with b), but is f a bijection? (1) (2 pts.) Let A = {a,b,c,d). List all the subsets of that contain a. Then for each one of them, write down its image under f. (ii) (2 pts.) Using your answer from (i), explain why f is not one-to-one and why fis not onto. (Note: you must provide two explanations!) So f is not a bijection. But it turns out that we just have to tweak it to make it into a bijection. Here's a new function based on f: Let g: Pa > P, where S 9(S) = { {g (S if bes 5-{a}) U {b} if by S. That is, g replaces a with b in Sonly when b is not in S; otherwise, g does not modify S at all. 1 (iii) (3 pts.) When A = {a, b, c, d), write down the images of all the subsets of A under g. Explain why the answers imply that g is a bijection. Now let's generalize. That is, for any set A that contains a and b, let's argue why the function g described above is a bijection. (iv) (2 pts.) Suppose Sand Sare two subsets of A that contain a. Argue why if S #S" then g(S)g(S'). Consider three cases: when both subsets contain b, when both subsets do not contain b, and when one contains b but the other doesn't contain b. (v) (1 pt.) Let T be a subset of A that contains b. Define the pre-image of T under g.