Associativity on Indexing Set

Theorem

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

Let $\left \langle {x_\alpha} \right \rangle_{\alpha \in A}$ be a family of terms of $S$ indexed by a finite nonempty set $A$.

Let $\left \langle {B_k} \right \rangle_{1 \le k \le n}$ be a family of distinct subsets of $A$ forming a partition of $A$. Then:

$\displaystyle \prod_{k=1}^n \left({\prod_{a \in B_k} x_\alpha}\right) = \prod_{\alpha \in A} x_\alpha$

Proof

For each $k \in \N^*$, let $\left|{B_k}\right| = p_k$.

Let $r_0 = 0$, $\displaystyle \forall k \in \N^*: r_k = \sum_{j=1}^k {p_j}$, and let $p = r_n$.

Then $r_k - r_{k-1} = p_k$, so by Isomorphism to Closed Interval, both $\left[{1 \,.\,.\, p_k}\right]$ and $\left[{r_{k-1}+1 \,.\,.\, r_k}\right]$ have $p_k$ elements.

By Unique Isomorphism between Finite Totally Ordered Sets, there is a unique isomorphism $\tau_k: \left[{1 \,.\,.\, p_k}\right] \to \left[{r_{k-1}+1 \,.\,.\, r_k}\right]$ as both are totally ordered.

The orderings on both of these are those induced by the ordering on $\N$.

It is clear that $\tau_k$ is defined as:

$\forall j \in \left[{1 \,.\,.\, p_k}\right]: \tau_k \left({j}\right) = r_k + j$

For each $k \in \left[{1 \,.\,.\, n}\right]$, let $\rho_k: \left[{1 \,.\,.\, p_k}\right] \to B_k$ be a bijection.

By Strictly Increasing Sequence induces Partition, the mapping $\sigma: \left[{1 \,.\,.\, p}\right] \to A$ defined by:

$\displaystyle \forall j \in \left[{r_{k-1}+1 \,.\,.\, r_k}\right]: \forall k \in \left[{1 \,.\,.\, n}\right]: \sigma \left({j}\right) = \rho_k \left({\tau_k^{-1} \left({j}\right)}\right)$

is a bijection.

Let $\forall j \in \left[{1 \,.\,.\, p}\right]: y_j = x_{\sigma \left({j}\right)}$.

By definition:

$\displaystyle \prod_{\alpha \in A} {x_\alpha} = \prod_{j=1}^p {x_{\sigma \left({j}\right)}} = \prod_{j=1}^p {y_j}$

Also:

$\displaystyle \forall k \in \left[{1 \,.\,.\, n}\right]: \prod_{\alpha \in B_k} {x_\alpha} = \prod_{i=1}^{p^k} {x_{\rho_k \left({i}\right)}}$

Also by definition:

$\displaystyle \prod_{j = r_{k-1}+1}^{r_k} y_j = \prod_{i=1}^{p_k} y_{\tau_k \left({i}\right)} = \prod_{i=1}^{p_k} x_{\sigma \left({\tau_k \left({i}\right)}\right)} = \prod_{i=1}^{p_k} x_{\rho_k \left({i}\right)}$

So by the General Associativity Theorem:

	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \prod_{a \in A} {x_a}\)	\(=\)	\(\displaystyle \prod_{j=1}^p y_j\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle \prod_{k=1}^n \left({\prod_{j = r_{k-1}+1}^{r_k} {y_j} }\right)\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle \prod_{k=1}^n \left({\prod_{i=1}^{p_k} x_{\rho_k \left({i}\right)} }\right)\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle \prod_{k=1}^n \left({\prod_{a \in B_k} x_\alpha}\right)\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)

$\blacksquare$

Sources

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