Take the 2-minute tour ×
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.

Is this a valid proof for the following?

Let $f$ and $g$ be functions such that $f: A \to B$ and $g: B \to C$. Prove or disprove that if $g(f(x))$ is surjective, then $g$ is surjective.

To show that $g$ is onto, it must be shown that for every element $c \in C$, $g(b) = c$ for some $b \in B$. Since we know that $g(f(x))$ is onto, then for every element $c \in C$, $g(f(a)) = c$ for some $a \in A$, which means that for every element $b \in B$, $f(a) = b$ for some $a \in A$.

That is, $g(f(a)) = g(b) = c$.

Therefore, we have shown that $g$ is onto $C$.

share|improve this question
1  
yes, that's a valid proof. –  user20266 Dec 11 '11 at 18:33
2  
No, that's not a valid proof. Specifically, $f$ does not have to be surjective which you assert in your "for every element $b\in B,$ $f(a) = b$ for some $a\in A$. –  Jason DeVito Dec 11 '11 at 18:35
    
ouch, did not look accurately enough. Only noted Krysten found the counter counter image which is needed... –  user20266 Dec 11 '11 at 18:43
add comment

2 Answers

up vote 3 down vote accepted

The idea is solid, but you have a flawed reasoning at the end there.

If $g$ is surjective it does not necessarily means that $f$ is surjective. Consider the case:

  • $A=\{0\}$, $B=\{1,2\}$ and $C=\{3\}$.
  • $f(0)=1$ and $g(1)=g(2)=3$.

The composition is surjective and indeed so is $g$, but not every $b\in B$ is $f(a)$ for some $a\in A$.


To correct your proof, note that it is not needed that $f$ is surjective, but rather that for every $c\in C$, there is some $a\in A$ such that $f(a)$ is sent to $c$ by $g$ (that is $g(f(a))=c$). This is enough to show that $g$ is surjective even if restricted to $\operatorname{Rng}(f)$.

share|improve this answer
    
thanks. this explanation really helped. –  Krysten Dec 11 '11 at 19:49
    
@Krysten: You're welcomed. –  Asaf Karagila Dec 11 '11 at 20:30
add comment

It is true that $g$ is surjective, but there are flaws in your argument. You are claiming that $f$ is surjective when you say "for every element $b \in B$, $f(a)=b$ for some $a \in A$." This is not true in general. What is true is that for any $c \in C$ there exists some $a$ such that $g(f(a)) = c$. Then $f(a) \in B$, and if we let $x = f(a)$, then $g(x) = g(f(a)) = c$. So $g$ is surjective.

share|improve this answer
    
thanks. this makes a lot of sense –  Krysten Dec 11 '11 at 19:50
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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