# Is this a typo in a proof regarding action of a permutation group on a set?

Recently, I asked a question about action of a permutation group on a set here. Let me summarize it.

Let $$\mathrm{S}_{m}$$ be the set of all permutations of $$\{1,2,\cdots,m\}$$. Then $$(\mathrm{S}_{m},\circ)$$ is a group where $$\circ$$ is function composition operation.

Show that $$\mathrm{S}_{m} \times \mathbb{N}^{m} \rightarrow \mathbb{N}^{m}, \quad(\sigma, x) \mapsto \sigma \cdot x := \left(x_{\sigma^{-1}(1)}, \ldots, x_{\sigma^{-1}(m)}\right)$$ defines an action of $$\mathrm{S}_{m}$$ on $$\mathbb{N}^{m}$$.

For $$\sigma , \tau \in \mathrm{S}_{m}$$ and $$x \in \mathbb{N}^{m}$$, I try to prove $$\sigma \cdot (\tau \cdot x) = (\sigma \circ \tau) \cdot x$$

In this answer, Wuestenfux presents the following proof:

\begin{aligned} \sigma \tau \cdot x &= (x_{(\sigma\tau)^{-1}(1)}, \ldots, x_{(\sigma\tau)^{-1}(n)})\\ &= (x_{\tau^{-1}\sigma^{-1}(1)}, \ldots, x_{\tau^{-1}\sigma^{-1}(n)}) \\ &= \tau\cdot (x_{\sigma^{-1}(1)}, \ldots, x_{\sigma^{-1}(n)})\\ &=\sigma\cdot(\tau \cdot x) \end{aligned}

Here he writes $$\sigma \tau$$ for $$\sigma \circ \tau$$.

In his proof, I think $$(x_{\tau^{-1}\sigma^{-1}(1)}, \ldots, x_{\tau^{-1}\sigma^{-1}(n)}) = \tau\cdot (x_{\sigma^{-1}(1)}, \ldots, x_{\sigma^{-1}(n)})$$ is wrong. Instead, it should be $$(x_{\tau^{-1}\sigma^{-1}(1)}, \ldots, x_{\tau^{-1}\sigma^{-1}(n)}) = \sigma \cdot (x_{\tau^{-1}(1)}, \ldots, x_{\tau^{-1}(n)})$$.

My reasoning:

1. In $$(x_{\tau^{-1}\sigma^{-1}(1)}, \ldots, x_{\tau^{-1}\sigma^{-1}(n)})$$, the flow of input-output is $$\sigma \longrightarrow \tau \longrightarrow x$$, whereas it is $$\tau \longrightarrow \sigma \longrightarrow x$$ in $$\tau\cdot (x_{\sigma^{-1}(1)}, \ldots, x_{\sigma^{-1}(n)})$$. As such, I feel that it is counter-intuitive to have $$(x_{\tau^{-1}\sigma^{-1}(1)}, \ldots, x_{\tau^{-1}\sigma^{-1}(n)}) = \tau\cdot (x_{\sigma^{-1}(1)}, \ldots, x_{\sigma^{-1}(n)})$$.

2. It's clear that $$\sigma \cdot x = x \circ \sigma^{-1}$$. Then \begin{aligned} \sigma \tau \cdot x &= x \circ (\sigma \circ \tau)^{-1}\\ &= x \circ (\tau^{-1} \circ \sigma^{-1})\\ &= (x \circ \tau^{-1}) \circ \sigma^{-1}\\ &= \sigma \cdot (x \circ \tau^{-1})\\ &= \sigma \cdot (x_{\tau^{-1}(1)}, \ldots, x_{\tau^{-1}(n)}) \end{aligned}

Please check if my reasoning is correct or not!

• See example 2.5 and 2.6 here. – Thomas Shelby Jun 1 at 4:01
• Hi @ThomasShelby. Thank you so much for your link! It really helps me understand what is going on behind the notation. I have posted my reasoning as an answer below. Could you please have a check on it? – Le Anh Dung Jun 1 at 9:32
• Thank you so much for your kindness @ThomasShelby :v – Le Anh Dung Jun 1 at 13:18

## 1 Answer

I found that the blue argument is not correct in @Wuestenfux's proof.

\begin{aligned} \sigma \tau \cdot x &= (x_{(\sigma\tau)^{-1}(1)}, \ldots, x_{(\sigma\tau)^{-1}(n)})\\ &= \color{blue}{(x_{\tau^{-1}\sigma^{-1}(1)}, \ldots, x_{\tau^{-1}\sigma^{-1}(n)})} \\ &= \color{blue}{\tau\cdot (x_{\sigma^{-1}(1)}, \ldots, x_{\sigma^{-1}(n)})}\\ &= \sigma\cdot(\tau \cdot x) \end{aligned}

We have

\begin{aligned} \sigma \cdot (\tau \cdot x) &= \color{blue}{\sigma \cdot (x_{\tau^{-1}(1)}, \ldots, x_{\tau^{-1}(n)})} \\ &= \sigma \cdot (d_1, \ldots, d_n) \quad \text{where} \quad d_i = x_{\tau^{-1}(i)} \\ &= (d_{\sigma^{-1} (1)}, \ldots, d_{\sigma^{-1} (n)}) \\ &= (x_{\tau^{-1} (\sigma^{-1}(1))}, \ldots, x_{\tau^{-1} (\sigma^{-1} (n))})\\ &= \color{blue}{(x_{\tau^{-1}\sigma^{-1}(1)}, \ldots, x_{\tau^{-1}\sigma^{-1}(n)})} \end{aligned}

It follows that $$(x_{\tau^{-1}\sigma^{-1}(1)}, \ldots, x_{\tau^{-1}\sigma^{-1}(n)}) = \sigma \cdot (x_{\tau^{-1}(1)}, \ldots, x_{\tau^{-1}(n)})$$ and NOT that $$(x_{\tau^{-1}\sigma^{-1}(1)}, \ldots, x_{\tau^{-1}\sigma^{-1}(n)}) = \tau\cdot (x_{\sigma^{-1}(1)}, \ldots, x_{\sigma^{-1}(n)})$$

• Seems correct. I wasn't convinced either. – Wuestenfux Jun 1 at 12:34
• Hi @Wuestenfux, I quite don't understand by "I wasn't convinced either". Did you mean that you are not convinced by my reasoning? – Le Anh Dung Jun 1 at 12:37
• Just my reasoning. I had to do a substitution. – Wuestenfux Jun 1 at 12:39
• Thank you so much for your interest in my question @Wuestenfux :) – Le Anh Dung Jun 1 at 14:14