6
$\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.

$\endgroup$
5
$\begingroup$

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.

$\endgroup$
  • 3
    $\begingroup$ You can (and should) use \circ for $\circ$ rather than o. $\endgroup$ – Asaf Karagila Oct 7 '12 at 15:11
  • $\begingroup$ Yes you are right: $f:A \rightarrow B$ and $g:B \rightarrow C$. With 1-1 you mean injective? (never heard about 1-1 and onto, sorry) So you say: f injective and g surjective is not necessary for $f \circ g$ beeing bijective? But did I made correct toughts about the other cases? $\endgroup$ – ulead86 Oct 7 '12 at 15:24
  • 1
    $\begingroup$ @ulead86: Yes. As I arranged the above functions; being injective for $f$ and surjective for $g$ is not necessarily leads us $g\circ f$ being bijective. Of course $g\circ f$ is bijective iff $f$ and $g$ are bijective. $\endgroup$ – mrs Oct 7 '12 at 15:35
  • 1
    $\begingroup$ @ulead86: Note that I covered a small part of your question not all your questions. I am waiting to see other's answers here. :) $\endgroup$ – mrs Oct 7 '12 at 15:43
  • 1
    $\begingroup$ @BabakSorouh ah I see, let's wait :) $\endgroup$ – ulead86 Oct 7 '12 at 17:21

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.