7
$\begingroup$

I struggling a little bit with sufficient and necessary conditions. I have to find sufficient and necessary conditions for the composition of two functions $g \circ f$ being injective, surjective or both.

Let $f: A \to B$ and $g: B \to C$ be two functions. Then $g \circ f = g(f(x))$.

We say $A$ is sufficient for $B$, if $A$ implies $B$ $(A \Rightarrow B)$ and we say $A$ is necessary for B, if $B$ can't hold without $A$, $B \Rightarrow A$. $A$ is necessary and sufficient if $A \Leftrightarrow B$ holds.

By drawing some picture with different cases I found the following

  • $f$ injective + $g$ injective $\Rightarrow g \circ f$ injective
  • $f$ surjective + $g$ surjective $\Rightarrow g \circ f$ surjective
  • $f$ bijective + $g$ bijective $\Rightarrow g \circ f$ bijective

And the other way around:

  • $g \circ f$ injective $\Rightarrow$ $f$ injective + $g$ can be both
  • $g \circ f$ surjective $\Rightarrow$ $f$ can be both + $g$ surjective
  • $g \circ f$ bijective $\Rightarrow$ $f$ injective + $g$ surjective

My solution for sufficient and necessary conditions:

  1. $g \circ f$ injective: f injective + g injective are sufficient, f injective is necessary
  2. $g \circ f$ surjective: f surjective + g surjective are sufficient, g surjective is necessary
  3. $g \circ f$ bijective: f bijective + g bijective are sufficient, f injective and g surjective are necessary

Are my ideas correct so far? And are there conditions which are necessary and sufficient at the same time? I would say "no".

Any hints and ideas are very welcome.

1 Answers 1

6

What I know about your nice question is as follows. I suppose that $f:A\to B$ and $g:B\to C$.

  1. If $g\circ f$ is 1-1 then $f$ is 1-1.

  2. If $g\circ f$ is onto then $g$ is onto.

so if $g\circ f$ is bijective then $f$ is 1-1 and $g$ is onto but, the converse is not true.

  1. $f(x)=f(x')\Longrightarrow g(f(x))=g(f(x'))\Longrightarrow (g\circ f)(x)=(g\circ f)(x')\Longrightarrow x=x'$

  2. if $c\in C$ then $\exists a (a\in A \wedge (g\circ f)(a)=c)\Longrightarrow\exists a(a\in A \wedge (g\big(f(a)\big)=c)$ so if we take $b=f(a)\in B$ then $g(b)=c$.

Now take $A=\{1,2\}, B=\{3,4,5\}, C=\{6,7\}$ and $f:A\to B\\f(1)=3,f(2)=4$ $g:B\to C\\ g(3)=g(4)=6,g(5)=7$ $f$ is 1-1 and $g$ is onto but $(g\circ f)(1)=g(3), (g\circ f)(2)=6$ which means that $g\circ f$ is not a bijective map.

  • 1
    @BabakSorouh ah I see, let's wait :)2012-10-07