GATE CS 2014 Set 3 Q.12 (CS Q.2): Sets, Relations, Functions, Partial Orders and Lattices

Let $X$ and $Y$ be finite sets and $f: X \to Y$ be a function. Which one of the following statements is TRUE?

For any subsets $A$ and $B$ of $X$ , $|f(A \cup B)| = |f(A)| + |f(B)|$

For any subsets $A$ and $B$ of $X$ , $f(A \cap B) = f(A) \cap f(B)$

For any subsets $A$ and $B$ of $X$ , $|f(A \cap B)| = \min \{|f(A)|, |f(B)|\}$

For any subsets $S$ and $T$ of $Y$ , $f^{-1}(S \cap T) = f^{-1}(S) \cap f^{-1}(T)$

Official answer and solution

Solution

Evaluate standard set-theoretic identities for images and inverse images under functions.

Analyze inverse images (Option D):
For any function $f: X \to Y$ and any subsets $S, T \subseteq Y$ :
$\begin{aligned} x \in f^{-1}(S \cap T) & \iff f(x) \in (S \cap T) \\ & \iff f(x) \in S \text{ and } f(x) \in T \\ & \iff x \in f^{-1}(S) \text{ and } x \in f^{-1}(T) \\ & \iff x \in f^{-1}(S) \cap f^{-1}(T). \end{aligned}$
Therefore, the inverse image distributes over intersection for EVERY function. Option D is universally TRUE.
Examine counterexamples for other options:
- Option A: Fails when $f(A)$ and $f(B)$ overlap; e.g., if $A = \{1\}, B = \{2\}$ with $f(1) = f(2) = y$ , then $|f(A \cup B)| = 1 \ne 1 + 1 = 2$ .
- Option B: Generally, $f(A \cap B) \subseteq f(A) \cap f(B)$ , but equality requires $f$ to be injective. If $A = \{1\}, B = \{2\}$ with $f(1) = f(2) = y$ , then $A \cap B = \emptyset \implies f(A \cap B) = \emptyset$ , whereas $f(A) \cap f(B) = \{y\}$ .
- Option C: Using the same counterexample, $|f(A \cap B)| = 0$ , while $\min(|f(A)|, |f(B)|) = 1$ .

Hence, only option D is TRUE.

Final answer

Common trap

Assuming direct images preserve intersections (option B), which holds only for injective (one-to-one) functions.

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.