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.

Suppose we have two functions, $f:X\rightarrow Y$ and $g:Y\rightarrow Z$. If both of these functions are onto, how can we show that $g\circ f:X\rightarrow Z$ is also onto?

share|improve this question
1  
It follows simply from the definitions of composition of functions and surjectivity (being onto). Do you know them? –  Damian Sobota Oct 24 '11 at 0:15
3  
Typo, the last one should be $X\to Z$. If $z\in Z$, $z=g(y)$ for some $y$, and $y=f(x)$ for some $x$. It follows that $\dots$. –  André Nicolas Oct 24 '11 at 0:15
2  
Hi jonnymath, I removed the functional analysis tag and replaced it by functions, because that seemed like a better fit for your question. Functional analysis is usually taught at the advanced undergraduate level. –  t.b. Oct 24 '11 at 0:17
add comment

3 Answers

up vote 3 down vote accepted

Note that $(g\circ f)(x)=g(f(x))$. So if $f$ is onto, then it means for all $y \in Y$ there exists an $x \in X$ such that $ y=f(x)$. Since $g$ is onto, it also meas that for all $z \in Z$ there exists a $ y \in Y$ such that $g(y)=g(f(x))=z$. Thus, for all $z\in Z$ there exists an $x \in X$ such that $g(f(x))=z$. Hence $g\circ f$ is onto.

One important point you should know from the construction above is that $g\circ f$ is still onto even if $f$ is not onto but $g$ is onto. In other words $g$ must necessarily be onto for $g\circ f$ to be onto.

share|improve this answer
1  
You can use \circ for the composition symbol rather than o. –  Asaf Karagila Oct 24 '11 at 0:22
    
Thank you for the correction. –  smanoos Oct 24 '11 at 0:24
    
@smanoos: Need to show that for every $z$ there is an $x$. A few changes are needed in the answer. –  André Nicolas Oct 24 '11 at 0:36
1  
You wrote: One important point you should know from the construction above is that $g\circ f$ is still onto even if $f$ is not onto but $g$ is onto. This is not true - just take $g$ and identity function and $f$ which is not onto. But guessing from what you wrote after (In other words...), this is not what you meant. –  Martin Sleziak Oct 26 '11 at 18:30
1  
@smanoos Yes, that's correct. But the sentence before is not, if I understand it correctly. I understood this sentence as: $g$ is onto $\Rightarrow$ $g\circ f$ is onto. (No conditions on $f$ here.) \\Perhaps you wanted to write something like: One important point you should know from the construction above is that if $g\circ f$ is onto then $g$ is onto, even if $f$ is not onto. (In this case I wanted to avoid editing your post, since this could lead to me changing your intentions.) –  Martin Sleziak Oct 27 '11 at 5:47
show 2 more comments

The important thing to learn when first studying mathematics is always to follow carefully and slowly with the definitions and theorems that you have seen in class.

Definition: Let $f\colon A\to B$, we say $f$ is surjective if for every $b\in B$ there is some $a\in A$ such that $f(a)=b$.

Definition: Let $f\colon A\to B$ and $g\colon B\to C$ functions, we define the composition $g\circ f$ as the function: $(g\circ f)(x) = g(f(x))$.

Of course it is perfectly possible that you were given different definitions in the course/book/etc. from which you study set theory. If indeed these are not the definitions you can try and prove the claim from the definitions you were given, or try to prove that the definitions above are the same.


Now suppose $f\colon X\to Y$ and $g\colon Y\to Z$ are two surjective functions, let $h$ be the composition, that is $h=g\circ f\colon X\to Z$. If we want to show that $h$ is surjective then we need to take an element $z\in Z$ and show that for some $x\in X$ we have $h(x)=z$.

Since we also know that $f,g$ are surjective we can pick some $y\in Y$ such that $g(y)=z$ and some $x\in X$ such that $f(x)=y$.

Now what can we say about $h(x)$?

share|improve this answer
    
from this it follows that $h(x)$ is also surjective, as noted by the above arguments, correct? –  johnnymath Oct 24 '11 at 0:58
    
@johnnymath: It follows that $h(x)=z$, since $z$ was an arbitrary element of $Z$ we have that $h$ is indeed surjective. –  Asaf Karagila Oct 24 '11 at 1:00
add comment

To present a different approach to the solution: Say that a function $f:A\to B$ is right cancelable if for all functions $g,h:B\to X$, if $g\circ f = h\circ f$ then $g=h$.

Exercise: prove that a function $f$ is surjective if, and only if, it is right cancelable.

Now if $f:A\to B$ and $f':B\to C$ are surjective, then each is right cancelable. So now, given $g,h:C\to X$, if $g\circ (f'\circ f)=h\circ (f'\circ f)$ then $(g\circ f')\circ f=(h\circ f')\circ f$ and thus $g\circ f'=h\circ f'$ and thus $g=h$. In short, the composition of right cancelable functions is (trivially) right cancelable. And this proves that the composition of surjective functions is surjective.

Interestingly, the concept of left cancelable function (defined in the obvious way) corresponds precisely to an injective function. This reveals an non-trivial duality between the concept of surjective function and injective function.

share|improve this answer
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.