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 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?

share|improve this question
2  
$g |_{f(A)}$ is an identity. –  copper.hat May 10 '12 at 23:17
add comment

2 Answers 2

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

share|improve this answer
4  
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
2  
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
add comment

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

share|improve this answer
add comment

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.