Skip to main content

Section 13.2 Associativity

If a binary operation is associative, the order in which we evaluate expressions that only involve that one binary operation does not matter.

In the video in Figure 13.2.1 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.

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

Now reproduce the definition by filling in the blanks.

Definition

Let S be a set and let * : S \(\times\) S \(\to\) S be a binary operation on S. We read a * b as 'a star b'.

Let e be

  • select

  • the identity with respect to * in S

  • some element in S

  • some odd element in S

  • some even element in S

  • some green element in S

.

An element b in S is an inverse of a in S with respect to * if

  • select

  • (a * b) * c = a * (b * c)

  • a * b = b * a

  • a * e = a and e * a = a

  • a * b = e and b * a = e

.

Answer 1.

\({\text{the identity with respect to * in S}}\)

Answer 2.

\({\text{a * b = e and b * a = e}}\)

When you know the binary operation in Checkpoint 13.1.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.

We continue to consider the binary operations from Example 13.1.3:

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

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

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

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 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:

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

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 obtain

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

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.

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.