set-theoretic difference of multisets

Question

What is the result of $A \backslash B$ , if $A$ and $B$ are multisets?

For instance, if $A = \{1,1,3\}$ and $B = \{1,2\}$, would the result of $A \backslash B$ be $\{1,3\}$ or $\{3\}$?

Answer 1

That's a good question and I'm not sure that there is a universally agreed upon definition of set theoretic difference for multisets. In the theoretical computer courses that I took, we used the following formalization of multisets:

A multiset $X$ is a function $$ X \colon \mathrm{dom}(X) \to \mathbb N^+. $$ $x$ is an element of $X$ iff $x \in \mathrm{dom}(X)$. $X(x)$ is the multiplicity of $x$ in the multiset $X$.

Note that a multiset is uniquely determined by its elements and their multiplicity.

Given two multisets $X,Y$ we can define a multiset $$ X \cap Y \colon \mathrm{dom}(X) \cap \mathrm{dom}(Y) \to \mathbb N^+, z \mapsto \min\{X(z),Y(z) \} $$ and likewise $$ X \cup Y \colon \mathrm{dom}(X) \cup \mathrm{dom}(Y) \to \mathbb N^+, z \mapsto X(z) + Y(z), $$ where we let $X(z) := 0$ for $z \not \in \mathrm{dom}(X)$ and likewise for $Y$.

We also define $$ X \setminus Y \colon \{ x \in \mathrm{dom}(X) \mid x \not \in \mathrm{dom}(Y) \vee (x \in \mathrm{dom}(Y) \wedge X(x) > Y(x) \} \to \mathbb N, z \mapsto X(z)- Y(z). $$

We may write (at least finite) multisets in the fashion that you did. And doing so this definition would yield that $$ \{1,1,3\} \setminus \{1,2\} = \{1,3 \} \text{ and } \{1,1,3\} \setminus \{1,1,2 \} = \{3\}. $$

Answer 2

Let K = A - B. Then A = K $\cup (A\cap B).$
Thus for multisets, you want a K with
A = K multiunion (A multiintersection B).
For A = {1,1,3}, B = {1,2}, A multiintersection B = {1}.
So K = {1,1,3} since {1,1,3} multiunion {1} = {1,1,3}.

More intuitive would be to look for a K with
A = K sum (A multiintersection B). That would be
K = {1,3} since {1,3} sum {1} = {1,1,3}.

See Wikipedia for definitions.