Multiset equality and submultisets

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 A and B are classes, then

A = B if and only if \left(\forall X\right) \left(X\in A \Leftrightarrow X\in B\right).

NBG also defines the relations of containment A\subseteq B and proper containment A\subset B between two classes:

A\subseteq B if and only if \left(\forall X\right) \left(X\in A \Rightarrow X\in B\right), and

A\subset B if and only if A\subseteq B \wedge A \neq B.

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 \mathcal{A} = \left\{ 1, 1, 2, 2, 2, 4\right\} and \mathcal{B} =  \left\{ 1, 2, 4, 4 \right\} over \mathbb{N}. If we try to define equality between multisets strictly on the basis on membership, we would have \mathcal{A} = \mathcal{B}. This isn’t quite what we want, since it doesn’t account for the multiplicity of each element. Instead, we have the following


Let \mathcal{A} = \left(A, f\right) and \mathcal{B} = \left(B, g\right) be multisets. \mathcal{A} and \mathcal{B} are equal if and only if

(i) \mathrm{support}\left(\mathcal{A}\right) = \mathrm{support}\left(\mathcal{B}\right) and

(ii) f|_S = g|_S, where S = \mathrm{support}\left(\mathcal{A}\right) and f|_S denotes the restriction of f to the domain S.

As usual, we denote equality by \mathcal{A} = \mathcal{B}.

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 \mathcal{A} = \left(A, f\right) and \mathcal{B} = \left(B, g\right) be multisets. \mathcal{A} is contained in \mathcal{B}, written \mathcal{A}\subseteq\mathcal{B}, if and only if

(i) \mathrm{support}\left(\mathcal{A}\right) \subseteq \mathrm{support}\left(\mathcal{B}\right) and

(ii) f|_S \leq g|_S, where S = \mathrm{support}\left(\mathcal{A}\right).

We may also say that \mathcal{A} is included in, or is a submultiset of, \mathcal{B}. The containment is proper if the two multisets are not equal:

\mathcal{A} \subset \mathcal{B} := \mathcal{A}\subseteq\mathcal{B} \wedge \mathcal{A}\neq\mathcal{B}.

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 x\in \mathcal{A} \Leftrightarrow x\in\mathrm{support}\left(\mathcal{A}\right) by definition. The multisets \mathcal{A} = \left\{ 1, 1, 2, 2, 2, 4\right\} and \mathcal{B} = \left\{ 1, 2, 4, 4 \right\} over \mathbb{N} that we considered earlier are an example of two multisets such that \mathcal{A} \neq \mathcal{B}, \mathcal{A}\not\subseteq\mathcal{B}, and \mathcal{B}\not\subseteq\mathcal{A}, despite the fact that they have the same support.

The identification of the sets A and B with the multisets \mathcal{A} = \left(A, f\right) and \mathcal{B} = \left(B, g\right) where f, g: x\mapsto 1 does indeed work correctly with these definitions, as we wanted. In both definitions, condition (ii) is automatically satisfied since f(x) = 1 = g(x) for all x\in \mathrm{support}\left(\mathcal{A}\right), and so our identification of these sets and multisets preserves both equality and containment.

Copyright © 2008 Michael L. McCliment.


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s

%d bloggers like this: