Associativity on Indexing Set

Theorem

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

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

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

Then:

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

Proof

For each $k \in \N_{>0}$, let $\left|{B_k}\right| = p_k$.

Let:

$r_0 = 0$

$\displaystyle \forall k \in \N_{>0}: r_k = \sum_{j \mathop = 1}^k {p_j}$

and:

$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 \mathop \in A} {x_\alpha} = \prod_{j \mathop = 1}^p {x_{\sigma \left({j}\right)}} = \prod_{j \mathop = 1}^p {y_j}$

Also:

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

Also by definition:

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

So by the General Associativity Theorem:

\(\ds \prod_{a \mathop \in A} {x_a}\)

\(=\)

\(\ds \prod_{j \mathop = 1}^p y_j\)

\(\ds \)

\(=\)

\(\ds \prod_{k \mathop = 1}^n \left({\prod_{j \mathop = r_{k - 1} \mathop + 1}^{r_k} {y_j} }\right)\)

\(\ds \)

\(=\)

\(\ds \prod_{k \mathop = 1}^n \left({\prod_{i \mathop = 1}^{p_k} x_{\rho_k \left({i}\right)} }\right)\)

\(\ds \)

\(=\)

\(\ds \prod_{k \mathop = 1}^n \left({\prod_{a \mathop \in B_k} x_\alpha}\right)\)

$\blacksquare$

Sources

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