General Commutativity Theorem

From ProofWiki
Jump to: navigation, search

Theorem

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

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

Suppose that:

$\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$

where $\N^*_n$ denotes the initial segment of $\N_{>0}$:

$\N^*_n = \left\{{1, 2, \ldots, n}\right\}$


Proof

The proof will proceed by the Principle of Mathematical Induction on $\N_{>0}$.

Let $T$ be the set of all $n \in \N_{>0}$ 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 \mathop \le k \mathop \le n}$ of $n$ elements 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$.


Basis for the Induction

We have that when $n = 1$:

$\sigma \left({1}\right) = 1$

and so:

$a_{\sigma \left({1}\right)} = a_1$

for all $\sigma: \left\{{1}\right\} \to \left\{{1}\right\}$.


Thus $1 \in T$.

This is our basis for the induction.


Induction Hypothesis

It is to be shown that, if $m \in T$ where $m \ge 1$, then it follows that $m + 1 \in T$.


This is the induction hypothesis:

$a_{\sigma \left({1}\right)} \circ \cdots \circ a_{\sigma \left({m}\right)} = a_1 \circ \cdots \circ a_m$

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

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

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


It is to be demonstrated that it follows that:

$a_{\sigma \left({1}\right)} \circ \cdots \circ a_{\sigma \left({m + 1}\right)} = a_1 \circ \cdots \circ a_{m + 1}$

holds for all sequences $\left \langle {a_k} \right \rangle_{1 \mathop \le k \mathop \le m + 1}$ of $m + 1$ elements of $S$ which satisfy:

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

for every permutation $\sigma: \N^*_{m + 1} \to \N^*_{m + 1}$.


Induction Step

This is our induction step:

Suppose $m \in T$.

Let $\left \langle {a_k} \right \rangle_{1 \le k \le m+1}$ be a sequence of $m+1$ elements of $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^*_{m+1} \to \N^*_{m+1}$ be a permutation of $\left[{1 \,.\,.\, m+1}\right]$.

There are three cases to consider:

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


$(1): \quad$ Suppose $\sigma \left({m+1}\right) = m + 1$.

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

From the induction hypothesis:

$m \in T$:

Thus:

$a_{\sigma \left({1}\right)} \circ \cdots \circ a_{\sigma \left({m}\right)} = a_1 \circ \cdots \circ a_m$

from which:

\(\displaystyle a_{\sigma \left({1}\right)} \circ \cdots \circ a_{\sigma \left({m + 1}\right)}\) \(=\) \(\displaystyle \left({a_{\sigma \left({1}\right)} \circ \cdots \circ a_{\sigma \left({m}\right)} }\right) \circ a_{\sigma \left({m + 1}\right)}\) $\quad$ $\quad$
\(\displaystyle \) \(=\) \(\displaystyle \left({a_1 \circ \cdots \circ a_m}\right) \circ a_{m + 1}\) $\quad$ $\quad$
\(\displaystyle \) \(=\) \(\displaystyle a_1 \circ \cdots \circ a_{m + 1}\) $\quad$ $\quad$


$(2): \quad$ Suppose $\sigma \left({1}\right) = m + 1$.


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

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


From Closed Interval of Naturally Ordered Semigroup with Successor equals Union with Successor:

$\left[{1 \,.\,.\, m + 1}\right] = \left[{1 \,.\,.\, m}\right] \cup \left\{{m + 1}\right\}$

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


Thus, as $m \in T$:

$a_{\tau \left({1}\right)} \circ \cdots \circ a_{\tau \left({m}\right)} = a_1 \circ \cdots \circ a_m$


So:

\(\displaystyle a_{\sigma \left({1}\right)} \circ \cdots \circ a_{\sigma \left({m + 1}\right)}\) \(=\) \(\displaystyle a_{\sigma \left({1}\right)} \circ \left({a_{\sigma \left({2}\right)} \circ \cdots \circ a_{\sigma \left({m + 1}\right)} }\right)\) $\quad$ $\quad$
\(\displaystyle \) \(=\) \(\displaystyle a_{m + 1} \circ \left({a_{\tau \left({1}\right)} \circ \cdots \circ a_{\tau \left({m + 1}\right)} }\right)\) $\quad$ $\quad$
\(\displaystyle \) \(=\) \(\displaystyle a_{m + 1} \circ \left({a_1 \circ \cdots \circ a_m}\right)\) $\quad$ $\quad$
\(\displaystyle \) \(=\) \(\displaystyle \left({a_1 \circ \cdots \circ a_m} \circ a_{m + 1}\right)\) $\quad$ Element Commutes with Product of Commuting Elements $\quad$
\(\displaystyle \) \(=\) \(\displaystyle a_1 \circ \cdots \circ a_{m + 1}\) $\quad$ $\quad$


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


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

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

Clearly $\tau$ is a permutation of $\N^*_{m+1}$.

So, by the first case:

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


Thus:

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


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


Thus by the Principle of Mathematical Induction:

$T = \N_{>0}$

The result follows.

$\blacksquare$


Sources