Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Possible Duplicate:
Injective and Surjective Functions

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?

share|cite|improve this question

marked as duplicate by Ross Millikan, t.b., Akhil Mathew Mar 20 '11 at 15:40

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.

Also, if any moderators can (since I can't add new tags) put "composite functions", "injective functions" and "one-to-one functions" as tags for me that would be great, thanks! – meiryo Mar 20 '11 at 13:57
This is not really discrete mathematics, as discreteness is not used in the proof. – Ross Millikan Mar 20 '11 at 15:17
up vote 3 down vote accepted

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?

share|cite|improve this answer
Still not too sure what you mean, can you elaborate further? – meiryo Mar 20 '11 at 14:28
anon is suggesting that you argue by contraposition, in other words show that if f is not injective then g(f) isn't either. If you want to show g(f) isn't injective you need to find two distinct points in A that g(f) sends to the same place. Anons comment will help you do that. – Jason Knapp Mar 20 '11 at 15:32

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

share|cite|improve this answer
Does this not assume $g$ is injective? – Anthony Peter Nov 9 '14 at 21:29
@AnthonyPeter: No, this is just saying that that if $g(a)\neq g(b)$ then we must have $a\neq b$. – Michalis Nov 10 '14 at 12:13

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.

share|cite|improve this answer

Not the answer you're looking for? Browse other questions tagged or ask your own question.