If the composition of two functions is a bijection then the initial map is injective and the latter map is surjective

Stub grade: B

This page is a stub

This page is a stub, so it contains little or minimal information and is on a to-do list for being expanded.The message provided is:

Unimportant but useful theorem, good to factor out.

• It has been done somewhere, sometime, but I cannot remember where!

Statement

Let $X,\ Y$ and $Z$ be sets. Let $f:X\rightarrow Y$ and $g:Y\rightarrow Z$ be maps. Suppose that $(g\circ f):X\rightarrow Z$ is a bijection. Then:

1. $f:X\rightarrow Y$ is an injection, and
2. $g:Y\rightarrow Z$ is a surjection

In the title the initial map refers to $f$, as it is applied first; the latter map is $g$ as it is applied second.

Proof

We wish to show:

1. $\forall x,x'\in X[f(x)\eq f(x')\implies x\eq x']$ - the definition of injectivity
2. $\forall z\in Z\exists y\in Y[g(y)\eq z]$ - the definition of surjectivity

$f$ is an injection

• Let $x,x'\in X$ be given
  1. Suppose $f(x)\neq f(x')$ - then by the nature of logical implication we do not care whether or not the RHS is true or false, we're done
  2. Suppose $f(x)\eq f(x')$ - we must show that in this case: $x\eq x'$
     • Suppose $x\neq x'$ (we will reach a contradiction)
       • Then $(g\circ f)(x)\neq (g\circ f)(x')$ - as $g\circ f$ is a bijection
       • This can be written: $g(f(x))\neq g(f(x'))$
         • But as $f(x)\eq f(x')$ we see $g(f(x))\eq g(f(x'))$ (as $g$ is a function, so must associate each item in the domain with exactly one item in the codomain
     • This is a contradiction, we cannot have both $g(f(x))\neq g(f(x'))$ and $g(f(x))\eq g(f(x'))$!
     • So we must have $x\eq x'$
• In either case the implication holds.

This completes the proof that $f$ is injective.

$g$ is a surjection

• Let $z\in Z$ be given. We must show $\exists y\in Y[g(y)\eq z]$
  • As $g\circ f$ is a bijection we know that: $\forall z'\in Z\exists x\in X[(g\circ f)(x)\eq z']$
    • Let $z':\eq z$, now $\exists x\in X[g(f(x))\eq z]$
      • Choose $y:\eq f(x)$
        • Now $y\in Y$, as required and $g(y)\eq g(f(x))\eq z$
      • So $g(y)\eq z$ as required.
• Since $z\in Z$ was arbitrary we have shown it for all, as required.