# Reaching unintended contradiction in proof

Problem statement, as written:

Suppose $$g\colon A\rightarrow B$$ and $$h\colon A\rightarrow B$$ are functions. Let $$C$$ be a set with more than one element. Suppose that $$f\circ g = f\circ h$$ for every function $$f\colon B\rightarrow C$$. Prove that $$g=h$$.

I can write out the “proof” I have produced thus far, but before doing, so wish to ask: does anyone else arrive at a contradiction- namely that the two distinct elements of $$C$$ turn out equal?

Attempted proof: $$C$$ is non-empty by hypothesis. If $$B$$ is empty, the theorem is vacuously true. Thus, suppose $$B$$ is non-empty. Now, if A is empty, vacuous truth again ensues, so let A be non-empty.

Thus, I take $$a \in A$$. Then $$g(a)=b_1$$ and $$h(a)=b_2$$ for some $$b_1,b_2 \in B$$ since $$g,h\colon A \rightarrow B$$. Define $$f =$${$$(b_1,c_1),(b_2,c_2)$$}. But then $$c_1 = c_2$$ since $$f \circ h = f \circ g$$.

I understand I could easily redefine $$f$$, but can’t seem to pin a definition which helps me complete the proof while also using the fact that $$C$$ must have at least two elements. Any insights?

What goes wrong in your approach is the fact that in order to be able to define $$f(b_1)$$ and $$f(b_2)$$ separately, you need to have that $$b_1\neq b_2$$ in the first place. Now, you are not defining $$f$$ properly.
An approach which uses your ideas but puts them in a better order: suppose that $$g\neq h$$. Then, there is an $$a\in A$$ such that $$g(a)\neq h(a)$$. Since $$C$$ has more than one element, we can pick two distinct elements $$c_1,c_2\in C$$. Define $$f: B \rightarrow C$$ by $$f(x)=c_1$$ if $$x\neq g(a)$$ and $$f(g(a))=c_2$$. Then, $$f(h(a))=c_1\neq c_2=f(g(a))$$, so $$f\circ h \neq f\circ g$$. This is a contradiction, so our assumption $$g\neq h$$ must be invalid, i.e., we have that $$g=h$$.
Your idea is ok but I would set it up slightly different. Consider that the statement $$\forall\;f: f\circ g = f\circ h \Rightarrow g=h$$ is equivalent to it's contraposition $$g\not= h \Rightarrow \exists\; f: f\circ g \not= f\circ h$$ So let's proof this one:
We have $$g\not= h$$ so there exists $$a\in A$$ and $$b_1, b_2 \in B, b_1 \not= b_2$$ s.t. $$g(a) = b_1, h(a) = b_2$$ Now define your $$f$$ by mentioning that $$c_1, c_2 \in C, c_1 \not= c_2$$ exist by assumption and you get by construction $$f\circ g \not= f\circ h$$ and we are done.