# General Associativity Theorem

## Contents

## Theorem

If an operation is associative on $3$ entities, then it is associative on any number of them.

### Formulation 1

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

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

Let $\left \langle {r_k} \right \rangle_{0 \mathop \le k \mathop \le s}$ be a strictly increasing sequence of natural numbers such that $r_0 = p$ and $r_s = p+n$.

Suppose:

- $\displaystyle \forall k \in \left[{1 \,.\,.\, s}\right]: b_k = \prod_{j \mathop = r_{k-1} \mathop + 1}^{r_k} {a_j}$

Then:

- $\displaystyle \forall n \in \N_{>0}: \prod_{k \mathop = 1}^s {b_k} = \prod_{k \mathop = p \mathop + 1}^{p \mathop + n} {a_k}$

That is:

- $\displaystyle \forall n \in \N_{>0}: \prod_{k \mathop = 1}^s \left({a_{r_{k-1} + 1} \circ a_{r_{k-1} + 2} \circ \ldots \circ a_{r_k}}\right) = a_{p + 1} \circ \ldots \circ a_{p + n}$

### Formulation 2

Let $n \in \N_{>0}$ and let $a_1, \ldots, a_n$ be elements of a set $S$.

Let $\circ$ be an associative operation on $S$.

Let the set $P_n \left({a_1, a_2, \ldots, a_n}\right)$ be defined inductively by:

- $P_1 \left({a_1}\right) = \left\{{a_1}\right\}$

- $P_2 \left({a_1, a_2}\right) = \left\{{a_1 \circ a_2}\right\}$

- $P_n \left({a_1, a_2, \ldots, a_n}\right) = \left\{{x \circ y: x \in P_r \left({a_1, a_2, \ldots, a_r}\right) \land y \in P_s \left({a_{r+1}, a_{r+2}, \ldots, a_{r+s}}\right), n = r+s}\right\}$

Then $P_n \left({a_1, a_2, \ldots, a_n}\right)$ consists of a unique entity which we can denote $a_1 \circ a_2 \circ \ldots \circ a_n$.

### Formulation 3

Let $\struct {S, \circ}$ be a semigroup.

Let $a_i$ denote elements of $S$.

Let $\circ$ be associative.

Let $n \in \Z$ be a positive integer such that $n \ge 3$.

Then all possible parenthesizations of the expression:

- $a_1 \circ a_2 \circ \cdots \circ a_n$

are equivalent.

## Also known as

Also known as the **general** (or **generalized**) **associative law**.

## Also see

## Comment

This theorem answers the following question:

It has been proved that, for example, union and intersection are associative in Union is Associative and Intersection is Associative.

That is:

- $R \cup \paren {S \cup T} = \paren {R \cup S} \cup T$

and the same with intersection.

However, are we sure that there is only one possible answer to $\displaystyle \bigcup_{i \mathop = 1}^n S_i$ and $\displaystyle \bigcap_{i \mathop = 1}^n S_i$?

That is, is it completely immaterial where we put the brackets in an expression containing an arbitrary number of multiple instances of one of these operations?

The question is a larger one than that: given *any* associative operation, is it *completely* associative?

This result shows that it is. Always.

## Sources

- 1967: George McCarty:
*Topology: An Introduction with Application to Topological Groups*... (previous) ... (next): $\text{II}$: Exercise $\text{C}$ - 1970: B. Hartley and T.O. Hawkes:
*Rings, Modules and Linear Algebra*... (previous) ... (next): $\S 1.3$: Some special classes of rings: $1.3$ - 1971: Allan Clark:
*Elements of Abstract Algebra*... (previous) ... (next): Chapter $2$: The Definition of Group Structure: $\S 27 \beta, \gamma$ - 1974: Thomas W. Hungerford:
*Algebra*... (previous) ... (next): $\text{I}$: Groups: $\S 1$: Semigroups, Monoids and Groups: Theorem $1.6$ - 1978: John S. Rose:
*A Course on Group Theory*... (previous) ... (next): $2$: Examples of Groups and Homomorphisms: $2.1$ Definition - 1978: Thomas A. Whitelaw:
*An Introduction to Abstract Algebra*... (previous) ... (next): $\S 28$. Associativity and commutativity