1
$\begingroup$

I'm just going through the problems that I got wrong on my discrete math exam, and I was not sure how to do this one. How would I go about making this chart? The chart has $f_1, \dots, f_5$ going across the top and down the side. I already got the question wrong, just want to know how to do it, in case it comes up again.

Let $A = \{1,2,3\}$ and define $f_1,f_2,f_3,f_4,f_5 \colon A \to A$ as follows: \begin{align} f_1 &= \{(1,1),(2,3),(3,2)\} \\ f_2 &= \{(1,3),(2,2),(3,1)\} \\ f_3 &= \{(1,2),(2,1),(3,3)\} \\ f_4 &= \{(1,2),(2,3),(3,1)\} \\ f_5 &= \{(1,3),(2,1),(3,2)\} \end{align} Show that each composite function $f_i\circ f_j$ is one of the given functions, or the identity, by completing a table. Find the inverse of those six functions that have inverses.

$\endgroup$
  • $\begingroup$ Changing the second f_i to $f_j$ is a substantial change that shouldn't have gone without input from the OP. $\endgroup$ – Eric Stucky Apr 12 '16 at 19:54
  • $\begingroup$ Yes, make a square table with the $f_i$ indexing the rows and columns. The entry for row $f_1$ and column $f_2$ will be $f_1\circ f_2 = \{(1,2),(2,3),(3,1)\} = f_4$, and the entry with row $f_2$ and column $f_1$ will be $f_2\circ f_1 = \{(1,3),(2,1),(3,2)\} = f_5$ and so on... $\endgroup$ – John Martin Apr 12 '16 at 19:55
  • $\begingroup$ What was the math behind this? f1∘f2={(1,2),(2,3),(3,1)} $\endgroup$ – Jebus Crust Apr 12 '16 at 19:58
  • $\begingroup$ @EricStucky “The table has $f_1,\dots,f_5$ going across the top and down the side”; I think that all compositions are to be taken into account. $\endgroup$ – egreg Apr 12 '16 at 20:00
  • 1
    $\begingroup$ for the inverse, switch left and right elements of each pair. For example $f_4(3)=1$, hence the inverse $f_4^{-1}(1)=3$. So $(3,1)\in f_4$, hence $(1,3)\in f_4^{-1}$. If $f_4=\{(1,2),(2,3),(3,1)\}$ then $f_4^{-1}=\{(2,1),(3,2),(1,3)\}=\{(1,3),(2,1),(3,2)=f_5$. $\endgroup$ – Mirko Apr 12 '16 at 20:46
1
$\begingroup$

If $f_0=\{(1,1),(2,2),(3,3)\}$ is the identity map, the six maps $\{f_0,f_1,f_2,f_3,f_4,f_5\}$ are six bijective maps $A\to A$.

Since $|A|=3$, there are exactly $6=3!$ bijective maps $A\to A$, so the above set is the set of all permutations of $A$. Since the composition of two bijective maps is a bijective map, $f_i\circ f_j$ must belong to the set for any $i,j$, with $0\le i,j\le 5$.

You can fill in the composition table by hand. Some of the compositions are here: $$ \begin{array}{c|cccccc} & f_0 & f_1 & f_2 & f_3 & f_4 & f_5 \\ \hline f_0 & & & & & & \\ f_1 & & & & & & \\ f_2 & & f_5 & & & & \\ f_3 & & & & & & \\ f_4 & & & f_1 & & & \\ f_5 & & & & & & \end{array} $$

$\endgroup$
  • $\begingroup$ The part you explained makes sense to me, but I still do not understand how you are filling in that chart? $\endgroup$ – Jebus Crust Apr 12 '16 at 20:08
  • 1
    $\begingroup$ @JebusCrust Composition of maps; $f_2\circ f_1(1)=f_2(1)=3$, $f_2\circ f_1(2)=f_2(3)=1$, $f_2\circ f_1(3)=f_2(2)=2$; therefore $f_2\circ f_1=f_5$. $\endgroup$ – egreg Apr 12 '16 at 20:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.