Suppose $S_n$ acts on a set of $k$ element subsets of $\{1,\ldots,n\}$, by $\sigma\cdot\{a_1,\ldots,a_k\}=\{\sigma(a_1),\ldots,\sigma(a_k)\}$ where $k<n$ and $\sigma\in S_n$. Show that action is faithful.

Proof: Suppose action not faithful, then there exist $\sigma, \tau\in S_n$ such that $\sigma\cdot\{a_1,\ldots,a_k\}=\tau\cdot\{a_1,\ldots,a_k\}$ for all $k$ element subsets $\{a_1,\ldots,a_k\}$, but $\sigma\ne \tau$. Then there exists an $x\in\{1,\ldots,n\}$ such that $\sigma(x)\ne\tau(x)$. But I can't see how to show $\sigma\cdot\{x,\ldots,a_k\}\ne\tau\cdot\{x,\ldots,a_k\}$.


You need to assume that $1 \le k$ as well as $k<n$.

Suppose that $1 \ne \sigma \in S_n$. So there exists $x$ with $\sigma(x) \ne x$. Then $\sigma^{-1}(x) \ne x$, so there exists a $k$-subset $S$ with $x \in S$ but $\sigma^{-1}(x) \not\in S$. Then $x \not\in \sigma(S)$, so $\sigma(S) \ne S$. So the action of $S_n$ on the set of $k$-subsets is faithful.

  • $\begingroup$ Why does $\sigma(S) \ne S$ imply the action is faithful? $\endgroup$ – Silent Mar 15 '18 at 14:18
  • $\begingroup$ That follows immediately from the definition of a faithful action. $\endgroup$ – Derek Holt Mar 15 '18 at 14:30

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.