You are here
Homeoperations on multisets
Primary tabs
operations on multisets
In this entry, we view multisets as functions whose ranges are the class $K$ of cardinal numbers. We define operations on multisets that mirror the operations on sets.
Definition. Let $f:A\to K$ and $g:B\to K$ be multisets.

The intersection of $f$ and $g$, denoted by $f\cap g$, is the multiset, whose domain is $A\cap B$, such that
$(f\cap g)(x):=\min(f(x),g(x)).$ 
The sum (or disjoint union) of $f$ and $g$, denoted by $f+g$, is the multiset whose domain is $A\cup B$ (not the disjoint union of $A$ and $B$), such that
$(f+g)(x):=f(x)+g(x),$ again keeping in mind that $f(x):=0$ if $x$ is not in the domain of $f$.
Clearly, all of the operations described so far are commutative. Furthermore, if $+$ is cancellable on both sides: $f+g=f+h$ implies $g=h$, and $g+f=h+f$ implies $g=h$.
Subtraction on multisets can also be defined. Suppose $f:A\to K$ and $g:B\to K$ are multisets. Let $C$ be the set $\{x\in A\cap B\mid f(x)>g(x)\}$. Then

the complement of $g$ in $f$, denoted by $fg$, is the multiset whose domain is $D:=(AB)\cup C$, such that
$(fg)(x):=f(x)g(x)$ for all $x\in D$.
For example, writing finite multisets (those with finite domains and finite multiplicities for all elements) in their usual notations, if $f=\{a,a,b,b,b,c,d,d\}$ and $g=\{b,b,c,c,c,d,d,e\}$, then

$f\cup g=\{a,a,b,b,b,c,c,c,d,d,e\}$

$f\cap g=\{b,b,c,d,d\}$

$f+g=\{a,a,b,b,b,b,b,c,c,c,c,d,d,d,d,e\}$

$fg=\{a,a,b\}$
We may characterize the union and intersection operations in terms of multisubsets.
Definition. A multiset $f:A\to K$ is a multisubset of a multiset $g:B\to K$ if
1. $A$ is a subset of $B$, and
2. $f(a)\leq g(a)$ for all $a\in A$.
We write $f\subseteq g$ to mean that $f$ is a multisubset of $g$.
Proposition 1.
Given multisets $f$ and $g$.

$f\cup g$ is the smallest multiset such that $f$ and $g$ are multisubsets of it. In other words, if $f\subseteq h$ and $g\subseteq h$, then $f\cup g\subseteq h$.

$f\cap g$ is the largest multiset that is a multisubset of $f$ and $g$. In other words, if $h\subseteq f$ and $h\subseteq g$, then $h\subseteq f\cap g$.
Remark. One may also define the powerset of a multiset $f$: the multiset such that each of its elements is a multisubset of $f$. However, the resulting multiset is just a set (the multiplicity of each element is $1$).
Mathematics Subject Classification
03E99 no label found Forums
 Planetary Bugs
 HS/Secondary
 University/Tertiary
 Graduate/Advanced
 Industry/Practice
 Research Topics
 LaTeX help
 Math Comptetitions
 Math History
 Math Humor
 PlanetMath Comments
 PlanetMath System Updates and News
 PlanetMath help
 PlanetMath.ORG
 Strategic Communications Development
 The Math Pub
 Testing messages (ignore)
 Other useful stuff
 Corrections