Difference between revisions of "Passing to the quotient (function)"

From Maths
Jump to: navigation, search
m (Made the diagram a bit neater, added in some points to make it easier to remember)
m (Tidied up a bit, fixed a typo or two.)
Line 57: Line 57:
 
'''Uniqueness'''
 
'''Uniqueness'''
 
: Suppose another function exists, <math>\tilde{f}':W\rightarrow Y</math> that isn't the same as <math>\tilde{f}:W\rightarrow Y</math>
 
: Suppose another function exists, <math>\tilde{f}':W\rightarrow Y</math> that isn't the same as <math>\tilde{f}:W\rightarrow Y</math>
:: That means <math>\exists u\in W:[\tilde{f}(u)\ne\tilde{f}'(u)]</math> (and as {{M|w}} is ''surjective'' {{M|1=\exists x\in X[p(x)=u]}})
+
:: That means <math>\exists u\in W:[\tilde{f}(u)\ne\tilde{f}'(u)]</math>
:: Both {{M|\tilde{f} }} and {{M|\tilde{f}'}} have the property of <math>f=\tilde{f}\circ w=\tilde{f}'\circ w</math> so:
+
::* Note, as {{M|w:X\rightarrow W}} is [[surjective]], that {{M|1=\exists x'\in X[w(x')=u]}}
::: {{M|f(x)=\tilde{f}(p(x))=\tilde{f}'(p(x))}} by hypothesis, for all {{M|x}} however, we know {{M|\tilde{f} }} and {{M|\tilde{f}'}} don't agree over their entire domain, the {{M|p(x)}} they do not agree on violate this property (as {{M|f}} cannot be two things for a given {{M|x}})
+
:: However for both {{M|\tilde{f} }} and {{M|\tilde{f}'}} we have the property of <math>f=\tilde{f}\circ w=\tilde{f}'\circ w</math> so:
:: This contradicts that {{M|\tilde{f} }} and {{M|\tilde{f}'}} are different
+
::: By hypothesis we have: {{M|1=\forall x\in X[f(x)=\tilde{f}(w(x))=\tilde{f}'(w(x))]}} however we know:
 +
:::* {{M|1=\exists x'\in X[w(x')=u]}} and {{M|1=\tilde{f}(u)\ne \tilde{f}'(u)}}, this means:
 +
:::** {{M|1=f(x')=\tilde{f}(w(x'))\ne\tilde{f}'(w(x'))}} - which contradicts the hypothesis.
 +
:: However if {{M|w}} is not surjective, then the parts of the domain on which {{M|\tilde{f} }} and {{M|\tilde{f}'}} disagree on may never actually come up; that is to say:
 +
::* {{M|1=\forall x\in X[\tilde{f}(w(x))=\tilde{f}'(w(x))]}} as {{m|w:X\rightarrow W}} may never take an {{M|x\in X}} to a {{M|z\in W}} where {{M|\tilde{f}(z)}} and {{M|\tilde{f}'(z)}} differ; ''but'' they could still be different functions.
  
  

Revision as of 16:18, 10 July 2016

Definition

Given a function, [ilmath]f:X\rightarrow Y[/ilmath] and another function, [ilmath]w:X\rightarrow W[/ilmath] (I have chosen [ilmath]W[/ilmath] to mean "whatever") we can say:

[ilmath]f[/ilmath] may be factored through [ilmath]w[/ilmath]

if [ilmath]f[/ilmath] and [ilmath]w[/ilmath] are such that:

  • [math]\forall x,y\in X[w(x)=w(y)\implies f(x)=f(y)][/math]
    (this is the same as: [math]\forall x,y\in X[f(x)\ne f(y)\implies w(x)\ne w(y)][/math])

Then [ilmath]f[/ilmath] induces a function, [ilmath]\tilde{f} [/ilmath] such that [math]f=\tilde{f}\circ w[/math], or more simply that the following diagram commutes:

[math] \begin{xy} \xymatrix{ X \ar[r]^w \ar[dr]_f & W \ar@{.>}[d]^{\tilde{f}}\\ & Y } \end{xy} [/math]
Diagram

Note:

  1. [ilmath]\tilde{f} [/ilmath] may be explicitly written as [ilmath]\tilde{f}:W\rightarrow Y[/ilmath] by [ilmath]\tilde{f}:v\mapsto f(w^{-1}(v))[/ilmath]
    • Or indeed [ilmath]\tilde{f}:=f\circ w^{-1}[/ilmath]
    • This is actually an abuse of notation as [ilmath]w^{-1}(x\in W)[/ilmath] is a subset of [ilmath]X[/ilmath], however it is safe to use it because (as is proved below) [ilmath]f[/ilmath] of any element of [ilmath]w^{-1}(x\in W)[/ilmath] for a given [ilmath]x[/ilmath] is the same.
  2. The function [ilmath]\tilde{f} [/ilmath] is unique if [ilmath]w[/ilmath] is surjective

Points to remember

  • Remembering the requirements:
    We want to induce a function [ilmath]\tilde{f}:W\rightarrow Y[/ilmath] - if [ilmath]w(x)=w(y)[/ilmath] then [ilmath]\tilde{f}(w(x))=\tilde{f}(w(y))[/ilmath] just by composition.
    If [ilmath]f(x)\ne f(y)[/ilmath] we're screwed in this case. So it is easy to see that we must have [ilmath][w(x)=w(y)]\implies[f(x)=f(y)][/ilmath] otherwise we cannot proceed.

Proof of claims

Claim: the induced function, [ilmath]\tilde{f} [/ilmath] exists and is given unambiguously by [ilmath]\tilde{f}:v\mapsto f(w^{-1}(v))[/ilmath]


Existence

Let [ilmath]\tilde{f}:W\rightarrow Y[/ilmath] be given by: [ilmath]f:v\mapsto f(w^{-1}(v))[/ilmath] - I need to prove this is a Function
This means I must check it is well defined, a function must associate each point in its domain with exactly 1 element of its codomain
Let [ilmath]v\in W[/ilmath] be given
Let [ilmath]a\in w^{-1}(v)[/ilmath] be given
Let [ilmath]b\in w^{-1}(v)[/ilmath] be given
We know [math]\forall a\in w^{-1}(v)[/math] that [math]w(a)=v[/math] by definition of [math]w^{-1}[/math]
This means [math]w(a)=w(b)[/math]
But by hypothesis [math]w(a)=w(b)\implies f(a)=f(b)[/math]
So [math]f(a)=f(b)[/math]
Thus given an [ilmath]a\in w^{-1}(v)[/ilmath], [math]\forall b\in w^{-1}[f(a)=f(b)][/math]
We now know (formally) that: (given a [ilmath]v[/ilmath]) [math]\exists y\in Y\forall a\in w^{-1}(v)[f(a)=y][/math] - notice the [math]\exists y[/math] comes first. We can uniquely define [math]f(w^{-1}(v))[/math]
Since [ilmath]v\in W[/ilmath] was arbitrary we know [math]\forall v\in W\exists y\in Y\forall a\in w^{-1}(v)[f(a)=y][/math]
We have now shown that [math]\tilde{f}[/math] can be well defined (as the function that maps a [ilmath]v\in W[/ilmath] to a [ilmath]y\in Y[/ilmath].
To calculate [math]\tilde{f}(v)[/math] we may choose any [math]a\in w^{-1}(v)[/math] and define [math]\tilde{f}(v)=f(a)[/math] - we know [math]f(a)[/math] is the same for whichever [math]a\in w^{-1}(v)[/math] we choose.
So we know the function [math]\tilde{f}:W\rightarrow Y[/math] given by [math]\tilde{f}:x\mapsto f(w^{-1}(x))[/math] exists


This completes the proof[1]

Claim: if [ilmath]w[/ilmath] is surjective then the induced [ilmath]\tilde{f} [/ilmath] is unique


Uniqueness

Suppose another function exists, [math]\tilde{f}':W\rightarrow Y[/math] that isn't the same as [math]\tilde{f}:W\rightarrow Y[/math]
That means [math]\exists u\in W:[\tilde{f}(u)\ne\tilde{f}'(u)][/math]
  • Note, as [ilmath]w:X\rightarrow W[/ilmath] is surjective, that [ilmath]\exists x'\in X[w(x')=u][/ilmath]
However for both [ilmath]\tilde{f} [/ilmath] and [ilmath]\tilde{f}'[/ilmath] we have the property of [math]f=\tilde{f}\circ w=\tilde{f}'\circ w[/math] so:
By hypothesis we have: [ilmath]\forall x\in X[f(x)=\tilde{f}(w(x))=\tilde{f}'(w(x))][/ilmath] however we know:
  • [ilmath]\exists x'\in X[w(x')=u][/ilmath] and [ilmath]\tilde{f}(u)\ne \tilde{f}'(u)[/ilmath], this means:
    • [ilmath]f(x')=\tilde{f}(w(x'))\ne\tilde{f}'(w(x'))[/ilmath] - which contradicts the hypothesis.
However if [ilmath]w[/ilmath] is not surjective, then the parts of the domain on which [ilmath]\tilde{f} [/ilmath] and [ilmath]\tilde{f}'[/ilmath] disagree on may never actually come up; that is to say:
  • [ilmath]\forall x\in X[\tilde{f}(w(x))=\tilde{f}'(w(x))][/ilmath] as [ilmath]w:X\rightarrow W[/ilmath] may never take an [ilmath]x\in X[/ilmath] to a [ilmath]z\in W[/ilmath] where [ilmath]\tilde{f}(z)[/ilmath] and [ilmath]\tilde{f}'(z)[/ilmath] differ; but they could still be different functions.


This completes the proof[1]

Notes:
  1. Notice that if [ilmath]w[/ilmath] is not surjective, the point(s) on which [ilmath]\tilde{f} [/ilmath] and [ilmath]\tilde{f}'[/ilmath] disagree on may never actually come up, so it is indeed not-unique if [ilmath]w[/ilmath] isn't surjective.

References

  1. 1.0 1.1 This is my (Alec's) own work