General Commutativity Theorem

Theorem

Let $\left({S, \circ}\right)$ be a semigroup.

Let $\left \langle {a_k} \right \rangle_{1 \le k \le n}$ be a sequence of terms of $S$.

Suppose $\forall i, j \in \left[{1 \,.\,.\, n}\right]: a_i \circ a_j = a_j \circ a_i$.

Then for every permutation $\sigma: \N^*_n \to \N^*_n$:

$a_{\sigma \left({1}\right)} \circ \cdots \circ a_{\sigma \left({n}\right)} = a_1 \circ \cdots \circ a_n$

Proof

Let $T$ be the set of all $n \in \N^*$ such that:

$a_{\sigma \left({1}\right)} \circ \cdots \circ a_{\sigma \left({n}\right)} = a_1 \circ \cdots \circ a_n$

holds for all sequences $\left \langle {a_k} \right \rangle_{1 \le k \le n}$ of $n$ terms of $S$ which satisfy:

$\forall i, j \in \left[{1 \,.\,.\, n}\right]: a_i \circ a_j = a_j \circ a_i$

for every permutation $\sigma: \N^*_n \to \N^*_n$.

It is clear that $1 \in T$.

Suppose $n \in T$.

Let $\left \langle {a_k} \right \rangle_{1 \le k \le n+1}$ be a sequence of $n+1$ terms in $S$ which satisfy:

$\forall i, j \in \left[{1 \,.\,.\, n+1}\right]: a_i \circ a_j = a_j \circ a_i$

Let $\sigma: \N^*_{n+1} \to \N^*_{n+1}$ be a permutation of $\left[{1 \,.\,.\, n+1}\right]$.

There are three cases to consider:

$(1): \quad \sigma \left({n+1}\right) = n + 1$

$(2): \quad \sigma \left({1}\right)= n + 1$

$(3): \quad \sigma \left({m}\right) = n + 1$ for some $m \in \left[{2 \,.\,.\, n}\right]$.

Suppose $\sigma \left({n+1}\right) = n + 1$:

Then the restriction of $\sigma$ to $\N^*_n$ is then a permutation of $\N^*_n$.

Thus, as $n \in T$:

$a_{\sigma \left({1}\right)} \circ \cdots \circ a_{\sigma \left({n}\right)} = a_1 \circ \cdots \circ a_n$

from which:

	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle a_{\sigma \left({1}\right)} \circ \cdots \circ a_{\sigma \left({n+1}\right)}\)	\(=\)	\(\displaystyle \left({a_{\sigma \left({1}\right)} \circ \cdots \circ a_{\sigma \left({n}\right)} }\right) \circ a_{\sigma \left({n+1}\right)}\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle \left({a_1 \circ \cdots \circ a_n}\right) \circ a_{n+1}\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle a_1 \circ \cdots \circ a_{n+1}\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)

Suppose $\sigma \left({1}\right)= n + 1$:

Let $\tau: \N^*_n \to \N^*_n$ be the mapping defined as:

$\forall k \in \left[{1 \,.\,.\, n}\right]: \tau \left({k}\right) = \sigma \left({k + 1}\right)$

From Closed Interval of Successor, $\left[{1 \,.\,.\, n+1}\right] = \left[{1 \,.\,.\, n}\right] \cup \left\{{n+1}\right\}$.

Thus $\tau$ is clearly a permutation on $\left[{1 \,.\,.\, n}\right]$.

Thus, as $n \in T$:

$a_{\tau \left({1}\right)} \circ \cdots \circ a_{\tau \left({n}\right)} = a_1 \circ \cdots \circ a_n$

So:

	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle a_{\sigma \left({1}\right)} \circ \cdots \circ a_{\sigma \left({n+1}\right)}\)	\(=\)	\(\displaystyle a_{\sigma \left({1}\right)} \circ \left({a_{\sigma \left({2}\right)} \circ \cdots \circ a_{\sigma \left({n+1}\right)} }\right)\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle a_{n+1} \circ \left({a_{\tau \left({1}\right)} \circ \cdots \circ a_{\tau \left({n+1}\right)} }\right)\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle a_{n+1} \circ \left({a_1 \circ \cdots \circ a_n}\right)\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle \left({a_1 \circ \cdots \circ a_n} \circ a_{n+1}\right)\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	Associativity and Commutativity Properties
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle a_1 \circ \cdots \circ a_{n+1}\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)

Suppose $\sigma \left({m}\right) = n + 1$ for some $m \in \left[{2 \,.\,.\, n}\right]$:

Let $\tau: \N^*_{n+1} \to \N^*_{n+1}$ be a mapping defined by:

$\forall k \in \N^*_{n+1}: \tau \left({k}\right) = \begin{cases} \sigma \left({k}\right): & k \in \left[{1 \,.\,.\, m-1}\right] \\ \sigma \left({k+1}\right): & k \in \left[{m \,.\,.\, n}\right] \\ n + 1: & k = n + 1 \end{cases}$

Clearly $\tau$ is a permutation of $\N^*_{n+1}$. So, by the first case:

$a_{\tau \left({1}\right)} \circ \cdots \circ a_{\tau \left({n+1}\right)} = a_1 \circ \cdots \circ a_{n+1}$

Thus:

	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle a_{\sigma \left({1}\right)} \circ \cdots \circ a_{\sigma \left({n+1}\right)}\)	\(=\)	\(\displaystyle \left({a_{\sigma \left({1}\right)} \circ \cdots \circ a_{\sigma \left({m-1}\right)} }\right) \circ \left({a_{\sigma \left({m}\right)} \circ \left({a_{\sigma \left({m+1}\right)} \circ \cdots \circ a_{\sigma \left({n+1}\right)} }\right)}\right)\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle \left({a_{\tau \left({1}\right)} \circ \cdots \circ a_{\tau \left({m-1}\right)} }\right) \circ \left({a_{\tau \left({n+1}\right)} \circ \left({a_{\tau \left({m}\right)} \circ \cdots \circ a_{\tau \left({n}\right)} }\right)}\right)\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle \left({a_{\tau \left({1}\right)} \circ \cdots \circ a_{\tau \left({m-1}\right)} }\right) \circ \left({\left({a_{\tau \left({m}\right)} \circ \cdots \circ a_{\tau \left({n}\right)} }\right) \circ a_{\tau \left({n+1}\right)} }\right)\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle a_{\tau \left({1}\right)} \circ \cdots \circ a_{\tau \left({n+1}\right)}\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle a_1 \circ \cdots \circ a_{n+1}\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)

So in all cases, $n+1 \in T$.

Thus by induction $T = \N^*$, and the result follows.

$\blacksquare$

Sources

• Seth Warner: Modern Algebra (1965)... (previous)... (next): $\S 18$: Theorem $18.7$