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 (→‎Proof of claims: Added link to surjective proof)
 
(3 intermediate revisions by the same user not shown)
Line 1: Line 1:
−
==Definition==
+
{{Refactor notice|review=true}}
−
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:
+
: See [[Passing to the quotient]] for a disambiguation of this term.
−
: '''{{M|f}} may be factored through {{M|w}}'''
+
__TOC__
−
if {{M|f}} and {{M|w}} are such that:
+
==Statement==
−
* <math>\forall x,y\in X[w(x)=w(y)\implies f(x)=f(y)]</math>  
+
{{float-right|{{/Diagram}}|style=max-width:20em;}}Given a function, {{M|f:X\rightarrow Y}} and another function, {{M|w:X\rightarrow W}}<ref group="Note">I have chosen {{M|W}} to mean "whatever"</ref> then "''{{M|f}} may be factored through {{M|w}}''" if<ref>Alec's own work, "distilled" from [[passing to the quotient (topology)]] which is defined by Mond (2013, Topology) and Lee (Intro to Top manifolds), by further abstracting the claim</ref>:
−
*: (this is the same as: <math>\forall x,y\in X[f(x)\ne f(y)\implies w(x)\ne w(y)]</math>)
+
* {{M|f}} is constant on the {{plural|fibre|s}} of {{M|w}}<ref group="Note">We can state this in 2 other equivalent ways:  
−
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]]:
+
# <math>\forall x,y\in X[w(x)=w(y)\implies f(x)=f(y)]</math>  
−
{| class="wikitable" border="1"
+
# <math>\forall x,y\in X[f(x)\ne f(y)\implies w(x)\ne w(y)]</math>
−
|-
+
See [[equivalent conditions to being constant on the fibres of a map]] for proofs and more details</ref><!--
−
| style="font-size:1.5em;" | <math>
+
 
−
\begin{xy}
+
END OF NOTE ON CONSTANT-ON-FIBRE PART
−
\xymatrix{
+
-->
−
X \ar[r]^w \ar[dr]_f & W \ar@{.>}[d]^{\tilde{f}}\\
+
If this condition is met then {{M|f}} ''induces'' a [[mapping]], {{M|\tilde{f}:W\rightarrow Y }}, such that <math>f=\tilde{f}\circ w</math> (equivalently, the diagram on the right [[Commutative diagram|commutes]]).
−
& Y
+
* {{M|\tilde{f}:W\rightarrow X}} may be given explicitly as: {{M|1=\tilde{f}:v\mapsto f(w^{-1}(v))}}<ref group="Note">Of course, only {{plural|bijection|s}} have {{plural|inverse function|s}}, we indulge in the common practice of using {{M|w^{-1}(v)}} to mean {{M|w^{-1}(\{v\})}}, in general for [[sets]] {{M|A}} and {{M|B}} and a [[mapping]] {{M|f:A\rightarrow B}} we use {{M|f^{-1}(C)}} to denote (for some {{M|C\in\mathcal{P}(B)}} (a [[subset of]] {{M|X}})) the {{link|pre-image|map}} of {{M|C}} under the [[function]] {{M|f}}, {{M|1=f^{-1}(C):=\{a\in A\ \vert\ f(a)\in C\} }}. Just as for {{M|D\in\mathcal{P}(A)}} (a subset of {{M|A}}) we use {{M|f(D)}} to denote the {{link|image|function}} of {{M|D}} under {{M|f}}, namely: {{M|1=f(D):=\{f(d)\in B\ \vert\ d\in D\} }}
−
}
+
{{Warning box|1=Writing {{M|\tilde{f}:v\mapsto f(w^{-1}(v))}} is dangerous as it may not be "''[[well-defined]]''"|2=A [[function]] (considered as a [[relation]]) of the form {{M|f:X\rightarrow Y}} must associate every {{M|x\in X}} with exactly one {{M|y\in Y}}.
−
\end{xy}
+
 
−
</math>
+
Suppose that {{M|1=w^{-1}(v)}} is [[empty-set|empty]] or contains 2 (or more!) elements, then what do we define {{M|\tilde{f} }} as?
−
|-
+
 
−
! Diagram
+
As it turns out it doesn't matter, but is really important to see why we must be so careful! This is why we require {{M|f}} to be constant on the fibres of {{M|w}}, as if we have {{M|1=w(x)=w(y)}} but {{M|f(x)\ne f(y)}} then no function composed with {{M|w}} can ever be equal to {{M|f}}!
−
|}
+
* Suppose that {{M|g:W\rightarrow Y}} is such that {{M|1=f=g\circ w}}, then {{M|1=f(x)=g(w(x))}}, and we have {{M|1=f(x)\ne f(y)}}, then:
−
Note:
+
** {{M|1=w(x)=w(y)}} so we must have {{M|1=g(w(x))=g(w(y))}}, so we must have {{M|1=f(x)=f(y)}}! A contradiction!
−
# {{M|\tilde{f} }} may be explicitly written as {{M|\tilde{f}:W\rightarrow Y}} by {{M|\tilde{f}:v\mapsto f(w^{-1}(v))}}
+
Lastly note the alternate forms of the "constant on fibres" (in the note above) is ''very'' similar to the definition of a function being [[injective]]
−
#* Or indeed {{M|1=\tilde{f}:=f\circ w^{-1} }}
+
{{Todo|Develop that last thought}}}}</ref>
−
#* 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.
+
** We may also write {{M|1=\tilde{f}=f\circ w^{-1} }} but this is a significant abuse of notation and should be avoided! It is safe to use here because of the "well-defined"-ness of {{M|\tilde{f} }}
−
# The function {{M|\tilde{f} }} is unique if {{M|w}} is [[Surjection|surjective]]
+
We may then say:
−
===Points to remember===
+
* "''{{M|f}} may be factored through {{M|w}} to {{M|\tilde{f} }}''" or "{{M|f}} descends to the quotient via {{M|w}} to give {{M|\tilde{f} }}"
 +
'''Claims: '''
 +
# {{M|\tilde{f}:W\rightarrow Y}} is given unambiguously by {{M|\tilde{f}:v\mapsto f(w^{-1}(v))}}
 +
# If {{M|w:X\rightarrow W}} is [[surjective]] then {{M|\tilde{f}:W\rightarrow Y}} is unique - the only function {{M|(:W\rightarrow Y)}} such that the diagram commutes
 +
# If {{M|f:X\rightarrow Y}} is [[surjective]] then {{M|\tilde{f}:W\rightarrow Y}} is [[surjective]] also
 +
==Caveats==
 +
The following are good points to keep in mind when dealing with situations like this:
 
* Remembering the requirements:
 
* 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.
+
*: We want to induce a function {{M|\tilde{f}:W\rightarrow Y}} such that all the information of {{M|f}} is "distilled" into {{M|w}}, notice that:
−
*: 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.
+
*:* if {{M|1=w(x)=w(y)}} then {{M|1=\tilde{f}(w(x))=\tilde{f}(w(y))}} just by composition of {{plural|function|s}}, regardless of {{M|\tilde{f} }}!
 +
*:* so if {{M|1=f(x)\ne f(y)}} but {{M|1=w(x)=w(y)}} then we're screwed and cannot use this.  
 +
*: So it is easy to see that we require {{M|1=[w(x)=w(y)]\implies[f(x)=f(y)]}} in order to proceed.
 
==Proof of claims==
 
==Proof of claims==
 +
* To see that '''if {{M|f}} is surjective so is {{M|\tilde{f} }} see my notes here:
 +
** [[Talk:Passing_to_the_quotient_(function)/Induced_is_surjective_iff_function_is_surjective]]
 +
{{Requires proof|grade=A|msg=Most of the proofs are done, I've done the surjective one like 3 times (CHECK THE TALK PAGE! SO YOU DON'T DO IT A FOURTH!) Also:
 +
* Move the proofs into sub-pages. It is just so much neater!}}
 
{{Begin Theorem}}
 
{{Begin Theorem}}
 
Claim: the induced function, {{M|\tilde{f} }} exists and is given unambiguously by {{M|\tilde{f}:v\mapsto f(w^{-1}(v))}}
 
Claim: the induced function, {{M|\tilde{f} }} exists and is given unambiguously by {{M|\tilde{f}:v\mapsto f(w^{-1}(v))}}
Line 57: Line 69:
 
'''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.
  
  
Line 69: Line 85:
 
{{End Proof}}
 
{{End Proof}}
 
{{End Theorem}}
 
{{End Theorem}}
 +
 +
==See also==
 +
* [[Passing to the quotient]] - disambiguation page
 +
* [[Equivalent conditions to being constant on the fibres of a map]]
 +
{{Todo|Factoring a map through the canonical projection of the equivalence relation it generates}}
 +
==Notes==
 +
<references group="Note"/>
 
==References==
 
==References==
 
<references/>
 
<references/>
−
{{Definition|Abstract Algebra}}
+
{{Theorem Of|Elementary Set Theory|Set Theory}}

Latest revision as of 20:49, 11 October 2016

This page is currently being refactored (along with many others)
Please note that this does not mean the content is unreliable. It just means the page doesn't conform to the style of the site (usually due to age) or a better way of presenting the information has been discovered.
This page is waiting for a final review, then this notice will be removed.
See Passing to the quotient for a disambiguation of this term.

Statement

[math] \begin{xy} \xymatrix{ X \ar[r]^w \ar[dr]_f & W \ar@{.>}[d]^{\tilde{f}}\\ & Y } \end{xy} [/math]
[ilmath]f[/ilmath] passing to the quotient
Given a function, [ilmath]f:X\rightarrow Y[/ilmath] and another function, [ilmath]w:X\rightarrow W[/ilmath][Note 1] then "[ilmath]f[/ilmath] may be factored through [ilmath]w[/ilmath]" if[1]:
  • [ilmath]f[/ilmath] is constant on the fibres of [ilmath]w[/ilmath][Note 2]

If this condition is met then [ilmath]f[/ilmath] induces a mapping, [ilmath]\tilde{f}:W\rightarrow Y [/ilmath], such that [math]f=\tilde{f}\circ w[/math] (equivalently, the diagram on the right commutes).

  • [ilmath]\tilde{f}:W\rightarrow X[/ilmath] may be given explicitly as: [ilmath]\tilde{f}:v\mapsto f(w^{-1}(v))[/ilmath][Note 3]
    • We may also write [ilmath]\tilde{f}=f\circ w^{-1}[/ilmath] but this is a significant abuse of notation and should be avoided! It is safe to use here because of the "well-defined"-ness of [ilmath]\tilde{f} [/ilmath]

We may then say:

  • "[ilmath]f[/ilmath] may be factored through [ilmath]w[/ilmath] to [ilmath]\tilde{f} [/ilmath]" or "[ilmath]f[/ilmath] descends to the quotient via [ilmath]w[/ilmath] to give [ilmath]\tilde{f} [/ilmath]"

Claims:

  1. [ilmath]\tilde{f}:W\rightarrow Y[/ilmath] is given unambiguously by [ilmath]\tilde{f}:v\mapsto f(w^{-1}(v))[/ilmath]
  2. If [ilmath]w:X\rightarrow W[/ilmath] is surjective then [ilmath]\tilde{f}:W\rightarrow Y[/ilmath] is unique - the only function [ilmath](:W\rightarrow Y)[/ilmath] such that the diagram commutes
  3. If [ilmath]f:X\rightarrow Y[/ilmath] is surjective then [ilmath]\tilde{f}:W\rightarrow Y[/ilmath] is surjective also

Caveats

The following are good points to keep in mind when dealing with situations like this:

  • Remembering the requirements:
    We want to induce a function [ilmath]\tilde{f}:W\rightarrow Y[/ilmath] such that all the information of [ilmath]f[/ilmath] is "distilled" into [ilmath]w[/ilmath], notice that:
    • if [ilmath]w(x)=w(y)[/ilmath] then [ilmath]\tilde{f}(w(x))=\tilde{f}(w(y))[/ilmath] just by composition of functions, regardless of [ilmath]\tilde{f} [/ilmath]!
    • so if [ilmath]f(x)\ne f(y)[/ilmath] but [ilmath]w(x)=w(y)[/ilmath] then we're screwed and cannot use this.
    So it is easy to see that we require [ilmath][w(x)=w(y)]\implies[f(x)=f(y)][/ilmath] in order to proceed.

Proof of claims

Grade: A
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:
Most of the proofs are done, I've done the surjective one like 3 times (CHECK THE TALK PAGE! SO YOU DON'T DO IT A FOURTH!) Also:
  • Move the proofs into sub-pages. It is just so much neater!

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[2]

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[2]

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.


See also

TODO: Factoring a map through the canonical projection of the equivalence relation it generates

Notes

  1. ↑ I have chosen [ilmath]W[/ilmath] to mean "whatever"
  2. ↑ We can state this in 2 other equivalent ways:
    1. [math]\forall x,y\in X[w(x)=w(y)\implies f(x)=f(y)][/math]
    2. [math]\forall x,y\in X[f(x)\ne f(y)\implies w(x)\ne w(y)][/math]
    See equivalent conditions to being constant on the fibres of a map for proofs and more details
  3. ↑ Of course, only bijections have inverse functions, we indulge in the common practice of using [ilmath]w^{-1}(v)[/ilmath] to mean [ilmath]w^{-1}(\{v\})[/ilmath], in general for sets [ilmath]A[/ilmath] and [ilmath]B[/ilmath] and a mapping [ilmath]f:A\rightarrow B[/ilmath] we use [ilmath]f^{-1}(C)[/ilmath] to denote (for some [ilmath]C\in\mathcal{P}(B)[/ilmath] (a subset of [ilmath]X[/ilmath])) the pre-image of [ilmath]C[/ilmath] under the function [ilmath]f[/ilmath], [ilmath]f^{-1}(C):=\{a\in A\ \vert\ f(a)\in C\}[/ilmath]. Just as for [ilmath]D\in\mathcal{P}(A)[/ilmath] (a subset of [ilmath]A[/ilmath]) we use [ilmath]f(D)[/ilmath] to denote the image of [ilmath]D[/ilmath] under [ilmath]f[/ilmath], namely: [ilmath]f(D):=\{f(d)\in B\ \vert\ d\in D\}[/ilmath]
    Caution: Writing [ilmath]\tilde{f}:v\mapsto f(w^{-1}(v))[/ilmath] is dangerous as it may not be "well-defined"
    A function (considered as a relation) of the form [ilmath]f:X\rightarrow Y[/ilmath] must associate every [ilmath]x\in X[/ilmath] with exactly one [ilmath]y\in Y[/ilmath].

    Suppose that [ilmath]w^{-1}(v)[/ilmath] is empty or contains 2 (or more!) elements, then what do we define [ilmath]\tilde{f} [/ilmath] as?

    As it turns out it doesn't matter, but is really important to see why we must be so careful! This is why we require [ilmath]f[/ilmath] to be constant on the fibres of [ilmath]w[/ilmath], as if we have [ilmath]w(x)=w(y)[/ilmath] but [ilmath]f(x)\ne f(y)[/ilmath] then no function composed with [ilmath]w[/ilmath] can ever be equal to [ilmath]f[/ilmath]!

    • Suppose that [ilmath]g:W\rightarrow Y[/ilmath] is such that [ilmath]f=g\circ w[/ilmath], then [ilmath]f(x)=g(w(x))[/ilmath], and we have [ilmath]f(x)\ne f(y)[/ilmath], then:
      • [ilmath]w(x)=w(y)[/ilmath] so we must have [ilmath]g(w(x))=g(w(y))[/ilmath], so we must have [ilmath]f(x)=f(y)[/ilmath]! A contradiction!

    Lastly note the alternate forms of the "constant on fibres" (in the note above) is very similar to the definition of a function being injective

    TODO: Develop that last thought

References

  1. ↑ Alec's own work, "distilled" from passing to the quotient (topology) which is defined by Mond (2013, Topology) and Lee (Intro to Top manifolds), by further abstracting the claim
  2. ↑ 2.0 2.1 This is my (Alec's) own work


Retrieved from "https://www.maths.kisogo.com/index.php?title=Passing_to_the_quotient_(function)&oldid=3286"