Difference between revisions of "Factoring a function through the projection of an equivalence relation induced by that function yields an injection"

From Maths
Jump to: navigation, search
(Created page with "{{Stub page|grade=A*|msg=Flesh out and demote}} __TOC__ ==Statement== {{float-right|{{/Diagram}}}}Let {{M|X}} and {{M|Y}} be sets, let {{M|f:X\rightarrow Y}} be any func...")
 
m
 
(2 intermediate revisions by the same user not shown)
Line 2: Line 2:
 
__TOC__
 
__TOC__
 
==Statement==
 
==Statement==
−
{{float-right|{{/Diagram}}}}Let {{M|X}} and {{M|Y}} be [[sets]], let {{M|f:X\rightarrow Y}} be any [[function]] between them, and let {{M|\sim\subseteq X\times X}} denote the ''[[equivalence relation]]'' [[equivalence relation induced by a function|induced by a function]], recall that means:
+
{{float-right|{{/Diagram}}}}Let {{M|X}} and {{M|Y}} be [[sets]], let {{M|f:X\rightarrow Y}} be any [[function]] between them, and let {{M|\sim\subseteq X\times X}} denote the ''[[equivalence relation]]'' [[equivalence relation induced by a function|induced by the function {{M|f}}]], recall that means:
 
* {{M|1=\forall x,x'\in X[x\sim x'\iff f(x)=f(x')]}}
 
* {{M|1=\forall x,x'\in X[x\sim x'\iff f(x)=f(x')]}}
−
Then we claim we can {{link|factor|function}}<ref group="Note">{{AKA}}: {{link|passing to the quotient|function}}</ref> {{M|f:X\rightarrow Y}} through {{M|\pi:X\rightarrow \frac{X}{\sim} }}<ref group="Note">the [[canonical projection of the equivalence relation]], given by {{M|\pi:x\mapsto [x]}} where {{M|[x]}} denotes the [[equivalence class]] containing {{M|x}}</ref> to {{underline|yield an [[injective]]}} map:
+
Then we claim we can {{link|factor|function}}<ref group="Note">{{AKA}}: {{link|passing to the quotient|function}}</ref> {{M|f:X\rightarrow Y}} through {{M|\pi:X\rightarrow \frac{X}{\sim} }}<ref group="Note">the [[canonical projection of the equivalence relation]], given by {{M|\pi:x\mapsto [x]}} where {{M|[x]}} denotes the [[equivalence class]] containing {{M|x}}</ref> to {{underline|yield a unique [[injective]]}} map<ref>[[File:MondTop2016ex1.pdf]]</ref>:
 
* {{M|\tilde{f}:\frac{X}{\sim}\rightarrow Y}}
 
* {{M|\tilde{f}:\frac{X}{\sim}\rightarrow Y}}
 
Furthermore, if {{M|f:X\rightarrow Y}} is [[surjective]] then {{M|\tilde{f}:\frac{X}{\sim}\rightarrow Y}} is not only [[injective]] but [[surjective]] to, that is: {{M|\tilde{f}:\frac{X}{\sim}\rightarrow Y}} is a [[bijection]]<ref group="Note">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</ref>.
 
Furthermore, if {{M|f:X\rightarrow Y}} is [[surjective]] then {{M|\tilde{f}:\frac{X}{\sim}\rightarrow Y}} is not only [[injective]] but [[surjective]] to, that is: {{M|\tilde{f}:\frac{X}{\sim}\rightarrow Y}} is a [[bijection]]<ref group="Note">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</ref>.
−
<div style="clear:both;"></div>
+
<!--<div style="clear:both;"></div>-->
 +
==Applications==
 +
Topology:
 +
* [[Factoring a continuous map through the projection of an equivalence relation induced by that map yields an injective continuous map|If {{M|f:X\rightarrow Y}} is a continuous map then factoring it through the projection of the equivalence relation it induces yields a continuous injection]] - topological version of this theorem almost exactly. We can extend this slightly in the case {{M|f:X\rightarrow Y}} is [[surjective]]:
 +
** [[If a surjective continuous map is factored through the canonical projection of the equivalence relation induced by that map then the yielded map is a continuous bijection|If {{M|f:X\rightarrow Y}} is continuous ''and'' surjective then factoring it through the canonical projection of the equivalence relation it induces yields a continuous bijection]] - this is an extension of the previous statement, recall that when we take a surjection and apply {{link|passing-to-the-quotient|function}} we get surjection, we know from above it's injective. So now it's [[bijective]]
 
==Proof==
 
==Proof==
 +
<!--
 
{{Requires proof|grade=A*|msg=Do this now, just saving work}}
 
{{Requires proof|grade=A*|msg=Do this now, just saving work}}
 +
* Note to self - uniqueness comes from that we're [[factor (function)|factoring]] through a [[surjective]] map (namely, {{M|\pi}}), we only really have to show the result is injective.-->Outline of proof method
 +
# We must check the set up satisfies the requirements of the {{link|passing-to-the-quotient|function}} theorem (to yield {{M|\tilde{f}:\frac{X}{\sim}\rightarrow Y}}).
 +
# We apply the theorem to get {{M|\tilde{f}:\frac{X}{\sim}\rightarrow Y}}.
 +
# Next we must show {{M|\tilde{f}:\frac{X}{\sim}\rightarrow Y}} is [[injective]]
 +
===Proof body===
 +
{{Requires proof|grade=D|msg=Part 3 was the only non-trivial part. It is obvious that we can factor {{M|f}} through {{M|\pi}}, in fact:
 +
* To do so requires that "{{M|f}} be constant on the {{plural|fibre|s}} of {{M|\pi}}", ie:
 +
** {{M|1=\forall x,y\in X[\pi(x)=\pi(y)\implies f(x)=f(y)]}} (see [[Equivalent conditions to being constant on the fibres of a map]])
 +
*** But if {{M|1=\pi(x)=\pi(y)}} then {{M|x\sim y}} and by definition {{M|1=x\sim y\iff f(x)=f(y)}}! Trivial!
 +
Oh just FYI there's a commented out note and a requires-proof template at the top of the {{C|1===proof==}} heading, remove that later!}}
 +
====Step 3====
 +
We wish to show that {{M|\tilde{f}:\frac{X}{\sim}\rightarrow Y}} is [[injective]], ie: {{M|1=\forall a,b\in\frac{X}{\sim}[\tilde{f}(a)=\tilde{f}(b)\implies a=b]}}
 +
* Let {{M|a,b\in\frac{X}{\sim} }} be given.
 +
** Suppose {{M|1=\tilde{f}(a)\ne\tilde{f}(b)}} then by the nature of [[logical implication]] we do not care whether or not {{M|1=a=b}}, either way it is true, we're done in this case.
 +
** Suppose {{M|1=\tilde{f}(a)=\tilde{f}(b)}}, by the nature of logical implication we now require this leads to {{M|1=a=b}}
 +
*** By the [[surjectivity]] of {{M|\pi:X\rightarrow\frac{X}{\sim} }} we see:
 +
**** {{M|1=\exists x\in X[\pi(x)=a]}} and {{M|1=\exists y\in X[\pi(y)=b]}}
 +
***** Note that {{M|1=\tilde{f}(a)=\tilde{f}(\pi(x))}} and {{M|1=\tilde{f}(b)=\tilde{f}(\pi(y))}}, also by assumption we have {{M|1=\tilde{f}(a)=\tilde{f}(\pi(x))= \tilde{f}(\pi(y))=\tilde{f}(b)}}
 +
***** Notice also that {{M|1=f(x)=\tilde{f}(\pi(x))}} and {{M|1=f(y)=\tilde{f}(\pi(y))}} (this is the whole point of {{M|\tilde{f} }})
 +
****** So we see {{M|1=f(x)=\tilde{f}(a)=\tilde{f}(\pi(x))= \tilde{f}(\pi(y))=\tilde{f}(b)=f(y)}}, or importantly:
 +
******* {{M|1=f(x)=f(y)}}
 +
****** Recall that {{M|1=x\sim y\iff f(x)=f(y)}}, so now we know {{M|x\sim y}}
 +
***** An elementary property of {{M|\pi:X\rightarrow\frac{X}{\sim} }} is that if {{M|x\sim y}} then {{M|1=\pi(x)=\pi(y)}}<ref group="Note">{{Todo|Link to statement, this ought to be mentioned somewhere explicit on this site!}}</ref><ref group="Note">{{Todo|This can be strengthened to {{M|\iff}} surely!}}</ref>
 +
****** Explicitly, notice we have: {{M|1=\pi(x)=\pi(y)}}
 +
***** Recall that {{M|1=a=\pi(x)}} and {{M|1=b=\pi(y)}} by definition of {{M|x}} and {{M|y}}, so:
 +
****** {{M|1=a=\pi(x)=\pi(y)=b}} or more simply: {{M|1=a=b}}
 +
*** We have shown that supposing {{M|1=f(a)=f(b)}} is given then {{M|1=a=b}}
 +
** Both cases have been evaluated and the implication holds for both
 +
* Since {{M|a,b\in\frac{X}{\sim} }} were arbitrary we have shown this for all {{M|a,b\in\frac{X}{\sim} }}
 +
 
==See also==
 
==See also==
 
* [[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]]
 
* [[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]]
 +
* [[Factoring a continuous map through the projection of an equivalence relation induced by that map yields an injective continuous map]]
 +
** [[If a surjective continuous map is factored through the canonical projection of the equivalence relation induced by that map then the yielded map is a continuous bijection]]
 
==Notes==
 
==Notes==
 
<references group="Note"/>
 
<references group="Note"/>

Latest revision as of 20:24, 9 October 2016

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

Statement

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

Applications

Topology:

Proof

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

Notes

  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!

References

  1. ↑ File:MondTop2016ex1.pdf


Retrieved from "https://www.maths.kisogo.com/index.php?title=Factoring_a_function_through_the_projection_of_an_equivalence_relation_induced_by_that_function_yields_an_injection&oldid=3254"