If an iterated function $f \circ f$ is the identity function, is $f$ an identity function also?

Question

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\}}$

Answer 1

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.

Answer 2

Hint: consider $f$ defined by $f(1)=2$, $f(2)=1$ and $f(3)=3$.

Answer 3

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?

Answer 4

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.