in Set Theory & Algebra
4,105 views
37 votes
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)$. 

  1. Find the number of equivalence classes defined by $\sim$. 
  2. Find the number of elements in each equivalence class. 
in Set Theory & Algebra
4.1k views

4 Comments

0
0

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

1
1
0
0

5 Answers

42 votes
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.$
edited by
by

4 Comments

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
3
Nice Explanation
1
1

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

0
0
26 votes
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.

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

2 Comments

lovely explanation warrior
0
0
Thanks for this wonderful depiction!
1
1
9 votes
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.
6 votes
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-

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

edited by

Related questions