# Proof verification: Composition of onto functions is onto

$$\textbf{Statement.}$$ Let $$f : X \rightarrow Y$$ and $$g : Y \rightarrow Z$$ be functions. Assume $$f$$ and $$g$$ are onto. Then $$g \circ f : X \rightarrow Z$$ is onto.

$$\textbf{Proof.}$$ Let $$(g \circ f)(x) \in Z$$. Then $$(g \circ f)(x) = z$$ for some $$z \in Z$$. Since $$x \in X$$, and $$(g \circ f)(x) = z$$, we conclude that $$g \circ f$$ is onto.

Is this a valid proof that $$g \circ f$$ is onto? Why or why not?

• Do it more carefully. What does onto mean? Use the hypotheses. But first, review the notion of onto, and understand it well. May 2 '20 at 21:40
• @AliceFasca To prove that a function is onto, means that in the case of $f : X \rightarrow Y$ , for every element $y$ $\in$ $Y$ there exist $x$ $\in$ $X$ such that $f(x)=y$. Try proving it this way, if you still can't figure it out respond to this comment and I'll be happy to help you. May 2 '20 at 21:46

Your proof is not valid, since you are assuming what you want to prove, i.e. the existence of such an $$x$$.

Take $$z \in Z$$, you want to show that $$\exists x \in X. (g \circ f)(x)=z.$$

$$g$$ onto $$\implies \exists y \in Y. g(y) = z.$$

$$f$$ onto $$\implies \exists x \in X. f(x) = y.$$

$$\implies \exists x \in X. (g \circ f)(x)=g(f(x))=z.$$

The issue with this proof is that you didn't use the assumption of onto. Let's show an example of why this argument doesn't work. Suppose $$X = \{1,2,3\}$$, $$Y = \{4,5,6\}, Z = \{7,8,9\}$$. Let's take away the assumption of onto for now, and let $$f(x) = 4$$ for all $$x \in X$$ and $$g(y) = 7$$ for all $$y\in Y$$.

If we copy the logic of your proof to this example then we have that $$(g \circ f)(x) = z$$ for some $$z \in Z$$. We have that $$x \in X$$ and $$(g \circ f)(x) = z$$, but clearly from how they were defined $$(g \circ f)(x)$$ will always be $$7$$ no matter the choice of $$x$$ and therefore is not onto.