GATE CSE 2023 | Question: 39

Question

Let $f: A \rightarrow 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} \text { if } f\left(a_{1}\right)=f\left(a_{2}\right),
\]
where $a_{1}, a_{2} \in A$. Let $\mathcal{E}=\{[x]: x \in A\}$ be the set of all the equivalence classes under $\sim$. Define a new mapping $F: \mathcal{E} \rightarrow B$ as
\[
F([x])=f(x), \quad \text { for all the equivalence classes }[x] \text { in } \mathcal{E} \text {. }
\]
Which of the following statements is/are $\text{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.

Comments

Must read : https://en.wikipedia.org/wiki/Surjective_function#:~:text=Let%20A/~%20be,o%20P(~).

---

@legend_of_cse i have named u "The wikipedia guy"😂

---

Sanjog karan believe .. more than 50% concept directly asked from standard wikipedia concept  eapecially in Discrete math ..

Answer 1

A given onto function f : A $\rightarrow$ B, where |A| $\neq$ 0 and |B| $\neq$ 0

An equivalence relation $\sim$ is defined on set A as : 

$a_{1} \sim a_{2}$ if $f(a_{1}) = f(a_{2})$, where $a_{1}$, $a_{2}$ $\in$ A.

 

Let's try to understand this question by using an example.

Let, A = {1, 2, 3, 4, - - - - - - , 18, 19, 20} & B = {0, 1, 2, 3} 

And, $\sim$ be Division Modulo 4.

 

---

NOTE : Division Modulo 4 is an Equivalence Relation.

---

 

If we try to observe Division Modulo 4 with respect to set A then, we will get such type of function mapping : 

 

 

From above mapping :

 

$[1]_{R}$ = {1, 5, 9, 13, 17} = $[5]_{R} = [9]_{R} = [13]_{R} = [17]_{R}$

 

$[2]_{R}$ = {2, 6, 10, 14, 18} = $[6]_{R} = [10]_{R} = [14]_{R} = [18]_{R}$

 

$[3]_{R}$ = {3, 7, 11, 15, 19} = $[7]_{R} = [11]_{R} = [15]_{R} = [19]_{R}$

 

$[4]_{R}$ = {4, 8, 12, 16, 20} = $[5]_{R} = [9]_{R} = [13]_{R} = [17]_{R}$

 

 

---

IMPORTANT CONCLUSION : Here, f is mapping elements from A to the remainders that we will get 

when divided by 4. 

Inshort we can say elements are mapped to their remainders.

---

 

Now, $\varepsilon$ be the set of all Equivalence class under $\sim$. So, 

$\varepsilon$ = { {1, 5, 9, 13, 17}, {2, 6, 10, 14, 18}, {3, 7, 11, 15, 19}, {4, 8, 12, 16, 20} }.

A new mapping F  : $\varepsilon$ $\rightarrow$ B is defined as : 

F([x]) = f(x), for all equivalence classes [x] in $\varepsilon$.

 

---

 

Let's try to observe the mapping of F, we will get this type of function mapping : 

 

---

IMPORTANT COLNCLUSION : Here, Set of all equivalence class are mapped to their

remainders in B.

---

 

Let's try to observe the options one by one.

Option A : F is  NOT well-defined.   

This is completely FALSE statement. F is well-defined.

 

Option B : F is an onto (or surjective) function.

This is TRUE statement as all elemets of B are covered. So, F is onto function.

 

Option C : F is a one-to-one (or injective) function.

This is TRUE statement as we can see every element in $\varepsilon$ is mapped to only one element in B.

So, F is one-to-one function.

 

Option D : F is a bijective function.

This is TRUE statement a F is both one-to-one & onto. Hence F is an Bijective Function.

 

---

 

Correct Answer : B, C, D.

Comments

best approach on how to think this questions...thanks

---

superb bhai

Answer 2

Here, equivalence relation $\sim$ on the set $A$ is defined as:
$$a_1 \sim a_2 \ \ if \ \ f(a_1)=f(a_2) $$

where $a_1,a_2 \in A$

So, consider $a_i,b_i,c_i,..\in A$ and $\alpha,\beta,\gamma,...\in B$ and the mapping as:

$a_1 \mapsto \alpha$, $a_2 \mapsto \alpha $,  $a_3 \mapsto \alpha,...$, $a_m \mapsto \alpha$

Similarly,

$b_1 \mapsto \beta$, $b_2 \mapsto \beta$,  $ \ b_3 \mapsto \beta,$$...$$,b_n \mapsto \beta$

$c_1 \mapsto \gamma$, $c_2 \mapsto \gamma$,  $\ c_3 \mapsto \gamma,$$...$$,c_p \mapsto \gamma$

and so on for the non-empty sets $A$ and $B$ and it is given that $f: A \rightarrow B$ is an onto function.

According to the definition of Equivalence relation, Equivalence class is:

$[a_1]=[a_2]=[a_3]=...=[a_m]$

$[b_1]=[b_2]=[b_3]=...=[b_n]$

$[c_1]=[c_2]=[c_3]=...=[c_p]$

and so on.

Now, set of equivalence classes under relation $\sim$ is defined as:

$\mathcal{E}= \{[a_1],[b_1],[c_1],...\}$

Now, given the new mapping $F: \mathcal{E} \rightarrow B$ as:

$F([x]) = f(x)$ for all $[x] \in \mathcal{E}$

It means mapping would be:

$a_1 \mapsto \alpha$

$b_1 \mapsto \beta$

$c_1 \mapsto \gamma$

and so on.

Since, all distinct $a_1,b_1,c_1,...$ maps to different elements of set $B$ and so, $F$ is an injective function. Here, we have taken $a_1,b_1,c_1,...$ as a leader for their own equivalence classes, you can take $a_2,b_2,c_2,... $ so on.

It is cleared from the mapping of $F$ that all the elements of set $B$ are covered,so, $F$ is surjective function because each element from their own equivalence class maps to according to the mapping of $f.$ We have taken one element from the group of $a's$ and maps to $\alpha$ and similarly for other groups of $b's, c's$ and so on.

Since, $F$ is both injective and surjective and hene $F$ is bijective function.

Here, we say, function $F$ well-defined or single-valued when:

$1)$ $F \subseteq [x] \times f(x)$

$2)$ The domain of $F$ is $[x]$

$3)$ if $([x],y), ([x],z)$ then $y=z$

Since from the mapping of $F$, it is cleared all the above three conditions are true because we have taken one element from the group of $a's,b's,c's,...$ and maps to $\alpha, \beta,\gamma,...$ and so, $f$ is well-defined function.

$\textbf{Therefore, (B),(C),(D)}$

Comments

sir where I am doing wrong in this question?

---

@Aditya_Singh 7 You need to equivalance class of [e] and [f] , they both map to 3 & 4 respectively. Why you are leaving e and f ? 
It not mean that equivalance class must be contain more than 1 element. An equivalance class may also contain single element only. 
For best visualization , consider the example on the function which combines all the reminders of 4 . It is bijection only.

---

yes I got it bro, thanks for rectifying me.

Answer 3

I found this is the easiest method.

Comments

You forgot (4,4) in ~, so 1 index will be [4] which maps to b

Also in F, co domain is B means b should also be there

---

yes u are questionis correct

solution fr this

 

Answer 4

It is given that $f$ is function defined from domain $A$ to co-domain $B$, $f:A \rightarrow B$, and $f$ is surjective, in other and simple words, $\text{“every element of $B$ has pre-image or is mapped by some element(s) in $A$”}$. Mathematically this can be defined as $$\displaystyle \mathbf{\forall}_{y \ \in B} \ \mathcal{\exists}_{x \ \in A} \ y = f(x) \tag{1}$$ Since $f$ is function, so no element in $A$ can be left unmapped to some element in $B$.

Let,

$$\begin{align}A &= \{x_1, x_2, \dots, x_a, \dots, x_b, \dots, x_n\} \cr B &= \{y_1, y_2,\dots, y_n\}\end{align}$$

It is given that $\forall _{a_1, a_2 \in A} \ f(a_1) = f(a_2) \Rightarrow a_1R_Ea_2$, where $R_E$ is equivalence relation, so instead of $\sim$ I’m using that notation.  

Now, according to defintion $(1)$, some elements of $A$ (say) $x_1,x_2,x_3$ would map to $y_i \in B$, similarly (say) $x_4, x_5$ would map to $y_j \in B$, hence sets of $x$ values forms a disjoint set while mapping to $y_i$ and $y_j$. So there are $|B|-1$ partitions or $|B|$ parts of $A$ and all of them are disjoint.

Let,

$$\begin{align}A_1 &= \{x_1, \dots, x_a\}; \ \forall _{x_i \in A_1} f(x_i) = y_1 \cr A_2 &= \{x_{a+1}, \dots, x_b\}; \ \forall _{x_i \in A_2} f(x_i) = y_2 \cr & \quad \vdots \cr A_n &= \{x_{m+1}, \dots, x_n\}; \ \forall _{x_i \in A_n} f(x_i) = y_n\end{align}$$

Let, $$\begin{align}& \ \ \ \ \ \forall_{a_1 \in A_1, a_2 \in A_2} \ f(a_1) \neq f(a_2) \Rightarrow a_1R_Ea_2 \cr &\equiv \forall_{a_1 \in A_1, a_2 \in A_2} \ False \Rightarrow a_1R_Ea_2 \cr &\equiv \forall_{a_1 \in A_1, a_2 \in A_2} \ True \cr &\equiv True\end{align}$$Although, whole first order logic expression is $True$ but it doesn't tell us about the truth value of $a_1R_Ea_2$, expression would be $True$ even if $a_1R_Ea_2$ or $a_1\cancel{R_E}a_2$, but we are actually concerned with $a_1R_Ea_2$. So lets’ make $a_1R_Ea_2 \equiv True$, then to make FOL expression $True$, $f(a_1)=f(a_2) \equiv True$. But this can only be $True$ when $a_1, a_2 \in A_i$. Using this we can say that $[a_j] = [a_k]: a_j,a_k \in A_i$, where $[.]$ is equivalence class.

So we get this,
$$\begin{align}\mathcal{Q} &= \{[x]: x \in A_j;  1 \leq j \leq n\}\cr &= \{[x]: x \in A_1 \cup A_2 \cup \dots \cup A_n\} \cr &= \{[x]: x \in A\}\end{align}$$

Now $\mathcal{Q}$ is similar to given set $\mathcal{E} = \{[x]: x \in A\}$ where $\mathcal{E}$ is set of all equivalance classes under $R_E$. New function $F$ has been defined as $F([x]) = f(x)$, and $F: \mathcal{Q} \rightarrow B$.
We can also write $\mathcal{Q}$ as, $$\mathcal{Q} = \{[x \in A_1], [x \in A_2], \dots, [x \in A_n]\} \tag{2}$$ $$\mathcal{Q} = \{\{x_1, x_2, \dots, x_a\}, \{x_{a+1}, \dots, x_b\}, \dots, \{x_{m+1}, \dots, x_n\}\} \tag{3}$$

If we look closely to $F$ then $F$ is taking $q \in \mathcal{Q}$ as an argument and we already know that $\exists_{y \in B}\forall_{x \in q} \ y = f(x)$ where $y$ is unique, hence $F(q)$ is unique. This shows that $\forall_{q_1, q_2 \in \mathcal{Q}} \ q_1 \neq q_2 \Rightarrow F(q_1) \neq F(q_2)$ which is definition of $\textbf{one-one}$ function.

In the beginning of the answer, we found the number of partitions sets or number of equivalence classes as $|B|$, this means $|\mathcal{Q}| = |B|$, here we can observe number of elements in domain is same as number of elements in co-domain and we already found $F$ to be one-one, so from here we can conclude $F$ is $\textbf{onto}$ function too.
 

$F$ is $\textbf{one-one}$ and $\textbf{onto}$, hence $F$ is $\textbf{bijective}$.

Since its MSQ type question,

$\textbf{(B), (C), (D)}$ are correct options.

Comments

@Deepak Poonia Sir, can you please provide your feedback over my answer.

Answer 5

SUMMARY : as an equivalence class has all the elements of set A which has the same image in B therefore each equivalence class will map to a unique and different image therefore epsilon -> B  is one one . also it is mentioned in the question that f is onto means every element in B has a pre image it means that epsilon -> B is also onto   . Therefore it is bijective.

Comments

@Aditya_Singh 7 sure,

Firstly your relation is incomplete , since in the the mapping from A->B , e is mapped to 3 and f to 4 , now since f(e)=f(e) so e will be related to e and same way f will be also related to itself so you also have to include (e,e),(f,f) in your relation.

now coming to the second part , question says function is from SET of all equivalence classes so it can't have duplicate elements , as [a]=[b] choose any one of them , same goes for [c]=[d], you will just have to add [e] and [f] as you have missed them in your relation earlier .

Now you can see f( [a] )=1 , f( [c] )=2, f( [e] )= 3 , f( [f] )=4;

since this function is both one one and onto hence this is bijective .

---

thanks a lot bhai...

---

very well explained

Answer 6

Let’s take a concrete example with small sets to make everything crystal clear.

🎯 Example:

Let  

- A = {1, 2, 3, 4}  

- B = {a, b}

Define a surjective function f : A → B as:

f(1) = a,  f(2) = a,  f(3) = b,  f(4) = b

✅ Step 1: Define Equivalence Relation ∼

We define:   x ∼ y ⇔ f(x) = f(y)

So:  

- 1 ∼ 2 because f(1) = f(2) = a  

- 3 ∼ 4 because f(3) = f(4) = b

Thus, the equivalence classes are:  

[1] = [2] = {1, 2}  

[3] = [4] = {3, 4}

Let $\boldsymbol{\epsilon}$ = { [1], [3] } = { {1,2}, {3,4} }

✅ Step 2: Define Function 

F : $\boldsymbol{\epsilon}$ → B

Define:  

F([x]) = f(x)

Check:  

- F([1]) = f(1) = a  

- F([3]) = f(3) = b

So:  
F({1,2}) = a,  F({3,4}) = b

✅ Step 3: Analyze Properties of F

- Well-defined? ✅ Yes — any x ∈ [1] gives f(x) = a, and x ∈ [3] gives f(x) = b  

- Injective? ✅ Yes — F([1]) = a, F([3]) = b, and they are distinct  

- Surjective? ✅ Yes — all elements of B = {a, b} are covered  

✅ So F is bijective.

🔁 Contrast with f

- f : A → B is surjective but not injective (e.g., f(1) = f(2) = a)  

- F : $\boldsymbol{\epsilon}$ → B fixes this by grouping equal outputs into equivalence classes, making it injective and hence bijective

✅ Final Summary

- f : A → B — surjective, not injective  

- Equivalence classes under ∼ — partition A into sets with same f-values  

- F([x]) = f(x) — becomes bijective from $\boldsymbol{\epsilon}$ → B