ads Operations

Section 11.1 Operations

One of the first mathematical skills that we all learn is how to add a pair of positive integers. A young child soon recognizes that something is wrong if a sum has two values, particularly if his or her sum is different from the teacher’s. In addition, it is unlikely that a child would consider assigning a non-positive value to the sum of two positive integers. In other words, at an early age we probably know that the sum of two positive integers is unique and belongs to the set of positive integers. This is what characterizes all binary operations on a set.

🔗

Subsection 11.1.1 What is an Operation?

Definition 11.1.1. Binary Operation.

Let \(S\) be a nonempty set. A binary operation on \(S\) is a rule that assigns to each ordered pair of elements of \(S\) a unique element of \(S\text{.}\) In other words, a binary operation is a function from \(S\times S\) into \(S\text{.}\)

🔗

Example 11.1.2. Some common binary operations.

Union and intersection are both binary operations on the power set of any universe. Addition and multiplication are binary operators on the natural numbers. Addition and multiplication are binary operations on the set of 2 by 2 real matrices, \(M_{2\times 2}(\mathbb{R})\text{.}\) Division is a binary operation on some sets of numbers, such as the positive reals. But on the integers (\(1/2\notin \mathbb{Z}\)) and even on the real numbers \((1/0\) is not defined), division is not a binary operation.

🔗

Note 11.1.3.

We stress that the image of each ordered pair must be in \(S\text{.}\) This requirement disqualifies subtraction on the natural numbers from consideration as a binary operation, since \(1 - 2\) is not a natural number. Subtraction is a binary operation on the integers.
🔗

🔗
On Notation. Despite the fact that a binary operation is a function, symbols, not letters, are used to name them. The most commonly used symbol for a binary operation is an asterisk, \(*\text{.}\) We will also use a diamond, \(\diamond\text{,}\) when a second symbol is needed.
🔗

🔗

🔗

If \(*\) is a binary operation on \(S\) and \(a, b \in S\text{,}\) there are three common ways of denoting the image of the pair \((a, b)\text{.}\) They are:

\begin{equation*} \begin{array}{ccc} *a b & a*b & a b * \\ \textrm{ Prefix Form} & \textrm{ Infix Form} & \textrm{ Postfix Form} \\ \end{array} \end{equation*}

We are all familiar with infix form. For example, \(2 + 3\) is how everyone is taught to write the sum of 2 and 3. But notice how \(2 + 3\) was just described in the previous sentence! The word sum preceded 2 and 3. Orally, prefix form is quite natural to us. The prefix and postfix forms are superior to infix form in some respects. In Chapter 10, we saw that algebraic expressions with more than one operation didn’t need parentheses if they were in prefix or postfix form. However, due to our familiarity with infix form, we will use it throughout most of the remainder of this book.

🔗

Some operations, such as negation of numbers and complementation of sets, are not binary, but unary operators.

🔗

Definition 11.1.4. Unary Operation.

Let \(S\) be a nonempty set. A unary operator on \(S\) is a rule that assigns to each element of \(S\) a unique element of \(S\text{.}\) In other words, a unary operator is a function from \(S\) into \(S\text{.}\)

🔗

Subsection 11.1.2 Properties of Operations

Whenever an operation on a set is encountered, there are several properties that should immediately come to mind. To effectively make use of an operation, you should know which of these properties it has. By now, you should be familiar with most of these properties. We will list the most common ones here to refresh your memory and define them for the first time in a general setting.

🔗

First we list properties of a single binary operation.

🔗

Definition 11.1.5. Commutative Property.

Let \(*\) be a binary operation on a set \(S\text{.}\) We say that \(*\) is commutative if and only if \(a * b = b * a\) for all \(a, b \in S\text{.}\)

🔗

Definition 11.1.6. Associative Property.

Let \(*\) be a binary operation on a set \(S\text{.}\) We say that \(*\) is associative if and only if \((a * b) * c = a * (b * c)\) for all \(a, b, c \in S\text{.}\)

🔗

Definition 11.1.7. Identity Property.

Let \(*\) be a binary operation on a set \(S\text{.}\) We say that \(*\) has an identity if and only if there exists an element, \(e\text{,}\) in \(S\) such that \(a * e = e * a = a\) for all \(a \in S\text{.}\)

🔗

The next property presumes that \(*\) has the identity property.

🔗

Definition 11.1.8. Inverse Property.

Let \(*\) be a binary operation on a set \(S\text{.}\) We say that \(*\) has the inverse property if and only if for each \(a \in S\text{,}\) there exists \(b \in S\) such that \(a*b = b*a = e\text{.}\) We call \(b\) an inverse of \(a\text{.}\)

🔗

Definition 11.1.9. Idempotent Property.

Let \(*\) be a binary operation on a set \(S\text{.}\) We say that \(*\) is idempotent if and only if \(a * a = a\) for all \(a \in S\text{.}\)

🔗

Now we list properties that apply to two binary operations.

🔗

Definition 11.1.10. Left Distributive Property.

Let \(*\) and \(\diamond\) be binary operations on a set \(S\text{.}\) We say that \(\diamond\) is left distributive over \(*\) if and only if \(a \diamond (b * c) = (a \diamond b) * (a \diamond c)\) for all \(a,b,c\in S\text{.}\)

🔗

Definition 11.1.11. Right Distributive Property.

Let \(*\) and \(\diamond\) be binary operations on a set \(S\text{.}\) We say that \(\diamond\) is right distributive over \(*\) if and only if \((b * c)\diamond a = (b\diamond a) * (c \diamond a)\) for all \(a,b,c\in S\text{.}\)

🔗

Definition 11.1.12. Distributive Property.

Let \(*\) and \(\diamond\) be binary operations on a set \(S\text{.}\) We say that \(\diamond\) is distributive over \(*\) if and only if \(\diamond\) is both left and right distributive over \(*\text{.}\)

🔗

There is one significant property of unary operations.

🔗

Definition 11.1.13. Involution Property.

Let \(-\) be a unary operation on \(S\text{.}\) We say that \(-\) has the involution property if \(-(-a) = a\) for all \(a \in S\text{.}\)

🔗

Finally, a property of sets, as they relate to operations.

🔗

Definition 11.1.14. Closure Property.

Let \(T\) be a subset of \(S\) and let \(*\) be a binary operation on \(S\text{.}\) We say that \(T\) is closed under \(*\) if \(a, b \in T\) implies that \(a * b \in T\text{.}\)

🔗

In other words, \(T\) is closed under \(*\) if by operating on elements of \(T\) with \(*\text{,}\) you can’t get new elements that are outside of \(T\text{.}\)

🔗

Example 11.1.15. Some examples of closure and non-closure.

The odd integers are closed under multiplication, but not under addition.
🔗

🔗
Let \(p\) be a proposition over \(U\) and let \(A\) be the set of propositions over \(U\) that imply \(p\text{.}\) That is; \(q \in A\) if \(q\Rightarrow p\text{.}\) Then \(A\) is closed under both conjunction and disjunction.
🔗

🔗
The set of positive integers that are multiples of 5 is closed under both addition and multiplication.
🔗

🔗

🔗

It is important to realize that the properties listed above depend on both the set and the operation(s). Statements such as “Multiplication is commutative.” or “The positive integers are closed.” are meaningless on their own. Naturally, if we have established a context in which the missing set or operation is clearly implied, then they would have meaning.

🔗

Subsection 11.1.3 Operation Tables

If the set on which a binary operation is defined is small, a table is often a good way of describing the operation. For example, we might want to define \(\oplus\) on \(\{0, 1, 2\}\) by \(a\oplus b=\left\{ \begin{array}{cc} a+b & \textrm{ if } a+b < 3 \\ a+b-3 & \textrm{ if } a+b\geq 3 \\ \end{array} \right.\) The table for \(\oplus\) is

\begin{equation*} \begin{array}{c | c c c} \oplus & 0 & 1 & 2 \\ \hline 0 & 0 & 1 & 2 \\ 1 & 1 & 2 & 0 \\ 2 & 2 & 0 & 1 \end{array} \end{equation*}

🔗

The top row and left column of an operation table are the column and row headings, respectively. To determine \(a\oplus b\text{,}\) find the entry in the row labeled \(a\) and the column labeled \(b\text{.}\) The following operation table serves to define \(*\) on \(\{i, j, k\}\text{.}\)

\begin{equation*} \begin{array}{c | c c c} * & i & j & k \\ \hline i & i & i & i \\ j & j & j & j \\ k & k & k & k \end{array} \end{equation*}

🔗

Note that \(j*k = j\text{,}\) yet \(k * j = k\text{.}\) Thus, \(*\) is not commutative. Commutativity is easy to identify in a table: the table must be symmetric with respect to the diagonal going from the top left to lower right.

🔗

Exercises 11.1.4 Exercises

1.

Determine the properties that the following operations have on the positive integers.

addition
🔗

🔗
multiplication
🔗

🔗
\(M\) defined by \(a M b = \textrm{ larger} \textrm{ of } a \textrm{ and } b\)
🔗

🔗
\(m\) defined by \(a m b = \textrm{ smaller} \textrm{ of } a \textrm{ and } b\)
🔗

🔗
\(@\) defined by \(a @ b = a^b\)
🔗

🔗

🔗

Answer.

Commutative, and associative. Notice that zero is the identity for addition, but it is not a positive integer.
🔗

🔗
Commutative, associative, and has an identity (1)
🔗

🔗
Commutative, associative, has an identity (1), and is idempotent
🔗

🔗
Commutative, associative, and idempotent
🔗

🔗
None. Notice that \(2 @ (3 @ 3) = 134217728\text{,}\) while \((2 @ 3) @ 3 = 512\text{;}\) and \(a @ 1 = a\text{,}\) while \(1 @ a = 1\text{.}\)
🔗

🔗

🔗

2.

Determine the properties that the following operations have on given sets.

Intersection on the set of subsets of \(\{1,2,3,4\}\text{.}\)
🔗

🔗
\(\omega\) defined on the positive integers by \(a \omega b = b\text{.}\)
🔗

🔗
\(*\) defined on the integers by \(a * b =a + b -2\)
🔗

🔗
\(\diamond\) defined on the positive real numbers by \(a \diamond b = \frac{a b}{2}\text{.}\)
🔗

🔗
Concatenation on the set of all strings of zeros and ones.
🔗

🔗

🔗

3.

Let \(*\) be an operation on a set \(S\) and \(A, B \subseteq S\text{.}\) Prove that if \(A\) and \(B\) are both closed under \(*\text{,}\) then \(A\cap B\) is also closed under \(*\text{,}\) but \(A \cup B\) need not be.

🔗

Answer.

\begin{equation*} \begin{split} a, b \in A \cap B & \Rightarrow a, b \in A \textrm{ by the definition of intersection}\\ & \Rightarrow a*b \in A\textrm{ by the closure of } A \textrm{ with respect to } * \end{split} \end{equation*}

Similarly, \(a, b \in A \cap B \Rightarrow a*b \in B\text{.}\) Therefore, \(a * b \in A \cap B\text{.}\) The set of positive integers is closed under addition, and so is the set of negative integers, but \(1 + -1 = 0\text{.}\) Therefore, their union, the nonzero integers, is not closed under addition.

🔗

4.

How can you pick out the identity of an operation from its table?

🔗

5.

Define \(a * b\) by \(\lvert a - b \rvert\text{,}\) the absolute value of \(a - b\text{.}\) Which properties does \(*\) have on the set of natural numbers, \(\mathbb{N}\text{?}\)

🔗

Answer.

\(*\) is commutative since \(\left| a-b\right| =\left| b-a\right|\) for all \(a, b \in \mathbb{N}\)
🔗

🔗
\(*\) is not associative. Take \(a = 1\text{,}\) \(b = 2\text{,}\) and \(c = 3\text{,}\) then \((a * b) * c =\left| \left| 1-2\right| -3\right| =2\) , and \(a * (b * c) = \left| 1-\left| 2-3\right| \right| = 0\text{.}\)
🔗

🔗
Zero is the identity for \(*\) on \(\mathbb{N}\text{,}\) since \(a*0=\left| a - 0\right| = a = \left| 0-a\right| = 0 * a.\)
🔗

🔗
Each element of \(\mathbb{N}\) inverts itself since \(a * a=\left| a-a\right| = 0\text{.}\)
🔗

🔗
\(*\) is not idempotent, since, for \(a\neq 0\text{,}\) \(a * a =0 \neq a\text{.}\)
🔗

🔗

🔗

6.

Which pairs of operations in Exercise 1 are distributive over one another?

🔗

You have attempted of activities on this page.

🔗

Prev Top Next