By johnnymath

2011-10-24 00:07:04 8 Comments

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?


@Ittay Weiss 2013-04-12 20:53:05

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.

@smanoos 2011-10-24 00:20:11

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.

@Asaf Karagila 2011-10-24 00:22:33

You can use \circ for the composition symbol rather than o.

@André Nicolas 2011-10-24 00:36:32

@smanoos: Need to show that for every $z$ there is an $x$. A few changes are needed in the answer.

@smanoos 2011-10-24 00:42:06

Right. I just did that. Thank you.

@Martin Sleziak 2011-10-26 18:30:55

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.

@smanoos 2011-10-27 03:24:07

@MartinSleziak. What I mean is that for $g\circ f$ to be onto, $g$ must always be onto. Right?

@Martin Sleziak 2011-10-27 05:47:13

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

@ged 2016-01-14 16:16:40

Mistake? "$g\circ f$ is still onto even if $f$ is not onto but $g$ is onto." Let X=Y=Z={1,2}. Let $f=x\mapsto 1$, $g=id$. $g$ is onto. But $g \circ f = f$ and it is not surjective("onto"), because there is no $(g \circ f)^{-1}(2)$

@Asaf Karagila 2011-10-24 00:16:23

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)$?

@johnnymath 2011-10-24 00:58:34

from this it follows that $h(x)$ is also surjective, as noted by the above arguments, correct?

@Asaf Karagila 2011-10-24 01:00:11

@johnnymath: It follows that $h(x)=z$, since $z$ was an arbitrary element of $Z$ we have that $h$ is indeed surjective.

Related Questions

Sponsored Content

3 Answered Questions

3 Answered Questions

Injectivity and Surjectivity of Composition Function

1 Answered Questions

2 Answered Questions

[SOLVED] Right Inverse for Surjective Function

1 Answered Questions

[SOLVED] Composition of two functions - Bijection

3 Answered Questions

[SOLVED] Behaviour of composition functions of a composite function

  • 2016-12-24 09:39:06
  • Aman Sinha
  • 52 View
  • 0 Score
  • 3 Answer
  • Tags:   functions

3 Answered Questions

[SOLVED] Onto and One to one functions given composite is also onto or one to one

  • 2015-03-24 02:54:36
  • Michealf
  • 41 View
  • 1 Score
  • 3 Answer
  • Tags:   functions

1 Answered Questions

Sponsored Content