Past exam of the mathematics course of the University of Oxford / 2021 / Prelims / Mathematics I / 5 (Permutations and one-sided group axioms)

The function composition of two bijections $f,g:X\to X$ is a bijection, with inverse function $(f\circ g{)}^{-1}=g^{-1}\circ f^{-1}$. Thus function composition is a binary operation on $\mathrm{Sym}(X)$. It is associative, since both $(f\circ g)\circ h$ and $f\circ (g\circ h)$ send $x$ to $f(g(h(x)))$.

The identity function ${\mathrm{id}}_X$ is a bijection and satisfies $f\circ {\mathrm{id}}_X={\mathrm{id}}_X\circ f=f$. Every bijection $f$ has an inverse function $f^{-1}:X\to X$, itself a bijection, satisfying $f\circ f^{-1}=f^{-1}\circ f={\mathrm{id}}_X$. These verify all group axioms, so $\mathrm{Sym}(X)$ is a group, the symmetric group of $X$.

For a singleton $X$, the symmetric group contains only the identity function. For a two-element set, it contains the identity function and the transposition exchanging the two elements; the latter squares to the identity function. In both cases all elements commute, so the group is Abelian.

If $X$ contains three distinct elements $a,b,c$, define the transpositions $\sigma =(ab)$ and $\tau =(bc)$, fixing every other element of $X$. They are bijections, even when $X$ is infinite. With function composition read from right to left,Thus they do not commute, so the symmetric group is not Abelian. Since $X$ is nonempty, this proves

For each $g\in G$, left translation in a group $L_g:x\mapsto gx$ is a bijection, with inverse function $L_{g^{-1}}$. Thus $\theta (g)=L_g$ belongs to $\mathrm{Sym}(G)$. For $g,h,x\in G$, associativity of the group operation givesHence $\theta$ is a group homomorphism. If $\theta (g)=\theta (h)$, evaluation at the identity element $e$ gives $g=ge=he=h$. ThereforeThis is the left regular representation used in Cayley's theorem.

Suppose $y\ast y=y$. Choose $z$ with $y\ast z=e$, using the given right inverse element property. Multiply the idempotent relation on the right by $z$. By associativity and the given right identity element property,Thus the only idempotent element of a semigroup is $e$. This argument uses no cancellation and does not assume a left identity element.

Suppose $x\ast z=e$. Using only associativity and the given right identity element property,Thus $z\ast x$ is an idempotent element of a semigroup. By i it equals $e$, provingNo left identity element or cancellation law is needed for this deduction.

For any $x$, choose $z$ with $x\ast z=e$. By ii, $z\ast x=e$ as well. Associativity and the right identity element property now giveThus $e$ is also a left identity element. The given binary operation is closed on $X$ and associative, $e$ is a two-sided identity element, and each $x$ has the two-sided inverse element $z$. All group axioms hold, so $(X,\ast )$ is a group. This is the one-sided group axioms criterion.

An injective function from a finite set to itself is surjective: its image of a function contains as many distinct elements as the entire set, so it cannot omit one. Thus every element of $I(X)$ is a bijection, and conversely every bijection is injective. HenceIt is a group under function composition by i.

The shift $s:\mathbb{N}\to \mathbb{N}$, $s(n)=n+1$, is injective, so $s\in I(\mathbb{N})$. It is not surjective: the least natural number is missing from its image of a function, whether $\mathbb{N}$ starts at zero or one. For every $t:\mathbb{N}\to \mathbb{N}$, the image of a function of $s\circ t$ is contained in the image of a function of $s$, so $s\circ t\ne {\mathrm{id}}_{\mathbb{N}}$.

The identity function belongs to $I(\mathbb{N})$ and is its identity element under function composition; any group structure using that operation would have this same identity element. Since $s$ has no right inverse element, $I(\mathbb{N})$ is not a group under function composition. It is a monoid, since injectivity is preserved by function composition.