1: Binary Operations

The most basic definition in this course is the following:

Definition 1.1: Binary Operation

A binary operation \(*\) on a set \(S\) is a function from \(S \times S\) to \(S\). If \((a,b) \in S \times S\) then we write \(a * b\) to indicate the image of the element \((a,b)\) under the function \(*\).

The following lemma explains in more detail exactly what this definition means.

Lemma 1.1 A binary operation \(*\) on a set \(S\) is a rule for combining two elements of \(S\) to produce a third element of \(S\). This rule must satisfy the following conditions:

(a)

\(a \in S \mbox{ and } b \in S \Longrightarrow a*b \in S\).

[S is closed under \(*\).]

(b)

For all \(a,b,c,d\) in \(S\)
\(a=c \mbox{ and } b=d \Longrightarrow a*b=c*d.\)

[Substiution is permissible.]

(c)

For all \(a,b,c, d\) in \(S\)
\(a=b \Longrightarrow a*c=b*c\).

(d)

For all \(a,b,c, d\) in \(S\)
\(c=d\Longrightarrow a*c=a*d\).

Proof Recall that a function \(f\) from set \(A\) to set \(B\) is a rule which assigns to each element \(x \in A\) an element, usually denoted by \(f(x)\), in the set \(B\). Moreover, this rule must satisfy the condition \[\begin{align} \label{eqn1.1} x=y \Longrightarrow f(x) = f(y) \end{align} \] On the other hand, the Cartesian product \(S \times S\) consists of the set of all ordered pairs \((a,b)\) where \(a, b \in S\). Equality of ordered pairs is defined by the rule \[\begin{align} \label{eqn1.2} a = c \mbox{ and } b = d \Longleftrightarrow (a,b) = (c,d). \end{align}\] Now in this case we assume that \(*\) is a function from the set \(S \times S\) to the set \(S\) and instead of writing \(*(a,b)\) we write \(a*b\). Now, if \(a, b \in S\) then \((a,b)\in S \times S\). So the rule \(*\) assigns to \((a,b)\) the element \(a*b \in S\). This establishes (a). Now implication ([eqn1.1]) becomes \[\begin{align} \label{eqn1.3} (a,b) = (c,d) \Longrightarrow a*b = c*d. \end{align}\] From ([eqn1.2]) and ([eqn1.3]) we obtain \[\begin{align} \label{eqn1.4} a = c \mbox{ and } b = d \Longrightarrow a*b = c*d. \end{align}\] This establishes (b).

To prove (c) we assume that \(a=b\). By reflexivity of equality, we have for all \(c \in S\) that \(c = c\). Thus we have \(a=b\) and \(c=c\) and it follows from part (b) that \(a*c=b*c\), as desired. The proof of (d) is similar. \(\blacksquare\)

Remark

In part (a) the order of \(a\) and \(b\) is important. We do not assume that \(a*b\) is the same as \(b*a\). Although sometimes it may be true that \(a*b = b*a\), it is not part of the definition of binary operation.

Statement (b) says that if \(a=c\) and \(b=d\), we can substitute \(c\) for \(a\) and \(d\) for \(b\) in the expression \(a*b\) and we obtain the expression \(c*d\) which is equal to \(a*b\). One might not think that such a natural statement is necessary. To see the need for it, see Problem 1.7 below.

Part (c) of the above lemma says that we can multiply both sides of an equation on the right by the the same element. Part (d), says that we can multiply both sides of an equation on the left by the same element.

Binary operations are usually denoted by symbols such as \[ \nonumber +, \cdot, * , \times, \circ, \star, \bullet, \diamond, \boxdot, \boxtimes, \otimes, \oplus, \odot, \vee, \wedge, \cup, \cap, \cdots\] Just as one often uses \(f\) for a generic function, we use \(*\) to indicate a generic binary operation. Moreover, if \(* : S\times S\to S\) is a given binary operation on a set \(S\), we write \(a * b\) instead of \(*(a,b)\). This is called infix notation. In practice, we abbreviate even more; just as we use \(ab\) instead of \(a \cdot b\) or \(a \times b\) in high school algebra, we will often use \(ab\) instead of \(a*b\) for a generic binary operation.

Notation. We denote the natural numbers, the integers, the rational numbers, and the real numbers by the symbols \(\mathbb{N}\), \(\mathbb{Z}\), \(\mathbb{Q}\), and \(\mathbb{R}\), respectively.

Recall that \[\begin{aligned} \mathbb{N} &=& \{ 1,2,3, \dots \} \\ \mathbb{Z} &=& \{ \dots, -3, -2, -1, 0, 1, 2, 3, \dots \} \\ \mathbb{Q} &=& \{ \frac n m: n,m \in \mathbb{Z}\mbox{ and } m \ne 0 \}\end{aligned}\] For now, we assume that students have a basic knowledge of all these number systems. Later in the course, we will give a list of axioms from which all properties of these number systems can be derived. See Appendix C for some basic properties of \(\mathbb{N}\) and \(\mathbb{Z}\) that we will need from time to time.

We now list some examples of binary operations. Some should be very familiar to you. Some may be new to you.

Example 1.1 Ordinary addition on \(\mathbb{N}\), \(\mathbb{Z}\), \(\mathbb{Q}\) and \(\mathbb{R}\).

Example 1.2 Ordinary multiplication on \(\mathbb{N}\), \(\mathbb{Z}\), \(\mathbb{Q}\) and \(\mathbb{R}\).

Example 1.3 Ordinary subtraction on \(\mathbb{Z}\), \(\mathbb{Q}\) and \(\mathbb{R}\). Note that subtraction is not a binary operation on \(\mathbb{N}\) since, for example, \(1 - 2 \notin \mathbb{N}\).

Example 1.4 Ordinary division on \(\mathbb{Q}- \{ 0 \}\) and \(\mathbb{R}- \{ 0 \}\). Note that division is not a binary operation on \(\mathbb{N}\) and \(\mathbb{Z}\) since, for example, \(\frac 1 2 \notin \mathbb{N}\) and \(\frac 1 2 \notin \mathbb{Z}\). Also note that we must remove 0 from \(\mathbb{Q}\) and \(\mathbb{R}\) since division by 0 is not defined.

Example 1.5 For each integer \(n \ge 2\) define the set \[ \nonumber \mathbb{Z}_n = \{ 0, 1, 2, \dots, n-1 \}.\] For all \(a, b \in \mathbb{Z}_n\) let

\(a + b =\) remainder when the ordinary sum of \(a\) and \(b\) is divided by \(n\), and

\(a \cdot b =\) remainder when the ordinary product of \(a\) and \(b\) is divided by \(n\).

The binary operations defined in Example 1.5 are usually referred to as addition modulo \(n\) and multiplication modulo \(n\). The integer \(n\) in \(\mathbb{Z}_n\) is called the modulus. The plural of modulus is moduli.

In Example 1.5, it would be more precise to use something like \(a +_n b\) and \(a \cdot_n b\) for addition and multiplication in \(\mathbb{Z}_n\), but in the interest of keeping the notation simple we omit the subscript \(n\). Of course, this means that in any given situation, we must be very clear about the value of \(n\). Note also that this is really an infinite class of examples: \(\mathbb{Z}_2 = \{0,1\}\), \(\mathbb{Z}_3 = \{0,1,2\}\), \(\mathbb{Z}_4 = \{0,1,2,3\}\), etc. Just to be clear, we give a few examples of addition and multiplication:

In \(\mathbb{Z}_4\):

\(2 + 3 =1\), \(2 + 2 = 0\), \(0 + 3 = 3\), \(2\cdot3= 2\), \(2\cdot2=0\) and \(1\cdot3=3\).

In \(\mathbb{Z}_5\):

\(2 + 3 =0\), \(2 + 2 = 4\), \(0 + 3 = 3\), \(2\cdot3=1\), \(2\cdot2=4\) and \(1\cdot3=3\)\

Example 1.6 For each integer \(n \ge 1\) we let \([n] = \{1,2, \cdots, n \}\).
A permutation on \([n]\) is a function from \([n]\) to \([n]\) which is both one-to-one and onto. We define \(S_n\) to be the set of all permutations on \([n]\). If \(\sigma\) and \(\tau\) are elements of \(S_n\) we define their product \(\sigma \tau\) to be the composition of \(\sigma\) and \(\tau\), that is, \[\nonumber \sigma \tau (i) = \sigma(\tau(i)) \quad \mbox{for all }\in \mbox{ n}.\] See Appendix B if any of the terms used in this example are unfamiliar.

Again, we have an infinite number of examples: \(S_1\), \(S_2\), \(S_3\), \(S_4\), etc. We discuss this example as well as the other examples in more detail later. First, we give a few more examples:

Example 1.7 Let \(K\) denote any one of the following: \(\mathbb{Z},\mathbb{Q}, \mathbb{R}, \mathbb{Z}_n\). Let \(M_2(K)\) be the set of all \(2 \times 2\) matrices \[\nonumber \left [ \begin{array} {c c} a & b \\ c & d \end{array} \right]\] where \(a,b,c,d\) are any elements of \(K\). Matrix addition and multiplication are defined by the following rules:

\[\left [ \nonumber \begin{array} {c c} a & b \\ c & d \end{array} \right] + \left [ \begin{array} {c c} a' & b' \\ c' & d' \end{array} \right] = \left [ \begin{array} {c c} a + a' & b+b' \\ c+c' & d+d' \end{array} \right]\]

\[\nonumber \left [ \begin{array} {c c} a & b \\ c & d \end{array} \right] \cdot \left [ \begin{array} {c c} a' & b' \\ c' & d' \end{array} \right] = \left [ \begin{array} {c c} aa' +bc' & ab'+bd' \\ ca'+dc'& cb'+dd' \end{array} \right]\]

for all \(a,b,c,d,a',b',c',d' \in K\).

Example 1.8 The usual addition of vectors in \(\mathbb{R}^n\), \(n \in \mathbb{N}\). More precisely

\[\nonumber \mathbb{R}^n = \{ (x_1, x_2, \dots, x_n) \ | \ x_i \in \mathbb{R}\mbox{ for all $i$} \}.\]

Addition is defined by the rule: \[\nonumber (x_1, x_2, \dots, x_n) + (y_1, y_2, \dots, y_n) = (x_1 + y_1, x_2 +y_2, \dots, x_n+y_n).\] where \(x_i+y_i\) denotes the usual addition of the real numbers \(x_i\) and \(y_i\).

Example 1.9 Addition modulo 2 for binary sequences of length \(n\), \(n \in \mathbb{N}\). (This example is important for computer science.) In this case the set is \[\nonumber \mathbb{Z}_2^n = \{ (x_1, x_2, \dots, x_n) \ | \ x_i \in \mathbb{Z}_2 \mbox{ for all $i$} \}.\] Recall that \(\mathbb{Z}_2 = \{0,1\}\). Addition is defined by the rule: \[(x_1, x_2, \dots, x_n) + (y_1, y_2, \dots, y_n) = (x_1 + y_1, x_2 +y_2, \dots, x_n+y_n).\] where \(x_i+y_i\) denotes addition modulo 2 (also called exclusive or) of \(x_i\) and \(y_i\). More precisely \(0+0=0\), \(0+1=1\), \(1+0=1\) and \(1+1=0\).

Example 1.10 The cross product \(\mathbf{u} \times \mathbf{v}\) of vectors \(\mathbf{u}\) and \(\mathbf{v}\) in \(\mathbb{R}^3\). Recall that if \[\begin{aligned} \mathbf{u} &=&(u_1,u_2,u_3) \\ \mathbf{v}&=&(v_1,v_2,v_3)\end{aligned}\] then \(\mathbf{u} \times \mathbf{v}\) is defined by the formula \[\nonumber \mathbf{u} \times \mathbf{v} = \left( \left | \begin{array} {cc} u_2&u_3\\v_2&v_3 \end{array} \right |, -\left | \begin{array} {cc} u_1&u_3\\v_1&v_3 \end{array} \right |, \left | \begin{array} {cc} u_1&u_2\\v_1&v_2 \end{array} \right | \right),\] where \[\nonumber \left | \begin{array} {cc} a&b\\c&d \end{array} \right | = ad-bc.\]

Example 1.11 The set operations \(\cup\) and \(\cap\) are binary operations on the set \(\mathcal{P}(X)\) of all subsets of \(X\). Recall that the set \(\mathcal{P}(X)\) is called the power set of \(X\); and, if \(A\) and \(B\) are sets, then \(A \cup B\) is called the union of \(A\) and \(B\) and \(A \cap B\) is called the intersection of \(A\) and \(B\).

Definition 1.2:

Assume that \(*\) is a binary operation on the set \(S\).

1. We say that \(*\) is associative if

   \[x*(y*z) = (x*y)*z \quad \mbox{for all x,y,z }\in\mbox{ S}.\]

2. We say that an element \(e\) in \(S\) is an identity with respect to \(*\) if

   \[x*e = x \mbox{ and } e*x = x \quad \mbox{for all $x$ in $S$}.\]

3. Let \(e \in S\) be an identity with respect to \(*\). Given \(x \in S\) we say that an element \(y \in S\) is an inverse of \(x\) if both \[x*y=e \mbox{ and } y*x=e.\]
4. We say that \(*\) is commutative if \[x*y=y*x \quad \mbox{ for all $x,y \in S.$}\]
5. We say that an element \(a\) of \(S\) is idempotent with respect to \(*\) if \[a*a=a.\]
6. We say that an element \(z\) of \(S\) is a zero with respect to \(*\) if \[z*x=z \mbox{ and } x*z=z \quad \mbox{for all $x \in S$}.\]

Problem 1.1 Assume that \(*\) is a binary operation on the set \(S\). Prove the following statements.

(i) If \(e\) and \(e'\) are identities with respect to \(*\) on \(S\) then \(e = e'\). [Hint: What is \(e*e'\)?]

(ii) If \(z\) and \(z'\) are zeros with respect to \(*\) on \(S\) then \(z = z'\). [Hint: What is \(z*z'\)?]

Problem 1.2 Go through all of the above examples of binary operations and determine which are not associative. Show non-associativity by giving three specific elements \(a,b,c\) such that \(a*(b*c) \ne (a*b)*c\).

Problem 1.3 Go through all of the above examples of binary operations and determine which are not commutative. Show non-commutativity by giving two specific elements \(a,b\) such that \(a*b \ne b*a\).

Remark

A set may have several binary operations on it. For example, consider the set \(\mathbb{R}\) of real numbers. We write \((\mathbb{R}, \cdot)\), \((\mathbb{R}, +)\), and \((\mathbb{R}, -)\) to indicate the set \(\mathbb{R}\) with the binary operations multiplication, addition and subtraction, respectively. Similarly, we use this notation for other sets such as the set \(M_2(\mathbb{R})\), of \(2 \times 2\) matrices over the real numbers \(\mathbb{R}\). We use \((M_2(\mathbb{R}), \cdot)\) and \((M_2(\mathbb{R}), + )\) to denote matrix multiplication and matrix addition, respectively, on \(M_2(\mathbb{R})\).

Problem 1.4 Determine which of the examples \((\mathbb{R}, \cdot)\), \((\mathbb{R}, +)\), \((M_2(\mathbb{R}), \cdot)\), and \((\mathcal{P}(X), \cup)\) have identities. If there is an identity, determine the elements which do not have inverses.

Problem 1.5 Determine which of the examples \((\mathbb{R}, \cdot)\), \((\mathbb{R}, +)\), \((M_2(\mathbb{R}), \cdot)\), and \((\mathcal{P}(X), \cup)\) have zeros. If there is a zero, determine whether or not there are non-zero elements whose product is zero.

Problem 1.6 Determine which of the examples \((\mathbb{R}, \cdot)\), \((\mathbb{R}, +)\), \((M_2(\mathbb{R}), \cdot)\), and \((\mathcal{P}(X), \cup)\) have idempotents. Try to find all idempotents in each case.

Problem 1.7 Here we give an example of a rule that appears to define a binary operation, but does not, since substitution is not permissible. Let \(a,b,c,d\) be integers with \(b \ne 0\) and \(d \ne 0\). Then \[\frac a b \in \mathbb{Q} \ \mbox{ and } \ \frac c d \in \mathbb{Q}.\] Define \(*\) on \(\mathbb{Q}\) by: \[\frac a b * \frac c d = \frac {a+c}{b^2+d^2}.\] Show that \[\frac a b * \frac c d \in \mathbb{Q},\] so \(\mathbb{Q}\) is closed under \(*\). Show by specific example that this rule does not permit substitution.