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):=\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):=\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 $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. $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	2013-03-22 19:13:23
Last modified on	2013-03-22 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