# Does $f\circ g$ injective imply $f$ injective for functions $f,g:A\to A$?

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

-
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

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 }.$$

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

-