operations on multisets


In this entry, we view multisets as functions whose ranges are the class K of cardinal numbersMathworldPlanetmath. We define operations on multisets that mirror the operationsMathworldPlanetmath on sets.

Definition. Let f:AK and g:BK be multisets.

  • The union of f and g, denoted by fg, is the multiset whose domain is AB, such that

    (fg)(x):=max(f(x),g(x)),

    keeping in mind that f(x):=0 if x is not in the domain of f.

  • The intersectionMathworldPlanetmath of f and g, denoted by fg, is the multiset, whose domain is AB, such that

    (fg)(x):=min(f(x),g(x)).
  • The sum (or disjoint unionMathworldPlanetmath) of f and g, denoted by f+g, is the multiset whose domain is AB (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 commutativePlanetmathPlanetmathPlanetmath. 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:AK and g:BK are multisets. Let C be the set {xABf(x)>g(x)}. Then

  • the complement of g in f, denoted by f-g, is the multiset whose domain is D:=(A-B)C, such that

    (f-g)(x):=f(x)-g(x)

    for all xD.

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

  • fg={a,a,b,b,b,c,c,c,d,d,e}

  • fg={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:AK is a multisubset of a multiset g:BK if

  1. 1.

    A is a subset of B, and

  2. 2.

    f(a)g(a) for all aA.

We write fg to mean that f is a multisubset of g.

Proposition 1.

Given multisets f and g.

  • fg is the smallest multiset such that f and g are multisubsets of it. In other words, if fh and gh, then fgh.

  • fg is the largest multiset that is a multisubset of f and g. In other words, if hf and hg, then hfg.

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