Passing to the quotient (function)

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:

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

Note:

1. $\tilde{f}$ may be explicitly written as $\tilde{f}:W\rightarrow Y$ by $\tilde{f}:v\mapsto f(w^{-1}(v))$
2. The function $\tilde{f}$ is unique if $w$ is surjective

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

[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

Notes:

1. 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.