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

From Maths
Jump to: navigation, search
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:
Flesh out and demote


[ilmath]\xymatrix{ X \ar[r]^f \ar[d]_{\pi} & Y \\ \frac{X}{\sim} \ar@{.>}[ur]_{\tilde{f} } }[/ilmath]
Commutative diagram showing the situation
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].




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

Grade: D
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]

See also


  1. AKA: passing to the quotient
  2. 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]
  3. See "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" for details

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

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


  1. File:MondTop2016ex1.pdf