Thread: compostion of functions question - Discrete Math

Let g: X -> Y and f: Y -> Z be functions. Justify your answer to each question below by giving either a proof or a counter example.

a) If f and f o g are one-to-one, does it follow that g is one-to-one?

b) If g and f o g are one-to-one, does it follow that f is one-to-one?

Any help would be much appreciated, thanks.

Originally Posted by rusty26

Let g: X -> Y and f: Y -> Z be functions. Justify your answer to each question below by giving either a proof or a counter example.

a) If f and f o g are one-to-one, does it follow that g is one-to-one?

Suppose g is not 1-1, then there exist x1 != x2 in X such that g(x1)=g(x2),
so as f is 1-1, f o g(x1)=f o g(x2), with x1 != x2, which contradicts f o g
being 1-1. Hence g must be 1-1.

b) If g and f o g are one-to-one, does it follow that f is one-to-one?

If g maps X onto Y yes (by a similar argument to the above), but not otherwise.

Let:

X={x1, x2, x3}, Y={y1, y2, y3, y4}, Z={z1, z2, z3, z4},

and:

g(x1)=y1, g(x2)=y2, g(x3)=y3,

f(y1)=z1, f(y2)=z2, f(y3)=z3, f(y4)=z3.

Then f o g is 1-1, but f is not 1-1.

RonL