2
$\begingroup$

Let $f \colon A \to B$ be a surjection and $g \colon B \to C$ be such that $g\circ f$ is an injection. Prove that both $f$ and $g$ are injections.

Since $f$ is onto then there exists a $f(a)$ such that $f(a)=b$, for all $b\in B$. Now since $g\circ f$ is one-one then for $a,a'\in A$ we get that $ g(f(a)) \ne g(f(a'))$ implies that $f(a)\ne f(a')$. Then since $f(a)\ne f(a') \implies b=f(a)\ne f(a')=b'$ implies that $b\ne b'$ hence $g$ is also one-one.

I can't find a way to show that $f$ is one-one.

Can I just say that since $b\ne b'$ and $f$ is onto then all of $b$ has an $a$ such that $f(a)=b$ but $f(a)\ne f(a')$ (which I proved above) thus $a\ne a'$ therefore $f$ is one-one?

$\endgroup$

2 Answers 2

2
$\begingroup$

$f$ is injection: Suppose $a, a' \in A$ and $f(a) = f(a')$. Applying $g$ to both side gives $g\circ f(a) = g\circ f(a')$. Since $g\circ f$ is injection, we conclude that $a = a'$. This shows that $f$ is injection. (Note that this is independent from the hypothesis that $f$ is surjection.)

$g$ is injection: Suppose $b, b' \in B$ and $g(b) = g(b')$. Since $f$ in surjection, there exists $a, a' \in A$ such that $b = f(a)$ and $b' = f(a')$. Hence we get $g\circ f(a) = g(b) = g(b') = g\circ f(a')$. Since $g\circ f$ is injection, $a = a'$ follows. Applying $f$ to both side gives $b = f(a) = f(a') = b'$. This shows that $g$ in injection.

Edited: Your proof in the question is wrong. To show the injectivity of $h$, you have to show that $$ h(x) = h(y) \implies x = y$$ as I did above or its contoraposition $$ x \neq y \implies h(x) \neq h(y) $$ for all $x$ and $y$. So your proof should be

  1. Assume $b \neq b'$.
  2. There exists $a, a' \in A$ such that $b = f(a)$ and $b' = f(a')$ since $f$ is surjection.
  3. Hence $f(a) \neq f(a')$.
  4. $a \neq a'$. Otherwise $f(a) = f(a')$, contradiction.
  5. $g \circ f(a) \neq g \circ f(a')$ since $g \circ f$ is injection.
  6. Therefore $g(b) \neq g(b')$.
  7. Conclude $g$ is injection.

  1. Assume $a \neq a'$.
  2. $g \circ f(a) \neq g \circ f(a')$ since $g \circ f$ is injection.
  3. Hence $f(a) \neq f(a')$. Otherwise $g \circ f(a) = g \circ f(a')$, contradiction.
  4. Conclude $f$ is injection.
$\endgroup$
7
  • $\begingroup$ Thanks. Can you tell me what I did wrong with my proof? And why did you say that since $f$ is onto then $a, a' \in A$ s.t $b=f(a)$ and $b'=f(a')$? I asked that because cant $f(a)$ also equal $b'$? $b'=f(a)$? $\endgroup$
    – Tom
    Commented Sep 14, 2013 at 7:49
  • $\begingroup$ @Tom I edited my answer a little to answer your second question. I hope it makes sense to you. $\endgroup$
    – Orat
    Commented Sep 14, 2013 at 7:58
  • $\begingroup$ @Tom I added my answer paragraphs which mentioned where your proof was wrong. It seems to me you misunderstand the definition of injection. $\endgroup$
    – Orat
    Commented Sep 14, 2013 at 8:20
  • $\begingroup$ I ended up with $b \neq b'$ because $f(a) = b$ and $f(a')=b'$ and since $f(a)\ne f(a')$ then I implied $b \neq b'$. Should I have said that since $g\circ f$ is an one-one then $g\circ f(a) \neq g\circ f(a')$ implies that $a\ne a'$ thus $f$ is one-one? $\endgroup$
    – Tom
    Commented Sep 15, 2013 at 0:43
  • $\begingroup$ @Tom Sorry, what you said is right --- ending up with $b \neq b'$ is nothing wrong. But to get $f(a) \neq f(a')$, you have to assume $a \neq a'$ first. Besides, injectivity of $g \circ f$ doesn't imply $g \circ f(a) \neq g \circ f(a) \implies a \neq a'$. In general, $P \implies Q$ is not equivalent of $Q \implies P$. $\endgroup$
    – Orat
    Commented Sep 15, 2013 at 2:15
0
$\begingroup$

if $f$ is not one-to-one there exists $a\neq a'$ such that $f(a)=f(a')$ then $g(f(a))=g(f(a'))$ because $g$ is a function, but $g\circ f$ is one-to-one so $a=a'$ in contraddiction with hypotesis.

$\endgroup$
1
  • $\begingroup$ Thanks that is definitely a more convenient way to see that. Can you tell me what I did wrong with my proof? $\endgroup$
    – Tom
    Commented Sep 14, 2013 at 7:52

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .