# Factoring a function through the projection of an equivalence relation induced by that function yields an injection

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:
Flesh out and demote

## Statement

 Commutative diagram showing the situation [ilmath]\xymatrix{ X \ar[r]^f \ar[d]_{\pi} & Y \\ \frac{X}{\sim} \ar@{.>}[ur]_{\tilde{f} } }[/ilmath]
Let [ilmath]X[/ilmath] and [ilmath]Y[/ilmath] be sets, let [ilmath]f:X\rightarrow Y[/ilmath] be any 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 unique injective map[1]:

• [ilmath]\tilde{f}:\frac{X}{\sim}\rightarrow Y[/ilmath]

Furthermore, if [ilmath]f:X\rightarrow Y[/ilmath] is surjective then [ilmath]\tilde{f}:\frac{X}{\sim}\rightarrow Y[/ilmath] is not only injective but surjective to, that is: [ilmath]\tilde{f}:\frac{X}{\sim}\rightarrow Y[/ilmath] is a bijection[Note 3].

Topology:

## Proof

Outline of proof method

1. We must check the set up satisfies the requirements of the passing-to-the-quotient theorem (to yield [ilmath]\tilde{f}:\frac{X}{\sim}\rightarrow Y[/ilmath]).
2. We apply the theorem to get [ilmath]\tilde{f}:\frac{X}{\sim}\rightarrow Y[/ilmath].
3. Next we must show [ilmath]\tilde{f}:\frac{X}{\sim}\rightarrow Y[/ilmath] is injective

### Proof body

This page requires one or more proofs to be filled in, it is on a to-do list for being expanded with them.
Please note that this does not mean the content is unreliable. Unless there are any caveats mentioned below the statement comes from a reliable source. As always, Warnings and limitations will be clearly shown and possibly highlighted if very important (see template:Caution et al).
The message provided is:
Part 3 was the only non-trivial part. It is obvious that we can factor [ilmath]f[/ilmath] through [ilmath]\pi[/ilmath], in fact:
• To do so requires that "[ilmath]f[/ilmath] be constant on the fibres of [ilmath]\pi[/ilmath]", ie:
Oh just FYI there's a commented out note and a requires-proof template at the top of the ==proof== heading, remove that later!

#### Step 3

We wish to show that [ilmath]\tilde{f}:\frac{X}{\sim}\rightarrow Y[/ilmath] is injective, ie: [ilmath]\forall a,b\in\frac{X}{\sim}[\tilde{f}(a)=\tilde{f}(b)\implies a=b][/ilmath]

• Let [ilmath]a,b\in\frac{X}{\sim} [/ilmath] be given.
• Suppose [ilmath]\tilde{f}(a)\ne\tilde{f}(b)[/ilmath] then by the nature of logical implication we do not care whether or not [ilmath]a=b[/ilmath], either way it is true, we're done in this case.
• Suppose [ilmath]\tilde{f}(a)=\tilde{f}(b)[/ilmath], by the nature of logical implication we now require this leads to [ilmath]a=b[/ilmath]
• By the surjectivity of [ilmath]\pi:X\rightarrow\frac{X}{\sim} [/ilmath] we see:
• [ilmath]\exists x\in X[\pi(x)=a][/ilmath] and [ilmath]\exists y\in X[\pi(y)=b][/ilmath]
• Note that [ilmath]\tilde{f}(a)=\tilde{f}(\pi(x))[/ilmath] and [ilmath]\tilde{f}(b)=\tilde{f}(\pi(y))[/ilmath], also by assumption we have [ilmath]\tilde{f}(a)=\tilde{f}(\pi(x))= \tilde{f}(\pi(y))=\tilde{f}(b)[/ilmath]
• Notice also that [ilmath]f(x)=\tilde{f}(\pi(x))[/ilmath] and [ilmath]f(y)=\tilde{f}(\pi(y))[/ilmath] (this is the whole point of [ilmath]\tilde{f} [/ilmath])
• So we see [ilmath]f(x)=\tilde{f}(a)=\tilde{f}(\pi(x))= \tilde{f}(\pi(y))=\tilde{f}(b)=f(y)[/ilmath], or importantly:
• [ilmath]f(x)=f(y)[/ilmath]
• Recall that [ilmath]x\sim y\iff f(x)=f(y)[/ilmath], so now we know [ilmath]x\sim y[/ilmath]
• An elementary property of [ilmath]\pi:X\rightarrow\frac{X}{\sim} [/ilmath] is that if [ilmath]x\sim y[/ilmath] then [ilmath]\pi(x)=\pi(y)[/ilmath][Note 4][Note 5]
• Explicitly, notice we have: [ilmath]\pi(x)=\pi(y)[/ilmath]
• Recall that [ilmath]a=\pi(x)[/ilmath] and [ilmath]b=\pi(y)[/ilmath] by definition of [ilmath]x[/ilmath] and [ilmath]y[/ilmath], so:
• [ilmath]a=\pi(x)=\pi(y)=b[/ilmath] or more simply: [ilmath]a=b[/ilmath]
• We have shown that supposing [ilmath]f(a)=f(b)[/ilmath] is given then [ilmath]a=b[/ilmath]
• Both cases have been evaluated and the implication holds for both
• Since [ilmath]a,b\in\frac{X}{\sim} [/ilmath] were arbitrary we have shown this for all [ilmath]a,b\in\frac{X}{\sim} [/ilmath]

## Notes

1. 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]

2. TODO: Link to statement, this ought to be mentioned somewhere explicit on this site!

3. TODO: This can be strengthened to [ilmath]\iff[/ilmath] surely!