Tao Analysis I - 3.3.5

Exercise 3.3.5

Let $f:X \mapsto Y$ and $g:Y \mapsto Z$ be functions. Show that if $g \circ f$ is injective, then $f$ must be injective. Is it true that $g$ must also be injective? Show that if $g \circ f$ is surjective, then $g$ must be surjective. Is it true that $f$ must also be surjective?

In the following, $x \in X$ and $y \in Y$.

Injectivity

We are given that $g \circ f$ is injective. Using Definition 3.3.17 for injectivity, this means

$$g(f(x)) = g(f(x')) \implies x=x'$$

For the purpose of contradiction, let's assume $f$ is not injective. This means that there is an $x$ and an $x'$, where $x \neq x'$, such that

$$f(x)=f(x')$$

That is, two different inputs for $f$ give the same output, due to $f$ not being injective. Because $g$ is a function, the same input gives the same output,

$$g(f(x))=g(f(x'))$$

This contradicts the given fact that $g \circ f$ is injective, $g(f(x))=g(f(x')) \implies x=x'$.

Thus, we have shown that if $g \circ f$ is injective, then $f$ must be injective. $\square$

We can show that $g$ doesn't have to be injective with a counter-example. Consider:

• $X=\{1,2\}$, $Y=\{1,2,3\}$, and $f(x)=x$. Here $f$ is injective.
• $Z=\{1,2\}$, and $g(1)=1$, $g(2)=2$, $g(3)=2$. Here $g$ is not injective.

Here, the composition $g \circ f$ is injective, even though $g$ is not.

Surjectivity

We are given that $g \circ f$ is surjective. By Definition 3.3.20, this means that for every $z \in Z$ there is an $x \in X$ such that $g(f(x))=z$.

Intuitively, it is clear that if $g$ is not surjective, then it doesn't hit some elements of $Z$ which contradicts the definition that $g(f(x))$ must hit every element of $Z$.

For the purpose of contradiction, let's assume $g$ is not surjective. That means there is an element $z' \in Z$ where $g(y) \neq z'$, which is true for all $y \in Y$. Now $f(x) \in Y$, so we have $g(f(x)) \neq z'$. This contradicts the given statement that $g \circ f$ is surjective.

Thus, we have shown that if $g \circ f$ is surjective, then $g$ must be surjective. $\square$

We can show that $f$ doesn't have to be surjective with a counter-example. Consider:

• $X=\{1,2,3\}$, $Y=\{1,2,3\}$, and $f(1)=1$, $f(2)=2$, $f(3)=2$. Here $f$ is not surjective.
• $Z=\{1,2\}$, and $g(x)=x$. Here $g$ is surjective.

Here, the composition $g \circ f$ is surjective, even though $f$ is not.