Associativity

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

Figure 13.8. Associativity by Matt Farmer and Stephen Steward.

Carefully read the definition.

Definition 13.9.

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.

Checkpoint 13.10. Definition of Associativity.

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

select
a * (b * c)
(a * b) * c
(a * b) * (a * c)
(a * b) * c

= (a * b) * c

select
for a=1 and b=2 and c=3
for all a in S, all b in S, and all c in S
for a=1 and b=2 and c=3
for some integers a, b, and c
for all a in S and some b in S

then the binary operation * is called

select
associative
commutative
distributive
transitive

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.

Example 13.11. Associativity of known binary operations.

We continue to consider the binary operations from Example 13.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 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.

Example 13.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:

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

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

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

Problem 13.14. Is \(\star:\Z_4\to\Z_4\) 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.

Prev Top Next