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.

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!

share|improve this question

4 Answers 4

up vote 4 down vote accepted

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.

share|improve this answer
    
I was going to ask if g wasn't surjective, since you're defining your codomain as (-1,1). But then I realized you could arbitrarily make it non-surjective by making the codomain something else, yet the composite func would still work. Thanks, I think I've got it! –  Carl Smotricz Sep 28 '10 at 12:19

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.

share|improve this answer

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

share|improve this answer

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

share|improve this answer

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.