Suppose f:A->B and g:B->C. Prove that if gof is one-to-one, then f is one-to-one.
I have no idea where to start. Any suggestions or comments that would help me are appreciated!
Thanks
Assume the contrary and see what happens. If f is not one-to-one, there exist such that and . Then, while , which violates the fact that g(f( )) is one-to-one. Therefore it's impossible for f to not be one-to-one.
If you need to prove IF-THEN statements, always try assuming that it's not necessarily the case, and see if it leads to a contradiction. If it does, you have found a proof.
Thanks a lot! I tried to do it by a different approach. Here's what I came up with:
PF - - -
Suppose that f(x1)=f(x2) in A. Then
g(f(x1)) = g(f(x2))
g o f(x1) = g o f(x2)
x1=x2 since g o f is one-to-one.
Because f(x1) = f(x2), then x1 = x2. Therefore we can conclude that f is one-to-one.
qed.
Is this a logical proof?
Thanks again!
Yes, this is a fine proof with only minor stylistic flaws. I would write "Suppose that f(x1)=f(x2) for some x1, x2 in A" and "Thus, f(x1) = f(x2) implies x1 = x2". I would even say this proof is a little shorter than the one in post #2. Indeed, the latter proof assumes f(x1) = f(x2) and x1 ≠ x2 and then uses f(x1) = f(x2) to conclude g(f(x1)) = g(f(x2)) and x1 = x2, which contradicts x1 ≠ x2. But it is possible not to assume x1 ≠ x2 and just say f(x1) = f(x2) ⇒ g(f(x1)) = g(f(x2)) ⇒ x1 = x2. Therefore I would not say that every implication should be proved by contradiction, though trying to come up with such a proof may be easier. Besides, direct proofs have some technical benefits (they contain computational information).