GATE 2023 CS Q.49: solution and answer

GATE 2023 · CSQ.49 · 2 marks · MSQ

Let $f : A \to B$ be an onto (or surjective) function, where $A$ and $B$ are nonempty sets. Define an equivalence relation $\sim$ on the set $A$ as

a_{1} \sim a_{2} if f (a_{1}) = f (a_{2}),

where $a_{1}, a_{2} \in A$ . Let $E = {[x] : x \in A}$ be the set of all the equivalence classes under $\sim$ . Define a new mapping $F : E \to B$ as

F ([x]) = f (x), for all the equivalence classes [x] in E .

Which of the following statements is/are TRUE?

(A)
$F$ is NOT well-defined.
(B)
$F$ is an onto (or surjective) function.
(C)
$F$ is a one-to-one (or injective) function.
(D)
$F$ is a bijective function.

See the question in the paper

Tap to open full size

Answer and solution

ANSWER

(B), (C) and (D) are true; (A) is false.

Official answer: B, C, DSource: Official answer key, GATE 2023 CS (IIT Kanpur)

Well-defined. $F$ is defined on a class $[x]$ through one chosen representative $x$ . If $[x] = [y]$ , then $x \sim y$ , so $f (x) = f (y)$ by the definition of $\sim$ . The value $F ([x]) = f (x)$ therefore does not depend on the representative, so $F$ is well-defined. Option (A) is false.
Onto. Take any $b \in B$ . Since $f$ is onto, there is $a \in A$ with $f (a) = b$ . Then $F ([a]) = f (a) = b$ , so every element of $B$ has a preimage under $F$ . Option (B) is true.
One-to-one. Suppose $F ([x]) = F ([y])$ . Then $f (x) = f (y)$ , which by the definition of $\sim$ means $x \sim y$ , so $[x] = [y]$ . Hence $F$ is injective. Option (C) is true.
Bijective. A bijective function is both onto and one-to-one. Steps 2 and 3 show both, so $F$ is bijective. Option (D) is true.
Conclusion. The true statements are (B), (C) and (D). In other words, the classes of $\sim$ correspond one-to-one with the elements of $B$ : $A / \sim ≅ B$ whenever $f$ is onto.

KEY IDEA

Grouping the elements of $A$ that $f$ sends to the same value gives a map from classes to $B$ that is well-defined by the definition of $\sim$ . The map is injective because equal values force equal classes, and onto because $f$ is onto. So it is bijective.

WATCH OUT FOR

Picking only (B) and (C), or forgetting that (D) follows from them. Another slip is doubting well-definedness: the check is that the value does not depend on which representative of the class is used, and here that holds by the definition of $\sim$ .

From the GATE 2023 CS paper. Every question of this paper · Download the full paper · All 8 Sets & relations questions, with notes

GATE 2023 CS Q.49: solution and answer

Answer and solution

More Sets & relations questions