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

𝒳=⟨X,ΞΌ X⟩,\mathcal{X} = \langle X,\mu_X\rangle,

where XX is a set and μ X:X→Card\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 ΞΌ X=0\mu_X = 0 on some elements of XX, but as Toby pointed out, this leads to thinks like

⟨{1,2,3},μ 1=2,μ 2=1,μ 3=0⟩\langle \{1,2,3\} , \mu_1 = 2, \mu_2 = 1, \mu_3 = 0\rangle

and

⟨{1,2},μ 1=2,μ 2=1⟩\langle \{1,2\} , \mu_1 = 2, \mu_2 = 1\rangle

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

How can we settle this?

One way is to specify a universal set UU and then a multiset is just a function 𝒳:Uβ†’Card\mathcal{X}:U\to Card.

Then we’d have

In this way, it is easy to verify that

𝒳+𝒴=𝒳\𝒴+𝒴\𝒳+2π’³βˆ©π’΄\mathcal{X}+\mathcal{Y} = \mathcal{X}\backslash\mathcal{Y} + \mathcal{Y}\backslash\mathcal{X} + 2\mathcal{X}\cap\mathcal{Y}

and

2𝒳βˆͺ𝒴=𝒳+𝒴+𝒳\𝒴+𝒴\𝒳.2\mathcal{X}\cup\mathcal{Y} = \mathcal{X}+\mathcal{Y} + \mathcal{X}\backslash\mathcal{Y} + \mathcal{Y}\backslash\mathcal{X}.

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:𝒳→XF_X:\mathcal{X}\to X with multiplicity function ΞΌ X\mu_X given by the cardinality of the fiber, i.e.

ΞΌ X(e)=|F X βˆ’1(e)|\mu_X(e) = |F_X^{-1}(e)|

Then we’d have

|𝒳|=βˆ‘ e∈XΞΌ X(e)|\mathcal{X}| = \sum_{e\in X} \mu_X(e)

and π’³βˆ©π’΄\mathcal{X}\cap\mathcal{Y} is the multiset with underlying set X∩YX\cap Y and multiplicity given by (not sure if this is right)

ΞΌ X∩Y(e)=|F X βˆ’1(e)∩F Y βˆ’1(e)|.\mu_{X\cap Y}(e) = |F_X^{-1}(e)\cap F_Y^{-1}(e)|.

snip

F X∩Y=π’³βˆ©π’΄β†’X∩YF_{X\cap Y} = \mathcal{X}\cap\mathcal{Y}\to X\cap Y

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!

category: notes
Revised on October 30, 2009 at 21:53:51 by Eric Forgy