Proof verification: Composition of onto functions is onto

504 Views Asked by At

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

2

There are 2 best solutions below

0
On BEST ANSWER

Your proof is not valid as 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 \text{ onto } \implies \exists y \in Y. g(y) = z.$$

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

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

0
On

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.