Proof that for any function $f:A\to B$ there exists a set $C$ and two functions $g:A\to C,h:C\to B$ not equal to $f$ such that $f=h\circ g$? 
Proof that for any function $f:A\to B$ there exists a set $C$ and two functions $g:A\to C,h:C\to B$ not equal to $f$ such that $f=h\circ g$?

I really have no clue how to tackle this problem. I have strong evidence to conclude this is true, but I don't know how to prove it.
I think this may be solved using category theory, knowing if in the category Set, for any morphism $f:A\longrightarrow B$, there are two morphisms such that their composition equals $f$. The axioms for category tells the opposite, that for any two morphism there exists their composition morphism, but is it true the other way around in this context? And if this is not true, what condition does $f$ need to have in order to not have this property?
 A: Pick $x \in A^c $ and define $C= A \cup \{x\} $ and $g (y) = y$  for all  $ y \in A$. and define $h: A \cup \{x\} \to B$ with $h = f$ on $A$,  and $h(x) = f(a)$ for some $a \in A$. Then observe that $f = hog$.
"Note that you always can assume $A$ is proper subset of a bigger set, this guarantees that $ A^c  \neq  \emptyset $ "
A: Assuming that $A\ne\varnothing$, you can let
$$ C = \{\; \{\{a\},\{A,B\}\} \mid a \in A \} $$
Then as a matter of (mainstream) set theory no element of $C$ can equal an element of $A$ or $B$.
Let $g$ be the natural bijection $A\to C$ and $h = f \circ g^{-1}$.
A: Since this is tagged category-theory and neither of the answers provided
work in an arbitrary category, let's try once more with the constraint
that the category has a terminal object and products --which is essentially
what the other solutions utilise.
Given arrow $f : A → B$, we seek a new pair $g : A → C, h : C → B$.


*

*Let $C = A × 1$ --note that in ℯ, 1 is any singleton set such as 1 = {*}.

*Then we naturally have $A → C = A × 1$ by $Id × !$ where $! : X → 1$ is the unique
map to the terminal object. 
So take $g : A → A×1$ to be $Id × !$, which in ℯ acts $a ↦ (a, *)$.

*Now for $C = A × 1 → B$ we simply ignore the terminal object and apply $f$,
that is $h = f ∘ proj_1$, which in ℯ acts $(x, y) ↦ f\,x$.
Hence we have produced new items $C, g, h$ and it remains to check that
$f = h ∘ g$.
$\def\stepWith#1#2{ \\ #1 & \quad \color{green}{\{\;\text{#2}\;\}} \\ & }\def\step#1{ \stepWith{=}{#1} }\newenvironment{calc}{\begin{align*} & }{\end{align*}}$
Indeed,
\begin{calc}
h ∘ g
\step{Definitions}
(f ∘ proj₁) ∘ (Id × !)
\step{ Composition is associtive }
f ∘ (proj₁ ∘ (Id × !))
\step{ Projection on products }
f ∘ Id
\step{ Identity maps }
f
\end{calc}
Neato! :-)
