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

Printable View

- Aug 31st 2013, 07:07 PMacberryHelp 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, 07:19 PMSworDRe: Help with proving a one-to-one function.
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. - Sep 1st 2013, 11:29 AMacberryRe: 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, 11:34 AMSworDRe: Help with proving a one-to-one function.
Yes, it is.

- Sep 1st 2013, 11:46 AMemakarovRe: Help with proving a one-to-one function.
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).