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

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.