0
$\begingroup$

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?

  • 3
    HINT: Consider the properties of injectivity and surjectivity.2012-11-14

1 Answers 1

1

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?

  • 0
    @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.2012-11-14