# operations on multisets

Definition. Let $f:A\to K$ and $g:B\to K$ be multisets.

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 $f-g$, is the multiset whose domain is $D:=(A-B)\cup C$, such that

 $(f-g)(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\}$

• $f-g=\{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. 1.

$A$ is a subset of $B$, and

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

Title operations on multisets OperationsOnMultisets 2013-03-22 19:13:23 2013-03-22 19:13:23 CWoo (3771) CWoo (3771) 9 CWoo (3771) Definition msc 03E99 multisubset