1
$\begingroup$

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?

$\endgroup$

2 Answers 2

1
$\begingroup$

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$.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .