General Associativity Theorem

Theorem

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

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

Formal Statement

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

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

Let $\left \langle {r_k} \right \rangle_{0 \le k \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=r_{k-1}+1}^{r_k} {a_j}$

Then:

$\displaystyle \prod_{k=1}^s {b_k} = \prod_{k = p + 1}^{p + n} {a_k}$

That is:

$\displaystyle \prod_{k=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}$

Alternative Formulation

Let $a_1, a_2, \ldots$ be elements of a set $S$ and let $n \in \N^*$.

Let $\circ$ be an associative operation.

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

Proof

Formal Statement

• Let $T$ be the set of all $n \in \N^*$ such that:

$(1): \quad$ for every sequence $\left \langle {a_k} \right \rangle_{p+1 \le k \le p+n}$ of elements of $S$

and:

$(2): \quad$ for every strictly increasing sequence $\left \langle {r_k} \right \rangle_{0 \le k \le s}$ of natural numbers such that $r_0 = p$ and $r_s = p+n$:

$\displaystyle b_k = \prod_{j=r_{k-1}+1}^{r_k} {a_j}$

• Let $n = 1$.

Then:

	\(\displaystyle \)	\(\displaystyle n\)	\(=\)	\(\displaystyle 1\)	\(\displaystyle \)
	\(\displaystyle \implies\)	\(\displaystyle r_s\)	\(=\)	\(\displaystyle r_0 + 1\)	\(\displaystyle \)
	\(\displaystyle \implies\)	\(\displaystyle s\)	\(=\)	\(\displaystyle 1\)	\(\displaystyle \)
	\(\displaystyle \implies\)	\(\displaystyle \prod_{k=1}^s {b_k}\)	\(=\)	\(\displaystyle b_1\)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle a_{p+1}\)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle \prod_{k=p+1}^{p+n} {a_k}\)	\(\displaystyle \)

So $1 \in T$.

• Now suppose $n \in T$.

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

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

Then $r_{s-1} \le p + n$.

There are two cases:

1. $r_{s-1} = p + n$;
2. $r_{s-1} < p + n$.

• First, suppose $r_{s-1} = p + n$.

Then $b_s = a_{p + n + 1}$.

Thus:

	\(\displaystyle \)	\(\displaystyle a_{p+1} \circ \ldots \circ a_{p+n}\)	\(=\)	\(\displaystyle b_1 \circ \ldots \circ b_{s-1}\)	\(\displaystyle \)	(as $n \in T$)
	\(\displaystyle \implies\)	\(\displaystyle a_{p+1} \circ \ldots \circ a_{p+n+1}\)	\(=\)	\(\displaystyle \left({a_{p+1} \circ \ldots \circ a_{p+n} }\right) \circ a_{p+n+1}\)	\(\displaystyle \)	Definition of Composite
	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle \left({b_1 \circ \ldots \circ b_{s-1} }\right) \circ b_s\)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle b_1 \circ \ldots \circ b_s\)	\(\displaystyle \)	Definition of Composite

• Secondly, suppose $r_{s-1} < p + n$.

Let $b'_s = a_{r_{s-1}+1} \circ \ldots \circ a_{r_s+1}$.

Then $b_s = b'_s \circ a_{p+n+1}$ by definition of composite.

Now $n \in T \implies a_{p+1} \circ \ldots \circ a_{p+n} = b_1 \circ \ldots \circ b_{s-1} \circ b'_s$.

Thus:

	\(\displaystyle \)	\(\displaystyle b_1 \circ \ldots \circ b_s\)	\(=\)	\(\displaystyle \left({b_1 \circ \ldots \circ b_{s-1} }\right) \circ \left({b'_s \circ a_{p+n+1} }\right)\)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle \left({\left({b_1 \circ \ldots \circ b_{s-1} }\right) \circ b'_s}\right) \circ a_{p+n+1}\)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle \left({b_1 \circ \ldots \circ b_{s-1} \circ b'_s}\right) \circ a_{p+n+1}\)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle \left({a_{p+1} \circ \ldots \circ a_{p+n} }\right) \circ a_{p+n+1}\)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle a_{p+1} \circ \ldots \circ a_{p+n} \circ a_{p+n+1}\)	\(\displaystyle \)

Thus in both cases $n + 1 \in T$.

So by the Principle of Finite Induction, $T = \N^*$.

$\blacksquare$

Alternative Formulation

The cases where $n = 1$ and $n = 2$ are clear.

Let $a = x \circ y \in P_n: x \in P_r, y \in P_s$.

If $r > 1$ then we write $x = a_1 \circ z$ where $z = a_2 \circ a_3 \circ \ldots \circ a_r$ by induction.

Then $x \circ y = \left({a_1 \circ z}\right) \circ y = a_1 \circ \left({z \circ y}\right) = a_1 \circ \left({a_2 \circ a_3 \circ \ldots \circ a_n}\right)$ (again by induction).

If $r=1$, then by induction $x \circ y = a_1 \circ y = a_1 \circ \left({a_2 \circ a_3 \circ \ldots \circ a_n}\right)$.

Thus in either case, $x \circ y = a_1 \circ \left({a_2 \circ a_3 \circ \ldots \circ a_n}\right)$ which is a single element of $P_n$.

Hence we see that $P_n \left({a_1, a_2, \ldots, a_n}\right)$ consists of a single element.

$\blacksquare$

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 \left({S \cup T}\right) = \left({R \cup S}\right) \cup T$ and the same with intersection.

However, are we sure that there is only one possible answer to $\displaystyle \bigcup_{i = 1}^n{S_i}$ and $\displaystyle \bigcap_{i = 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

• J.A. Green: Sets and Groups (1965)... (previous)... (next): $\S 4.2$
• Seth Warner: Modern Algebra (1965): $\S 18$: Theorem $18.5$
• George McCarty: Topology: An Introduction with Application to Topological Groups (1967): Chapter $\text{II}$: Exercise $\text{C}$
• B. Hartley and T.O. Hawkes: Rings, Modules and Linear Algebra (1970): $\S 1.3$: $1.3$
• Allan Clark: Elements of Abstract Algebra (1971)... (previous)... (next): $\S 27 \beta, \gamma$
• Thomas A. Whitelaw: An Introduction to Abstract Algebra (1978)... (previous)... (next): $\S 28$
• John F. Humphreys: A Course in Group Theory (1996): $\S 3$: Proposition $3.6$