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
Does $f\circ g$ injective imply $f$ injective for functions $f,g:A\to A$?
-
0Sorry for my previous comment, I read $f \circ g$ as $g(f(x))$. – 2011-11-19
2 Answers
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 }.$
-
0how $f(0)=f(1)=f(0)$, $f=\frac{x}{2}$? – 2013-08-02
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$.