# isomorphism between some Permutation groups

Let $S_n$ be the Permutation group on ${1,...,n}$ , where $n\in \mathbb{N}$, and let $H$ be a subgroup of $S_{n+m}$,where $\sigma\in H$ iff for each $1 \le i \le n \ : \ 1 \le \sigma(i) \le n$ .

Prove that $H$ is isomorphic to $S_n\times S_m$.

My attempt:

Let $\phi(\sigma):H\to S_n\times S_m$ be: $(\sigma_1,\sigma_2)$ where :

$\sigma_1(i):[n]\to [n] , \sigma_1(i) = \sigma(i)$

$\sigma_2(j):[m]\to [m] , \sigma_2(j)=\sigma(j)$

How can I prove that it's a bijection?

Or maybe it isn't at all?

• Your notation is ambiguous. By $[n]$, I assume you mean $\{1,2,\ldots,n\}$, and by $[m]$, I assume you mean $\{n+1,n+2,\ldots,n+m\}$? – Bungo Apr 7 '17 at 22:00
• As written, your $\sigma_2$ is not well-defined: unless $m=n$, it is certainly possible for $\sigma(j) > m$ for some $j \in [m]$, in which case $\sigma_2$ is not a permutation on $[m]$. You may have the right idea in mind but it is not expressed accurately. – Erick Wong Apr 7 '17 at 22:02
• Assuming that you have shown that $\phi$ is a homomorphism, you can check injectivity by showing that its kernel is trivial. Surjectivity should be easy to show directly. Take an arbitrary element $(\sigma_1, \sigma_2) \in S_n \times S_m$, and show that there is some $\phi \in H$ that maps to that element. – Bungo Apr 7 '17 at 22:04
• @ChikChak Then do you want $\sigma_2(j) = \sigma(j+n)$ instead of $\sigma_2(j) = \sigma(j)$? – Bungo Apr 7 '17 at 22:05
• @Bungo I think you want the RHS to be $\sigma(j+n)-n$. – Erick Wong Apr 7 '17 at 22:06

## 1 Answer

I can't guess what $[m]$ means, but I presume that your $\sigma$ is

\begin{align} \phi(\sigma)=(\sigma |_{\{1,\cdots,n\}} , \sigma|_{\{{1',\cdots,m'\}}})\end{align} where we consider $S_{n+m}$ as the permutation group of $\{1,\cdots,n,1',\cdots,m'\}$.

Since $|H|=|S_n \times S_m |$, showing injectivity will be suffice. This follows

\begin{align} \phi(\sigma)=id &\Leftrightarrow \sigma |_{\{1,\cdots,n\}}=id|_{\{1,\cdots,n\}} \,\;\mathrm{and}\;\, \sigma|_{\{{1',\cdots,m'\}}} =id|_{\{1',\cdots,m'\}}\\ &\Leftrightarrow \sigma=id \end{align} where $id$ is the identity function on $\{1,\cdots,n,1',\cdots,m'\}$.

• What do you mean by ${1',...,m'}$?and why does it even shows injectivity? – ChikChak Apr 8 '17 at 11:15
• @Chikchak // $1', ..., m'$ are just an alias of $n+1 , \cdots , n+m$. I used this notation just for convenience. For second question, this is because of Pigeonhole principle, stating that for every finite set $A,B$ such that $|A|=|B|$, and a function $f:A\to B$, $f$ is injective if and only if $f$ is surjective. – Toast Apr 8 '17 at 12:10
• What I mean is,why showing what you proved with the $id$ function,proves injectivity? – ChikChak Apr 8 '17 at 18:57
• @ChikChak Once one knows that $\phi$ is a homomorphism, then injectivity is exactly equivalent to having a trivial kernel. Are you asking how to see that $\phi$ is a homomorphism? – Erick Wong Apr 8 '17 at 23:56
• @ErickWong is right. – Toast Apr 9 '17 at 6:01