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$