if $m, n \in \mathbb{N}$, $m < n$, then $S_m$ isomorphic to subgroup of $S_n$

Question

How do show that if $m, n \in \mathbb{N}$ and $m < n$, then $S_m$ is isomorphic to a subgroup of $S_n$, without using any "overpowered" results?

Answer 1

Let $\sigma$ be any permutation in $S_m$. Define the permutation $\phi(\sigma)\in S_n$ by $\phi(\sigma)(i)=\sigma(i)$ if $i\le m$, and by $\phi(\sigma)(i)=i$ if $m+1\le i\le n$. It is not hard to verify that $\phi$ is an isomorphism from $S_m$ to a subgroup of $S_n$.

Answer 2

We first prove a lemma.

Lemma. Let $X$ be a set and let $G = \{f: X \to X\text{ }|\text{ }f\text{ is a bijection}\}$. This is a group under composition. Let $A \subseteq X$ be a subset, and let $H_A = \{f \in S_X\text{ }|\text{ }f(a) = a\text{ for all }a \in A\}$. Then $H_A$ is a subgroup of $S_X$.

Proof. We first show the group under composition part. Let $f, g \in G$. If $f \circ g(a) = f \circ g(b)$, then $g(a) = g(b)$ and so $a = b$, establishing injectivity of $f \circ g$. For $y \in X$, choose $z$ such that $g(z) = f^{-1}(y)$. Then $f \circ g(z) = y$ so $f\circ g$ is surjective. Thus $G$ is closed under composition. If $f \in G$, $f^{-1}$ is also a bijection $X \to X$ so $f^{-1} \in G$. And of course the identity is a bijection. Since function composition is associative, $G$ is a group.

To show that $H_A$ is a subgroup of $S_X$, we use the subgroup criterion. $H_A$ is nonempty since it contains the identity. For $f, g \in H_A$, note that $g^{-1}(a) = a$ for all $a \in A$ so $f \circ g^{-1} = a$ for all $a \in A$. Since composition of bijections gives a bijection (as in the above) it follows $f \circ g^{-1} \in H_A$, so $H_A$ is a subgroup. $\square$

Let $A = \{m+1, m+2, \dots, n\}$. By our lemma, $H_A$ is a subgroup of $S_n$. For $\sigma \in H_A$, let $\varphi(\sigma)$ be the corresponding permutation in $S_m$ $($only the first $m$ numbers are moved amongst themselves, so $\sigma$ is essentially a permutation of $m$ letters$)$. $\varphi$ is clearly a bijection. Since function composition preserves fixed points, $\varphi$ is also a homomorphism $($again, only the first $m$ letters are permuted amongst themselves by $\sigma)$. Thus $S_m \cong H_A \le S_n$.

Answer 3

Intuition answer (not proof)

Consider $S_3$ and $S_5$. When we write in cycle notation, it's clear that $(123)\in S_3$ and $(123) \in S_5$. The same can be said for all other cycles in $S_3$ (e.g. $(12)\in S_3$ and $S_5$). So, take the subgroup of $S_5$ that consists of only the cycles that are also in $S_3$.

The same idea extends to any $S_n$, $S_m$.

Of course, this abuses the notation a bit, because writing in cycle notation does not completely define a mapping--the domain is lacking from the cycle notation. However, thinking in these "loose" terms helped me visualize the isomorphism.