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