Surjection on composed function? Helping a buddy with his "intro to math" course for CompSci. I'm afraid my 'leet math skills are already giving out, so any help would be appreciated!
If f and g are both surjective functions, then so is the composition f o g. (so far so good).
I would expect the converse to be true too: If f o g is a surjective function, does that mean f and g are surjective?
From my research so far it seems that in this case f is indeed surjective but g is not necessarily so. Can anybody explain why, please? An example would rock!
 A: The example to keep in mind is the following: take $X=\{x\}$ be a one element set, $Y=\{1,2\}$, a two elements set; and $Z=\{a\}$ a one-element set. Let $f\colon X\to Y$ be given by $f(x)=1$, and $g\colon Y\to Z$ by $g(1)=g(2)=a$. Then $g\circ f\colon X\to Y$ is bijective (one-to-one and onto), $f$ is one-to-one but not onto, and $g$ is onto but not one-to-one. So even if you know more about the composition, still the best you can conclude is that the second function is onto, but not necessarily the first.
So: if a composition $g\circ f$ is one-to-one, the best you can say is that $f$ is one-to-one; if $g\circ f$ is onto, then the best you can say is that $g$ is onto. Intuitively, in the one-to-one case, the second function can be ill-behaved outside the image of $f$, but the composition "will never know". And in the onto-case, $g$ can have a lot of redundancy, so that $f$ does not have to get to every point in the domain of $g$, just to "enough" of them.
A: It is important to consider the codomain when talking about the `surjectivity' of a function. Let us give a real-valued example of functions for now.
Let $g(x)$ be any function that maps the real number line to the interval $(-1, 1)$ (eg. sin) and let $f(x) = \frac{x}{x^2-1}$ be considered only over the interval $(-1, 1)$. Notice that $f(x)$ is continuous over this interval, and the range of f is the real line (You can graph x/(x^2-1) at wolframalpha.com to see this as well).
Thus it is not necessary that $g(x)$ be surjective. In fact, the real number line is isomorphic to any open interval.
A: Consider $f: X \rightarrow Y$, $g: Y \rightarrow Z$, then $g \circ f: X \rightarrow Z$. If it is surjective, it means that for any $z \in Z$ there exists $x \in X$ such that $(g \circ f)(x) = g(f(x)) = z$; thus, if $y = f(x)$, then $g(y) = z$, which shows that $g$ is surjective
A: For a treatment of these basic facts about what happens to injectivity and surjectivity under composition, see Section 2.5 of these lecture notes from a "transition to upper level mathematics" course that I taught twice at UGA.  Note that elsewhere in the course there were exercises asking students to prove that certain other statements which are not listed here are not always true: e.g. if $g \circ f$ is surjective, then $g$ must be surjective (as is in the notes) but $f$ need not be.  Similarly, if $g \circ f$ is injective, then $f$ must be injective (...) but $g$ need not be.
Given how fundamental and ubiquitous these results are, it's surprising that they are not always covered in standard texts.  (I guess the student is supposed to figure them out for herself, but in my experience most actual undergraduates do much better if they are exposed to these concepts in the context of an actual formal course.)
