2.1 Binary Operations

2.1   Definition (Binary operation.) Let $A$ be a set. A binary operation on $A$ is a function $\circ\colon A\times A\to A$. Binary operations are usually denoted by special symbols such as

$$+,-,\cdot,\slash,\times,\circ,\wedge,\vee,\cup,\cap$$

rather than by letters. If $\circ\colon A\times A\to A$ is a binary operation, we write $a\circ b$ instead of $\circ (a,b)$. By the definition of function (1.57), a binary operation is a triple $(A\times A,A,\circ)$, but as is usual for functions, we refer to `` the binary operation $\circ$" instead of `` the binary operation $(A\times A,A,\circ)$".

2.2   Examples. The usual operations of addition $(+)$, subtraction $(-)$ and multiplication $(\cdot)$ are binary operations on $\mbox{{\bf Z}}$ and on $\mbox{{\bf Q}}$. Subtraction is not a binary operation on $\mbox{{\bf N}}$, because $3-5$ is not in $\mbox{{\bf N}}$. Division is not a binary operation on $\mbox{{\bf Q}}$, because division by $0$ is not defined. However, division is a binary operation on $\mbox{{\bf Q}}\setminus\{0\}$.

Let $\mbox{$\cal S$}$ be the set of all sets.^2.1 Then union $(\cup)$ and intersection $(\cap)$ and set difference $(\setminus)$ are binary operations on $\mbox{$\cal S$}$.

Let $\mbox{${\cal P}$}$ be the set of all propositions. Then and and or are binary operations on $\mbox{${\cal P}$}$. In mathematical logic, and is usually represented by $\land$ or $\&$, and or is represented by $\lor$ or $\bigvee$.

2.3   Definition (Identity element.) Let $\circ$ be a binary operation on a set $A$. An element $e\in A$ is an identity element for $\circ$ (or just an identity for $\circ$) if

$$\mbox{ for all } a\in A,\quad e\circ a=a=a\circ e.$$

2.4   Examples. $0$ is an identity for addition on $\mbox{{\bf Z}}$, and $1$ is an identity for multiplication on $\mbox{{\bf Z}}$. There is no identity for subtraction on $\mbox{{\bf Z}}$, since for all $e\in\mbox{{\bf Z}}$ we have

$$e \mbox{ is an identity for } - \mbox{$\Longrightarrow$} e-1=1 \mbox{ and } 1=1-e,$$

$$\mbox{$\Longrightarrow$} e=2 \mbox{ and } e=0,$$

$$\mbox{$\Longrightarrow$} 0=2.$$ (2.5)

Since (2.5) is false, the first statement is also false; i.e., for all $e\in\mbox{{\bf Z}}$, $e$ is not an identity for $-$. $\mid\!\mid\!\mid$

2.6   Exercise. Let $\mbox{$\cal S$}(\mbox{{\bf Z}})$ denote the set of all subsets of $\mbox{{\bf Z}}$. Then union $\cup$ and intersection $\cap$ are binary operations on $\mbox{$\cal S$}(\mbox{{\bf Z}})$. Is there an identity element for $\cup$? If so, what is it? Is there an identity element for $\cap$? If so, what is it?

2.7   Theorem (Uniqueness of identities.) Let $\circ$ be a binary operation on a set $A$. Suppose that $e,f$ are both identity elements for $\circ$. Then $e=f$. (Hence we usually talk about the identity for $\circ$, rather than an identity for $\circ$.)

Proof: Let $e,f$ be identity elements for $\circ$. Then

$$e=e\circ f \qquad \mbox{ (since } f \mbox{ is an identity for } \circ )$$

and

$$e\circ f=f \qquad \mbox{ (since } e \mbox{ is an identity for } \circ ).$$

It follows that $e=f$. $\mid\!\mid\!\mid$

2.8   Remark. The conclusion of the previous proof used transitivity of equality 1.37). I usually use the properties of equality without explicitly mentioning them.

2.9   Definition (Inverse.) Let $\circ$ be a binary operation on a set $A$, and suppose that there is an identity element $e$ for $\circ$. (We know that this identity is unique.) Let $x$ be an element of $A$. We say that an element $y$ of $A$ is an inverse for $x$ under $\circ$ if

$$x\circ y=e=y\circ x.$$

We say that $x$ is invertible under $\circ$ if $x$ has an inverse under $\circ$.

2.10   Examples. For the operation $+$ on $\mbox{{\bf Z}}$, every element $x$ has an inverse, namely $-x$.

For the operation $+$ on $\mbox{{\bf N}}$, the only element that has an inverse is $0$; $0$ is its own inverse.

For the operation $\cdot$ on $\mbox{{\bf Z}}$, the only invertible elements are $1$ and $-1$. Both of these elements are equal to their own inverses.

If $\circ$ is any binary operation with identity $e$, then $e\circ e=e$, so $e$ is always invertible, and $e$ is equal to its own inverse.

2.11   Exercise. A Let $\mbox{$\cal S$}(\mbox{{\bf Z}})$ be the set of all subsets of $\mbox{{\bf Z}}$. In exercise 2.6 you should have shown that both of the operations $\cup$ and $\cap$ on $\mbox{$\cal S$}(\mbox{{\bf Z}})$ have identity elements.

a

Which subsets $A$ of $\mbox{{\bf Z}}$ have inverses for $\cup$? What are these inverses?

b

Which subsets $A$ of $\mbox{{\bf Z}}$ have inverses for $\cap$? What are these inverses?

2.12   Entertainment. Let $S$ be a set, and let $\mbox{$\cal S$}(S)$ be the set of all subsets of $S$. Define a binary operation $\Delta$ on $\mbox{$\cal S$}(S)$ by

$$A\Delta B=(A\setminus B)\cup (B\setminus A) \mbox{ for all } A,B\in\mbox{$\cal S$}(S).$$

Thus $A\Delta B$ consists of all points that are in exactly one of the sets $A,B$. We call $A\Delta B$ the symmetric difference of $A$ and $B$. Show that there is an identity element for $\Delta$, and that every element of $\mbox{$\cal S$}(S)$ is invertible for $\Delta$.

2.13   Definition (Associative operation.) Let $\circ$ be a binary operation on a set $A$. We say that $\circ$ is associative if

$$\mbox{ for all } a,b,c\in A,\quad a\circ (b\circ c)=(a\circ b)\circ c.$$

2.14   Examples. Both $+$ and $\cdot$ are associative operations on $\mbox{{\bf Q}}$. Subtraction $(-)$ is not an associative operation on $\mbox{{\bf Z}}$, since

$$(1-1)-1\neq 1-(1-1).$$

Observe that to show that a binary operation $\circ$ on a set $A$ is not associative, it is sufficient to find one point $(a,b,c)$ in $A^3$ such that $a\circ (b\circ c)\neq (a\circ b)\circ c$.

You should convince yourself that both $\cap$ and $\cup$ are associative operations on the set $\mbox{$\cal S$}$ of all sets. If $A,B,C$ are sets, then

$$\begin{eqnarray*} A\cap (B\cap C)=(A\cap B)\cap C &=&\mbox{ set of points in all... ...cup B)\cup C &=&\mbox{ set of points in at least one of } A,B,C. \end{eqnarray*}$$

2.15   Theorem (Uniqueness of inverses.) Let $\circ$ be an associative operation on a set $A$, and suppose that there is an identity $e$ for $\circ$. Let $x,y,z\in A$. If $y$ and $z$ are inverses for $x$, then $y=z$.

Proof: Since $y$ and $z$ are inverses for $x$, we have

$$y\circ x=e=x\circ y$$

and

$$z\circ x=e=x\circ z.$$

Hence,

$$y=y\circ e=y\circ (x\circ z)=(y\circ x)\circ z=e\circ z=z.\mbox{ $\mid\!\mid\!\mid$}$$

2.16   Definition (Invertible element.) Let $\circ$ be a binary operation on a set $A$, having an identity element $e$. I will say that an element $x\in A$ is invertible for $\circ$, if $x$ has an inverse. If $\circ$ is associative, then every invertible element for $\circ$ has a unique inverse, which I call the inverse for $x$ under $\circ$.

2.17   Theorem (Double inverse theorem.) Let $\circ$ be an associative binary operation on a set $A$, with identity $e$, and let $x\in A$. If $x$ is invertible for $\circ$, let $x^{-1}$ denote the (unique) inverse for $x$. Then $x^{-1}$ is invertible and $(x^{-1})^{-1}=x$.

Proof: If $y$ is the inverse for $x$, then

$$y\circ x=e=x\circ y.$$

But this is exactly the condition for $x$ to be the inverse for $y$. $\mid\!\mid\!\mid$

2.18   Examples. As special cases of the double inverse theorem, we have

$$-(-x)=x \quad \mbox{ for all } x\in\mbox{{\bf Q}}$$

and

$$(x^{-1})^{-1}=x \quad \mbox{ for all } x\in\mbox{{\bf Q}}\setminus \{0\}.$$

Here, as usual, $x^{-1}$ denotes the multiplicative inverse for $x$.

2.19   Theorem (Cancellation law.) Let $\circ$ be an associative binary operation on a set $A$, having identity $e$, and let $v\in A$ be an invertible element for $\circ$. Then

$$\mbox{ for all } x,y\in A \;\; (x\circ v=y\circ v)\mbox{$\hspace{1ex}\Longrightarrow\hspace{1ex}$}(x=y),$$ (2.20)

and

$$\mbox{ for all } x,y\in A \;\; (v\circ x=v\circ y)\mbox{$\hspace{1ex}\Longrightarrow\hspace{1ex}$}(x=y).$$ (2.21)

Proof: Let $v$ be invertible, and let $w$ be the inverse for $v$. Then for all $x,y\in A$,

$$\begin{eqnarray*} x\circ v=y\circ v&\mbox{$\Longrightarrow$}& (x\circ v)\circ w ... ...htarrow$}& x\circ e=y\circ e \\ &\mbox{$\Longrightarrow$}& x=y. \end{eqnarray*}$$

This proves (2.20). The proof of (2.21) is left to you.

2.22   Exercise. Prove the second half of the cancellation theorem.

2.23   Warning. If $\circ$ is a binary operation on a set $A$, then an expression such as

$$a\circ b\circ c\circ d$$

is ambiguous, and should not be written without including a way of resolving the ambiguity. For example in $\mbox{{\bf Z}}$, $a-b-c-d$ could be interpreted as any of

$$\; \left(a-(b-c)\right)-d,$$ (2.24)

$$\; \left((a-b)-c\right)-d,$$ (2.25)

$$\; (a-b)-(c-d),$$ (2.26)

$$\; a-\left(b-(c-d)\right),$$ (2.27)

$$\; a-((b-c)-d).$$ (2.28)

2.29   Entertainment. Is it possible to find integers $a,b,c,d$ such that the five numbers (2.24)-(2.28) are all different? If so, find four such integers.

2.30   Exercise. Let $\circ$ be an associative binary operation on a set $A$, and let $a,b,c,d$ be elements of $A$.

a)

Show that there are five different ways to sensibly put parentheses in the expression

$$a\circ b\circ c\circ d,$$

and that all five ways produce the same result. (Each way will use two sets of parentheses, e.g. $${\left(a\circ(b\circ c)\right)\circ d}$$ is one way. If you arrange things correctly, you will just need to apply the associative law four times.)

b)

Show that if $a,b,c,d,e$ are elements of $A$, then there are 14 ways to put parentheses in

$$a\circ b\circ c\circ d\circ e,$$

and that all 14 ways lead to the same result. Here each sensible way of inserting parentheses will involve three pairs.

2.31   Entertainment. Show that there are 42 ways to put parentheses in

$$a_1\circ a_2\circ a_3\circ a_4\circ a_5\circ a_6.$$

This can be done without actually writing down all the ways (and there isn't much point in writing down all the ways, because no one would read it if you did). If you did part b. of the previous exercise in such a way that really showed that there are just 14 ways, you should be able to do this, and then to calculate the number of ways to parenthesize products with seven factors. There is a simple (but hard to guess) formula for the number of ways to put parentheses in products with $n$ factors. You can find the formula, along with a derivation, in [44].

2.32   Definition (Commutative operation.) Let $\circ$ be a binary operation on a set $A$. We say that $\circ$ is commutative if

$$\mbox{ for all } a,b\in A \quad a\circ b=b\circ a.$$

2.33   Examples. Both $+$ and $\cdot$ are commutative operations on $\mbox{{\bf Q}}$. However $-$ is not a commutative operation on $\mbox{{\bf Q}}$, because $3-2\neq 2-3$.

The operations $\cup$ and $\cap$ are both commutative operations on the set $\mbox{$\cal S$}$ of all sets, and and and or are commutative operations on the set $\mbox{${\cal P}$}$ of all propositions. The set difference operation $(\setminus)$ is not commutative on $\mbox{$\cal S$}$, since

$$\{1,2\}\setminus \{2,3\}\neq\{2,3\}\setminus \{1,2\}.$$