If a surjective function is factored through the canonical projection of the equivalence relation induced by that function then the yielded function is a bijection
From Maths
Stub grade: A
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:
Does it really warrant it's own page? It's only a minor extension of Factoring a function through the projection of an equivalence relation induced by that function yields an injection
Contents
- Note: there is a precursor theorem: Factoring a function through the projection of an equivalence relation induced by that function yields an injection
Statement
Let [ilmath]X[/ilmath] and [ilmath]Y[/ilmath] be sets, let [ilmath]f:X\rightarrow Y[/ilmath] be any surjective function between them, and let [ilmath]\sim\subseteq X\times X[/ilmath] denote the equivalence relation induced by the function [ilmath]f[/ilmath], recall that means:- [ilmath]\forall x,x'\in X[x\sim x'\iff f(x)=f(x')][/ilmath]
Then we claim we can factor^{[Note 1]} [ilmath]f:X\rightarrow Y[/ilmath] through [ilmath]\pi:X\rightarrow \frac{X}{\sim} [/ilmath]^{[Note 2]} to yield a bijective map^{[1]}:
- [ilmath]\tilde{f}:\frac{X}{\sim}\rightarrow Y[/ilmath]
Proof
We know from applying factoring a function through the projection of an equivalence relation induced by that function yields an injection that:
- we get a unique^{[Note 3]} injection [ilmath]\tilde{f}:\frac{X}{\sim}\rightarrow Y[/ilmath]
We also know that:
- If [ilmath]f[/ilmath] is surjective and descends to the quotient [ilmath]\tilde{f} [/ilmath], then [ilmath]\tilde{f} [/ilmath] is also surjective.
Thus we see [ilmath]\tilde{f}:\frac{X}{\sim}\rightarrow Y[/ilmath] is a unique bijection (it is surjective and injective)
Notes
- ↑ AKA: passing to the quotient
- ↑ the canonical projection of the equivalence relation, given by [ilmath]\pi:x\mapsto [x][/ilmath] where [ilmath][x][/ilmath] denotes the equivalence class containing [ilmath]x[/ilmath]
- ↑ As [ilmath]\pi:X\rightarrow\frac{X}{\sim} [/ilmath] is surjective - see factor (function)