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 have some problem with proof of the following question: I have two functions $f,g: A \to A$, I know that $(f \circ g)$ is injective, is it possible at all to prove that $f$ is injective? I know that if $g: A \to B$ and $f: B \to C$, I can find example which contradicts my suggestion, but what is going on when I have $f,g: A \to A$, thanks in advance for any help

share|improve this question
    
Perhaps some answers and links given here math.stackexchange.com/questions/75880/if-g-circ-f-is-the-identity-function-then‌​-which-of-f-and-g-is-onto-and-w/ might be useful for you. –  Martin Sleziak Nov 19 '11 at 12:48
    
Sorry for my previous comment, I read $f \circ g$ as $g(f(x))$. –  Rudy the Reindeer Nov 19 '11 at 13:01

2 Answers 2

up vote 6 down vote accepted

No, it is not possible to prove it, because it is false. Let $A=\mathbb{Z}$, the set of integers, and let $f:A\to A$ be defined by $f(x)=\left\lfloor\frac{x}{2}\right\rfloor$, and let $g:A\to A$ be defined by $g(x)=2x$. Then $$(f\circ g)(x)=f(2x)=\left\lfloor\frac{2x}{2}\right\rfloor=x$$ is the identity, so $(f\circ g)$ is certainly injective, but $f$ is not injective; for example $f(0)=f(1)=0$.

What is happening is that, for each $x\in A$, the image of $g$ contains at most one element of $f^{-1}(x)$. Thus, the fact that $f$ isn't injective is not noticeable if we only look at the image of $g$, as we do when we compose with $g$ first.

However, if you assume that your set $A$ is finite, then it is true that $(f\circ g)$ injective $\implies$ $f$ injective, because for a finite set $A$, any map $h:A\to A$ is injective iff it is surjective iff it is bijective, so $$(f\circ g)\text{ injective }\implies(f\circ g)\text{ bijective }\implies(f\circ g)\text{ surjective }\implies$$ $$ f\text{ surjective }\implies f \text{ bijective }\implies f \text{ injective }.$$

share|improve this answer
    
best, thank You a lot –  math_lover Nov 19 '11 at 12:41
    
No problem, glad to help! –  Zev Chonoles Nov 19 '11 at 12:42
    
how $f(0)=f(1)=f(0)$, $f=\frac{x}{2}$? –  Ofir Attia Aug 2 '13 at 17:46

There is a counterexample whenever $A$ is Dedekind infinite. Suppose that $g:A\to A$ is an injective map whose range $g(A)$ is a proper subset of $A$. Let $a_0\in A$. Let $f:A\to A$ be defined by $f(g(a))=a$ for all $a\in A$, and $f(a)=a_0$ for all $a\in A\setminus g(A)$. Then $f(g(a))=a$ for all $a\in A$, so $f\circ g$ is injective. There exists $a_1\in A\setminus g(A)$, so $a_1\neq g(a_0)$, but $f(a_1)=f(g(a_0))=a_0$, showing that $f$ is not injective.

An example of this is $A=\{0,1,2,3,4,\ldots\}$, $g(n)=n+1$, $f(n)=n-1$ if $n>0$, $f(0)=0$.

share|improve this answer

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.