# Given $f$ and $g$, prove/disprove whether $g \circ f$ is injective/surjective

Given for any sets $X, Y, Z$ and any maps $f:X \to Y$ and $g:Y \to Z$, prove/ disprove the following statements. If the statement is true, give a proof of the statement. If the statement is false, give a proof of the negation the statement.

1. If $f$ is injective and $g$ is injective, then $g \circ f$ is injective.
2. If $f$ is injective and $g$ is surjective, then $g \circ f$ is injective.
3. If $f$ is surjective and $g$ is injective, then $g \circ f$ is injective.
4. If $f$ is injective and $g$ is surjective, then $g \circ f$ is surjective.
5. If $f$ is surjective and $g$ is injective, then $g \circ f$ is surjective.
6. If $f$ is surjective and $g$ is surjective, then $g \circ f$ is surjective.

I know that only statement 1 and statement 6 are true, and all the other statements are false.

Proof of Statement 1

To prove: $\forall x_1,x_2 \in X, (g \circ f)(x_1)=(g \circ f)(x_2) \Rightarrow x_1=x_2$

Since both $f$ and $g$ are injective, i.e.

$\forall x_1,x_2 \in X,f(x_1)=f(x_2) \Rightarrow x_1=x_2\\ \forall y_1,y_2 \in Y, g(y_1)=g(y_2) \Rightarrow y_1=y_2$

Suppose $x_1,x_2 \in X$ such that $(g \circ f)(x_1)=(g \circ f)(x_2)$,

By definition of composite maps, $g(f(x_1))=g(f(x_2))$

Since $g$ is injective, $f(x_1)=f(x_2)$.

Since $f$ is injective, $x_1=x_2$

I am unsure on how I can proceed to proceed to prove/disprove the other statements. Please advise

• To disprove (2) for example, let $Z$ have a single element. Then as long as $X$ has at least $2$ elements, $g \circ f$ cannot be injective. You can get a lot of counterexamples this way. – Joppy Oct 2 '17 at 14:07
• try to find anti examples where $X,Y,Z$ are finite – Yanko Oct 2 '17 at 14:07
• @Joppy is there a way to prove that the negation of the statement, i.e. $\exists x_1,x_2 \in X , ((g \circ f)(x_1)=(g \circ f)(x_2)) \land (x_1 \not= x_2)$ – kevinbobbkoh Oct 3 '17 at 7:06
• @yanko I'm limited to disproving the statement only by proving the negation of the statement. Can you advise? – kevinbobbkoh Oct 3 '17 at 7:07
• Isnt a counterexample a proof of the negation? The statement is something like "for all $f$ injective, for all $g$ surjective, $g \circ f$ is injective". The negation is "there exists $f$ injective and $g$ surjective such that $g\circ f$ is not injective". A proof of that is giving an example of such an $f$ and $g$. – Joppy Oct 3 '17 at 9:08