GATE 2023 CS – Question 49
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?
Practise this question in The GATE Grind →
Show answer and explanation
Correct answer: (B) F is an onto (or surjective) function.; (C) F is a one-to-one (or injective) function.; (D) F is a bijective function.
Explanation
$F:E\to B$ is defined by $F([x])=f(x)$.
- **Well-defined:** if $[x]=[y]$ then $f(x)=f(y)$ by the definition of $\sim$, so the value does not depend on the representative. (A) is false.
- **Onto:** $f$ is onto, so every $b\in B$ equals $f(x)=F([x])$ for some $x$. (B) is true.
- **One-to-one:** $F([x])=F([y])\Rightarrow f(x)=f(y)\Rightarrow x\sim y\Rightarrow[x]=[y]$. (C) is true.
- **Bijective:** onto + one-to-one. (D) is true.
Answer: B, C, D.
More Discrete Mathematics: Sets, Relations, Functions, Partial Orders and Lattices questions
- GATE 2021 CS (CS1) Q53
- GATE 2020 CS Q27
- GATE 2019 CS Q31
- GATE 2019 CS Q64
- GATE 2018 CS Q37
- GATE 2015 CS (CS1) Q11
All Discrete Mathematics: Sets, Relations, Functions, Partial Orders and Lattices questions →