Difference between revisions of "Passing to the quotient (function)"
(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 (→Proof of claims: Added link to surjective proof) |
||
(4 intermediate revisions by the same user not shown) | |||
Line 1: | Line 1: | ||
− | == | + | {{Refactor notice|review=true}} |
− | Given a function, {{M|f:X\rightarrow Y}} and another function, {{M|w:X\rightarrow W}} | + | : See [[Passing to the quotient]] for a disambiguation of this term. |
− | + | __TOC__ | |
− | + | ==Statement== | |
− | + | {{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>: | |
− | + | * {{M|f}} is constant on the {{plural|fibre|s}} of {{M|w}}<ref group="Note">We can state this in 2 other equivalent ways: | |
− | :: < | + | # <math>\forall x,y\in X[w(x)=w(y)\implies f(x)=f(y)]</math> |
− | + | # <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><!-- |
− | + | ||
− | + | END OF NOTE ON CONSTANT-ON-FIBRE PART | |
− | } | + | --> |
− | \ | + | 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]]). |
− | </ | + | * {{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}}. | |
− | + | ||
− | # | + | 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? |
+ | |||
+ | 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: | ||
+ | ** {{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! | ||
+ | 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}}}}</ref> | ||
+ | ** 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} }} | ||
+ | We may then say: | ||
+ | * "''{{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: | ||
+ | *: 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=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 45: | 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> | + | :: That means <math>\exists u\in W:[\tilde{f}(u)\ne\tilde{f}'(u)]</math> |
− | :: | + | ::* Note, as {{M|w:X\rightarrow W}} is [[surjective]], that {{M|1=\exists x'\in X[w(x')=u]}} |
− | ::: {{M|f(x)=\tilde{f}( | + | :: 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: |
− | + | ::: 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 58: | Line 86: | ||
{{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/> | ||
− | + | {{Theorem Of|Elementary Set Theory|Set Theory}} | |
− | {{ | + |
Latest revision as of 20:49, 11 October 2016
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
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]: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:
- [ilmath]\tilde{f}:W\rightarrow Y[/ilmath] is given unambiguously by [ilmath]\tilde{f}:v\mapsto f(w^{-1}(v))[/ilmath]
- 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
- 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.
- 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:
Proof of claims
- To see that if [ilmath]f[/ilmath] is surjective so is [ilmath]\tilde{f} [/ilmath] see my notes here:
The message provided is:
- 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]
- 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[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.
- [ilmath]\exists x'\in X[w(x')=u][/ilmath] and [ilmath]\tilde{f}(u)\ne \tilde{f}'(u)[/ilmath], this means:
- By hypothesis we have: [ilmath]\forall x\in X[f(x)=\tilde{f}(w(x))=\tilde{f}'(w(x))][/ilmath] however we know:
- 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.
- That means [math]\exists u\in W:[\tilde{f}(u)\ne\tilde{f}'(u)][/math]
This completes the proof[2]
- 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.
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
- ↑ I have chosen [ilmath]W[/ilmath] to mean "whatever"
- ↑ We can state this in 2 other equivalent ways:
- [math]\forall x,y\in X[w(x)=w(y)\implies f(x)=f(y)][/math]
- [math]\forall x,y\in X[f(x)\ne f(y)\implies w(x)\ne w(y)][/math]
- ↑ 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
- 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:
References
- ↑ 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.0 2.1 This is my (Alec's) own work
- Todo
- Refactoring
- Refactoring (unknown grade)
- Refactoring pages pending final review
- Pages requiring proofs
- Theorems
- Theorems, lemmas and corollaries
- Elementary Set Theory Theorems
- Elementary Set Theory Theorems, lemmas and corollaries
- Elementary Set Theory
- Set Theory Theorems
- Set Theory Theorems, lemmas and corollaries
- Set Theory