# Binary operation, function composition

If $A$ is the set of all bijective functions $f:\{1,2\} \to \{1,2\}$ , how do we prove that function composition is a binary operation on $A$?

I know that function composition is a binary operation on a set $A$ where $A$ is the set of all functions, but how do you prove it for all bijective functions?

Would a better place to start be to list all of the possible elements of $A$?

In this case you only have two bijections: $$f=\{(1,1),(2,2)\},g=\{(1,2),(2,1)\}$$ All you need to do is show that $f \circ g$ , $g \circ f$, $f \circ f$ , $g \circ g$ are in $A$. $$f \circ g = \{(1,2),(2,1)\}=g \in A$$ $$g \circ f = \{(1,2),(2,1)\}=g \in A$$ $$f \circ f = \{(1,1),(2,2)\}=f \in A$$ $$g \circ g = \{(1,1),(2,2)\}=f \in A$$

• How are f and g bijections?
– ncm
Feb 25, 2014 at 18:51
• I wrote them as relations from $A \times A$. It means: $f(1)=g(2)=1$, $f(2)=g(1)=2$. Fine now? Feb 25, 2014 at 18:53
• @ncm I meant $\{1,2\} \times \{1,2\}$, not $A \times A$.. Feb 26, 2014 at 11:25

You can list the bijections in this case, but the general case is not much harder. You have to show that given two bijections from $A$ to $A$, their composition is a bijection as well.

And that follows from the general theorem that a composition of bijections is a bijection (and if you don't know that, you should sit down to prove that, because it's important.)

• Proving it is even less tedious than listing all of the compositions.. :-) Feb 25, 2014 at 18:01
• How would you prove that the composition of bijections is a bijection? Which general thereom is that?
– ncm
Feb 25, 2014 at 18:24
• Show that if $f\colon A\to B$ and $g\colon B\to C$ are injective functions, then their composition is an injection; and if the functions are surjective, then their composition is surjective. Feb 25, 2014 at 18:25