Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

As Definition for $f \circ g$ I've got $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 f \circ g$ injective
  • $f$ surjective + $g$ surjective $\Rightarrow f \circ g$ surjective
  • $f$ bijective + $g$ bijective $\Rightarrow f \circ g$ bijective

And the other way around:

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

My solution for sufficient and necessary conditions:

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

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

Any hints and ideas are very welcome.

Greetings

share|improve this question

1 Answer 1

up vote 4 down vote accepted

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.

share|improve this answer
2  
You can (and should) use \circ for $\circ$ rather than o. –  Asaf Karagila Oct 7 '12 at 15:11
    
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? –  ulead86 Oct 7 '12 at 15:24
1  
@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. –  Babak S. Oct 7 '12 at 15:35
1  
@ulead86: Note that I covered a small part of your question not all your questions. I am waiting to see other's answers here. :) –  Babak S. Oct 7 '12 at 15:43
1  
@BabakSorouh ah I see, let's wait :) –  ulead86 Oct 7 '12 at 17:21

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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