Difference between revisions of "Passing to the quotient (function)"
From Maths
(Created page with "==Definition== Given a function, {{M|f:X\rightarrow Y}} and another function, {{M|w:X\rightarrow W}} (I have chosen {{M|W}} to mean "whatever") we can say: : '''{{M|f}} may be...") |
m (Made the diagram a bit neater, added in some points to make it easier to remember) |
||
| Line 3: | Line 3: | ||
: '''{{M|f}} may be factored through {{M|w}}''' | : '''{{M|f}} may be factored through {{M|w}}''' | ||
if {{M|f}} and {{M|w}} are such that: | if {{M|f}} and {{M|w}} 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>) | + | * <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 {{M|f}} ''induces'' a function, {{M|\tilde{f} }} such that <math>f=\tilde{f}\circ w</math>, or more simply that the following [[Commutative diagram|diagram commutes]]: | Then {{M|f}} ''induces'' a function, {{M|\tilde{f} }} such that <math>f=\tilde{f}\circ w</math>, or more simply that the following [[Commutative diagram|diagram commutes]]: | ||
| − | : | + | {| class="wikitable" border="1" |
| + | |- | ||
| + | | style="font-size:1.5em;" | <math> | ||
\begin{xy} | \begin{xy} | ||
\xymatrix{ | \xymatrix{ | ||
| Line 13: | Line 16: | ||
\end{xy} | \end{xy} | ||
</math> | </math> | ||
| + | |- | ||
| + | ! Diagram | ||
| + | |} | ||
Note: | Note: | ||
# {{M|\tilde{f} }} may be explicitly written as {{M|\tilde{f}:W\rightarrow Y}} by {{M|\tilde{f}:v\mapsto f(w^{-1}(v))}} | # {{M|\tilde{f} }} may be explicitly written as {{M|\tilde{f}:W\rightarrow Y}} by {{M|\tilde{f}:v\mapsto f(w^{-1}(v))}} | ||
| + | #* Or indeed {{M|1=\tilde{f}:=f\circ w^{-1} }} | ||
| + | #* This is actually an abuse of notation as {{M|w^{-1}(x\in W)}} is a subset of {{M|X}}, however it is safe to use it because (as is proved below) {{M|f}} of any element of {{M|w^{-1}(x\in W)}} for a given {{M|x}} is the same. | ||
# The function {{M|\tilde{f} }} is unique if {{M|w}} is [[Surjection|surjective]] | # The function {{M|\tilde{f} }} is unique if {{M|w}} is [[Surjection|surjective]] | ||
| + | ===Points to remember=== | ||
| + | * Remembering the requirements: | ||
| + | *: We want to induce a function {{M|\tilde{f}:W\rightarrow Y}} - if {{M|1=w(x)=w(y)}} then {{M|1=\tilde{f}(w(x))=\tilde{f}(w(y))}} just by composition. | ||
| + | *: If {{M|1=f(x)\ne f(y)}} we're screwed in this case. So it is easy to see that we must have {{M|1=[w(x)=w(y)]\implies[f(x)=f(y)]}} otherwise we cannot proceed. | ||
==Proof of claims== | ==Proof of claims== | ||
{{Begin Theorem}} | {{Begin Theorem}} | ||
| Line 57: | Line 69: | ||
{{End Proof}} | {{End Proof}} | ||
{{End Theorem}} | {{End Theorem}} | ||
| − | |||
==References== | ==References== | ||
<references/> | <references/> | ||
| − | |||
{{Definition|Abstract Algebra}} | {{Definition|Abstract Algebra}} | ||
Revision as of 00:19, 19 November 2015
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:
- [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.
- 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]
- Let [ilmath]b\in w^{-1}(v)[/ilmath] be given
- 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]
- Let [ilmath]a\in w^{-1}(v)[/ilmath] be given
- 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]
- Let [ilmath]v\in W[/ilmath] be given
- 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.
- 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
- 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] (and as [ilmath]w[/ilmath] is surjective [ilmath]\exists x\in X[p(x)=u][/ilmath])
- Both [ilmath]\tilde{f} [/ilmath] and [ilmath]\tilde{f}'[/ilmath] have the property of [math]f=\tilde{f}\circ w=\tilde{f}'\circ w[/math] so:
- by hypothesis, for all [ilmath]x[/ilmath] however, we know [ilmath]\tilde{f} [/ilmath] and [ilmath]\tilde{f}'[/ilmath] don't agree over their entire domain, the [ilmath]p(x)[/ilmath] they do not agree on violate this property (as [ilmath]f[/ilmath] cannot be two things for a given [ilmath]x[/ilmath])
- This contradicts that [ilmath]\tilde{f} [/ilmath] and [ilmath]\tilde{f}'[/ilmath] are different
This completes the proof[1]
- Notes:
- 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.
