Surjectivity of Composition of Surjective Functions

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?

Solution 1:

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.

Solution 2:

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

Solution 3:

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.