2
$\begingroup$

I realize that there has already been an answer to this problem. But I want to know if my proof was correct. Thank you for your time.

Problem

Suppose A,B, and C are sets and $f: A \rightarrow B$

Suppose that C has at least two elements, and for all functions $g$ and $h$ from B to C, if $g \circ h = h \circ f$ then $g = h$. Prove that $f$ is onto.

Proof

Suppose f is not onto. Then there is $b_1$ such that for all $a \in A$, $f(a) \neq b_1$. Suppose $(b_1, c_1) \in g$ and $(b_1, c_2) \in h$. For the assumption that $g \circ h = h \circ f$ then $g = h$ to be true, $(b_1, c_1) = (b_1, c_2)$ whenever $g \circ f = h \circ f $.

Assume $g \circ f = h \circ f$. Since $b_1 \notin Ran(f)$, $(a,c_1) \notin g \circ f$ and $(a,c_2) \notin h \circ f$. This means that as long as there are at least two elements in C, it is possible that $(b_1, c_2) \neq (b_1, c_2)$ while $g \circ f = h \circ f$. (Even if $c_1 \neq c_2$, it can still be true that $g \circ f = h \circ f$ since $c_1$ and $c_2$ are not in the range of $g \circ f$ and $h \circ f$.)

This is a contradiction, hence $f$ is onto.

$\endgroup$
0
$\begingroup$

After the end of the second sentence, your first paragraph is a mess. There is no $g$ or $h$ defined or assumed yet, so you can’t talk about them, and certainly not talk about pairs in $g$ or in $h$. The final sentence “For the assumption...” is also incorrect as written and does not make much sense. That whole thing needs to be removed.

Second paragraph also starts badly. Who are $c_1$ and $c_2$? Who are $g$ and $h$? They are not given, so you can’t take them as given. Finally, any ‘proof’ that ends with “It’s possible that” or “it can still be true” is not really a proof. You aren’t proving something, you are just suggesting that it might be the case that something happens. That’s not a proof. In a proof, you are supposed to show that something does happen, unequivocally. Until you actually exhibit it happening, you are not proving anything.

So I would say that this attempt is not correct.

What you want to do after your first sentence is to actually construct two functions $g,h\colon B\to C$ with the properties that $g\circ f = h\circ f$, and $g\neq h$. That will give a you proof by contrapositive, rather than one by contradiction.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.