Symmetric Groups and Permutation Notation

We verify each axiom directly from the definition of $S_n$ as a set of bijections, using proof by direct construction/verification.

Closure. If $\sigma, \tau : [n] \to [n]$ are bijections, then so is $\sigma\tau := \sigma \circ \tau$. Indeed, the composition of two injective functions is injective: if $(\sigma\tau)(i) = (\sigma\tau)(j)$, then $\sigma(\tau(i)) = \sigma(\tau(j))$, and injectivity of $\sigma$ gives $\tau(i) = \tau(j)$, and then injectivity of $\tau$ gives $i = j$. The composition of two surjective functions on a finite set is surjective: since $\sigma$ and $\tau$ are bijections on a set with the same finite domain and codomain, injectivity already forces surjectivity (a finite set cannot inject properly into itself), so $\sigma\tau$ is a bijection $[n]\to[n]$, i.e. $\sigma\tau \in S_n$.

Associativity. For any functions $\sigma, \tau, \rho : [n] \to [n]$ and any $i \in [n]$,

Since this holds for every $i \in [n]$, the functions $(\sigma\tau)\rho$ and $\sigma(\tau\rho)$ are equal. This is simply associativity of function composition in general, which holds regardless of bijectivity.

Identity. Let $e : [n] \to [n]$ be the identity map, $e(i) = i$ for all $i$. Then $e$ is trivially a bijection, so $e \in S_n$, and for every $\sigma \in S_n$ and every $i$,

so $\sigma e = e \sigma = \sigma$. Thus $e$ is a two-sided identity.

Inverses. Since $\sigma$ is a bijection $[n] \to [n]$, it has a set-theoretic inverse function $\sigma^{-1} : [n] \to [n]$ defined by: $\sigma^{-1}(j)$ is the unique $i \in [n]$ with $\sigma(i) = j$ (existence and uniqueness of such $i$ follow from surjectivity and injectivity of $\sigma$ respectively). The function $\sigma^{-1}$ is itself a bijection (its inverse is $\sigma$), so $\sigma^{-1} \in S_n$. By construction, for all $i$,

so $\sigma^{-1}\sigma = \sigma\sigma^{-1} = e$. All four axioms hold, so $(S_n, \circ)$ is a group.

Order count. We count bijections $[n] \to [n]$ directly. A bijection $\sigma$ is determined by choosing $\sigma(1)$, then $\sigma(2)$, and so on, subject to all values being distinct (this is exactly what injectivity on a finite set of equal domain/codomain size requires, and by the argument above such an injective assignment is automatically a bijection). There are $n$ choices for $\sigma(1)$; having chosen $\sigma(1), \dots, \sigma(k-1)$ as $k-1$ distinct values, there remain $n - (k-1)$ available values for $\sigma(k)$ so that all images stay distinct. By the multiplication principle, the total number of such sequences of choices is

Each such sequence of choices corresponds to exactly one bijection and every bijection arises from exactly one such sequence, so $|S_n| = n!$. $\blacksquare$

We check the two sides agree on every point of $[n]$ (proof by case analysis on where a point can lie). Let $x \in [n]$. There are three mutually exclusive cases, since $\{a_1,\dots,a_k\}$ and $\{b_1,\dots,b_m\}$ are disjoint. Case 1: $x = a_i$ for some $i$. Then $\beta$ fixes $x$ (as $x \notin \{b_1,\dots,b_m\}$), so $(\alpha\beta)(x) = \alpha(\beta(x)) = \alpha(x)$, and $\alpha(x) = a_{i+1}$ (indices mod $k$, so $a_{k+1} := a_1$) again lies among the $a$'s, hence is fixed by $\beta$. For the other order, $\alpha$ fixes $x$ only if $x \notin \{a_1,\dots,a_k\}$, which is false here — instead we compute $(\beta\alpha)(x) = \beta(\alpha(x))$; since $\alpha(x) = a_{i+1} \notin \{b_1,\dots,b_m\}$, $\beta$ fixes it, giving $\beta(\alpha(x)) = a_{i+1}$. Both sides equal $a_{i+1}$. Case 2: $x = b_j$ for some $j$. Symmetric to Case 1 with the roles of $\alpha, \beta$ exchanged: both $(\alpha\beta)(x)$ and $(\beta\alpha)(x)$ equal $b_{j+1}$ (indices mod $m$). Case 3: $x$ is fixed by both $\alpha$ and $\beta$. Then $(\alpha\beta)(x) = \alpha(\beta(x)) = \alpha(x) = x$ and $(\beta\alpha)(x) = \beta(\alpha(x)) = \beta(x) = x$. In every case $(\alpha\beta)(x) = (\beta\alpha)(x)$, so $\alpha\beta = \beta\alpha$ as functions on $[n]$. $\blacksquare$

We use the orbit structure of $\sigma$ acting on $[n]$; the technique is a direct construction followed by a uniqueness argument via equivalence classes.

Existence. Define a relation on $[n]$ by $x \sim y$ iff $y = \sigma^k(x)$ for some integer $k \in \mathbb{Z}$ (where $\sigma^k$ denotes $\sigma$ composed with itself $k$ times, $\sigma^0 = e$, and $\sigma^{-k} = (\sigma^{-1})^k$). This is an equivalence relation: reflexivity holds via $k=0$; symmetry holds since $y = \sigma^k(x) \Rightarrow x = \sigma^{-k}(y)$; transitivity holds since $y=\sigma^k(x), z = \sigma^m(y) \Rightarrow z = \sigma^{m+k}(x)$. Call the equivalence classes the orbits of $\sigma$; since $[n]$ is finite, there are finitely many orbits, say $O_1, \dots, O_r$, partitioning $[n]$. Fix an orbit $O_i$ and pick any $a \in O_i$. Consider the sequence $a, \sigma(a), \sigma^2(a), \dots$. Since $[n]$ is finite, this sequence must repeat: there exist $0 \le p < q$ with $\sigma^p(a) = \sigma^q(a)$. Applying $\sigma^{-p}$ (which exists since $\sigma$ is invertible) gives $a = \sigma^{q-p}(a)$. Let $\ell \ge 1$ be the smallest positive integer with $\sigma^\ell(a) = a$ (such $\ell$ exists by the previous sentence and the well-ordering principle). We claim $a, \sigma(a), \dots, \sigma^{\ell - 1}(a)$ are pairwise distinct: if $\sigma^s(a) = \sigma^t(a)$ for $0 \le s < t \le \ell - 1$, applying $\sigma^{-s}$ gives $a = \sigma^{t-s}(a)$ with $0 < t - s < \ell$, contradicting minimality of $\ell$. Moreover every element of the orbit $O_i$ has this form: if $y = \sigma^k(a)$, write $k = q\ell + s$ with $0 \le s < \ell$ (division algorithm), then $y = \sigma^{q\ell + s}(a) = \sigma^s\big((\sigma^\ell)^q(a)\big) = \sigma^s(a)$ since $\sigma^\ell(a) = a$ implies $(\sigma^\ell)^q(a) = a$ by induction on $q$. Hence

a set of exactly $\ell$ distinct elements, and $\sigma$ acts on $O_i$ exactly as the cycle $\gamma_i := (a\ \ \sigma(a)\ \ \sigma^2(a)\ \cdots\ \sigma^{\ell-1}(a))$ acts, while fixing every point outside $O_i$. Since the orbits $O_1,\dots,O_r$ partition $[n]$, the corresponding cycles $\gamma_1,\dots,\gamma_r$ are pairwise disjoint (they move disjoint sets of symbols), and for every $x \in [n]$, $x$ lies in exactly one orbit $O_i$, on which $\sigma$ and $\gamma_i$ agree, while all other $\gamma_j$ ($j \ne i$) fix $x$. Hence

for every $x$ (using that disjoint cycles commute and fix each other's moved points, Lemma above), so $\sigma = \gamma_1 \gamma_2 \cdots \gamma_r$.

Uniqueness. Suppose $\sigma = \delta_1 \cdots \delta_s$ is any expression of $\sigma$ as a product of pairwise disjoint nontrivial cycles. We show the multiset of cycles $\{\delta_1,\dots,\delta_s\}$ must coincide with $\{\gamma_1,\dots,\gamma_r\}$ (as sets of symbols moved, with the internal cyclic order determined). Since the $\delta_j$ are pairwise disjoint, for a point $x$ moved by $\delta_j$ (i.e. $\delta_j(x) \ne x$), every other factor $\delta_{j'}$ ($j' \ne j$) fixes $x$, so

and inductively $\sigma^k(x) = \delta_j^k(x)$ for all $k \ge 0$. Thus the orbit of $x$ under repeated application of $\sigma$ coincides exactly with the orbit of $x$ under $\delta_j$, which is precisely the set of symbols moved by $\delta_j$ together with $x$'s trajectory around that cycle. This orbit is, by definition, one of the $\sigma$-orbits $O_i$ constructed above, and the cyclic order in which $\delta_j$ moves its points must match $x, \sigma(x), \sigma^2(x), \dots$, which is exactly the cyclic order recorded in $\gamma_i$. Hence $\delta_j$ equals $\gamma_i$ as a cycle (same set of moved points, same cyclic pattern, possibly written starting from a different symbol — but a cycle $(a_1\,\cdots\,a_\ell)$ and $(a_2\,\cdots\,a_\ell\,a_1)$ denote the identical function, so this is not a genuine ambiguity). Every nontrivial factor $\delta_j$ therefore matches some $\gamma_i$, every $\gamma_i$ arises this way (taking $x \in O_i$ with $|O_i|>1$), and distinct $\delta_j$'s correspond to distinct $\gamma_i$'s since their moved-point sets are disjoint and partition the non-fixed points of $\sigma$. Hence $\{\delta_1,\dots,\delta_s\} = \{\gamma_1,\dots,\gamma_r\}$ as sets of cycles, i.e. the decomposition is unique up to the order of the factors and the starting symbol chosen within each cycle. $\blacksquare$