# General Associativity Theorem

## Theorem

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

### Formulation 1

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

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

Let $\sequence {r_k}_{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:

- $\ds \forall k \in \closedint 1 s: b_k = \prod_{j \mathop = r_{k - 1} \mathop + 1}^{r_k} {a_j}$

Then:

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

- $\ds \forall n \in \N_{>0}: \prod_{k \mathop = 1}^s \paren {a_{r_{k - 1} + 1} \circ a_{r_{k - 1} + 2} \circ \ldots \circ a_{r_k} } = 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 $\map {P_n} {a_1, a_2, \ldots, a_n}$ be defined inductively by:

- $\map {P_1} {a_1} = \set {a_1}$

- $\map {P_2} {a_1, a_2} = \set {a_1 \circ a_2}$

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

Then $\map {P_n} {a_1, a_2, \ldots, a_n}$ 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

## Motivation

The General Associativity 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 $\ds \bigcup_{i \mathop = 1}^n S_i$ and $\ds \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): Chapter $\text{II}$: Groups: Exercise $\text{C}$ - 1967: Michael Spivak:
*Calculus*... (previous) ... (next): Part $\text I$: Prologue: Chapter $1$: Basic Properties of Numbers

*in the context of addition*

- 1970: B. Hartley and T.O. Hawkes:
*Rings, Modules and Linear Algebra*... (previous) ... (next): Chapter $1$: Rings - Definitions and Examples: $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