0
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Joppy Oct 2 '17 at 14:07
  • $\begingroup$ try to find anti examples where $X,Y,Z$ are finite $\endgroup$ – Yanko Oct 2 '17 at 14:07
  • $\begingroup$ @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)$ $\endgroup$ – kevinbobbkoh Oct 3 '17 at 7:06
  • $\begingroup$ @yanko I'm limited to disproving the statement only by proving the negation of the statement. Can you advise? $\endgroup$ – kevinbobbkoh Oct 3 '17 at 7:07
  • $\begingroup$ 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$. $\endgroup$ – Joppy Oct 3 '17 at 9:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.