In the video in Figure 13.8 we introduce the associative property for binary operations and give examples. Following the video we present the formal definition of associativity, give further examples, and discuss methods for determining whether an binary operation is associative in detail.
Let \(S\) be a set and \(\bullet:S\times S \to S\) be a binary operation on \(S\text{.}\) Then, \(\bullet\) is associative if \(a\bullet(b\bullet c) = (a\bullet b)\bullet c\) for all \(a\in S\text{,}\)\(b\in S\text{,}\) and \(c\in S\text{.}\)
When you know the binary operation in Checkpoint 13.5 is associative, you only need to evaluate one of the last two expressions, since the results will be the same.
We already know that addition and multiplication of integers are associative. In the following example we also investigate whether subtraction of integers is associative.
It is often labor-intensive to verify that a binary operation is associative. We demonstrate the verification process for a binary operation on a (small) finite set in the following example.
Example13.12.Associativity of \(\star:T\times T\to T\).
Let \(T=\{\Tx,\Ty,\Tz\}\text{,}\) and let the binary operation \(\star:T\times T\to T\) be given by the table in Example 13.4. To prove that \(\star\) is associative, we exhaust all possibilities. We verify that for all \(a\in T\text{,}\)\(b\in T\text{,}\) and \(c\in T\text{,}\)
\begin{equation*}
a\star(b\star c)\text{ is equal to } (a\star b)\star c
\end{equation*}
by separately computing \(a\star(b\star c)\) in the left column and \((a\star b)\star c\) in the right column and noticing that the two computations in each row match.
In the case where one of the general elements is the identity element, there is a shortcut. We can handle several cases at the same time by setting one of the three general elements equal to the identity element and using variables for the other two general elements. Notice that for all \(a\in T\) we have \(\Ty\star a=a\) and \(a\star\Ty=a\text{.}\) Then, for all \(a\in T\) and all \(b\in T\) we have:
We have shown that \(a\star(b\star c)=(a\star b)\star c\) for all \(a\in T\text{,}\)\(b\in T\text{,}\) and \(c\in T\text{.}\) Thus, the binary operation \(\star:T\times T\to T\) is associative.
Example13.13.Associativity of \(\oplus:\Z_5\times\Z_5\to\Z_5\).
Consider the binary operation \(\oplus:\Z_5\times\Z_5\to\Z_5\) defined by \(a\oplus b=(a+b)\fmod 5\text{.}\) We use the associativity of \(+\) to show that \(\oplus\) is associative. For all \(a\in\Z_5\) and \(b\in\Z_5\) and \(c\in\Z_5\) we have by the definition of \(\oplus\) that
We have shown that \(a\oplus(b\oplus c)=(a\oplus b)\oplus c\) for all \(a\in\Z_5\) and \(b\in\Z_5\) and \(c\in\Z_5\text{,}\) so \(\oplus\) is associative.
Consider \(\Z_4=\{0,1,2,3\}\) with the binary operation \(\star:\Z_4\to\Z_4\) given by \(a\star b=(a^b)\fmod 4\text{.}\) Decide whether \(\star\) is associative.
As it often is easier to find a counterexample than to find a proof, we try finding a counterexample first. We check whether \(2\star(3\star 2)\) is equal to \((2\star3)\star 2\text{.}\) We get:
We find that \(2\star(3\star 2)\ne (2\star3)\star 2\text{.}\) That means we got lucky in our search for a counterexample. In particular, because for \(a=2\text{,}\)\(b=3\text{,}\)and \(c=2\) we have \(a\star(b\star c)\ne (a\star b)\star c\text{,}\) the binary operation \(\star\) is not associative.