Eric Forgy Multiset

Warning: This page represents personal notes and likely contains errors. Feedback is welcome.

See An Overview of the Applications of Multisets

A nice way to denote a multiset is

where $X$ is a set and $\mu_X:X\to Card$ is a multiplicity function.

What is the “best” way to both define multisets and to denote multisets?

One thing I would like to do is allow $\mu_X = 0$ on some elements of $X$, but as Toby pointed out, this leads to thinks like

and

denoting “different” multisets, but we’d like to think of these as describing the “same” multiset $\{1,1,2\}$.

How can we settle this?

One way is to specify a universal set $U$ and then a multiset is just a function $\mathcal{X}:U\to Card$.

Then we’d have

• $|\mathcal{X}| = \sum_{e\in U} \mathcal{X}(e)$
• $\mathcal{X}\cap\mathcal{Y} = \min(\mathcal{X},\mathcal{Y})$
• $\mathcal{X}\cup\mathcal{Y} = \max(\mathcal{X},\mathcal{Y})$
• $\mathcal{X}\backslash\mathcal{Y} = \max(0,\mathcal{X}-\mathcal{Y})$
• $(\mathcal{X}+\mathcal{Y})(e) = \mathcal{X}(e)+\mathcal{Y}(e)$
• $(\mathcal{X}\mathcal{Y})(e) = \mathcal{X}(e)\mathcal{Y}(e)$
• $\langle \mathcal{X},\mathcal{Y}\rangle = \sum_{e\in U} \mathcal{X}(e)\mathcal{Y}(e)$

In this way, it is easy to verify that

and

This is “ok”, but I’m not excited about it because we lose the feeling that we’re working with “sets”.

Is there another way?

We can define a multiset $\mathcal{X}$ via a surjection $F_X:\mathcal{X}\to X$ with multiplicity function $\mu_X$ given by the cardinality of the fiber, i.e.

Then we’d have

and $\mathcal{X}\cap\mathcal{Y}$ is the multiset with underlying set $X\cap Y$ and multiplicity given by (not sure if this is right)

snip

Oh! Free Abelian monoids

A multiset is a free Abelian monoid on Set.

---

Oh! Hassler Whitney (one of my all-time favorite mathematicians) has thought about multisets!

• Characteristic Functions and the Algebra of Logic, Annals of Mathematics, Vol 34 (1933), 405-414.