Multisets

This article needs more work.

Please help by expanding it!

A multiset (some authors use bag or mset) is a generalization of the notion of set. In a multiset, the members (elements) are allowed to appear more than once (i.e. the [finite] multiplicity is any positive integer), whereas in a set the members can appear only once. (Both are unordered collections.) Some authors allow infinite multiplicities.

For example, the multiset  

{a, a, a, a, a, b, b, b, c, d, d}

, which may be written in compact form as the map  

{a: 5, b: 3, c: 1, d: 2}

, where for each distinct member we specify the multiplicity. (An alternative notation is  

{a^5, b^3, c^1, d^2}

.) A common application for the multiset is the prime factors dividing a number. For example, the multiset of prime factors of  

522720

is  

{2, 2, 2, 2, 2, 3, 3, 3, 5, 11, 11}

, which may be written in compact form as the map  

{2: 5, 3: 3, 5: 1, 11: 2}

, where for each distinct member we specify the multiplicity. (An alternative notation is  

{2^5, 3^3, 5^1, 11^2}

.)

Support set

The root set (or support set) of a multiset is the set of its distinct elements. The dimension of a multiset is the cardinality of the support set.

Multiplicity

An element  

m

of a multiset  

M

has multiplicity  

n

if and only if

$m{\in }^{n}M,m{\in ̸}^{n+1}M,$

where  

∈ n

means "is contained at least  

n

times," where  

n

is a nonnegative integer. (Trivially,  

∈ 0

is always true.)

Multiplicity function

The multiplicity of an element  

m

, denoted  

ν (m)

, is a cardinal number; most authors require a positive integer, though some are more general. The multiplicity is positive if  

m

is contained at least once in the multiset  

M

, and zero otherwise. The multiplicity function of a multiset is a generalization of the characteristic function of a set. The height of a multiset is the greatest multiplicity.

Cardinality

The cardinality of a multiset is a cardinal number. The cardinality  

#M

of a multiset  

M

is the number of elements (with multiplicity) that it contains, and is thus the sum of the multiplicities of its members, i.e.

$\mathrm{\#}M:=\sum _{m\in M}\nu (m),$

where  

ν (m)

is the multiplicity of  

m

.

Submultisets

A submultiset is a generalization of the notion of subset. To obtain a submultiset of a multiset  

M

, for each member  

m ∈ M

we may choose a multiplicity in the range  

[0, νM  (m)]

.

Powerset of a multiset

The powerset of a multiset

℘ (M  )

is defined as the set of all submultisets of

M

. For example, the set (with cardinality  

3  ×  2  ×  2 = 12

) of submultisets of  

{a  ^2, b  ^1, c  ^1}

are (in lexicographic order)

{{ }, {a  ^1}, {a  ^2}, {a  ^2, b  ^1}, {a  ^2, b  ^1, c  ^1}, {a  ^2, c  ^1}, {a  ^1, b  ^1}, {a  ^1, b  ^1, c  ^1}, {a  ^1, c  ^1}, {b  ^1}, {b  ^1, c  ^1}, {c  ^1}}.

The cardinality of the powerset of a multiset

℘ (M  )

is

#℘ (M  )  =    m∈M ∏   m∈M    (ν (m) + 1),

where

ν (m)

is the multiplicity of

m

.

Multiset partitions

(...)

Multiset operations

Multiset sum

The multiset sum  

M ⊎ N

of two multisets  

M

and  

N

is defined as the multiset for which each member  

m

have the sum of the multiplicities it has in both multisets

${\nu }_{M\uplus N}(m):={\nu }_M(m)+{\nu }_N(m).$

Generalized set operations

The following multiset operations generalize set operations.

Multiset containment is a Boolean operation, denoted  

m ∈ M

, which evaluates to true if and only if  

νM  (m) > 0

. Multiset inclusion is a Boolean operation, denoted  

M ⊆ N

, which evaluates to true if and only if  

νM  (m)   ≤   νN  (m)

. Strict multiset inclusion is a Boolean operation, denoted  

M ⊂ N

, which evaluates to true if and only if  

νM  (m) < νN  (m)

. The multiset union  

M ⋃ N

of two multisets  

M

and  

N

is defined as the multiset for which each member  

m

have the maximal multiplicity it has in either multisets

${\nu }_{M\cup N}(m):=\max ({\nu }_M(m),{\nu }_N(m)).$

The multiset intersection  

M ⋂ N

of two multisets  

M

and  

N

is defined as the multiset for which each member  

m

have the minimal multiplicity it has in either multisets. Example:  

gcd (M, N)

.

${\nu }_{M\cap N}(m):=\min ({\nu }_M(m),{\nu }_N(m)).$

The multiset difference  

M ＼ N

of two multisets  

M

and  

N

is defined as the multiset for which each member  

m

have multiplicity. Example:  

M / gcd (M, N)

.

${\nu }_{M\setminus N}(m):=\{\begin{array}{ll}{\nu }_M(m)-{\nu }_N(m)& \text{if }{\nu }_M(m)\ge {\nu }_N(m),\\ 0& \text{otherwise}.\end{array}$

The multiset symmetric difference  

M Δ N   :=   (M ＼ N) ⋃ (N ＼ M) = (M ⋃ N) ＼ (M ⋂ N)

of two multisets  

M

and  

N

is defined as the multiset for which each member  

m

have multiplicity. Example:  

max(M / gcd(M, N), N / gcd(M, N)) = lcm(M, N) / gcd(M, N)

.

${\nu }_{M\mathrm{\Delta }N}(m):=\max ({\nu }_M(m),{\nu }_N(m))-\min ({\nu }_M(m),{\nu }_N(m)).$

Generalizations of multisets

Signed multisets

A signed multiset is a generalization of the notion of multiset. In a signed multiset, the members (elements) may have any integer as signed multiplicity, whereas in a multiset the members may only have nonnegative integers as multiplicity.

An example is the signed multiset of prime factors of rational numbers (in reduced form), e.g. for  

522720 9947

we get  

{2: 5, 3: 3, 5: 1, 7: −3, 11: 2, 29: −1}

, where for each distinct member we specify the signed multiplicity. (An alternative notation is  

{2^5, 3^3, 5^1, 7^(−3), 11^2, 29^(−1)}

.)

Weighted sets

Weighted sets might be a further generalization of multisets where the multiplicity would be any real number.

Equivalence with maps

As stated in the introduction, a multiset can be seen a map from some domain  

D

(containing the support) to the nonnegative integers  

ℕ

, this map being the same as the multiplicity function. The above generalizations of signed or weighted multisets then simply consist in allowing signed integers ( 

ℤ

) or real numbers ( 

ℝ

) as values of the map which defines the multiset.

See also

• Sequence (ordered collection of elements, not necessary distinct)

External links

• http://math.stackexchange.com/questions/152223/why-does-mathematical-convention-deal-so-ineptly-with-multisets