8
$\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$

1 Answer 1

Reset to default
9
$\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$
5
  • 3
    $\begingroup$ You can (and should) use \circ for $\circ$ rather than o. $\endgroup$
    – Asaf Karagila ♦
    Oct 7, 2012 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, 2012 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$
    – Mikasa
    Oct 7, 2012 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$
    – Mikasa
    Oct 7, 2012 at 15:43
  • 1
    $\begingroup$ @BabakSorouh ah I see, let's wait :) $\endgroup$
    – ulead86
    Oct 7, 2012 at 17:21

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .