Exercise 1.7.10 (For which values of $k$ are these actions faithful?)

Proof. Let ${𝒫}_k(A)$ denote the set of all subsets of $A$ of cardinality $k$.

(a)

In this part, $S_A$ acts on ${𝒫}_k(A)$ by $\sigma \cdot \{a_1,a_2,\dots ,a_k\}=\{\sigma (a_1),\sigma (a_2),\dots ,\sigma (a_k)\}$, where $1\le k\le n$.

(For clarity, I explain the method in the case $k=3$ and $A=\{1,2,3,4,5\}$. Suppose that $\sigma$ is an element of the kernel of the action. Then $\sigma \cdot X=X$ for all $X\in {𝒫}_3([[1,5]])$. Since $\sigma$ is injective,

$$\begin{array}{llll}\hfill & \sigma (1)\notin \{\sigma (2),\sigma (3),\sigma (4)\}=\{2,3,4\}& \hfill & \\ \hfill & \sigma (1)\notin \{\sigma (3),\sigma (4),\sigma (5)\}=\{3,4,5\},& \hfill & \end{array}$$

therefore $\sigma (1)\notin \{2,3,4,5\}$ so $\sigma (1)=1$, and similarly $\sigma (a)=a$ for all $a\in A$, thus $\sigma ={\mathrm{Id}}_A$, so the kernel of the action is $\{{\mathrm{Id}}_A\}$ and the action is faithful.)

We prove the generalization:

• If $k=n$, then ${𝒫}_k(A)={𝒫}_n(A)=\{A\}$. Therefore every $\sigma \in S_A$ satisfies $\sigma \cdot A=A$, so the kernel of the action is $S_A$, and the action is not faithful.

• Suppose now that $1\le k<n$. Let $\sigma$ be in the kernel of the action, so that for all $X\in {𝒫}_k(A)$, $\sigma \cdot X=X$. Let $a$ be any element of $A$, and let $b\ne a$ be any other element. Since $k<n$, there is some subset $X\in {𝒫}_k(A)$ such that $b\in X$ but $a\notin X$ (to obtain $X$, we take $X=Y\cup \{b\}$, where $Y\in {𝒫}_{k-1}(A\setminus \{a,b\})$: this is possible because $k-1\le n-2$ so that ${𝒫}_{k-1}(A\setminus \{a,b\})$ is not empty).

  Since $a\notin X,\sigma (a)\notin \sigma \cdot X=X$, therefore $\sigma (a)\ne b$. This is true for for every $b\in A$ such that $b\ne a$, therefore $\sigma (a)=a$, where $a$ is an arbitrary element of $A$, so $\sigma ={\mathrm{Id}}_A$. This shows that the kernel of the action is $\{{\mathrm{Id}}_A\}$ , so the action is faithful.

In conclusion, the values of $k\in [[1,n]]$ such that the action of $S_n$ on ${𝒫}_k(A)$ is faithful are $1,2,\dots n-1$, but not $n$.

(b)

In part (b), $S_A$ acts on $A^k$ by $\sigma \cdot (a_1,a_2,\dots ,a_k)=(\sigma (a_1),\sigma (a_2),\dots ,\sigma (a_k))$, where $k\in \mathbb{Z},k\ge 1$. Let $\sigma \in S_A$ be some permutation in the kernel of this action. Then for all $X\in A^k$, $\sigma \cdot X=X$. In particular, if $X=(a,a,\dots ,a)\in A^k$, then $(\sigma (a),\sigma (a),\dots ,\sigma (a))=(a,a,\dots ,a)$, so $\sigma (a)=a$ for every $a\in A$ and $\sigma ={\mathrm{Id}}_A$. This shows that the kernel of this action is $\{{\mathrm{Id}}_A\}$ thus the action is faithful for every $n\in {\mathbb{Z}}^{\text{+}}$.