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 [ilmath]X,\ Y[/ilmath] and [ilmath]Z[/ilmath] be sets. Let [ilmath]f:X\rightarrow Y[/ilmath] and [ilmath]g:Y\rightarrow Z[/ilmath] be maps. Suppose that [ilmath](g\circ f):X\rightarrow Z[/ilmath] is a bijection. Then:

1. [ilmath]f:X\rightarrow Y[/ilmath] is an injection, and
2. [ilmath]g:Y\rightarrow Z[/ilmath] is a surjection

In the title the initial map refers to [ilmath]f[/ilmath], as it is applied first; the latter map is [ilmath]g[/ilmath] as it is applied second.

Proof

We wish to show:

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

[ilmath]f[/ilmath] is an injection

• Let [ilmath]x,x'\in X[/ilmath] be given
  1. Suppose [ilmath]f(x)\neq f(x')[/ilmath] - 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 [ilmath]f(x)\eq f(x')[/ilmath] - we must show that in this case: [ilmath]x\eq x'[/ilmath]
     • Suppose [ilmath]x\neq x'[/ilmath] (we will reach a contradiction)
       • Then [ilmath](g\circ f)(x)\neq (g\circ f)(x')[/ilmath] - as [ilmath]g\circ f[/ilmath] is a bijection
       • This can be written: [ilmath]g(f(x))\neq g(f(x'))[/ilmath]
         • But as [ilmath]f(x)\eq f(x')[/ilmath] we see [ilmath]g(f(x))\eq g(f(x'))[/ilmath] (as [ilmath]g[/ilmath] 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 [ilmath]g(f(x))\neq g(f(x'))[/ilmath] and [ilmath]g(f(x))\eq g(f(x'))[/ilmath]!
     • So we must have [ilmath]x\eq x'[/ilmath]
• In either case the implication holds.

This completes the proof that [ilmath]f[/ilmath] is injective.

[ilmath]g[/ilmath] is a surjection

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