Skip to main content

MAT 112 Integers and Modern Applications for the Uninitiated

Section13.2Associativity

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.
Carefully read the definition.

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

Checkpoint13.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’.
If
• 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.

Example13.11.Associativity of known binary operations.

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

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

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

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