9
$\begingroup$

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?

  • 2
    $g |_{f(A)}$ is an identity.2012-05-10

2 Answers 2

18

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

  • 0
    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$.2012-05-11
2

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