Definition 13.39.
Let \(S\) be a set and \(\bullet:S\times S \to S\) be a binary operation on \(S\text{.}\) Then, \(\bullet\) is commutative if \(a \bullet b=b \bullet a\) for all \(a\in S\) and \(b\in S\text{.}\)
Section 13.5 Commutativity
In Part I we have already discussed the commutativity of addition and multiplication of integers. Commutativity of addition meant that, for example, \(2+7=9\) and also \(7+2=9\text{.}\) Also recall that this property does not hold for subtraction, as is proved by the counterexample \(2-7=-5\) but \(7-2=5\text{.}\) In the following we introduce the commutative property for general binary operations.
In the video in Figure 13.38 we introduce the commutative property for general binary operations and give examples. Following the video we present the formal definition of commutativity, give examples, and discuss methods for determining whether an binary operation is commutative in detail.
Carefully read the definition.
Now reproduce the definition by filling in the blanks.
Checkpoint 13.40. Commutative.
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’.
The operation * is commutative 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
for
- select
- all a in S
- one a in S
- all a in S and all b in S
- one a in S and one b in S
- all a in S, all b in S, and all c in S
- one a in S, one b in S, and one c in S
- the identity e with respect to * in S
- all e in S
.
We already know that addition and multiplication of integers are commutative. In the following example we also investigate whether subtraction of integers is commutative.
Example 13.41. Commutativity of known binary operations.
We consider the binary operations from Example 13.3:
- The addition of integers \(+:\Z\times\Z\to\Z\) is commutative.
- The multiplication of natural numbers \(\cdot:\N\times\N\to\N\) is commutative.
- We have \(5-2=3\) and \(2-5=(-3)\text{.}\) As \(3\ne(-3)\) we have \(5-2\ne 2-5\text{.}\) This counterexample shows that the binary operation \(-:\Z\times\Z\to\Z\) is not commutative.
Example 13.42. Commutativity 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 commutative, we exhaust all possibilities. We verify that for all \(a\in T\) and \(b\in T\text{,}\)
\begin{equation*}
a\star b\text{ is equal to } b \star a
\end{equation*}
by separately computing \(a\star b\) in the left column and \(b\star a\) 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 two general elements equal to the identity element and using a variable for the other general element. Recall that the identity element is \(\Ty\) for \(T\) with respect to \(\star\text{.}\) Then, for all \(a\in T\) we have:
\begin{gather*}
a\star \Ty=a\\
\Ty\star a=a
\end{gather*}
Now, note that if the two general elements are the same, there is nothing to check. For all \(a \in T\text{,}\) we trivially have that \(a\star a = a\star a\text{.}\) So, the only remaining case to check is covered here:
\begin{gather*}
\Tx\star \Tz=\Ty\\
\Tz\star \Tx=\Ty
\end{gather*}
We have shown that \(a\star b=b\star a\) for all \(a\in T\) and \(b\in T\text{.}\) Thus, the binary operation \(\star:T\times T \to T\) is commutative.
When we have an operation on a set given by an operation table, we can determine whether or not the operation is commutative by observing whether or not the operation table possesses a particular symmetry. We locate the diagonal of the table from the operation symbol in the top left corner of the table to the bottom right corner of the table. Then, we determine whether or not that diagonal acts as a mirror for the other entries in the table. If so, the operation is commutative.
Example 13.43. Commutativity of \(\star:T\times T\to T\) revisited.
With the above comment in mind, we revisit Example 13.42. We shade the diagonal that must act as a mirror for the other entries in the table if the operation is commutative. Then, we individually verify the symmetry by pointing out the pairs of entries that need to match and noting that they do, in fact, match.
| \(\star\) | \(\Tx\) | \(\Ty\) | \(\Tz\) |
|---|---|---|---|
| \(\Tx\) | \(\color{gray}\Tz\) | \(\color{red}\Tx\) | \(\Ty\) |
| \(\Ty\) | \(\color{red}\Tx\) | \(\color{gray}\Ty\) | \(\Tz\) |
| \(\Tz\) | \(\Ty\) | \(\Tz\) | \(\color{gray}\Tx\) |
| \(\star\) | \(\Tx\) | \(\Ty\) | \(\Tz\) |
|---|---|---|---|
| \(\Tx\) | \(\color{gray}\Tz\) | \(\Tx\) | \(\color{red}\Ty\) |
| \(\Ty\) | \(\Tx\) | \(\color{gray}\Ty\) | \(\Tz\) |
| \(\Tz\) | \(\color{red}\Ty\) | \(\Tz\) | \(\color{gray}\Tx\) |
| \(\star\) | \(\Tx\) | \(\Ty\) | \(\Tz\) |
|---|---|---|---|
| \(\Tx\) | \(\color{gray}\Tz\) | \(\Tx\) | \(\Ty\) |
| \(\Ty\) | \(\Tx\) | \(\color{gray}\Ty\) | \(\color{red}\Tz\) |
| \(\Tz\) | \(\Ty\) | \(\color{red}\Tz\) | \(\color{gray}\Tx\) |
Example 13.44. Commutativity 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 follow an approach that is similar to that from Example 13.13 to show that \(\oplus\) is commutative. Let \(a\in\Z_5\) and \(b\in\Z_5\text{.}\) By the definition of \(\oplus\) and the commutativity of addition of integers we have
\begin{equation*}
a\oplus b = (a+b)\fmod 5 = (b+a)\fmod 5=b\oplus a\text{.}
\end{equation*}
Thus \(\oplus\) is commutative
Problem 13.45. Commutativity of a binary operation given by a table.
Let \(A = \{\Tg,\Th,\Tc,\Td\}\) and let \(\diamond:A\times A\to A\) be defined by the table:
| \(\diamond\) | \(\Tg\) | \(\Th\) | \(\Tc\) | \(\Td\) |
|---|---|---|---|---|
| \(\Tg\) | \(\Tg\) | \(\Th\) | \(\Tc\) | \(\Td\) |
| \(\Th\) | \(\Th\) | \(\Tg\) | \(\Td\) | \(\Tc\) |
| \(\Tc\) | \(\Tc\) | \(\Td\) | \(\Tg\) | \(\Box\) |
| \(\Td\) | \(\Td\) | \(\Tc\) | \(\Th\) | \(\Tg\) |
Which element in the box makes the operation \(\diamond\) commutative?
Solution.
The operation \(\diamond\) is commutative if for all \(a\) and \(b\) in \(A\) we have \(a\diamond b=b\diamond a\text{.}\) In particular we must have \(\Td\diamond\Tc=\Tc\diamond\Td\text{.}\) Since \(\Td\diamond\Tc=\Th\) we must also have \(\Tc\diamond\Td=\Th\text{.}\) Hence the element \(\Th\) in the box makes \(\diamond\) commutative.
Problem 13.46. A non-commutative binary operations.
Give an example of a binary operation that is not commutative.
Solution.
Consider the binary operation subtraction \(-:\Z\times\Z\to\Z\text{.}\) Since \(3-2=1\) and \(2-3=-1\text{,}\) and \(1\ne -1\text{,}\) the binary operation \(-\) is not commutative.
When a binary operation is based on a commutative operation such that addition or multiplication, it is commutative itself.
Problem 13.47. Is this binary operations commutative ?
Decide whether the binary operation \(\otimes:\Z_{11}^\otimes\times \Z_{11}^\otimes\to \Z_{11}^\otimes\) given by \(a\otimes b = (a\cdot b) \fmod 11\) is commutative.
Answer.
The binary operation \(\otimes:\Z_{11}^\otimes\times \Z_{11}^\otimes\to \Z_{11}^\otimes\) given by \(a\otimes b = (a\cdot b) \fmod 11\) is commutative.
Solution.
We know multiplication of integers is commutative. That is, for all integers \(a\) and \(b\) we have \((a\cdot b) = (b\cdot a)\text{.}\) Thus
\begin{equation*}
a\otimes b = (a\cdot b) \fmod 11 = (b\cdot a) \fmod 11 = b\otimes a\text{,}
\end{equation*}
which means that the binary operation \(\otimes\) is commutative.
Problem 13.48. Is this binary operations commutative ?
Decide whether the binary operation \(\oplus:\Z_{11}\times \Z_{11}\to \Z_{11}\) given by \(a\oplus b = (a+b) \fmod 11\) is commutative.
Answer.
The binary operation \(\oplus:\Z_{11}\times \Z_{11}\to \Z_{11}\) given by \(a\oplus b = (a+b) \fmod 11\) is commutative.
Solution.
We proceed as in Problem 13.47.
Because the addition of integers is commutative, we have \(a+b=b+a\) for all integers \(a\) and \(b\text{.}\) Thus
\begin{equation*}
a\oplus b = (a+b) \fmod 11=(b+a)\fmod 11 = b\oplus a,
\end{equation*}
which means that \(\oplus\) is a commutative binary operation.
When we suspect that a binary operation is not commutative, we look for a counterexample. If we find a counterexample we have proven that the binary operation is not commutative.
Problem 13.49. Is this binary operations commutative ?
Decide whether the binary operation \(\ominus:\Z_{11}\times \Z_{11}\to \Z_{11}\) given by \(a\ominus b = (a-b) \fmod 11\) is commutative.
Answer.
The binary operation \(\ominus:\Z_{11}\times \Z_{11}\to \Z_{11}\) given by \(a\ominus b = (a-b) \fmod 11\) is not commutative.
Solution.
We know that subtraction of integers is not commutative. So we suspect that the binary operation \(\ominus\) that is based on subtraction is not commutative. We find a counterexample. Let \(a:=1\) and \(b:=0\text{.}\) Then
\begin{equation*}
a\ominus b = 1\ominus 0 = (1-0) \fmod 11 = 1 \fmod 11 = 1
\end{equation*}
and
\begin{equation*}
b\ominus a = 0\ominus 1 = (0-1) \fmod 11 = (-1) \fmod 11 = 10\text{.}
\end{equation*}
We have found \(a\) and \(b\) such that \(a\ominus b\) is not equal to \(b\ominus a\text{.}\) So the binary operation \(\ominus\) is not commutative.
In Checkpoint 13.50 decide whether the given binary operations are commutative. If it is not commutative give a counterexample.
Checkpoint 13.50. Are these commutative ?
Decide whether the following binary operations are commutative. If the binary operation is not commutative, give a counterexample, otherwise leave the field empty.
(1) Let the binary operation \(\otimes:\mathbb{Z}_{15}\times \mathbb{Z}_{15}\to \mathbb{Z}_{15}\) be given by \(a \otimes b = \left(a\cdot b\right) \bmod 15\text{.}\)
The binary operation \(\otimes\) is
- select
- commutative
- not commutative
.
Counterexample: The statement is false, because for \(a=\) \(\in \mathbb{Z}_{15}\) we have \(a \otimes 9 \ne 9 \otimes a\text{.}\)
(2) Let the binary operation \(\ominus:\mathbb{Z}_{14}\times \mathbb{Z}_{14}\to \mathbb{Z}_{14}\) be given by \(a \ominus b = \left(a-b\right) \bmod 14\text{.}\)
The binary operation \(\ominus\) is
- select
- commutative
- not commutative
.
Counterexample: The statement is false, because for \(a=\) \(\in \mathbb{Z}_{14}\) we have \(a \ominus 12 \ne 12 \ominus a\text{.}\)
(3) Let the binary operation \(\ominus:\mathbb{Z}_{10}\times \mathbb{Z}_{10}\to \mathbb{Z}_{10}\) be given by \(a \ominus b = \left(a-b\right) \bmod 10\text{.}\)
The binary operation \(\ominus\) is
- select
- commutative
- not commutative
.
Counterexample: The statement is false, because for \(a=\) \(\in \mathbb{Z}_{10}\) we have \(a \ominus 3 \ne 3 \ominus a\text{.}\)
Hint.
The binary operation \(\otimes\) is commutative if \(a \otimes b = b \otimes a\) for all \(a\in \mathbb{Z}_{15}\) and for all \(b\in \mathbb{Z}_{15}\text{.}\)
The binary operation \(\ominus\) is commutative if \(a \ominus b = b \ominus a\) for all \(a\in \mathbb{Z}_{14}\) and for all \(b\in \mathbb{Z}_{14}\text{.}\)
The binary operation \(\ominus\) is commutative if \(a \ominus b = b \ominus a\) for all \(a\in \mathbb{Z}_{10}\) and for all \(b\in \mathbb{Z}_{10}\text{.}\)
