General Associativity Theorem/Formulation 2/Proof 1

Jump to: navigation, search

Theorem

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

Proof

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 = \paren {a_1 \circ z} \circ y = a_1 \circ \paren {z \circ y} = a_1 \circ \paren {a_2 \circ a_3 \circ \ldots \circ a_n}$ (again by induction).

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

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

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

$\blacksquare$