The symmetric group $\mathrm{Sym}(X)$: the bijections of a set $X$ under composition

Let $X$ be a set. A permutation of $X$ is a bijection $f:X\to X$ (Injection, surjection, bijection). The symmetric group of $X$ is the set of all permutations of $X$,

$\mathrm{Sym}(X):=\{f:X\to X:f\text{ is a bijection}\},$

equipped with composition as its operation,

$(f\circ g)(x)=f(g(x))(x\in X),$

and with the identity map ${\mathrm{i}\mathrm{d}}_X$, given by ${\mathrm{i}\mathrm{d}}_X(x)=x$, as distinguished element.

Composition of two bijections of $X$ is again a bijection of $X$ (Injection, surjection, bijection), so $\mathrm{Sym}(X)$ is closed under $\circ$ and $\circ$ is a binary operation on it (Binary operation on a set; associativity, commutativity, and a subset closed under the operation); and ${\mathrm{i}\mathrm{d}}_X$ is a bijection of $X$, so it is an element of $\mathrm{Sym}(X)$, and it is a two-sided identity for composition (Left identity, right identity, and two-sided identity for a binary operation) because $f\circ {\mathrm{i}\mathrm{d}}_X=f={\mathrm{i}\mathrm{d}}_X\circ f$ holds pointwise for every $f$. That $(\mathrm{Sym}(X),\circ ,{\mathrm{i}\mathrm{d}}_X)$ is a group is $\mathrm{Sym}(X)$ is a group under composition, and it is non-abelian whenever $X$ has at least three distinct elements.

Cycle notation for a finite list of distinct points. For distinct elements $x_0,x_1,\dots ,x_{k-1}$ of $X$ with $k\ge 2$, the symbol $(x_0{x}_1\cdots x_{k-1})$ denotes the permutation sending $x_i$ to $x_{i+1}$ for $i<k-1$, sending $x_{k-1}$ to $x_0$, and fixing every element of $X$ outside $\{x_0,\dots ,x_{k-1}\}$. It is a bijection, because the map described sends the set $\{x_0,\dots ,x_{k-1}\}$ onto itself by a rule with an evident inverse (send each $x_{i+1}$ back to $x_i$ and $x_0$ back to $x_{k-1}$) and fixes the complement pointwise. A transposition is such a symbol with $k=2$, that is $(ab)$ with $a\mathrm{\ne }b$: it exchanges $a$ and $b$ and fixes everything else, and it satisfies $(ab)\circ (ab)={\mathrm{i}\mathrm{d}}_X$.

A product of cycle symbols means their composite, so $(ab)(cd)$ is $(ab)\circ (cd)$.

• Order of composition. With the convention $(f\circ g)(x)=f(g(x))$ the right-hand factor acts first. Both conventions are in use in the literature; this one is the one already fixed for function composition in the library and is the one used in every computation on this page and its companion.

• Why this is defined here rather than with the finite symmetric groups. $\mathrm{Sym}(X)$ for an arbitrary set $X$ is the ambient object needed as soon as one speaks of a group acting on a set, which is earlier in the reading order than the combinatorial study of $S_n$; homing it here keeps every citation of it backward-pointing.

• The general cycle notation above is used on this page only for transpositions; cycles of length $3$ and $4$, and products of two disjoint transpositions, appear on the companion examples page. The systematic theory, including the factorisation of an arbitrary permutation of a finite set into disjoint cycles, belongs to a later page.