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}$$
Diagram

Note:

1. $\tilde{f}$ may be explicitly written as $\tilde{f}:W\rightarrow Y$ by $\tilde{f}:v\mapsto 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.
2. 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

[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)]$$

• Note, as $w:X\rightarrow W$ is surjective, that $\exists x'\in X[w(x')=u]$

However for both $\tilde{f}$ and $\tilde{f}'$ we have the property of $$f=\tilde{f}\circ w=\tilde{f}'\circ w$$ so:

By hypothesis we have: $\forall x\in X[f(x)=\tilde{f}(w(x))=\tilde{f}'(w(x))]$ however we know:

• $\exists x'\in X[w(x')=u]$ and $\tilde{f}(u)\ne \tilde{f}'(u)$, this means:
  • $f(x')=\tilde{f}(w(x'))\ne\tilde{f}'(w(x'))$ - which contradicts the hypothesis.

However if $w$ is not surjective, then the parts of the domain on which $\tilde{f}$ and $\tilde{f}'$ disagree on may never actually come up; that is to say:

• $\forall x\in X[\tilde{f}(w(x))=\tilde{f}'(w(x))]$ as $w:X\rightarrow W$ may never take an $x\in X$ to a $z\in W$ where $\tilde{f}(z)$ and $\tilde{f}'(z)$ differ; but they could still be different functions.

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.