If an iterated function $f \circ f$ is the identity function, is $f$ an identity function also? If we have
$f: \{1, 2, 3\} \to \{1, 2, 3\}$
and
$f \circ f = id_{\{1,2,3\}}$
is the following then always true for every function?
$f = id_{\{1,2,3\}}$
 A: Hint: consider $f$ defined by $f(1)=2$, $f(2)=1$ and $f(3)=3$.
A: Notice that we could easily show that $f$ is bijective, since if $f\circ f$ is bijective, as the identity is, it must be that $f$ is injective (since were it not, $f\circ f$ could not be either) and that $f$ is surjective (for the same reason).
In particular, this implies that $f$ will be a member of the symmetric group $S_3$. We could apply Cauchy's theorem to show that there must be some non-zero element $f$ of $S_3$ such that $f^2$ is the identity (where $f^2=f\circ f$ - an iterate of $f$) - which implies that your statement is false.
However, interestingly, a consequence of Lagrange's theorem is that $f^6$ is always the identity, which in turn can be used to show that if $f^5=f\circ f\circ f\circ f\circ f$ is the identity, then $f$ is as well.
A: If $f: S \to S$ is a function satisfying $f(f(x)) = x$ for all $x \in S$, consider what the implications are of having a fixed $x \in S$ so that $f(x) \neq x$; setting $y := f(x)$, we must have:
$$f(x) = y$$ by definition, and $$f(y) = f(f(x)) = x.$$
Given this observation, can you then describe exactly what the nature of such a function $f$ must be?
A: Note that we have $f^{-1}\circ f =  f\circ f^{-1}= id\{1, 2, 3\}\;\forall \text{ permutations on } \{1, 2, 3\}$.
By definition, all permutations on a set are bijective functions, so every permutation has an inverse.
You need only find a single bijective function $f$ which is its own inverse, (a permutation of order $2$ and you'll have your counter-example.
