2.1.1 Multiplication Tables
If \(M=\{ x_1,x_2,\ldots , x_n\} \) is a finite set and “\(\cdot \)” is a binary operation on \(M\). The multiplication table for \(M\) is the following \(n\times n\)-table of elements of \(M\):
Note that \(M\) is commutative if and only if the multiplication table is symmetric (in the sense that \(x_ix_j = x_jx_i\) for all \(i,j\)).
The magma \((\mathbb {Z},+)\) is associative and has \(0\) as its identity element. The magma \((\mathbb {N},+)\) is also associative with \(0\) as its identity element. If \(n{\gt}0\), then the magma \((\mathbb {Z}_{\geq n},+)\) is associative, but does not have an identity element.
The following definition is motivated by computer science.
Suppose \(k\) is a positive integer and \(S\) is a set. A word of length \(k\) in S is a \(k\)-tuple \(\mathbf{m}=(m_1,\ldots , m_k)\) of elements of \(S\). If \(\mathbf{a}=(a_1,\ldots , a_i)\) and \(\mathbf{b}=(b_1,\ldots , b_j)\) are two words of length \(i\) and \(j\) respectively then the concatenation of \(\mathbf{a}\) and \(\mathbf{b}\) is the word \(\mathbf{a}.\mathbf{b}:=(a_1,\ldots , a_i, b_1,\ldots , b_j)\).
We write \(W_k(S)\) for the set of words of length \(k\) in \(S\). So \(W_k(S)\) is just equal to the set \(S^k\). We write \(W(S) = \cup _{k=1}^{\infty } W_k(S)\) for the union of the sets \(W_k(S)\). An element of \(W(S)\) is called a word in \(S\). Then concatenation is a binary operation
This makes \(W(S)\) into a magma, which called the magma of words in \(S\).
Suppose \(M\) is a magma and \(\mathbf{m}\) is a word of length \(k{\gt}0\) in \(M\). We define a set \(P(\mathbf{m})\) of products of \(\mathbf{m}\) inductively as follows. If \(k=1\), then \(P(\mathbf{m})=\{ m_1\} \). Suppose then inductively that \(P(\mathbf{n})\) is defined for every word \(\mathbf{n}\) of length strictly less than \(\mathbf{m}\). Then \(P(\mathbf{n})\) is the set of all products \(xy\) where \(x\in P(\mathbf{a}), y\in P(\mathbf{b})\) and \(\mathbf{n}=\mathbf{a}.\mathbf{b}\).
Suppose \(M\) is an associative magma, and \(\mathbf{m}=(m_1,\ldots , m_k)\) is a word in \(M\) of length \(k{\gt}0\). Then \(P(\mathbf{m})\) consists of a single element.
We induct on \(k\). For \(k=1\) the theorem is obvious. So suppose that \(k{\gt}1\) and the theorem is known for all words of length strictly less than \(k\). Write \(\mathbf{h}=(m_1,\ldots , m_{k-1})\) and \(\mathbf{t}=m_k\). Then, by induction, \(P(\mathbf{h})\) consists of a single element \(u\) and \(P(\mathbf{t})\) obviously consists of the single element \(m_k\). Since \(\mathbf{m}=\mathbf{h}.\mathbf{t}\), \(um_k\in P(\mathbf{m})\). Now suppose \(z\in P(\mathbf{m})\). By definition, \(z=xy\) where \(x\in P(\mathbf{a}), y\in P(\mathbf{b})\) with \(\mathbf{m}=\mathbf{a}\cdot \mathbf{b}\). Suppose \(\mathbf{a}=(m_1,\ldots , m_i)\) and \(\mathbf{b}=(m_{i+1},\ldots , m_k)\). Since \(1\leq i{\lt}k\), \(P(\mathbf{b})\) consists of a single element. So, setting \(\mathbf{b}'=(m_{i+1},\ldots , m_{k-1})\), we have \(y=y'm_k\) where \(y'\) is the unique element of \(P(\mathbf{b}')\). Then \(xy'\) is an element of \(P(\mathbf{h})\), so it is equal to \(u\). So, by associativity, we have \(z=xy=x(y'm_k)=(xy')m_k=um_k\).
If \(M\) is an associative magma and \(\mathbf{m}=(m_1,\ldots , m_k)\) is a word in \(M\) of length \(k{\gt}0\), then we write \(\Pi (\mathbf{m})\) or simply \(m_1m_2\cdots m_k\) for the unique element of \(P(\mathbf{m})\).