Dark Mode

Kathleen
asked
in Set Theory & Algebra
Oct 10, 2014

4,105 views
37 votes

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

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

can anyone explain this question in easy way.

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

0

42 votes

Best answer

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

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

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 @Ayush Upadhyaya and @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 :)

3

26 votes

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.

9 votes

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.

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.

6 votes

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-

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

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