Before we talk about operations (union, intersection, etc.) on multisets, it will be helpful to talk a bit more about a particular construction associated with the power set of a set.
To start with, let’s look at the finite field The operation tables for are:
If we take 0 as false and 1 as true, then multiplication corresponds to conjunction in classical logic and addition corresponds to exclusive disjunction
Let be a set and The characteristic function of (relative to ) is the function defined by
With this definition, we actually have a bijective correspondence between the power set and the functions
Let’s consider the sums and products of characteristic functions. If then and are both well defined functions from to —in other words, the sum and the product of two characteristic functions are again characteristic functions for some subsets of
For the product we will have if and only if , so the product yields the characteristic function of the set . This isn’t particularly surprising, since multiplication in corresponds to logical conjunction. The sum, however, does not correspond to intersection (remember that the sum in corresponds to exclusive disjunction). If then whenever exactly one of and equals 1, so we have the symmetric difference.
Using these two results, we can easily determine the formulas involving characteristic functions that correspond to the other typical set operations. For the difference (relative complement) of two subsets of a set we have
One of the identities among the set operations applied to is The characteristic function is the constant value 1; combining this identity with the previous results, we find that
Incidentally, in each element is its own additive inverse, so we have for all so each of the formulas we have derived above can also be expressed in terms of subtraction.
If we further consider as an ordered field, we obtain two additional ways to represent unions and intersections in terms of their characteristic functions:
One final observation. If and is the characteristic function of relative to , then has a unique extension defined by
In order for the sums and products of characteristic functions to be well-defined, they must have a common domain. The existence of this unique extension ensures that we can always find a common domain in which to represent any family of sets by their characteristic functions.
Copyright © 2008 Michael L. McCliment.