# Cancellation laws for function composition

Okay I was asked to make a conjecture about cancellation laws for function composition. I figured it would go something like "For all sets $A$ and functions $g: A \rightarrow B$ and $h: A \rightarrow B$, $f \circ g = f \circ h$ implies that $g=h$."

I'm pretty sure $g=h$ isn't always true, but is there a property of $f$ that makes this true?

-
HINT: Consider the properties of injectivity and surjectivity. –  Ittay Weiss Nov 14 '12 at 6:10

Notice that if there are distinct $b_1,b_2\in B$ such that $f(b_1)=f(b_2)$, you won’t necessarily be able to cancel $f$: there might be some $a\in A$ such that $g(a)=b_1$ and $h(a)=b_2$, but you’d still have $(f\circ g)(a)=(f\circ h)(a)$. Thus, you want $f$ to be injective (one-to-one). Can you prove that that’s sufficient?
Okay so if $f$ is one-to-one, then for all sets A and functions g:A→B and h:A→B, f∘g=f∘h implies that g=h. I'm having trouble coming up with a proof for this. I guess that for every $c \in C$ there is at most one $b \in B$ such that $f$$b$$=f$$a$$$. I'm not sure where to go after that though. –  GAtechWizard Nov 14 '12 at 14:14
@GAtechWizard: Do the usual thing: suppose that $g\ne h$. Then there is some $a\in A$ such that $g(a)\ne h(a)$. Let $b_1=g(a)$ and $b_2=h(a)$. Then $$f(b_1)=f\big(g(a)\big)=(f\circ g)(a)=(f\circ h)(a)=f\big(h(a)\big)=f(b_2)\;,$$ contradicting the assumption that $f$ is one-to-one. –  Brian M. Scott Nov 14 '12 at 14:21