1. ## Another functions proof

Hello, I have a question that I not sure how to proceed on:

Let X be a nonempty set and let $f:X \rightarrow X$ be a function such that $(f \circ f) = f$.
Show that if f is onto then $f = 1^{}_{X}$.

I started by saying:

Suppose f is onto. Then for each $y \in X$ there exists at least one $x \in X$ such that $f(x) = y$.

And then I can't think what to do next. The previous question which was where I got to suppose f was one-to-one seemed much easier!

2. Hint:

Let $f \neq 1^{}_{X}$. Then there exists a x1 such that f(x1) = x2 and x1<>x2

fof(x1) = f(x1) ---- by your definition of f
also fof(x1) = f(f(x1)) = f(x2)
thus f(x1) = f(x2) => f is not one-to-one

Can you try to complete?

3. Also if you could please confirm that set X is finite - else I'm running into some cotradictions. If anyone else can also please confirm to us that X has to be finite for this result to hold. Thanks

4. I'll just leave this blank...

5. Sorry for all the sutipidity above. You do not need the condition that X is finite.

Let x be in the range of f. We will prove that f(x) = x for fof = f to hold true.

Assume otherwise. i.e. f(x) = y where y <> x for some x in the range of f.

As x is in the range of f, so there exists z such that f(z) = x; z<> x

consider fof(z) = f(z) = x; also fof(z) = f(f(z)) = f(x) = y; but we assumed y <> x so contradiction !!

hence every element in the range of f get mapped to itself. as f is onto thus f is identify function.

6. No Swlabr - I do not think we need the assumtion that X should be finite. Please see my re-worked proof below. fof = f is a much stronger condition I guess.

7. Originally Posted by aman_cc
No Swlabr - I do not think we need the assumtion that X should be finite. Please see my re-worked proof below. fof = f is a much stronger condition I guess.
yeah - I realised my counter-example wasn't a counter-example...it wasn't a surjection!

8. mistake, nvm

9. Here is direct proof.
If $a\in X$ then by the given $\left( {\exists b \in X} \right)\left[ {f(b) = a} \right]$.
Because $f \circ f(b) = f(b)$ we have $f(a) = f\left( {f(b)} \right) = f(b) = a$.