#####
Definition11.1.1Binary 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{.}\)

#####
Example11.1.2Some 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})\). 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\), there are three common ways of denoting the image of the pair \((a, b)\). They are: \[\begin{array}{ccc} *a b & a*b & a b * \\ \textrm{ Prefix Form} & \textrm{ Infix Form} & \textrm{ Postfix Form} \\ \end{array}\] 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.

#####
Definition11.1.4Unary 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{.}\)

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.

#####
Definition11.1.5Commutative 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\).

#####
Definition11.1.6Associative 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\).

#####
Definition11.1.7Identity 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\).

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

#####
Definition11.1.8Inverse 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\), there exists \(b \in S\) such that \(a*b = b*a = e\). We call \(b\) an inverse of \(a\text{.}\)

#####
Definition11.1.9Idempotent 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\).

Now we list properties that apply to two binary operations.

#####
Definition11.1.10Left 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\).

#####
Definition11.1.11Right 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\).

#####
Definition11.1.12Distributive 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.

#####
Definition11.1.13Involution Property

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

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

#####
Definition11.1.14Closure 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\).

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{.}\)

#####
Example11.1.15Some 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\). 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.

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{array}{c | c c c} \oplus & 0 & 1 & 2 \\ \hline 0 & 0 & 1 & 2 \\ 1 & 1 & 2 & 0 \\ 2 & 2 & 0 & 1 \end{array} \]

The top row and left column of an operation table are the column and row headings, respectively. To determine \(a\oplus b\), 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\}\). \[ \begin{array}{c | c c c} * & i & j & k \\ \hline i & i & i & i \\ j & j & j & j \\ k & k & k & k \end{array} \]

Note that \(j*k = j\), yet \(k * j = k\). 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.