General Associativity Theorem

From ProofWiki
Jump to navigation Jump to search


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$.


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


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


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.