# Every function $f$ can be factored into $f = i \circ s$, with $i$ injective and $s$ surjective

As in the title, if $$X$$ and $$Y$$ are two arbitrary sets and $$f:X \to Y$$, my proof was by taking $$x_1 \sim x_2 \iff f(x_1) = f(x_2),$$ $$s: X \to X/\sim$$ to be the canonical surjection of $$X$$ into the quotient set of $$X$$ wrt $$\sim$$, i.e. $$s(x) = \{z \in X: f(z) = f(x)\}$$ and $$i: X/\sim \to Y$$ to be the map defined by $$i(Z) = f(z)$$, for any $$z$$ in $$Z$$. Since all $$z$$ in an equivalence class are mapped to the same element of $$Y$$, $$i$$ is well defined.

Is the above correct?

The proposed answer however was another one, namely $$s: X \to f(X)$$ and $$i: f(X) \to Y$$ defined as $$s(x) = f(x)$$ and $$i(w) = w$$.

If my solution was correct, which choice is more "canonical"?

Still, if my solution is correct, to what extent can we say that the decomposition into injective and surjective is "unique"? I would say that $$X / \sim$$ and $$f(X)$$ are "isomorphic" because of something like the first isomorphism theorem in linear algebra..

• I have to say I like more your solution, the proposed answer is just restricting the range of the function, and then using the Inclusion map. Although your answer is basically the same: (I use $s_2$ for the proposed $s$) for each $x∈X$ we have $s_2^{-1}(x)=f^{-1}(x)=[x]_\sim$. So the difference is that while you took the preimages, the proposed solution took the value. The 2 solutions describe the same thing
– ℋolo
Sep 30 '19 at 8:58
• I was a bit puzzled because I did not find my solution anywhere in the web..
– Tom
Sep 30 '19 at 9:02
• But eg wiki en.wikipedia.org/wiki/Bijection,_injection_and_surjection mentions the "proposed" answer and not "mine"..
– Tom
Sep 30 '19 at 9:03
• I am not sure why Wiki chose that way, but, like I said, both ways describe the same thing: going from $x$ to something that describe uniquely $f(x)$, and from there to $f(x)$ itself(note that $f(x)$ is also a way to describe uniquely $f(x)$)(Also note that $|X/\sim|=|f(X)|$ as well as that for every algebra with underline set $f(X)$, there is canonical isomorphic algebra with underline set of $X/\sim$, the canonical bijection between the 2 is the isomorphism)(algebra over a set $A$, is the set $A$ is operators)
– ℋolo
Sep 30 '19 at 12:47

Your answer is correct, assuming by $$i(Z) = f(z)$$, you mean that $$i$$ maps the equivalence class of $$z$$ under $$\sim$$ to $$f(z)$$ (you may want to make this more clear).

One thing to note is that your answer and the answer provided in the solutions are very similar. We can naturally associate the equivalence classes of $$\sim$$ uniquely to elements of the range of $$f$$. If we make this identification, then your answers are really the same.

This lends credence to the idea that this decomposition might be somewhat "unique" in some sense. Let's set up the problem. Suppose $$f : X \to Y$$ satisfies $$f = i_1 \circ s_1 = i_2 \circ s_2$$ where $$s_k : X \to Z_k$$ are surjective and $$i_k : Z_k \to Y$$ are injective, for $$k = 1, 2$$. We can actually show that there is a bijection $$\phi : Z_1 \to Z_2$$ such that $$s_2 = \phi \circ s_1$$ and $$i_1 = i_2 \circ \phi$$.

By this, I mean that there is some $$\phi$$ which provides us a rule for identifying elements of $$Z_1$$ and $$Z_2$$ in such a way that, after identification, the decompositions $$i_1 \circ s_1$$ and $$i_2 \circ s_2$$ become the same decomposition.

So, let's construct this $$\phi$$. As $$i_k$$ is injective, there must exist some left inverses $$j_k : Y \to Z_k$$ (i.e. $$j_k \circ i_k : Z_k \to Z_k$$ is the identity map on $$Z_k$$). Similarly, as $$s_k$$ is surjective, there must exist some right inverses $$t_k : Z_k \to X$$ (i.e. $$s_k \circ t_k : Z_k \to Z_k$$ is the identity map). Define $$\phi = j_2 \circ i_1 : Z_1 \to Z_2.$$ Then $$\phi \circ (s_1 \circ t_2) = j_2 \circ (i_1 \circ s_1) \circ t_2 = j_2 \circ f \circ t_2 = (j_2 \circ i_2) \circ (s_2 \circ t_2),$$ which is the identity on $$Z_2$$. We need to show that $$(s_1 \circ t_2) \circ \phi = s_1 \circ t_2 \circ j_2 \circ i_1$$ is the identity on $$Z_1$$. This is a little less straight forward. \begin{align*} (s_1 \circ t_2) \circ \phi &= (j_1 \circ i_1) \circ (s_1 \circ t_2) \circ \phi \circ (s_1 \circ t_1) \\ &= j_1 \circ (i_1 \circ s_1) \circ t_2 \circ j_2 \circ (i_1 \circ s_1) \circ t_1 \\ &= j_1 \circ f \circ t_2 \circ j_2 \circ f \circ t_1 \\ &= j_1 \circ (i_2 \circ s_2) \circ t_2 \circ j_2 \circ (i_2 \circ s_2) \circ t_1 \\ &= j_1 \circ i_2 \circ s_2 \circ t_1 \\ &= (j_1 \circ i_1) \circ (s_1 \circ t_1), \end{align*} which is the identity on $$Z_1$$, as required. Therefore, $$\phi$$ is invertible with inverse $$s_1 \circ t_2$$.

Obviously, by construction, we have $$i_2 \circ \phi = (i_2 \circ j_2) \circ i_1 = i_1.$$ Our proof also came with an expression for $$\phi^{-1}$$ which we can also use: $$\phi^{-1} \circ s_2 = s_1 \circ (t_2 \circ s_2) = s_1 \implies s_2 = \phi \circ s_1$$ as required.

• Perfectly clear - thank you!
– Tom
Sep 30 '19 at 12:12

Your approach is fine. The relation $$\sim$$ is an equivalence relation on $$X$$ and the quotient set $$X/\sim$$ gives rise to the surjective mapping $$f_1:X\rightarrow X/\sim : x\mapsto \bar x$$ where $$\bar x=\{x'\in X\mid x\sim x'\}$$ is the equivalence class of $$x$$.

Moreover, the mapping $$f_2:X/\equiv \rightarrow f(X): \bar x\mapsto f(x)$$ is injective. This mapping is well-defined, since if $$x\sim x'$$, then $$f(x)=f(x')$$.

Saying ''isomorphic'' is a bit too much, since there is underlying algebraic structure (such as vector spaces).

• in the second line "gives rise to the injective mapping".. you meant surjective?
– Tom
Sep 30 '19 at 8:56
• Try \sim which gives $\sim$ Sep 30 '19 at 8:56