**Review: Associativity, commutativity, and idempotence
**

A binary operation on a set is a function . It is usually written using an infix notation rather than a functional notation such as .

The operation is *associative* if and only if for all . It is *commutative* if and only if for all . It is *idempotent* if and only if for all .

We’ve defined four operations on families of multisets where for all : sums, products, intersections, and unions. As I’ve already commented in a couple of places, we can restrict our attention to families where . This provides us with four binary operations on . Today’s post collects together the properties of these binary operations.

**Proposition 1:** *The operations *, , *, and ** on * *are all associative and commutative.*

Proof:

Let . The first four parts follow directly from the associativity and commutativity of and as binary operations on .

**Associativity of .**

**Commutativity of .**

**Associativity of .**

**Commutativity of .**

The remaining parts follow from the following facts:

- Let be partially ordered sets. Then and whenever the suprema and infima exist.
- The supremum and infimum of every set of cardinals exist.

**Associativity of .**

**Commutativity of .**

**Associativity of .**

**Commutativity of .**

**Proposition 2:** *The operations ** and ** on * *are idempotent.*

Proof:

Let .

**Idempotence of .**

**Idempotence of .**

The other two operations—sum and product—are *not* idempotent. One counterexample is the multiset , for which we have

and

.

Copyright © 2008 Michael L. McCliment.