How to prove that $\alpha\beta =\beta\alpha$ if $\alpha$ and $\beta $ are disjoint permutations of $S_n$ symmetric group of $n$ elements. Two permutations are said to be disjoint if every elment moved by one is fixed by another permutation.  My attempt : Let any $x \in [n]$,    if $\beta$ fixes element $x$, $\alpha\beta(x)$ it will be $\alpha(x)$ let's say $\alpha(x) = y \in  [n]$, now we need to show that $\beta\alpha(x)$ is equal to $y$, $\beta(y)$ will be $y$ as $y$ will be moved by $\alpha$.   Is there better way to prove this? I will go by case by case.
122080
I'm trying to prove that in a symmetric group two disjoint cycles commute. But I suspect that something is not right about my proof (a sense of vagueness). Some hints would be appreciated.  Here's my proof:  Let $\sigma=(s_1 s_2 ... s_n)$, $\tau=(t_1 t_2 ... t_m)$ for some integers $m, n$. That is, $s_i \neq t_j$ for any $i \in [1, n]$, $j \in [1, m]$. Now, $\sigma\tau=(s_1 ... s_n)(t_1 ... t_m)$ is a cycle of disjoint permutations, which cannot be represented by any other disjoint permutations. Thus $\sigma\tau=\tau\sigma$.
88756
I am struggling with the end of my proof.   So far I have used the fact that $S_n=\langle T\rangle$ where $T=\{(i\text{ }j)|1\leq i&lt;j\leq n\}$ to show that $S_n$ is generated by the set $\{(1\text{ }2),(1\text{ }3),\cdots,(1\text{ }n)\}$ of $n-1$ transpositions.   I am struggling with proving that $S_n$ is also generated by the set $\{(1\text{ }2),(2\text{ }3),\cdots,(n-1\text{ }n)\}$ of $n-1$ transpositions. Essentially I want to show that each $(1\text{ }i)$ is a product of these transpositions to reach this conclusion.   Here is what I have so far...    Consider any $(1\text{ }i)$ transposition in $S_n$. Notice by the composition of a permutation that \begin{eqnarray*} (1\text{ }i-1)(i-1\text{ }i)(1\text{ }i-1)&amp;=&amp;\begin{bmatrix}     1       &amp; i-1 &amp; i   \\     i-1       &amp; 1 &amp; i    \end{bmatrix} \begin{bmatrix}     1       &amp; i-1 &amp; i   \\    1       &amp; i &amp; i-1  \end{bmatrix} \begin{bmatrix}    1       &amp; i-1 &amp; i   \\     i-1       &amp; 1 &amp; i \end{bmatrix}\\ &amp;=&amp; \begin{bmatrix}     1       &amp; i-1 &amp; i   \\     i-1       &amp; 1 &amp; i    \end{bmatrix} \begin{bmatrix}    1       &amp; i-1 &amp; i   \\     i       &amp; 1 &amp; i-1 \end{bmatrix}\\ &amp;=&amp; \begin{bmatrix}    1       &amp; i-1 &amp; i   \\     i       &amp; i-1 &amp; 1 \end{bmatrix}\\ &amp;=&amp; (1\text{ }i) \end{eqnarray*}  Now we want to use this property, call it STAR, to show that $S_n$ is also generated by the set  $$Y=\{(1\text{ }2),(2\text{ }3),\cdots,(n-1\text{ }n)\}$$ of $n-1$ transpositions. Notice for each $(i\text{ }j)$ in $Y$ that $j-i=1$. Suppose $n=2$. Then $S_2=\{(1),(1\text{ }2)\}$, and we done because $2-1=1$. Suppose $n=3$. Then $S_3$ is generated by the set $\{(1\text{ }2),(1\text{ }3)\}$. By STAR,  $$ (1\text{ }3)=(1\text{ }2)(2\text{ }3)(1\text{ }2) $$ $$ (1\text{ }2)=(1\text{ }1)(1\text{ }2)(1\text{ }1) = (1\text{ }2) $$ Therefore $S_3$ is generated by $\{(1\text{ }2),(2\text{ }3)\}$ and for each $(i\text{ }j)$ we have $j-i=1$.    And here is where I am struggling. I do not know how to apply induction to this. I want to show that each side part will continue breaking down using the property I stated until all of $S_n$ is created. Here is why I think this: $$ (1\text{ }1)(1\text{ }2)(1\text{ }1)=(1\text{ }2) $$ $$ (1\text{ }2)(2\text{ }3)(1\text{ }2)=(1\text{ }3) $$ $$ \cdots $$ $$ (1\text{ }n-1)(n-1\text{ } n)(1\text{ } n-1)=(1\text{ }n) $$ Any input would be much appreciated. Best.
112043
Suppose I fix $n$ and let $\sigma_k$ represent the $k$th permutation of $S_n$ with respect to  some ordering (whatever ordering might serve my purpose). Is there an elementary formula for $\sigma_k(i)$ which requires only $i, k,$ and $n$?  Is one known for small $n$, perhaps even as small as 4?
54138
I'm working through Rotman (1994). It's the 2nd chapter where my curiosity lead me to a question that is not from the book. Here's the problem that inspired the question:      2.8. Imbed $S_n$ as a subgroup of $A_{n+2}$, but show, for $n\ge2$, that $S_n$ cannot be imbedded in $A_{n+1}.$    Since the alternate subgroup has the property of even parity, I thought that a little investigation of parity for the second and third symmetric groups was in order. So I constructed a table for each of them, grouped by even and odd number of disjoint products.   I'll forego writing the actual table and simply provide the answers. In symmetric groups with an even idegree, two even permutations come together under composition to produce an even permutation. Two odds also make an even. Two different parities produce odd elements.   When the symmetric group has an odd degree, e.g. $S_3$, two odds make an odd, two evens make an odd, and two different parities make an even element. Exactly the opposite results from the symmetric groups with even index.   Two questions: is this enough to prove the $A_{n+1}$ case? And can this be generalized modulo 2 e.g. $A_{2n+1}$?
97103
$(G,*)$ is an abelian group and $a,b$ are elements of G. Let $n=ord(a)$ and $m=ord(b)$ in $G$. Show that the order of $a*b$ is equal to $nm$ if $gcd(n,m)=1$.  I have already proved that $ord(a*b)|nm$. But the other part is a problem.  Thanks
67912
The set of permutations of the natural numbers has the cardinality of the continuum. I've got injections in both directions, no problem. The Schröder–Bernstein theorem tells us that this implies the existence of a bijection. I'm wondering if it's possible to construct one explicitly.  (In what follows, I'm using the convention that $0\not\in\Bbb N$. This obviously doesn't change anything, cardinality-wise.)    For $\Bbb R\to S_\Bbb N$, we note that every real number is the limit of some rearrangement of the alternating harmonic series. If $\alpha\in\Bbb R$, we start with positive terms: $1+\frac13+\frac15+\cdots$, until we obtain a partial sum greater than $\alpha$. We then add negative terms until our partial sum is less than $\alpha$, then we switch back to the positive terms, starting with the first unused one, etc.  In this way, we construct a series, and if we take the absolute values of the reciprocals of the terms of it, we have a permutation of $\Bbb N$. This mapping is not onto, because many permutations of the series converge to $\alpha$ - all we have to do is "overshoot" at some point, and then continue converging to $\alpha$ as usual. (More trivially, we only get permutations with $\sigma(1)=1$ using this particular construction.)    In the other direction, if we have a permutation $\sigma\in S_\Bbb N$, we can write the continued fraction $[\sigma(1);\sigma(2),\sigma(3),\ldots]$. This actually injects $S_\Bbb N$ into $\Bbb R\setminus\Bbb Q$, because non-terminating continued fractions represent irrational numbers. Thus, this mapping is not onto; it is not even onto the irrationals.For example, no permutation of $\Bbb N$ maps in this way to any quadratic irrational, or to $e$, or to any other irrational whose c.f. expansion has repeated terms.    So, those injections are fun and all, but finding an explicit bijection seems hard. Clearly, a bijection between $S_\Bbb N$ and any interval would suffice, because there are standard, elementary ways to construct bijections between $\Bbb R$ and any interval.  I have Googled in vain for a solution, and I don't believe this question is a duplicate. I will be happy for a hint or a full solution, or an explanation of why such an explicit construction is impossible.  Full disclosure: someone online claimed that this is "not hard", but refused to explain how, other than mentioning the Cauchy sequence construction of the reals. I don't see how that's useful, and I think he's mistaken or bluffing. I'm not too proud to admit I'm stumped. :/
66754
I have been working on this exercise for a while now. It's in B.L. van der Waerden's Algebra (Volume I), page $19$. The exercise is as follows:     The order of the symmetric group $S_n$ is $n!=\prod_{1}^{n}\nu$. (Mathematical induction on $n$.)   I don't comprehend how we can logically use induction here. It seems that the first step would be proving $S_1$ has $1!=1$ elements. This is simply justified: There is only one permutation of $1$, the permutation of $1$ to itself.  The next step would be assuming that $S_n$ has order $n!$. Now here is where I get stuck. How do I use this to show that $S_{n+1}$ has order $(n+1)!$?  Here is my attempt: I am thinking this is because all $n!$ permutations of $S_n$ now have a new element to permutate. For example, if we take one single permutation $$ p(1,\dots,n) = \begin{pmatrix} 1 &amp; 2 &amp; 3 &amp; \dots &amp; n\\ 1 &amp; 2 &amp; 3 &amp; \dots &amp; n \end{pmatrix} $$ We now have $n$ modifications of this single permutation by adding the symbol $(n+1)$:  \begin{align} p(1,2,\dots,n,(n+1))&amp;= \begin{pmatrix} 1 &amp; 2 &amp; \dots &amp; n &amp; (n+1)\\ 1 &amp; 2 &amp; \dots &amp; n &amp; (n+1) \end{pmatrix}\\ p(2,1,\dots,n,(n+1))&amp;= \begin{pmatrix} 1 &amp; 2 &amp; \dots &amp; n &amp; (n+1)\\ 2 &amp; 1 &amp; \dots &amp; n &amp; (n+1) \end{pmatrix}\\ \vdots\\ p(n,2,\dots,1,(n+1))&amp;= \begin{pmatrix} 1 &amp; 2 &amp; \dots &amp; n &amp; (n+1)\\ n &amp; 2 &amp; \dots &amp; 1 &amp; (n+1) \end{pmatrix}\\ p((n+1),2,\dots,n,1)&amp;= \begin{pmatrix} 1 &amp; 2 &amp; \dots &amp; n &amp; (n+1)\\ (n+1) &amp; 2 &amp; \dots &amp; n &amp; 1 \end{pmatrix} \end{align}  There are actually $(n+1)$ permutations of that specific form, but we take $p(1,\dots,n)=p(1,\dots,n,(n+1))$ in order to illustrate and prove our original statement. We can make this general equality for all $n!$ permutations: $p(x_1,x_2,\dots,x_n)=p(x_1,x_2,\dots,x_n,x_{n+1})$ where $x_i$ is any symbol of our finite set of $n$ symbols and $x_{n+1}$ is strictly defined as the symbol $(n+1)$.  We can repeat this process for all $n!$ permutations in $S_n$. This gives us $n!n$ permutations. Then, adding in the original $n!$ permutations, we have $n!n+n!=(n+1)n!=(n+1)!$. Consequently, $S_n$ has order $n!$.  How is my reasoning here? Furthermore, is there a more elegant argument? I do not really see my argument here as incorrect, it just seems to lack elegance. My reasoning may well be very incorrect, however. If so, please point it out to me.
122837
Let $H&lt;S_{n}$ and suppose $H$ is not contained in $A_{n}$. Write $H$ as $$H=E\cup O$$ where $E$ and $O$ represent the sets of even and odd elements, respectively. Let $E=\{{\alpha_1,...,\alpha_n}\}$ and $O=\{{\beta_1,...,\beta_m}\}$. Since $O$ is non-empty, it contains at least one element, say $\beta_1$. The same goes for $E$ because $e\in E$. Our goal is to prove $m=n$. The products $\beta_1\alpha_i$, $i=1,...n$, are all distinct elements in $O$, and it follows that $O$ has at least $n$ elements, i.e. $m\geq n$. In the case of strict inequality, $m&gt;n$, add at least one extra odd element ($\beta_{n+1}$) to the list $$\beta_1\alpha_1,...,\beta_1\alpha_n,\beta_{n+1}$$  This is where I find myself stuck. Any help appreciated. Can this route work?
36575
Let the permutation group $S_3$ act on $\mathbb{R}^3$ by permuting the elements.   How can we show that this action can be written as  $\sigma (x_1, x_2, x_3) = ( x_{\sigma^{-1}(1)}, x_{\sigma^{-1}(2)}, x_{\sigma^{-1}(3)})$ for $\sigma \in S_3$, $(x_1, x_2, x_3) \in \mathbb{R}^3$.  For instance, if $\sigma = (123)$, we have $\sigma (x_1, x_2, x_3) = (123)(x_1, x_2, x_3) = (x_3, x_1, x_2)$.  Just looking at some examples, this seems so obvious, but I'm not sure how to go about showing it.
70337
In Dummit &amp; Foote, page 131  Let $K$ be a conjugacy class and suppose that $K$ is subset of $A_n$ .  Show that if $\sigma$  belongs to $S_n$ then , $\sigma$ does not commute with any odd permutation if and only if the cycle type of  consists of distinct odd integers.  Deduce that $K$ is a union of two -conjugacy classes in $A_n$ if and only if the cycle type of  an element of $K$ consists of distinct odd integers.   [Hint: Assume first that $\sigma$  belongs to $S_n$ does not commute with any odd permutation. Observe that $\sigma$ commutes with each cycle in its own cycle decomposition, so that each cycle must have odd length. If two cycles have the same odd length , find a product of  transpositions which interchanges them and commutes with $\sigma$ . Conversely, if the cycle type of $\sigma$ consists of distinct integers, prove that $\sigma$ commutes only with the subgroup generated by the cycles in its cycle decomposition.]  the exercise number 21 , i uesed the hints to prove that the cycles of cycle decomposition of $\sigma $ must be of odd length , but i don't know how to prove that the cycle type is distinct . the text said find transposition which interchanges them and commute $\sigma$ , my question is , interchange what ?!!! what does this mean ? can anyone help ?
63191
Prove the following in $S_n$:  Let $\alpha = (a_1,a_2,\ldots,a_s)$ be a cycle and let $\pi$ be a permutation in $S_n$. Then $\pi\alpha\pi^{-1}$ is the cycle $(\pi(a_1),\ldots,\pi(a_s)).$     I'm not sure where to even start.
110511
Let $K$ and $N$ be normal subgroups of $G$ such that $K \cap N = \langle e \rangle$. Prove that $nk = kn$ for all $n \in N$ and for all $k \in K$.   Since $K$ and $N$ are normal, we have $nK = Kn$ and $kN = Nk$. However, on their own they don't imply $nk = kn$. How can I prove this?
43847
Let $\sigma = (1234) \in S_6$. List all elements in $N(\sigma) = \{\alpha\in S_6 \mid \sigma\alpha=\alpha\sigma\}$.   I know this relates to cycles and orders, but I am having trouble finding the order of $N(\sigma)$ and then the list of elements.
110596
I am currently working through Joseph Rotman's book &quot;Galois Theory&quot; and am trying to prove the following theorem.  If $f(x) \in F[x]$ has $n$ distinct roots in its splitting field $E$, then $\operatorname{Gal}(E/F)$ is isomorphic to a subgroup of the symmetric group $S_n$, thus its order is a divisor of $n!$.  I have struggled to understand the proof in the book and have therefore tried to write my own proof of this fact, I have found some questions close to this on this site, but haven't been able to find exactly what I'm looking for. My proof (so far) is as follows: Proof: Let $X = \{\alpha_1, ... , \alpha_n \}$ be the set of roots of $f(x)$, as $E$ is the splitting field of $f$, it may be written as $E = F(\alpha_1, ... , \alpha_n)$ and noting that $\alpha_i \neq \alpha_j$ for $i\neq j$. Let $\sigma \in \operatorname{Gal}(E/F)$ then $\sigma(X) = X$ (a result from an earlier lemma). Now I would like to construct an injective homomorphism from $\operatorname{Gal}(E/F)$ to $S_n$, my guess is the map which sends $\sigma$ to its restriction in $X$, which I shall denote by $\sigma_X$. Let $g$ be this map, then it is clear that $g$ is a homomorphism. Now I try to show that $g$ is injective, consider $\sigma, \phi \in \operatorname{Gal}(E/F)$ where $\sigma \neq \phi$, both of these functions are F-automorphisms of $E/F$, so they &quot;fix&quot; $F$, then we can conclude that $\sigma$ and $\phi$ can be different if and only if they act differently on $X$, which in the language of mathematics is precisely $\sigma \neq \phi \Leftrightarrow \sigma_X \neq \phi_X$. This is the definition of an injective function. This means that $\left|\operatorname{Gal}(E/F)\right| \leq |S_n| = n!$, however due to having constructed a homomorphism, we have mapped a group  to another group, hence we have mapped $\operatorname{Gal}(E/F)$ to a subgroup of $S_n$, whose order divides $|S_n|$ and therefore $\left|\operatorname{Gal}(E/F)\right|$ divides $n!$, completing the proof. Question I am wondering whether my proof for this is correct, I think that it is mostly there, with the statement  we can conclude that $\sigma$ and $\phi$ can be different if and only if they act differently on X  perhaps being the only issue.
34209
I'm trying trying to prove that an $n$-cycle in some symmetric group has order $n$, but I don't know where to start. Would appreciate some hints.
46025
Let $A,B &lt; G$ be two subgroups of some group $G$, then I have a question on the proof of the following: $$  |AB| = \frac{|A||B|}{|A \cap B|}. $$ Proof: Let $D = A \cap B$, arrange $A$ and $B$ in left cosets and right cosets regarding $D$ (which is also a subgroup) $$  A = D \cup s_2 D \cup s_3 D \cup \ldots \cup s_n D, \quad   B = D \cup D t_2 \cup D t_3 \cup \ldots \cup D t_m $$ Now the fact that $\frac{|A||B|}{|D|}$ are distinct results from the following equations: If $$  s_{\alpha}D D t_{\beta} = s_{\alpha_1} D D t_{\beta_1} $$ then $$  s_{\alpha_1}^{-1} s_{\alpha} D = D t_{\beta} t_{\beta}^{-1} $$ As the first member of the last equation represents an element of $A$ while the second member represents an element of $B$, it results that the last equation implies $\alpha_1 = \alpha$ and $\beta_1 = \beta$.  The last step is not clear to me, why does $\alpha_1 = \alpha$ and $\beta_1 = \beta$ follows? Is it the case that if $aD = Db$ for $a \in A$ and $b \in B$ that $a=b=1$ follows? I don't believe this and cannot prove it either? Could someone please explain the last step?
74986
Let $\sigma \in S_n \;$ then $\; \sum_{i=1}^n|\sigma(i)-i|\;$ is an even number. I tried to show the statement for cyclic permutations first. However, I am not getting anywhere. The statement is trivial for transposition $(k,l)$. That´s all what I have found out so far. Can someone give me a hint why the statement is in fact true for any cyclic permutation ?