Can a multiset be a subset of a set?

Question

This is a bit of a silly question but its bothering me.

Given a multiset say $p=\{a,a,g,h,h\}$ And another set $t=\{a,g,h\}$ Can I say that $p\subset t$.

In other words is p a subset of t?.

Answer 1

The problem is that there are several different, more or less equivalent, ways to present a multiset. Here are two of them.

• A multiset is a pair $(X, \sim)$, with $X$ a set and $\sim$ an equivalence relation on $X$. In your case, one can make $p=(P, \sim_{p})$, with $$P=\{a, a^{*}, g, h, h^{*}\},$$ and $a\sim_{p} a^{*}$ and $h\sim_{p} h^{*}$ (meaning, in a way, that $a$ and $a^{*}$, and $h$ and $h^{*}$, are the same elements, $a$ and $h$ respectively). In that case, a set is a multiset where $\sim$ is the identity, and we say, for two multisets $m_{1}=(X_{1}, \sim_{1})$ and $m_{2}=(x_{2}, \sim_{2})$, that $m_{1}$ is contained in $m_{2}$ if $$X_{1}\subseteq X_{2}\quad\text{and}\quad \forall x_{1}, x_{2}\in X_{1} (x_{1}\sim_{1}x_{2}\Rightarrow x_{1}\sim_{2}x_{2})$$ (you could, instead of $X_{1}\subseteq X_{2}$, use that there is an injective function, but that would probably be considered more general). Then it is clear that, under this definition, $p$ is not a submultiset of $t=(T, \sim_{t})$, for $T=\{a, g, h\}$ and $\sim_{t}$ the identity on $T$; BUT, $t$ is a submultiset of $p$, and $T$ is a subset of $P$.

• A multiset is a pair $(X, m)$, with $X$ a set and $m$ a function mapping elements of $X$ to cardinals. That way, we can take $p=(P, m_{p})$, with $P=\{a, g, h\}$, and $m_{p}(a)=2$, $m_{p}(g)=1$ and $m_{p}(h)=2$ (meaning $a$ and $h$ appear twice in $p$, while $g$ appears once). We say $(X_{1}, m_{1})$ is a submultiset of $(X_{2}, m_{2})$ if $$X_{1}\subseteq X_{2}\quad\text{and}\quad \forall x\in X_{1}(m_{1}(x)\leq m_{2}(x)).$$ If we define $t$ as $(T, m_{t})$, for $T=\{a, g, h\}$ and $m_{t}(a)=m_{t}(g)=m_{t}(h)=1$ (a set is, with this definition, a multiset whose multiplicity function is always $1$), then we have $t$ is still a submultiset of $p$; but, and perhaps this definition is better regarding this intuitive aspect, $P$ and $T$ are EQUAL.

So, to summarize, you can not usually say $p$ is a submultiset of $t$; however, if you consider the underlying set of $p$ (the $P$ in my second definition), it indeed equals $t$.