Paper 4, Section II, D

Let $X$ be a set, and let $f$ and $g$ be functions from $X$ to $X$. Which of the following are always true and which can be false? Give proofs or counterexamples as appropriate.

(i) If $f g$ is the identity map then $g f$ is the identity map.

(ii) If $f g=g$ then $f$ is the identity map.

(iii) If $f g=f$ then $g$ is the identity map.

How (if at all) do your answers change if we are given that $X$ is finite?

Determine which sets $X$ have the following property: if $f$ is a function from $X$ to $X$ such that for every $x \in X$ there exists a positive integer $n$ with $f^{n}(x)=x$, then there exists a positive integer $n$ such that $f^{n}$ is the identity map. [Here $f^{n}$ denotes the $n$-fold composition of $f$ with itself.]

*Typos? Please submit corrections to this page on GitHub.*