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$?

Question

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?

Answer 1

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

Answer 2

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 $ "

Answer 3

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! :-)