A basic multiset identity says:

$$A+B = (A \cap B) + (A \cup B)$$

Allowing ourselves to use negative multiplicities and rearranging:

$$A-(A \cap B) = (A \cup B)-B$$

But since $A \supseteq (A \cap B),$ hence the LHS denotes a genuine (non-negative) multiset. Equivalently, since $(A \cup B) \supseteq B$, hence the RHS denotes a multiset. Of course, they're equal, so we've really just verified the same thing twice!

Anyway define that $A \mathop{-\!-} B$ equals $A - (A \cap B)$, or else $(A \cup B)-B$ if you prefer.

Question. Has anyone ever suggested a name or notation for the operation $\mathop{-\!-}$ on multisets?

This shows up naturally in the following way. Suppose we're living in a circle of $n$ beads. We begin taking steps of size $m$. How many steps must we take before we return to the starting point? Easy! Write $[n]$ for the multiset of prime factors of $n$ and $[m]$ for the multiset of prime factors of $n$. Write $\Pi(M)$ for the product of the elements of any multiset $M$ whose elements are numbers. Then the number of steps before we return to our starting point is $$\Pi([n]\mathop{-\!-}\,[m]).$$

(I haven't proved this, so its potentially completely wrong...)

  • $\begingroup$ Isn't $A \setminus B$ what you're looking for? $\endgroup$ – Lord_Farin Aug 20 '15 at 18:57
  • $\begingroup$ @Lord_Farin, yep! Feel free to put that as an answer. $\endgroup$ – goblin Aug 20 '15 at 18:59

In naive set theory, we usually have the operation $$A \setminus B := \{x: x \in A, x \notin B\}$$ For ordinary sets, we have: $$A \setminus B = A - (A \cap B) = (A \cup B) - B$$ although usually the latter two are also written using $\setminus$.

Therefore, it would seem reasonable to retain this definition for multisets. Indeed, this definition also preserves the identities with $\setminus$ for multisets: $$A \setminus B = A \setminus (A \cap B) = (A \cup B) \setminus B$$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.