Problem: Let $A$ and $B$ be two sets and $f:A\to B$ and $g:B\to A$ two functions such that $f\circ g\circ f$ is a bijection. Prove that $f$ and $g$ are also bijection.

Proof Attempt: We first show that $f$ is an injection. Let $f(x)=f(y)$ then $$g(f(x))=g(f(y))$$ $$f(g(f(x)))=g(g(f(y)))$$ $$(f\circ g\circ f)(x)=(f\circ g\circ f)(y)$$ $$x=y.$$ So it is an injection.

Now we will show $f$ is a surjection. Let $y\in B$ then there exists an $x\in A$ such that $(f\circ g\circ f)(x)=y.$ Or in other words for any $y\in B$ there exists an element $x'=g(f(x))\in A$ such that $f(x')=y.$ Hence $f$ is a surjection. Thus $f$ is a bijection.

Now we will show that $g$ is a bijection. We know that $f$ is a bijection and hence $f^{-1}$ is a bijection so we have that $f^{-1}\circ f\circ g\circ f\circ f^{-1}$ is a bijection. But this mapping is identical to $g$ and so we have that $g$ is a bijection.

Is this a valid proof?

  • 8
    $\begingroup$ Well done. I see no problems. $\endgroup$ – Randall Nov 5 '17 at 23:01
  • $\begingroup$ @Randall Thanks! $\endgroup$ – model_checker Nov 5 '17 at 23:02
  • 1
    $\begingroup$ Finally made the 2k mark! $\endgroup$ – model_checker Nov 5 '17 at 23:08
  • $\begingroup$ Note that this can be deduced from the result at math.stackexchange.com/questions/1324627/…. $\endgroup$ – Patrick Stevens Feb 11 '18 at 9:23
  • $\begingroup$ @Hello_World: Perhaps you should self-answer this so it doesn't hang around as an unanswered question. $\endgroup$ – Nick Matteo Mar 6 at 7:06

Your Answer

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

Browse other questions tagged or ask your own question.