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?.

  • $\begingroup$ @KarthikKannan $p$ is a multiset. $\endgroup$ – Umberto P. Jan 22 at 11:51
  • $\begingroup$ @karthik kannan yes but in the sense that p is just a collection of objects is it a subset or can we not relate multisets to sets? $\endgroup$ – The homeschooler Jan 22 at 11:52
  • $\begingroup$ @UmbertoP. I apologize for not noticing that. I shall delete that comment. $\endgroup$ – Karthik Kannan Jan 22 at 11:53
  • $\begingroup$ $p$ is not a submultiset of the (multi)set $t$ as some eleemnts occur too often. One might say that the underlying set of the multiset $p$ is a subset of the set $t$, perhaps? $\endgroup$ – Hagen von Eitzen Jan 22 at 12:09
  • $\begingroup$ @Hagen von Eitzen is p not a subset of t then? $\endgroup$ – The homeschooler Jan 22 at 12:28

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$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.