next up previous index
Next: 2.3 The Field Axioms Up: 2. Fields Previous: 2.1 Binary Operations   Index


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

\begin{displaymath}E\circ x=E=x\circ E \mbox{ for all } x\in C.\end{displaymath}

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
$\displaystyle 1\oslash 3$ $\textstyle =$ $\displaystyle 0.333333333$ (2.36)
$\displaystyle 0.333333333 \odot 3$ $\textstyle =$ $\displaystyle 0.999999999$ (2.37)
$\displaystyle 0.333333333 \odot 3.000000003$ $\textstyle =$ $\displaystyle 1$ (2.38)
$\displaystyle 0.333333333 \odot 3.000000004$ $\textstyle =$ $\displaystyle 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

\begin{displaymath}\mbox{{\bf Z}}_n=\{x\in\mbox{{\bf N}}\colon x<n\}.\end{displaymath}

Hence, for example

\begin{displaymath}\mbox{{\bf Z}}_5=\{0,1,2,3,4\}.\end{displaymath}

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$,

\begin{displaymath}a\oplus_n b=\mbox{ remainder when } a+b\mbox{ is divided by } n\end{displaymath}


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

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

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

\begin{displaymath}4\odot_5 4=1 \quad\mbox{ since } 4\cdot 4=3\cdot 5+1.\end{displaymath}

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

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

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.


next up previous index
Next: 2.3 The Field Axioms Up: 2. Fields Previous: 2.1 Binary Operations   Index