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

1. ## 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

2. ## 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 $\displaystyle x,y \in A$ such that $\displaystyle f(x) = f(y)$ and $\displaystyle x \neq y$. Then, $\displaystyle g(f(x)) = g(f(y))$ while $\displaystyle 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.

3. ## 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!

Yes, it is.

5. ## Re: Help with proving a one-to-one function.

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