If the composition of two functions is a bijection then the initial map is injective and the latter map is surjective
From Maths
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!
Contents
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
- [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:
- [ilmath]\forall x,x'\in X[f(x)\eq f(x')\implies x\eq x'][/ilmath] - the definition of injectivity
- [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
- 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
- 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]
- Suppose [ilmath]x\neq x'[/ilmath] (we will reach a contradiction)
- 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.
- Choose [ilmath]y:\eq f(x)[/ilmath]
- Let [ilmath]z':\eq z[/ilmath], now [ilmath]\exists x\in X[g(f(x))\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]
- Since [ilmath]z\in Z[/ilmath] was arbitrary we have shown it for all, as required.
References