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

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 .

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

Proof: Let be identity elements for . Then

and

It follows that .

We say that is

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.

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

Thus consists of all points that are in exactly one of the sets . We call the

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

Proof: Since and are inverses for , we have

and

Hence,

Proof: If is the inverse for , then

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

and

Here, as usual, denotes the multiplicative inverse for .

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.

is ambiguous, and should not be written without including a way of resolving the ambiguity. For example in , could be interpreted as any 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.

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

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