4,105 views

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.

.….....................…...…..…............…..........….

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.$
by

This question really deserves an upvote. It took me 2 days to understand the solution fully and now I’m fully satisfied. Thank You @Arjun Sir for your crystal clear explanation (first everything went above my head though). And thanks to @Warrior whose depiction made it much easier.

I would ask everyone to first read @Sachin Mittal 1 Sir’s doubt, to which @Shreya Roy has given a beautiful explanation. Then read @MiNiPanda’s comments. The concept of equivalence class will be cleared. Then read @Arjun Sir’s answer lastly followed by @Warrior’s answer which is just it’s extension :)

Hope my comment helps for a proper understanding of the way to understand this q :)

Nice Explanation

@Shreya Roy

So each class has 81 pairs but 9 elements

Here each class is not having 81 pairs but all the three classes combinely having 81 pairs.

in each class there are 27 pairs and 9 elements.

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.

by

lovely explanation warrior
Thanks for this wonderful depiction!
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.

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.