The GATE Grind

GATE 2023 CS – Question 49

Engineering Mathematics · Discrete Mathematics: Sets, Relations, Functions, Partial Orders and Lattices · 2 marks · Multiple select

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?

  1. F is NOT well-defined.
  2. F is an onto (or surjective) function.
  3. F is a one-to-one (or injective) function.
  4. F is a bijective function.

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 is well-defined because f is constant on each class. It is onto because f is onto, and one-to-one because F([x])=F([y]) implies f(x)=f(y), i.e. [x]=[y]. Hence F is bijective.