0
$\begingroup$

Given are 3 functions $f,g,h$ of afinite Set $P$, and also given is that $g \circ f$ and $h \circ f$ are bijective.

Need to prove $h \circ g \circ f$ is bijective.


I know that as $g \circ f$ and $h \circ f$ are bijective, so both are injective as well as surjective. So

If $g \circ f$ is surjective then $g$ is surjective

If $h \circ g$ is injective then $g$ is injective

So it means $g$ is bijective

But using this information along with the information that the set is finite, how will I be able to conclude that $h \circ g \circ f$ is bijective.

Can anybody provide a hint to tackle this problem.

$\endgroup$
  • $\begingroup$ Can you show that $f$ and $h$ are bijections as well? Then $h \circ g \circ f$ is the composition of bijections... $\endgroup$ – Michael Biro Nov 2 '15 at 21:58
  • $\begingroup$ With what you've given, you can show quite easily that $h\circ g\circ f$ is surjective. A surjective map from a finite set to itself can be shown to be bijective $\endgroup$ – Robert Chamberlain Nov 2 '15 at 21:59
  • $\begingroup$ @TheRob you are correct but then how to proceed to show that $h \circ g \circ f$ is surjective $\endgroup$ – TechJ Nov 2 '15 at 22:03
  • $\begingroup$ @MichaelBiro we can only show for $g$, as $g$ is common in both $g \circ f$ and $h \circ g$ $\endgroup$ – TechJ Nov 2 '15 at 22:05
  • $\begingroup$ You're given $h\circ f$ bijective, so $h$ is surjective, $g\circ f$ is bijective so it's definitely surjective. The composition of surjective maps is surjective, so $h\circ g\circ f$ is surjective $\endgroup$ – Robert Chamberlain Nov 2 '15 at 22:07
2
$\begingroup$

Use that for a function on a finite set $P$, being an injection, a surjection or a bijection are all equivalent.

$f$ is already injective (from $g \circ f)$, you already know $g$ is too and $h$ is surjective. So all are bijections...

$\endgroup$
1
$\begingroup$

$g\circ f$ bijective implies $f$ is injective and $g$ surjective. Similarly, $h$ is surjective.

Furthermore, for a map from a finite set into itself, injective $\iff$ surjective $\iff$ bijective. Hence $f, g,h$ are all bijective. So $h\circ g\circ f$ is bijective.

$\endgroup$

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.