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

From Maths
Jump to: navigation, search
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]:

  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.

References

  1. Introduction to Topological Manifolds - John M. Lee