Let \(X\) ܺand \(Y\) be finite sets and ݂:ܺ \(f: X \to Y\) be a function.…
2014
Let \(X\) ܺand \(Y\) be finite sets and ݂:ܺ \(f: X \to Y\) be a function. Which one of the following statements is TRUE?
- A.
For any subsets
\(A\)and\(B\)of\(X, |f(A \cup B)| = |f(A)| + |f(B)|\) - B.
For any subsets
\(A\)and\(B\)of\(X, f(A \cap B) = f(A) \cap f(B)\) - C.
For any subsets
\(A\)and\(B\)of\(X, |f(A \cap B)| = \min \{|f(A)|, |f(B)|\}\) - D.
For any subsets
\(S\)and\(T\)of\(Y, f^{-1}(S \cap T) = f^{-1}(S) \cap f^{-1}(T)\)
Attempted by 136 students.
Show answer & explanation
Correct answer: D
Correct statement: f^{-1}(S ∩ T) = f^{-1}(S) ∩ f^{-1}(T).
Proof (two inclusions):
If x ∈ f^{-1}(S ∩ T), then f(x) ∈ S ∩ T, so f(x) ∈ S and f(x) ∈ T. Hence x ∈ f^{-1}(S) and x ∈ f^{-1}(T), therefore x ∈ f^{-1}(S) ∩ f^{-1}(T).
If x ∈ f^{-1}(S) ∩ f^{-1}(T), then f(x) ∈ S and f(x) ∈ T, so f(x) ∈ S ∩ T. Thus x ∈ f^{-1}(S ∩ T).
Conclusion: f^{-1}(S ∩ T) = f^{-1}(S) ∩ f^{-1}(T).
Why the other statements fail:
|f(A ∪ B)| = |f(A)| + |f(B)| is false because f(A) and f(B) can overlap. Example: X = {1,2}, Y = {a}, f(1)=a, f(2)=a, A={1}, B={2}. Then |f(A ∪ B)| = 1 but |f(A)| + |f(B)| = 2.
f(A ∩ B) = f(A) ∩ f(B) need not hold; only f(A ∩ B) ⊆ f(A) ∩ f(B) always holds. Example: X = {1,2}, Y = {a}, f(1)=a, f(2)=a, A={1}, B={2}. Then f(A ∩ B) = ∅ while f(A) ∩ f(B) = {a}.
|f(A ∩ B)| = min{|f(A)|, |f(B)|} is false; at best |f(A ∩ B)| ≤ min{|f(A)|, |f(B)|}. Example: X = {1,2}, Y = {a,b}, f(1)=a, f(2)=b, A={1}, B={2}. Then |f(A ∩ B)| = 0 but min{|f(A)|,|f(B)|} = 1.
A video solution is available for this question — log in and enroll to watch it.