The two most common relations between sets, and between classes in general, are equality and containment. Recall that we’re working in von Neumann-Bernays-Gödel (NBG) set theory, so we have a primitive notion of a class. NBG distinguishes between sets—classes that are members of some other class—and proper classes—classes that are not sets.
Equality of two classes in NBG is defined extensionally: if and are classes, then
if and only if
NBG also defines the relations of containment and proper containment between two classes:
if and only if , and
if and only if
When the classes in question are sets, these are just the familiar notions of set equality and containment. We want to define equality and containment relationships for multisets in such a way that we can continue to identify sets with multisets where every element has multiplicity one.
We’ll start by considering the equality of multisets. Suppose we have two multisets and over . If we try to define equality between multisets strictly on the basis on membership, we would have . This isn’t quite what we want, since it doesn’t account for the multiplicity of each element. Instead, we have the following
Let and be multisets. and are equal if and only if
(ii) , where and denotes the restriction of to the domain
As usual, we denote equality by
The definition not only accounts for the multiplicity of the elements, but also allows for the two multisets to have different underlying sets. Condition (ii) uses the fact that any two cardinals are comparable. Similar considerations apply when we define the containment relationship.
Let and be multisets. is contained in written if and only if
We may also say that is included in, or is a submultiset of, The containment is proper if the two multisets are not equal:
With classes, including sets, we can check whether two classes are equal by checking whether they are coextensional. Extensionality is also used to check containment. With multisets, these checks do not suffice, since by definition. The multisets and over that we considered earlier are an example of two multisets such that and despite the fact that they have the same support.
The identification of the sets and with the multisets and where does indeed work correctly with these definitions, as we wanted. In both definitions, condition (ii) is automatically satisfied since for all and so our identification of these sets and multisets preserves both equality and containment.
Copyright © 2008 Michael L. McCliment.