Let X and Y be finite sets and f : X -> Y be a function. Which one of the following statements is TRUE? A. For any subsets A and B of X, |f(A U B)| = |f(A)| + |f(B)| B. For any subsets A and B of X, f(A intersect B) = f(A) intersect f(B) C. For any subsets A and B of X, |f(A intersect B)| = min{|f(A)|, |f(B)|} D. For any subsets S and T of Y, f^(-1)(S intersect T) = f^(-1)(S) intersect f^(-1)(T)
GATE 2014 · Discrete Mathematics · Functions · medium
Answer: D. For any subsets S and T of Y, f^(-1)(S intersect T) = f^(-1)(S) intersect f^(-1)(T)
- Break the forward-image options: Let f(1) = f(2) = a with A = {1}, B = {2}. Then A intersect B = empty so f(A intersect B) = empty, but f(A) intersect f(B) = {a}. This kills B and C, and a similar overlap makes |f(A U B)| < |f(A)| + |f(B)|, killing A.
- Prove the preimage identity (D): x in f^(-1)(S intersect T) <=> f(x) in S intersect T <=> f(x) in S and f(x) in T <=> x in f^(-1)(S) and x in f^(-1)(T). So the two sides are equal for every f.
- Select the true statement: Only D holds for all functions, so the answer is option D.