Is g(f) One-to-One if f is Not One-to-One? Prove It.

[major_maths]

1. Assume that f : A -> B and g : B -> C and that f is not one
to one. Prove that g(f) is not one to one.

2. one-to-one: x1 != x2 and f(x1) != f(x2)
not one-to-one: f(x1)=f(x2) and x1 != x2

3. The start of the proof should go as follows:

Assume f: A->B, g: B -> C, f is not 1-1, g is 1-1.
Since f is not 1-1, there exists an x1 and an x2 in the dom(f) such that f(x1) = f(x2) and x1 != x2.
Since g is 1-1, for every x1 and x2 in dom(f), if x1 != x2 then g(x1) != g(x2).

And that's as far as I got. I'm not sure if I should assume g is 1-1 since that's not explicitly in the instructions, but I don't thing g(f) could be 1-1 if g wasn't 1-1. I tried plugging f(x1) into g but I couldn't find a logical way to get to the conclusion by doing that.

 

[Dick]

You don't need to assume anything about g, do you? If f(x1)=f(x2) then g(f(x1))=g(f(x2)), yes? What does that tell you about g(f)?

 

[major_maths]

Oh. It tells me that g(f) is not one-to-one. But if that's the case, shouldn't f(x1) = f(x2)? I thought that that was the other part of the definition of not being one-to-one, that if the inputs are different then the outputs should be the same. And since f(x1) and f(x2) are the inputs in this case, shouldn't they be equal?

 

[Dick]

Oh. It tells me that g(f) is not one-to-one. But if that's the case, shouldn't f(x1) = f(x2)? I thought that that was the other part of the definition of not being one-to-one, that if the inputs are different then the outputs should be the same. And since f(x1) and f(x2) are the inputs in this case, shouldn't they be equal?

I'm really not sure I understand that. Sure, g(f) is not one-to-one. But what 'other part of not being one-to-one' are talking about? If two different inputs give the same output then it's not one-to-one. There is no other part of NOT being one-to-one.

 

[gb7nash]

Like Dick said, you don't need g to be not 1-1 to obtain the solution. From the hypothesis, there exist x₁ and x₂ such that f(x₁) = f(x₂), where f(x₁) and f(x₂) are members of B. Since g maps B to C, then g is...