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$
10
  • $\begingroup$ Changing the second f_i to $f_j$ is a substantial change that shouldn't have gone without input from the OP. $\endgroup$ Commented Apr 12, 2016 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$ Commented Apr 12, 2016 at 19:55
  • $\begingroup$ What was the math behind this? f1∘f2={(1,2),(2,3),(3,1)} $\endgroup$ Commented Apr 12, 2016 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
    Commented Apr 12, 2016 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
    Commented Apr 12, 2016 at 20:46

2 Answers 2

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$
2
  • $\begingroup$ The part you explained makes sense to me, but I still do not understand how you are filling in that chart? $\endgroup$ Commented Apr 12, 2016 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
    Commented Apr 12, 2016 at 20:12
0
$\begingroup$

In cycle notation: \begin{alignat}{1} &f_1=(23)\\ &f_2=(13)\\ &f_3=(12)\\ &f_4=(123)\\ &f_5=(132)\\ \end{alignat} By "completing a table etc." they mean to explicty prove that: $$\forall i,j\in A, \exists k\in A \text{ such that } f_if_j=f_k, \text{ or otherwise } f_if_j=()$$ In fact (composition is right to left): \begin{alignat}{1} &f_1^2=()\\ &f_1f_2=(123)=f_4\\ &f_1f_3=(132)=f_5\\ &f_1f_4=(13)=f_2\\ &f_1f_5=(12)=f_3\\ \\ &f_2f_1=(132)=f_5\\ &f_2^2=()\\ &f_2f_3=(123)=f_4\\ &f_2f_4=(12)=f_3\\ &f_2f_5=(23)=f_1\\ \\ &f_3f_1=(123)=f_4\\ &f_3f_2=(132)=f_5\\ &f_3^2=()\\ &f_3f_4=(23)=f_1\\ &f_3f_5=(13)=f_2\\ \\ &f_4f_1=(12)=f_3\\ &f_4f_2=(23)=f_1\\ &f_4f_3=(13)=f_2\\ &f_4^2=(132)=f_5\\ &f_4f_5=()\\ \\ &f_5f_1=(12)=f_3\\ &f_5f_2=(23)=f_1\\ &f_5f_3=(13)=f_2\\ &f_5f_4=()\\ &f_5^2=(123)=f_4\\ \end{alignat} Therefore, every $f_i$ has inverse; in particular, $f_{1,2,3}$ are self-inverses ("involutions"), whereas $f_4$ and $f_5$ are inverses each other.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .