If g(f(x)) is one-to-one (injective) show f(x) is also one-to-one given that $f$ is a function from A to B and $g$ a function from B to C. I've just started my Discrete math course and I'd like some help on this. I'm pretty sure we're supposed to use set theory laws to prove this. So far I know the three conditions that satisfy an injective function (sorry, having difficulties typing all this TeX markup so I'll skip that). Any help? |
|||||
|
This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.
|
Hint: suppose that $f$ is not one to one. Then there are $x \ne y$ such that $f(x)=f(y)$. Can you conculude that $g\circ f$ is not one to one? |
|||||
|
|
Or the other way around: Take $x \ne y$. Since $g \circ f$ is injective we have $g(f(x))\ne g(f(y))$, so we must have $f(x)\ne f(y)$. |
|||
|
|
|
Hence $g \circ f$ is injective then by definition it means that for all $x, y$ in the domain of $f$ (being the domain of $g \circ f$) we get $$[(g \circ f) (x) = (g \circ f)(y)] \Rightarrow x = y.$$ Assume now that $f(x) = f(y)$. Then of course $(g \circ f)(x) = g(f(x)) = g(f(y)) = (g \circ f)(y)$. By previous implication we obtain $x = y$ and hence $f$ is injective. |
|||
|
|
