5,899 views
41 votes
41 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. 

5 Answers

Best answer
47 votes
47 votes
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
29 votes
29 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.

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.

Related questions

40 votes
40 votes
5 answers
1
34 votes
34 votes
5 answers
3