Associativity

Section 13.2 Associativity

If a binary operation is associative, we can group an expression in different ways. The result stays the same when the expression uses only that one operation.

🔗

The video in Figure 13.2.1 introduces associativity for binary operations. It also gives examples. After the video, we give the formal definition and more examples. Then we give methods for deciding whether a binary operation is associative.

🔗

Figure 13.2.1. Associativity by Matt Farmer and Stephen Steward.

🔗

Carefully read the definition.

🔗

Definition 13.2.2.

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{.}\)

🔗

We know that integer addition and multiplication are associative. The next example checks whether integer subtraction is also associative.

🔗

Example 13.2.3. Associativity of known binary operations.

We continue to consider the binary operations from Example 13.1.3:

The addition of integers \(+:\Z\times\Z\to\Z\) is associative.
🔗

🔗
The multiplication of natural numbers \(\cdot:\N\times\N\to\N\) is associative.
🔗

🔗
For the difference of integers \(-:\Z\times\Z\to\Z\) we have

\begin{equation*} 3-(2-1)=3-1=2 \text{.} \end{equation*}

and

\begin{equation*} (3-2)-1=1-1=0 \end{equation*}

As \(2\ne 0\) the binary operation \(-\) (minus) is not associative.

🔗

🔗

🔗

It often takes a lot of work to check that a binary operation is associative. We show the check process for a binary operation on a (small) finite set in the following example.

🔗

Example 13.2.4. 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.1.4. To prove that \(\star\) is associative, we exhaust all possibilities. We check 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:

🔗

\(\Ty\star(a\star b)=a\star b\)	and	\((\Ty\star a)\star b=a\star b\)
\(a\star(\Ty\star b)=a\star b\)	and	\((a\star \Ty)\star b=a\star b\)
\(a\star(b\star \Ty)=a\star b\)	and	\((a\star b)\star \Ty=a\star b\)

We explicitly cover the remaining cases:

🔗

\(\Tx\star(\Tx\star \Tx)=\Tx\star \Tz=\Ty\)	and	\((\Tx\star \Tx)\star \Tx=\Tz\star \Tx=\Ty\)
\(\Tx\star(\Tx\star \Tz)=\Tx\star \Ty=\Tx\)	and	\((\Tx\star \Tx)\star \Tz=\Tz\star \Tz=\Tx\)
\(\Tx\star(\Tz\star \Tx)=\Tx\star \Ty=\Tx\)	and	\((\Tx\star \Tz)\star \Tx=\Ty\star \Tx=\Tx\)
\(\Tx\star(\Tz\star \Tz)=\Tx\star \Tx=\Tz\)	and	\((\Tx\star \Tz)\star \Tz=\Ty\star \Tz=\Tz\)

\(\Tz\star(\Tx\star \Tx)=\Tz\star \Tz=\Tx\)	and	\((\Tz\star \Tx)\star \Tx=\Ty\star \Tx=\Tx\)
\(\Tz\star(\Tx\star \Tz)=\Tz\star \Ty=\Tz\)	and	\((\Tz\star \Tx)\star \Tz=\Ty\star \Tz=\Tz\)
\(\Tz\star(\Tz\star \Tx)=\Tz\star \Ty=\Tz\)	and	\((\Tz\star \Tz)\star \Tx=\Tx\star \Tx=\Tz\)
\(\Tz\star(\Tz\star \Tz)=\Tz\star \Tx=\Ty\)	and	\((\Tz\star \Tz)\star \Tz=\Tx\star \Tz=\Ty\)

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{.}\) So, the binary operation \(\star:T\times T\to T\) is associative.

🔗

Example 13.2.5. 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

\begin{equation*} a\oplus(b\oplus c)=a\oplus ((b+c)\fmod 5)=(a+((b+c)\fmod 5))\fmod 5\text{.} \end{equation*}

🔗

With Theorem 3.4.10 we get

\begin{equation*} (a+((b+c)\fmod 5))\fmod 5=(a+(b+c))\fmod 5\text{.} \end{equation*}

🔗

As the addition \(+\) of integers is associative we have

\begin{equation*} (a+(b+c))\fmod 5=((a+b)+c)\fmod 5\text{.} \end{equation*}

🔗

Again applying Theorem 3.4.10 and the definition of \(\oplus\) we get

\begin{align*} ((a+b)+c)\fmod 5 \amp= (((a+b)\fmod 5)+c)\fmod 5\\ \amp=((a\oplus b)+c)\fmod 5\\ \amp=(a\oplus b)\oplus c\text{.} \end{align*}

🔗

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.

🔗

Problem 13.2.6. Is \(\star:\Z_4\times\Z_4\to\Z_4\) associative.

Consider \(\Z_4=\{0,1,2,3\}\) with the binary operation \(\star:\Z_4\times\Z_4\to\Z_4\) given by \(a\star b=(a^b)\fmod 4\text{.}\) Decide whether \(\star\) is associative.

🔗

Solution.

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:

\begin{align*} 2\star(3\star 2)\amp=2\star (3^2 \fmod 4) = 2\star (9 \fmod 4) = 2\star 1 = (2\cdot 1) \fmod 4 =2\\ (2\star3)\star 2\amp=(2^3\fmod 4)\star 2= (8\fmod 4)\star 2= 0\star 2 = 0 \fmod 4 =0 \end{align*}

🔗

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.

🔗

Prev Top Next