GATE CSE 1996 | Question: 8

Question

Let $F$ be the collection of all functions $f: \{1, 2, 3\} \to \{1, 2, 3\}$. If $f$ and $g \in F$, define an equivalence relation $\sim$ by $f\sim g$ if and only if $f(3) = g(3)$. 

1. Find the number of equivalence classes defined by $\sim$. 
2. Find the number of elements in each equivalence class. 

Comments

can anyone explain this question in easy way.

https://gateoverflow.in/2760/gate-cse-1996-question-8?start=0#a_list_title

---

Detailed Video Solution, with Complete Analysis: Video Solution with Complete Analysis (Click HERE) 

---

Note : "Deepak Sir" answer is one of the best answer for this Question, if u really want to understand everything go and watch ..I bet u will amazed and save ur time.

Answer 1

Total number of functions = $3 * 3 * 3 = 27$ as each of $1, 2$, and 3 has $3$ choice to map to.

Now, for the equivalence relation, we need the mapping of 3 to be fixed. i.e., two functions $f$ and $g$ are related if and only if $f(3) = g(3).$ So, with 3 -> 1, we can get 3 * 3 = 9 functions as 2 and 3 have 3 choices to map to each, and similarly 9 each for 3 -> 2 and 3 -> 3.

a. So, total number of equivalence classes $= 3$, one each for $3$ $->$ $1, 3$ $->$ $2$, and $3 -> 3$.

b. Number of elements (elements here are functions) in each equivalence class $= 9.$

Comments

@harshitraj12, $f(3) = g(3)$ means that two elements in $F$ are related in and only if they map $3$ to same element of co-domain. 

Detailed Video Solution, with Complete Analysis: Video Solution with Complete Analysis (Click HERE) 

---

Thank you sir, This is what I am waiting for!!!

---

@Pranavpurkar right.

There are 9 elements in each equivalence class,each element in a particular equivalence class will have 3 pairs so, $|  [f(3)=1] |$=$|  [f(3)=2] |$=$|  [f(3)=3] |$=$27$.

Total pairs in a Relation will be $81$.

Answer 2

First, read the answer given by Arjun sir and then just see the table for the number of equivalence class and number of elements in each class.

S.no	class1(3->1 fixed)	class2(3->2 fixed)	class3(3->3fixed)
1	{(1,1),(2,2),(3,1)}	{(1,1),(2,2),(3,2)}	{(1,1),(2,2),(3,3)}
2	{(1,1),(2,1),(3,1)}	{(1,1),(2,1),(3,2)}	{(1,1),(2,1),(3,3)}
3	{(1,1),(2,3),(3,1)}	{(1,1),(2,3),(3,2)}	{(1,1),(2,3),(3,3)}
4	{(1,2),(2,2),(3,1)}	{(1,2),(2,2),(3,2)}	{(1,2),(2,2),(3,3)}
5	{(1,2),(2,1),(3,1)}	{(1,2),(2,1),(3,2)}	{(1,2),(2,1),(3,3)}
6	{(1,2),(2,3),(3,1)}	{(1,2),(2,3),(3,2)}	{(1,2),(2,3),(3,3)}
7	{(1,3),(2,2),(3,1)}	{(1,3),(2,2),(3,2)}	{(1,3),(2,2),(3,3)}
8	{(1,3),(2,1),(3,1)}	{(1,3),(2,1),(3,2)}	{(1,3),(2,1),(3,3)}
9	{(1,3),(2,3),(3,1)}	{(1,3),(2,3),(3,2)}	{(1,3),(2,3),(3,3)}

So,we can clearly see that there are exactly 3 distinct equivalence class and no of elements in each equivalence class is 9.

The correct answer for (a) is 3 and for (b) is 9.

Comments

lovely explanation warrior

---

Thanks for this wonderful depiction!

Answer 3

Here given is the set of all the functions {1,2,3}→{1,2,3} => 27 functions

and the equivalence relation R saying that any 2 functions from above set will be related i.e., f R g , if f(3) = g(3).

Now, as a property of equivalence classes of elements, any 2 elements which are related, will fall in the same equivalence class.

So, all those functions which have f(3) = 3 will fall in 1 class, those with f(3) = 2 will fall in second, and f(3) = 1 in third.

Hence the 3 equivalence classes, and size of each is 3^2.

Answer 4

As given in the diagram, each branch represents a function in $F$. e.g. $f1 = \left \{ (3,1), (1,1), (2,1) \right \}$ forms a function.

Now, the the relation $\sim$ will be as follows- 

$\sim \ = \left \{ {\color {Red}{(f_1, f_1), (f_1, f_2), (f_1, f_3), \dots, (f_1, f_9), (f_2, f_1), (f_2, f_2), (f_2, f_3), \dots, (f_2, f_9), (f_3, f_1), (f_3, f_2), (f_3, f_3), \dots, (f_3, f_9), \dots, (f_9, f_1), (f_9, f_2), (f_9, f_3), \dots, (f_9, f_9),}} \\ {\color {Blue}{(f_{10}, f_{10}), (f_{10}, f_{11}), (f_{10}, f_{12}), \dots, (f_{10}, f_{18}), (f_{11}, f_{10}), (f_{11}, f_{11}), (f_{11}, f_{12}), \dots, (f_{11}, f_{18}), (f_{12}, f_{12}), (f_{12}, f_{11}), (f_{12}, f_{12}), \dots, (f_{12}, f_{18}), \dots, (f_{18}, f_{10}), (f_{18}, f_{11}), (f_{18}, f_{12}), \dots, (f_{18}, f_{18}),}} \\ {\color {Green}{(f_{19}, f_{19}), (f_{19}, f_{20}), (f_{19}, f_{21}), \dots, (f_{19}, f_{27}), (f_{20}, f_{19}), (f_{20}, f_{20}), (f_{20}, f_{21}), \dots, (f_{27}, f_{27}), (f_{21}, f_{21}), (f_{21}, f_{20}), (f_{21}, f_{21}), \dots, (f_{21}, f_{27}), \dots, (f_{27}, f_{19}), (f_{27}, f_{20}), (f_{27}, f_{21}), \dots, (f_{27}, f_{27})}} \right \}$

Therefore, there are 3 equivalence classes which are as follows-

• Class 1 - $[f_1] = [f_2] = [f_3] = \dots = [f_9] = \left \{ f_1, f_2, f_3, \dots, f_9 \right \}$
• Class 2 - $[f_{10}] = [f_{11}] = [f_{12}] = \dots = [f_{18}] = \left \{ f_{10}, f_{11}, f_{12}, \dots, f_{18} \right \}$
• Class 3 - $[f_{19}] = [f_{20}] = [f_{21}] = \dots = [f_{27}] = \left \{ f_{19}, f_{20}, f_{21}, \dots, f_{27 }\right \}$

Therefore, we can see that there are 3 equivalence classes, each having 9 elements.

Answer 5

Detailed Video Solution, with Complete Analysis: Video Solution with Complete Analysis (Click HERE)  

Two functions f and g  in F are said to be Equivalent if and only if f(3)=g(3).

For any function f in F, f(3) can be either 1 or 2 or 3.

When f(3) = 1, Number of such functions possible in F for which f(3) = 1, will be  3^2 = 9 and all these 9 functions for which f(3) = 1, Are Equivalent (according to the condition defined for Equivalence of functions) 

Similarly for, When f(3) = 2  and When f(3) = 3. 

So, there will be Three Equivalence Classes, One for when f(3) = 1, One for when f(3) = 2, and One for f(3) = 3.  And Each equivalence class will have 9 Elements(functions) each.

So, Answer for 

1. : number of equivalence classes defined by "∼"  = 3

2.:  number of elements in each equivalence class  = 9

Comments

@Deppakk Poonia (Dee) Sir, I am confused. I studied equivalence relation still can’t understand. Please, if possoble then represent your solution pictorially with some more examples. Thank you.

Answer 6

Functions from $\{1,2,3\}$ to $\{1,2,3\}$ and an Equivalence Relation

Let $F$ be the collection of all functions 
\[
F : \{1,2,3\} \to \{1,2,3\}.
\]

(i) Total number of functions

The domain of the functions has 3 elements: 1, 2, 3.  

The co-domain also has 3 elements: 1, 2, 3.  

Each element in the domain can be mapped to any element in the co-domain:  

- For 1, there are 3 choices.  

- For 2, there are 3 choices.  

- For 3, there are 3 choices.  

Multiplying these together gives the total number of functions:  
\[
|F| = 3 \times 3 \times 3 = 27
\]

So, there are 27 functions in $F$.

other way: 

The number of elements in the domain is $3$ and the number of elements in the co-domain is also $3$.  

The total number of functions from the domain to the co-domain is given by
\[
|F| = |\text{co-domain}|^{|\text{domain}|} = 3^3 = 27.
\]
Hence, there are $27$ functions in $F$.

(ii) Defining a relation on $F$

Define a relation $\sim$ on $F$ by:  
\[
f \sim g \iff f(3) = g(3)
\]

This means two functions are related if and only if their value at 3 is the same.  

Examples:  

-  If $f(3) = 3$ and $g(3) = 3$, then $f \sim g$.  

- If $f(3) = 1$ and $g(3) = 3$, then $f \not\sim g$.

(iii) Checking equivalence relation (RST) 

- Reflexive: $f(3) = f(3)$, so $f \sim f$.  

- Symmetric: If $f(3) = g(3)$, then $g(3) = f(3)$, so $f \sim g \implies g \sim f$.  

- Transitive: If $f(3) = g(3)$ and $g(3) = h(3)$, then $f(3) = h(3)$, so $f \sim g$ and $g \sim h \implies f \sim h$.

Thus, $\sim$ is an equivalence relation.

(iv) Equivalence classes

Equivalence classes are determined by the value of $f(3)$:  

- $f(3) = 1$ forms one class.  

- $f(3) = 2$ forms another class.  

- $f(3) = 3$ forms another class.  

Example: For $f(3) = 1$, $f(1)$ and $f(2)$ can each take any of 3 values.  

(v) Size of each equivalence class

For each fixed $f(3)$:  

- $f(1)$ has 3 choices.  

- $f(2)$ has 3 choices.  

Hence, size of each class:  
\[
3 \times 3 = 9
\]

(vi) Conclusion

- Number of equivalence classes: 3  

- Number of functions in each class: 9