Exercise 14.3.1

Proof. (a) If $n=1$, then $S_n=\{e\}$ and $G=\{e\}$. Then $G$ is primitive (we can’t partition $\{1,\dots ,n\}=\{1\}$ with classes $R_i$ such that $|R_i|>1$ for some $i$), but $G$ is transitive, since $e(1)=1$. So the assumption $G\subset S_n$ is primitive but not transitive implies $n>1$. (b) If $k=1$, there is only one orbit $R_1=G\cdot 1$. Then $G$ is transitive: if $i,j\in \{1,n\}$, $i=\sigma (1),j=\tau (1),\sigma ,\tau \in G$, thus $(\tau {\sigma }^{-1})(i)=j$, where $\tau {\sigma }^{-1}\in G$. This shows that $G$ is transitive. Since $G$ is not transitive, then $k>1$.

We know that the orbits partition $\{1,\dots ,n\}$.

Now we prove that, if $\sigma \in G$ and $R_i$ is an orbit, then $\sigma (R_i)=R_i$ is the same orbit $R_i$.

Fix $x\in R_i$, so that $R_i={\mathcal{}O}_x=G\cdot x$ is the orbit of $x$.

Let $u\in R_i$. Then $u=\tau (x)$ for some $\tau \in G$. Then $\sigma (u)=(\mathit{\sigma \tau })(x)\in R_i$. This proves $\sigma (R_i)\subset R_i$.

Conversely, for every $u=\tau (x)\in R_i$, $u=\sigma (({\sigma }^{-1}\tau )(x))$ ,where $({\sigma }^{-1}\tau )(x)\in R_i$, thus $u\in \sigma (R_i)$. Therefore $R_i\subset \sigma (R_i)$. For all $\sigma \in G$,

(c) If $|R_i|>1$ for some $i$, then $G$ is imprimitive by Definition 14.2.5. By assumption, $G$ is primitive, thus $|R_i|=1$ for all $i$, so that every orbit consists of a single element. This means that for all $\sigma \in G$, and for all $i\in \{1,\dots ,n\}$, $\sigma (i)=i$. Therefore $\sigma =e$ for all $\sigma \in G$, $G=\{e\}$. Since $n>1$ by part (a), $G$ is imprimitive, because there are partitions with at least two classes, and several elements in a class, for instance $R_1=\{1,2\},R_2=\{1,\dots ,n\}\setminus R_1$, is preserved by $G=\{e\}$. This proves that $G=\{e\}$ is imprimitive when $n>1$, in contradiction with the assumption.

This contradiction proves $|R_i|>i$ for some index $i$, thus $G$ is imprimitive.

To conclude, all primitive permutation groups are transitive. □