# Help with proving a one-to-one function.

• Aug 31st 2013, 06:07 PM
acberry
Help with proving a one-to-one function.
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
• Aug 31st 2013, 06:19 PM
SworD
Re: Help with proving a one-to-one function.
Assume the contrary and see what happens. If f is not one-to-one, there exist $x,y \in A$ such that $f(x) = f(y)$ and $x \neq y$. Then, $g(f(x)) = g(f(y))$ while $x \neq y$, 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.
• Sep 1st 2013, 10:29 AM
acberry
Re: Help with proving a one-to-one function.
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!
• Sep 1st 2013, 10:34 AM
SworD
Re: Help with proving a one-to-one function.
Yes, it is.
• Sep 1st 2013, 10:46 AM
emakarov
Re: Help with proving a one-to-one function.
Quote:

Originally Posted by acberry
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?

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