0
$\begingroup$

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$?

$\endgroup$

2 Answers 2

2
$\begingroup$

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$$

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

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

$\endgroup$
3
  • 1
    $\begingroup$ Proving it is even less tedious than listing all of the compositions.. :-) $\endgroup$
    – user76568
    Feb 25, 2014 at 18:01
  • $\begingroup$ How would you prove that the composition of bijections is a bijection? Which general thereom is that? $\endgroup$
    – ncm
    Feb 25, 2014 at 18:24
  • $\begingroup$ 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. $\endgroup$
    – Asaf Karagila
    Feb 25, 2014 at 18:25

You must log in to answer this question.

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