Skip to main content
\(\newcommand{\identity}{\mathrm{id}} \newcommand{\notdivide}{{\not{\mid}}} \newcommand{\notsubset}{\not\subset} \newcommand{\lcm}{\operatorname{lcm}} \newcommand{\gf}{\operatorname{GF}} \newcommand{\inn}{\operatorname{Inn}} \newcommand{\aut}{\operatorname{Aut}} \newcommand{\Hom}{\operatorname{Hom}} \newcommand{\cis}{\operatorname{cis}} \newcommand{\chr}{\operatorname{char}} \newcommand{\Null}{\operatorname{Null}} \renewcommand{\vec}[1]{\mathbf{#1}} \newcommand{\lt}{ < } \newcommand{\gt}{ > } \newcommand{\amp}{ & } \)

Section11.1Operations

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.

Subsection11.1.1What is an Operation?

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\). In other words, a binary operation is a function from \(S\times S\) into \(S\).

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.

Note11.1.3

  1. We stress that the image of each ordered pair must be in \(S\). 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.

  2. 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, \(*\). We will also use a diamond, \(\diamond\), when a second symbol is needed.

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\). In other words, a unary operator is a function from \(S\) into \(S\).

Subsection11.1.2Properties 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.

Definition11.1.5Commutative Property

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

Definition11.1.6Associative Property

Let \(*\) be a binary operation on a set \(S\). We say that \(*\) is associative 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\). We say that \(*\) has an identity if there exists an element, \(e\), 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\). We say that \(*\) has the inverse property 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\).

Definition11.1.9Idempotent Property

Let \(*\) be a binary operation on a set \(S\). We say that \(*\) is idempotent 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\). We say that \(\diamond\) is left distributive over * 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\). We say that \(\diamond\) is right distributive over * 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\). We say that \(\diamond\) is distributive over \(*\) if \(\diamond\) is both left and right distributive over \(*\).

There is one significant property of unary operations.

Definition11.1.13Involution Property

Let \(-\) be a unary operation on \(S\). 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\)., 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 \(*\), you can't get new elements that are outside of \(T\).

Example11.1.15Some examples of closure and non-closure

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

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

  3. The set 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.

Subsection11.1.3Operation 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{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\). 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.

Subsection11.1.4Exercises for Section 11.1

1

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

  1. addition

  2. multiplication

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

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

  5. @ defined by \(a @ b = a^b\)

Answer
2

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

3

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

Answer
4

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

5

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

Answer