Next: 2.2 Some Examples Up: 2. Fields Previous: 2. Fields   Index

2.1 Binary Operations

2.1   Definition (Binary operation.) Let be a set. A binary operation on is a function . Binary operations are usually denoted by special symbols such as

rather than by letters. If is a binary operation, we write instead of . By the definition of function (1.57), a binary operation is a triple , but as is usual for functions, we refer to  the binary operation " instead of  the binary operation ".

2.2   Examples. The usual operations of addition , subtraction and multiplication are binary operations on and on . Subtraction is not a binary operation on , because is not in . Division is not a binary operation on , because division by is not defined. However, division is a binary operation on .

Let be the set of all sets.2.1 Then union and intersection and set difference are binary operations on .

Let be the set of all propositions. Then and and or are binary operations on . In mathematical logic, and is usually represented by or , and or is represented by or .

2.3   Definition (Identity element.) Let be a binary operation on a set . An element is an identity element for (or just an identity for ) if

2.4   Examples. is an identity for addition on , and is an identity for multiplication on . There is no identity for subtraction on , since for all we have
 (2.5)

Since (2.5) is false, the first statement is also false; i.e., for all , is not an identity for .

2.6   Exercise. Let denote the set of all subsets of . Then union and intersection are binary operations on . Is there an identity element for ? If so, what is it? Is there an identity element for ? If so, what is it?

2.7   Theorem (Uniqueness of identities.) Let be a binary operation on a set . Suppose that are both identity elements for . Then . (Hence we usually talk about the identity for , rather than an identity for .)

Proof: Let be identity elements for . Then

and

It follows that .

2.8   Remark. The conclusion of the previous proof used transitivity of equality 1.37). I usually use the properties of equality without explicitly mentioning them.

2.9   Definition (Inverse.) Let be a binary operation on a set , and suppose that there is an identity element for . (We know that this identity is unique.) Let be an element of . We say that an element of is an inverse for under if

We say that is invertible under if has an inverse under .

2.10   Examples. For the operation on , every element has an inverse, namely .

For the operation on , the only element that has an inverse is ; is its own inverse.

For the operation on , the only invertible elements are and . Both of these elements are equal to their own inverses.

If is any binary operation with identity , then , so is always invertible, and is equal to its own inverse.

2.11   Exercise. A Let be the set of all subsets of . In exercise 2.6 you should have shown that both of the operations and on have identity elements.

a
Which subsets of have inverses for ? What are these inverses?
b
Which subsets of have inverses for ? What are these inverses?

2.12   Entertainment. Let be a set, and let be the set of all subsets of . Define a binary operation on by

Thus consists of all points that are in exactly one of the sets . We call the symmetric difference of and . Show that there is an identity element for , and that every element of is invertible for .

2.13   Definition (Associative operation.) Let be a binary operation on a set . We say that is associative if

2.14   Examples. Both and are associative operations on . Subtraction is not an associative operation on , since

Observe that to show that a binary operation on a set is not associative, it is sufficient to find one point in such that .

You should convince yourself that both and are associative operations on the set of all sets. If are sets, then

2.15   Theorem (Uniqueness of inverses.) Let be an associative operation on a set , and suppose that there is an identity for . Let . If and are inverses for , then .

Proof: Since and are inverses for , we have

and

Hence,

2.16   Definition (Invertible element.) Let be a binary operation on a set , having an identity element . I will say that an element is invertible for , if has an inverse. If is associative, then every invertible element for has a unique inverse, which I call the inverse for under .

2.17   Theorem (Double inverse theorem.) Let be an associative binary operation on a set , with identity , and let . If is invertible for , let denote the (unique) inverse for . Then is invertible and .

Proof: If is the inverse for , then

But this is exactly the condition for to be the inverse for .

2.18   Examples. As special cases of the double inverse theorem, we have

and

Here, as usual, denotes the multiplicative inverse for .

2.19   Theorem (Cancellation law.) Let be an associative binary operation on a set , having identity , and let be an invertible element for . Then
 (2.20)

and
 (2.21)

Proof: Let be invertible, and let be the inverse for . Then for all ,

This proves (2.20). The proof of (2.21) is left to you.

2.22   Exercise. Prove the second half of the cancellation theorem.

2.23   Warning. If is a binary operation on a set , then an expression such as

is ambiguous, and should not be written without including a way of resolving the ambiguity. For example in , could be interpreted as any of
 (2.24) (2.25) (2.26) (2.27) (2.28)

2.29   Entertainment. Is it possible to find integers such that the five numbers (2.24)-(2.28) are all different? If so, find four such integers.

2.30   Exercise. Let be an associative binary operation on a set , and let be elements of .

a)
Show that there are five different ways to sensibly put parentheses in the expression

and that all five ways produce the same result. (Each way will use two sets of parentheses, e.g. is one way. If you arrange things correctly, you will just need to apply the associative law four times.)

b)
Show that if are elements of , then there are 14 ways to put parentheses in

and that all 14 ways lead to the same result. Here each sensible way of inserting parentheses will involve three pairs.

2.31   Entertainment. Show that there are 42 ways to put parentheses in

This can be done without actually writing down all the ways (and there isn't much point in writing down all the ways, because no one would read it if you did). If you did part b. of the previous exercise in such a way that really showed that there are just 14 ways, you should be able to do this, and then to calculate the number of ways to parenthesize products with seven factors. There is a simple (but hard to guess) formula for the number of ways to put parentheses in products with factors. You can find the formula, along with a derivation, in [44].

2.32   Definition (Commutative operation.) Let be a binary operation on a set . We say that is commutative if

2.33   Examples. Both and are commutative operations on . However is not a commutative operation on , because .

The operations and are both commutative operations on the set of all sets, and and and or are commutative operations on the set of all propositions. The set difference operation is not commutative on , since

Next: 2.2 Some Examples Up: 2. Fields Previous: 2. Fields   Index