Suppose f is a function from a set A to its power set P(A). Colour an element x
ID: 1889309 • Letter: S
Question
Suppose f is a function from a set A to its power set P(A). Colour an element x of A blue if x is in f(x). Colour all the other elements red. Let R be the subset of A made up of red elements only.(a) For the set A = {1,2,3} list the elements of P(A).
(b) Suppose f(1) = {1,2}, f(2) = {1}, and f(3) = {1,2,3}. In this example, what are the elements of R?
(c) (in general, not in the example of parts a and b): Prove that there is no element x is in A with f(x) = R.
Please explain your reasoning for each one.
Explanation / Answer
(a) Recall that the power set of A is the set of all subsets of A. Since A contains three elements, P(A) contains 23 = 8 elements, and they are
, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, and {1, 2, 3}.
(b) Since f(1) = {1, 2} and 1 {1, 2} = f(1), 1 is a blue element. Similarly, 3 is a blue element, because 3 {1, 2, 3} = f(3). However, 2 is not blue since f(2) = {1} and 2 {1}. Therefore 2 is the only red element of A = {1, 2, 3} and thus the only element of R.
(c) Suppose f: A P(A). Color an element x A blue if x f(x). Color all other elements red. Let R be the subset of A made up of red elements only. We wish to show that there is no element x A with f(x) = R. Assuming the contrary, suppose there is an element x0 A such that f(x0) = R. Then either x0 R or x0 R.
Case 1: x0 R. Then x0 is a red element. Furthermore, since x0 R = f(x0), we have that x0 is a blue element, which is impossible.
Case 2: x0 R. Then x0 is not a red element. Yet x0 is not a blue element because f(x0) = R does not contain x0. Thus x0 must be a red element, which is also impossible.
Both cases lead to a contradiction. Hence, there is no element x A with f(x) = R, as required.
Hope that helps!