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.
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.
