This is Exercise 7.2.1 of Robinson's, "A Course in the Theory of Groups (Second Edition)". According to this search for "symmetric group primitive" in the group-theory tag, this is new to MSE.
Arguments are written on the left.
Here "$Y\subset X$" means "$Y$ is a proper subset of $X$".
The Details:
(This can be skipped.)
A permutation group $G$ on a set $X$ is a subgroup of $S_X$ (but not simply isomorphic to such a subgroup).
An action $\cdot: X\times G\to X$ is a function such that, for all $x\in X$ and $g,h\in G$, we have $x\cdot e=x$ and $(x\cdot g)\cdot h=x\cdot (gh)$.
A transitive action of a permutation group $G$ on $X$ is an action of $G$ on $X$ such that, for any $x,y\in X$, we have some permutation $\pi\in G$ with $x\pi=y$.
If $G$ acts transitively on $X$, then $G$ is called transitive.
Let $G$ be a transitive permutation group on $X$. If $Y\subset X$ has at least two elements, it is called a domain on imprimitivity of $G$ if, for each $\pi\in G$, either $Y=Y\pi$ or $Y\cap Y\pi=\varnothing$. We call $G$ imprimitive in this case; otherwise, $G$ is primitive.
The following theorem is on page 198:
Theorem 7.2.3: Let $G$ be a transitive permutation group on a set $X$ and let $a\in X$. Then $G$ is primitive if and only if $G_a$ is a maximal subgroup of $G$.
Here $G_a$ is the pointwise stabiliser ${\rm St}_G(a)$.
The Question:
Prove that $S_n$ is primitive.
Thoughts:
That $G=S_n$ is a transitive permutation group is clear. Indeed, its elements are permutations of $X=\{1,\dots, n\}$ and, for any $x,y\in X$, we have
$$x(xy)=y,$$
where $(xy)$ is given by
$$a(xy)=\begin{cases}
a &: a\notin \{x,y\},\\
x &: a=y,\\
y &: a=x.
\end{cases}$$
Let $Y\subset X$ have at least two elements. I need to show that, for some $\pi\in G$, we have neither $Y=Y\pi$ nor $Y\cap Y\pi=\varnothing$.
Alternatively, if for any $a\in X$, $G_a$ is maximal in $G$, then I would be done by Theorem 7.2.3.
Note that $|X|\ge 3$.
I have been stuck on this exercise for over a week. I'd move on if it wasn't so simple looking; I think I should be able to do it. But I think it's time I ask here . . .
Please help 🙂
Best Answer
Consider that $Y=Y\pi$ means that all the items in $Y$ are permuted amongst themselves, and $Y\cap Y\pi=\varnothing$ means the items in $Y$ are all mapped to outside of $Y$.
You want to find a permutation $\pi$ that does neither, so for example find one that maps one item in $Y$ to itself and maps another item in $Y$ to outside of $Y$. Note that $Y$ has at least two elements, and $Y$ is not the whole of $X$ so there is at least one element outside of $Y$. A single transposition between an element of $Y$ and an element of $X-Y$ will do.
This shows that $S_X$ (or $S_n$) is primitive, because for any candidate $Y$ for a domain of imprimitivity we can find a $\pi \in S_X$ that shows it is not.