Theorem 1 (Associativity theorem)

Let E be an associative magma whose law is denoted by $\top$. Let A be a totally ordered non-empty finite set, which is the union of an ordered sequence of non-empty subsets $(B_i)_{i \in I}$ such that the relations $\alpha \in B_i, \beta \in B_j, i < j$ imply $\alpha < \beta$; let $(x_\alpha)_{\alpha \in A}$ be an ordered sequence of elements in E with A as indexing set. Then

† The use of this terminology and the notation $\prod_{\alpha \in A} x_\alpha$ must be avoided if there is any risk of confusion with the product of the sets $x_\alpha$ defined in the theory of sets (Set Theory, II, § 5, no. 3). However, if the $x_\alpha$ are cardinals and addition (resp. multiplication) is the cardinal sum (resp. the cardinal product), the cardinal denoted by $\sum_{\alpha \in A} x_\alpha$ (resp. $\prod_{\alpha \in A} x_\alpha$) in the above notation is the cardinal sum (resp. cardinal product) of the family $(x_\alpha)_{\alpha \in A}$ (Set Theory, III, § 3, no. 3).

§ 1.3

We prove the theorem by induction on the cardinal $n$ of $A$. Let $p$ be the cardinal of $I$ and $h$ its least element; let $J = I - \{h\}$. If $n = 1$, as the $B_i$ are non-empty, of necessity $p = 1$ and the theorem is obvious. Otherwise, assuming the theorem holds for an indexing set with at most $n - 1$ elements, we distinguish two cases:

(a) $B_h$ has a single element $\beta$. Let $C = \bigcup_{i \in J} B_i$. The left-hand side of (3) is equal, by definition, to $x_\beta \top \left( \prod_{\alpha \in C} x_\alpha \right)$; the right-hand side is equal, by definition, to

the result follows from the fact that the theorem is assumed true for $C$ and $(B_i)_{i \in J}$.

(b) Otherwise, let $\beta$ be the least element of $A$ (and hence of $B_h$); let $A' = A - \{\beta\}$ and let $B'_i = A' \cap B_i$ for $i \in I$; then $B'_i = B_i$ for $i \in J$. The set $A'$ has $n - 1$ elements and the conditions of the theorem hold for $A'$ and its subsets $B'_i$; hence by hypothesis:

Forming the composition of $x_\beta$ with each side, we have on the left-hand side side, by definition, $\prod_{\alpha \in A} x_\alpha$ and on the right-hand side, using the associativity, which is equal, by Definition 3, to the right-hand side of formula (3).

For an associative law denoted by $\top$ the composition $\prod_{p \leq i \leq q} x_i$ of a sequence $(x_i)_{i \in [p, q]}$ is also denoted (since no confusion can arise) by

A particular case of Theorem 1 is the formula Consider an ordered sequence of $n$ terms all of whose terms are equal to the same element $x \in E$. The composition of this sequence is denoted by $\prod^n x$ for a law denoted by $\top$, $\prod^n x$ for a law denoted by $\perp$. For a law written multiplicatively the composition is denoted by $x^n$ and called the $n$-th power of $x$. For a law written additively the composition is usually denoted by $nx$. The associativity theorem applied to an ordered sequence all of whose terms are equal gives the equation

In particular, if $p = 2$,

and if $n_1 = n_2 = \cdots = n_p = m$,

If $X$ is a subset of $E$, we sometimes denote, in conformity with the above notation, by $\frac{p}{T} X$ the set $X_1 T X_2 T \cdots T X_p$, where

it is thus the set of all compositions $x_1 T x_2 T \cdots T x_p$ with $x_1 \in X, x_2 \in X, \ldots, x_p \in X$.

It is important not to confuse this set with the set of $\frac{p}{T} x$, where $x$ runs through $X$.