# Must $g$ be the identity if $f = g \circ f$?

I am finding it hard to solve the following problem.
Let $A$ is a set and $f : A \rightarrow A$ and $g : A \rightarrow A$. If $f = g \circ f$, must $g$ be an identity function always?
Will there be any counterexamples to show that $g$ must not be a identity function?

-
$g |_{f(A)}$ is an identity. – copper.hat May 10 '12 at 23:17

Take $A=\{0,1,2\}$ and $f$ is the constant function $0$ while $g(0)=0$ and $g(1)=g(2)=1$.

Let us find exactly why the above works, and deduce a nice corollary: $\newcommand{rng}{\operatorname{rng}}\newcommand{id}{\operatorname{id}}$

Theorem: Suppose that $f,g\colon A\to A$ then $f=g\circ f$ if and only if $g$ restricted to $\rng f$ is the identity.

Proof: Suppose that $g$ is the identity on $\rng f$ then for $x\in A$ we have $g(f(x))=f(x)$ since $f(x)\in\rng f$.

In the other direction, suppose that $f=g\circ f$, let $y\in\rng f$ then $y=f(x)$ for some $x\in A$. We have that $g(y)=g(f(x))=f(x)=y$, as wanted. $\square$

Corollary: $f$ is surjective if and only if $g=\id_A$.

Proof: Assume that $f$ is surjective and apply the above theorem with $\rng f=A$. In the other direction, suppose that $f$ is not surjective, let $x\in\rng f$ and $y\in A\setminus\rng f$. Define $g$ as follows: $$g(a)=\begin{cases} x &a=y\\ a &\text{otherwise.}\end{cases}$$ By the above theorem we have that $g\circ f=f$ but clearly $g\neq\id_A$.

-
What's nice is that I never thought about this before now. It seems like a good exercise in an intro to set theory class. Maybe next year! – Asaf Karagila May 10 '12 at 23:02
In fact, $f$ is surjective if and only if whenever $g\circ f = f$, we have $g=\mathrm{id}$. A slight strengthening of the "right-cancellable" criterion, since you can test a single type of functions. – Arturo Magidin May 10 '12 at 23:54
This is very similar to an exercise from Isaacs's algebra that I always thought was nice. Find a group of mappings on a set $X$ to itself that is not a subgroup of $S_X$. Then show that if any of the maps is injective, it is a subgroup of $S_X$. – user641 May 11 '12 at 2:43

Projections give you plenty of counterexamples with $f=g$. For instance, $f:\mathbb R^2\to \mathbb R^2$ given by $f(x,y)=x$.

-