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 union of $f$ and $g$, denoted by $f\cup g$, is the multiset whose domain is $A\cup B$, such that
$$(f\cup g)(x):=\mathrm{max}(f(x),g(x)),$$ keeping in mind that $f(x):=0$ if $x$ is not in the domain of $f$.

•
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):=\mathrm{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)\le 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$).
Title  operations on multisets 

Canonical name  OperationsOnMultisets 
Date of creation  20130322 19:13:23 
Last modified on  20130322 19:13:23 
Owner  CWoo (3771) 
Last modified by  CWoo (3771) 
Numerical id  9 
Author  CWoo (3771) 
Entry type  Definition 
Classification  msc 03E99 
Defines  multisubset 