General Associativity Theorem

From ProofWiki
Jump to navigation Jump to search

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

in the context of addition
Retrieved from "https://proofwiki.org/w/index.php?title=General_Associativity_Theorem&oldid=497604"