2.2 Some Examples

2.34   Example (non-commutative $and$.) Many computer languages support an and operation that is not commutative. Here is a script of a Maple session. My statements are shown in typewriter font. Maple's responses are shown in italics.

> P := (x = 1/y);

${P} := {x}={\displaystyle \frac {1}{{y}}}$

> Q := (x*y=1);

${Q} := {x}\,{y}=1$

> y:= 0;

${y} := 0$

> x := 1;

${x} := 1$

> Q and P;

${\it false}$

> P and Q;

Error, division by zero

When evaluating $Q$ $and$ $P$, Maple first found that $Q$ is false, and then, without looking at $P$, concluded that $Q$ $and$ $P$ must be false. When evaluating $P$ $and$ $Q$, Maple first tried to evaluate $P$, and in the process discovered that $P$ is not a proposition. Mathematically, both $Q$ $and$ $P$ and $P$ $and$ $Q$ are errors when $y=0$ and $x=1$. Many programmers consider the non-commutativity of $and$ to be a feature (i.e. good), rather than a bug (i.e. bad).

2.35   Example (Calculator operations.) Let $\widetilde C$ denote the set of all numbers that can be entered into your calculator. The exact composition of $\widetilde C$ depends on the model of your calculator. Let $C=\widetilde C\cup\{E\}$ where $E$ is some object not in $\widetilde C$. I will call $E$ the error. I think of $E$ as the result produced when you enter $1/0$. Define four binary operations $\oplus,\ominus ,\odot$, and $\oslash$ on $C$ by

$$\begin{eqnarray*} a\oplus b &=&\mbox{ result produced when you calculate } a+b. ... ... a\oslash b &=&\mbox{ result produced when you calculate } a/b. \end{eqnarray*}$$

On my calculator

$$\begin{eqnarray*} &\;&2\oplus 2=4. \\ &\;&10^{50}\odot 10^{50}=E. \\ &\;&1111111111\odot 1111111111=1.2345679\times 10^{18}. \end{eqnarray*}$$

If $\circ$ denotes any of $\oplus,\ominus,\odot,\oslash$, I define

$$E\circ x=E=x\circ E \mbox{ for all } x\in C.$$

On all calculators with which I am familiar, $\oplus$ and $\odot$ are commutative operations, $0$ is an identity for $\oplus$, $1$ is an identity for $\odot$, and every element of $C$ except for $E$ is invertible for $\oplus$. On my calculator

$$1\oslash 3 = 0.333333333$$ (2.36)

$$0.333333333 \odot 3 = 0.999999999$$ (2.37)

$$0.333333333 \odot 3.000000003 = 1$$ (2.38)

$$0.333333333 \odot 3.000000004 = 1.$$ (2.39)

Thus $0.333333333$ has two different inverses! It follows from theorem 2.15 that $\odot$ is not associative. Your calculator may give different results for the calculations (2.38) and (2.39) but none of the calculator operations are associative.

2.40   Exercise. A Verify that calculator addition $(\oplus)$ and calculator multiplication $(\odot)$ are not associative, by finding calculator numbers $a$, $b$, $c$, $x$, $y$, and $z$ such that $a \oplus(b\oplus c) \neq (a\oplus b)\oplus c$, and $x\odot(y\odot z) \neq (x\odot y)\odot z$.

2.41   Notation. If $n\in\mbox{{\bf N}}$, let

$$\mbox{{\bf Z}}_n=\{x\in\mbox{{\bf N}}\colon x<n\}.$$

Hence, for example

$$\mbox{{\bf Z}}_5=\{0,1,2,3,4\}.$$

2.42   Definition ( $\oplus_n,\odot_n$.) Let $n\in\mbox{{\bf N}}$, with $n\geq 2$. We define two binary operations $\oplus_n$ and $\odot_n$ on $\mbox{{\bf Z}}_n$ by:

for all $a,b\in\mbox{{\bf Z}}_n$,

$$a\oplus_n b=\mbox{ remainder when } a+b\mbox{ is divided by } n$$

and for all $a,b\in\mbox{{\bf Z}}_n$,

$$a\odot_n b =\mbox{ remainder when } a\cdot b \mbox{ is divided by } n.$$

Thus,

$$\begin{eqnarray*} 4\oplus_5 4&=&3 \quad\mbox{ since } 4+4=1\cdot 5+3,\\ 1\odot_5 4 &=& 4\quad\mbox{ since } 1\cdot 4 = 0 \cdot 5 + 4, \end{eqnarray*}$$

and

$$4\odot_5 4=1 \quad\mbox{ since } 4\cdot 4=3\cdot 5+1.$$

The operations $\oplus_n$ and $\odot_n$ are both commutative (since $+$ and $\cdot$ are commutative on $\mbox{{\bf Z}}$). Clearly $0$ is an identity for $\oplus_n$, and $1$ is an identity for $\odot_n$. Every element of $\mbox{{\bf Z}}_n$ is invertible for $\oplus_n$ and

$$\mbox{ inverse for } k \mbox{ under } \oplus_n=\cases{ n-k &if $k\neq 0$\cr 0 &if $k=0$.}$$

2.43   Definition (Multiplication table.) Let $\circ$ be a binary operation on a finite set $A=\{a_1,a_2,\cdots,a_n\}$ having $n$ elements. We construct a multiplication table for $\circ$ as follows: We write down a table with $n$ rows and $n$ columns. Along the top of the table we list the elements of $A$ as labels for the columns. Along the left side of the table we list the elements of $A$ (in the same order) as labels for the rows. (See the figure to see what is meant by this.) If $(x,y)\in A^2$, we write the product $x\circ y$ in the box of our table whose row label is $x$ and whose column label is $y$.

$\circ$	$a_1$	$a_2$	$\cdots$	$a_n$
$a_1$	$a_1\circ a_1$	$a_1\circ a_2$	$\cdots$	$a_1\circ a_n$
$a_2$	$a_2\circ a_1$	$a_2\circ a_2$	$\cdots$	$a_2\circ a_n$
$\vdots$	$\vdots$	$\vdots$	$\;$	$\vdots$
$a_n$	$a_n\circ a_1$	$a_n\circ a_2$	$\cdots$	$a_n\circ a_n$

Multiplication table for $\circ$

2.44   Examples. Below are the multiplication tables for $\oplus_5$ and $\odot_5$:

$\oplus_5$	0	1	2	3	4
0	0	1	2	3	4
1	1	2	3	4	0
2	2	3	4	0	1
3	3	4	0	1	2
4	4	0	1	2	3

$\odot_5$	0	1	2	3	4
0	0	0	0	0	0
1	0	1	2	3	4
2	0	2	4	1	3
3	0	3	1	4	2
4	0	4	3	2	1

By looking at the multiplication table for $\odot_5$ we see that

$$\begin{eqnarray*} &\;&1\odot_5 1=1 \qquad 2\odot_5 3=1 \\ &\;&4\odot_5 4=1\qquad 3\odot_5 2=1. \end{eqnarray*}$$

Hence all the non-zero elements of $\mbox{{\bf Z}}_5$ have inverses under $\odot_5$.

Both of the operations $\oplus_n$ and $\odot_n$ are associative. This follows from the fact that $+$ and $\cdot$ are associative operations on $\mbox{{\bf Z}}$, by a straightforward but lengthy argument. The details are given in appendix B.

2.45   Exercise. Write down the multiplication table for $\odot_6$ on $\mbox{{\bf Z}}_6$. Determine which elements of $\mbox{{\bf Z}}_6$ are invertible for $\odot_6$, and find the inverse for each invertible element.

2.46   Exercise. Let $\{x,y,z\}$ be a set containing three distinct elements. $(x\neq y$, $y\neq z$, $z\neq x)$. Let $\circ$ be the binary operation on $\{x,y,z\}$ determined by the multiplication table:

$\;$	$x$	$y$	$z$
$x$	$x$	$y$	$z$
$y$	$y$	$x$	$x$
$z$	$z$	$x$	$x$

a)

Show that there is an identity element for $\circ$. (Which of $x,y,z$ is the identity?)

b)

Show that $y$ has two different inverses for $\circ$.

c)

Explain why the result of part b does not contradict the theorem on uniqueness of inverses.

2.47   Note. An early example of a binary operation that was not an obvious generalization of one of the operations $+,-,\cdot,/$ on numbers was the use of union and intersection as binary operations on the set of all sets by George Boole[11]. In Laws of Thought (1854), Boole introduces the operation $+$ (for union) and $\times$ (for intersection) on `` classes" (although he usually writes $xy$ instead of $x \times y$). He explicitly states

$$\begin{eqnarray*} x+y &=& y+x \\ xy&=&yx \\ x(y+z)&=&xy+xz \end{eqnarray*}$$

which he calls commutative and distributive laws. He does not mention associativity, and writes $xyz$ without parentheses. He denotes `` Nothing" by $0$ and `` the Universe" by $1$, and notes that $0$ and $1$ have the usual properties. As an example of the distributive law, Boole gives

European men and women $=$ European men and European women.

Boole's $+$ is not really a binary operation since he only defines $x+y$ when $x$ and $y$ have no elements in common.

The word associative, in its mathematical sense, was introduced by William Hamilton[24, p114] in 1843 in a paper on quaternions. According to [14, p284], the words commutative and distributive were introduced by Francois -Joseph Servois in 1813.