Past exam of the mathematics course of the University of Cambridge / 2012 / ia / Paper 4 / 5D (Numbers and Sets)

Take $fg=f\circ g$. The assertion can fail on an infinite set. On $X={\mathbb{N}}_0$, set $g(n)=n+1$, $f(0)=0$, and $f(n)=n-1$ for $n\ge 1$. Then $f(g(n))=n$ for every $n$, but $g(f(0))=1\ne 0$. Thus a right inverse need not be a left inverse.

On a finite set it is always true. From $fg={\mathrm{id}}_X$, $g$ is an injection: equality of two $g$-values gives equality after applying $f$. An injective self-map of a finite set is a bijection. Composing $fg={\mathrm{id}}_X$ with $g^{-1}$ shows $f=g^{-1}$, and hence $gf={\mathrm{id}}_X$. This includes the empty set.

It can be false even on a two-element finite set. On $X=\{0,1\}$, let $f$ and $g$ both be the constant map with value $0$. Then $fg=g$, but $f(1)=0\ne 1$. In general the equation says exactly that $f$ fixes the image $g(X)$; it says nothing about other points. If $g$ happens to be a surjection, it does force $f$ to be the identity map, but finiteness alone does not ensure this. The empty set and a singleton have only one self-map, so the assertion is trivially true on those sets.

It can be false even on a two-element finite set. The same constant maps $f=g=0$ on $\{0,1\}$ satisfy $fg=f$, while $g\ne {\mathrm{id}}_X$. Indeed, a constant $f$ makes $fg=f$ for every $g$. If $f$ were an injection, one could cancel it pointwise to conclude $g(x)=x$, but finiteness alone supplies no such hypothesis. As before, the assertion is trivial on the empty set or a singleton.

The final property concerns a pointwise periodic self-map. Such a map is a bijection: each point has a predecessor in its finite cycle, giving surjectivity; if $f(x)=f(y)$, choose a common multiple $N$ of periods of $x,y$ and apply $f^{N-1}$ to get $x=y$. Its finite cycles are therefore disjoint.

If $X$ is finite, choose the least common multiple of the finitely many cycle lengths. This positive integer $N$ gives $f^N={\mathrm{id}}_X$. The empty set satisfies the property with $N=1$.

Conversely, in the usual set theory with choice, every infinite $X$ contains a countably infinite set. Divide such a subset into disjoint finite blocks $B_j$ of sizes $j+1$, $j\ge 1$, make $f$ a cyclic permutation on each block, and fix every other point. Every point returns to itself, but an identity iterate would have to be divisible by every block length $j+1$. No positive integer has that property: take a block longer than that integer. Thus the uniform period criterion for pointwise periodic maps givesThe axiom of choice assumption is stated here because extracting a countably infinite subset of an arbitrary infinite set is not an unrestricted theorem in set theory without choice.