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?

  • 1
    $\begingroup$ 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\}$? $\endgroup$ – Bungo Apr 7 '17 at 22:00
  • 1
    $\begingroup$ 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. $\endgroup$ – Erick Wong Apr 7 '17 at 22:02
  • 1
    $\begingroup$ 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. $\endgroup$ – Bungo Apr 7 '17 at 22:04
  • 2
    $\begingroup$ @ChikChak Then do you want $\sigma_2(j) = \sigma(j+n)$ instead of $\sigma_2(j) = \sigma(j)$? $\endgroup$ – Bungo Apr 7 '17 at 22:05
  • 2
    $\begingroup$ @Bungo I think you want the RHS to be $\sigma(j+n)-n$. $\endgroup$ – Erick Wong Apr 7 '17 at 22:06

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'\}$.

  • $\begingroup$ What do you mean by ${1',...,m'}$?and why does it even shows injectivity? $\endgroup$ – ChikChak Apr 8 '17 at 11:15
  • 1
    $\begingroup$ @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. $\endgroup$ – Toast Apr 8 '17 at 12:10
  • $\begingroup$ What I mean is,why showing what you proved with the $id$ function,proves injectivity? $\endgroup$ – ChikChak Apr 8 '17 at 18:57
  • 1
    $\begingroup$ @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? $\endgroup$ – Erick Wong Apr 8 '17 at 23:56
  • $\begingroup$ @ErickWong is right. $\endgroup$ – Toast Apr 9 '17 at 6:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.