Friday, July 25, 2025

If g and f are injections, so is g ∘ f, and same with bijections

Show that if $f: A\rightarrow B$ and $g: B\rightarrow C$ are injections, so is $g\circ f: A\rightarrow C$.

Recall that a function $h:X\to Y$ is injective (one‐to‐one) precisely when

$$ h(x_1)=h(x_2)\implies x_1=x_2. $$


Theorem. If

$$ f:A\longrightarrow B \quad\text{and}\quad g:B\longrightarrow C $$

are both injective, then their composite

$$ g\circ f:A\longrightarrow C $$

is injective.


Proof. Let $x_1,x_2\in A$ and suppose

$$ (g\circ f)(x_1)\;=\;(g\circ f)(x_2). $$

By definition of composition, this means

$$ g\bigl(f(x_1)\bigr) \;=\; g\bigl(f(x_2)\bigr). $$

Since $g$ is injective, we conclude

$$ f(x_1)=f(x_2). $$

But $f$ is injective, so from $f(x_1)=f(x_2)$ it follows that

$$ x_1 = x_2. $$

Thus

$$ (g\circ f)(x_1)=(g\circ f)(x_2) \;\Longrightarrow\; x_1=x_2, $$

showing $g\circ f$ is injective. $\boxed{}$


Alternative (via contrapositive). One can also argue:

  • If $x_1\neq x_2$, then since $f$ is injective, $f(x_1)\neq f(x_2)$.
  • Then since $g$ is injective, $g\bigl(f(x_1)\bigr)\neq g\bigl(f(x_2)\bigr)$.
  • Hence $(g\circ f)(x_1)\neq(g\circ f)(x_2)$.

This directly shows “distinct inputs give distinct outputs,” i.e.\ $g\circ f$ is one‐to‐one.

Separate conversation with o4-mini:

Show that if $f: A\rightarrow B$ and $g: B\rightarrow C$ are bijections, so is $g\circ f: A\rightarrow C$.

Proof. Suppose

$$ f:A\to B\quad\text{and}\quad g:B\to C $$

are both bijections. We must show that $g\circ f:A\to C$ is bijective, i.e. both injective and surjective.


1. Injectivity

Take any $a,a'\in A$ and assume

$$ (g\circ f)(a)\;=\;(g\circ f)(a'). $$

Then

$$ g\bigl(f(a)\bigr)\;=\;g\bigl(f(a')\bigr). $$

Since $g$ is injective, it follows that

$$ f(a)\;=\;f(a'). $$

But $f$ is injective, so from $f(a)=f(a')$ we conclude

$$ a\;=\;a'. $$

Hence $g\circ f$ is injective.


2. Surjectivity

Let $c\in C$ be arbitrary. Since $g$ is surjective, there exists some

$$ b\in B\quad\text{such that}\quad g(b)=c. $$

Next, because $f$ is surjective, there exists

$$ a\in A\quad\text{such that}\quad f(a)=b. $$

Therefore

$$ (g\circ f)(a) \;=\; g\bigl(f(a)\bigr) \;=\; g(b) \;=\; c. $$

Since $c$ was arbitrary in $C$, this shows $g\circ f$ is surjective.


3. Conclusion

Having established that $g\circ f$ is both injective and surjective, we conclude that

$$ g\circ f:A\;\longrightarrow\;C $$

is a bijection. Moreover, one can check directly that its inverse is

$$ \bigl(g\circ f\bigr)^{-1} \;=\; f^{-1}\circ g^{-1}, $$

providing an explicit bijective inverse.

No comments:

Post a Comment