= Factorization through a surjection
{title2=$g=h\circ f$}
For a <surjective function> $f:B\to A$ and a function $g:B\to C$, there is a unique function $h:A\to C$ with $g=h\circ f$ if and only if $g$ is constant on each <fiber of a function> of $f$. Define $h(a)$ to be the common value on $f^{-1}(a)$; it is well-defined and unique because that fiber is nonempty. This uniquely specified value requires no simultaneous arbitrary choices.
For a concrete example, restrict the <codomain> of the finite <function> above to its <image of a function> $I=\{0,1,2\}$, making $f:A\to I$ <surjective>. Define $g(a)=g(b)=5$, $g(c)=7$ and $g(d)=9$. Then $h(y)=2y+5$ on $I$ gives $g=h\circ f$: knowing the output of $f$ is enough to compute $g$. If instead $g(a)\ne g(b)$, no such $h$ can exist, because $h(f(a))=h(f(b))$ must be the same value.
The <surjectivity> assumption supplies uniqueness on the full target. If the original unused target value three were retained, the factorization would impose no condition on $h(3)$, and different extensions could agree on every actual input. Thus <factorization through a surjection> formalizes when a compressed description retains all information needed for a later calculation.
// Target: combinatorics.bigb
Back to article page
