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

Revision as of 00:19, 19 November 2015

Definition

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

$f$ may be factored through $w$

if $f$ and $w$ are such that:

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

Then $f$ induces a function, $\tilde{f}$ such that

$f=\tilde{f}\circ w$ , or more simply that the following diagram commutes:

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

Note:

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

Points to remember

Remembering the requirements:
We want to induce a function $\tilde{f}:W\rightarrow Y$ - if $w(x)=w(y)$ then $\tilde{f}(w(x))=\tilde{f}(w(y))$ just by composition.

If $f(x)\ne f(y)$ we're screwed in this case. So it is easy to see that we must have $[w(x)=w(y)]\implies[f(x)=f(y)]$ otherwise we cannot proceed.

Proof of claims

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

Existence

Let

$\tilde{f}:W\rightarrow Y$ be given by:

$f:v\mapsto f(w^{-1}(v))$ - 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

$v\in W$ be given

Let

$a\in w^{-1}(v)$ be given

Let

$b\in w^{-1}(v)$ be given

We know

$\forall a\in w^{-1}(v)$ that

$w(a)=v$ by definition of

$w^{-1}$

This means

$w(a)=w(b)$

But by hypothesis

$w(a)=w(b)\implies f(a)=f(b)$

So

$f(a)=f(b)$

Thus given an

$a\in w^{-1}(v)$ ,

$\forall b\in w^{-1}[f(a)=f(b)]$

We now know (formally) that: (given a

$v$ )

$\exists y\in Y\forall a\in w^{-1}(v)[f(a)=y]$ - notice the

$\exists y$ comes first. We can uniquely define

$f(w^{-1}(v))$

Since

$v\in W$ was arbitrary we know

$\forall v\in W\exists y\in Y\forall a\in w^{-1}(v)[f(a)=y]$

We have now shown that

$\tilde{f}$ can be well defined (as the function that maps a

$v\in W$ to a

$y\in Y$ .

To calculate

$\tilde{f}(v)$ we may choose any

$a\in w^{-1}(v)$ and define

$\tilde{f}(v)=f(a)$ - we know

$f(a)$ is the same for whichever

$a\in w^{-1}(v)$ we choose.

So we know the function

$\tilde{f}:W\rightarrow Y$ given by

$\tilde{f}:x\mapsto f(w^{-1}(x))$ exists

This completes the proof^[1]

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

Uniqueness

Suppose another function exists,

$\tilde{f}':W\rightarrow Y$ that isn't the same as

$\tilde{f}:W\rightarrow Y$

That means

$\exists u\in W:[\tilde{f}(u)\ne\tilde{f}'(u)]$ (and as

$w$ is surjective

$\exists x\in X[p(x)=u]$ )

Both

$\tilde{f}$ and

$\tilde{f}'$ have the property of

$f=\tilde{f}\circ w=\tilde{f}'\circ w$ so:

by hypothesis, for all

$x$ however, we know

$\tilde{f}$ and

$\tilde{f}'$ don't agree over their entire domain, the

$p(x)$ they do not agree on violate this property (as

$f$ cannot be two things for a given

$x$ )

This contradicts that

$\tilde{f}$ and

$\tilde{f}'$ are different

This completes the proof^[1]

Notes:

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

References

↑ ^{Jump up to: 1.0} ^1.1 This is my (Alec's) own work

[Alec-1] {Jump up to: 1.0} ^1.1 This is my (Alec's) own work

[1]

@@ Line 3: / Line 3: @@
 : '''{{M|f}} may be factored through {{M|w}}'''
 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]]:
-:: <math>
+{| class="wikitable" border="1"
+|-
+| style="font-size:1.5em;" | <math>
 \begin{xy}
 \xymatrix{
@@ Line 13: / Line 16: @@
 \end{xy}
 </math>
+|-
+! Diagram
+|}
 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))}}
+#* 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]]
+===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==
 {{Begin Theorem}}
@@ Line 57: / Line 69: @@
 {{End Proof}}
 {{End Theorem}}
 ==References==
 <references/>
 {{Definition|Abstract Algebra}}

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

Revision as of 00:19, 19 November 2015

Contents

Definition

Points to remember

Proof of claims

References

Navigation menu

Views

Personal tools

Navigation

Search

Tools