submultiset

A submultiset is a relation between multisets over a common base set. If U is the base set and A and B are multisets on U, then A is a submultiset of B if, for every element u in U, the multiplicity of u in A is less than or equal to its multiplicity in B. In other words, A ⊆ B in the multiset sense.

This relation is a partial order on the set of multisets over U: it is reflexive (every multiset is a submultiset of itself), antisymmetric (if A ⊆ B and B ⊆ A then A and B have identical multiplicities for all elements), and transitive (if A ⊆ B and B ⊆ C then A ⊆ C). A submultiset is proper when at least one element has strictly smaller multiplicity in A than in B. The empty multiset is a submultiset of any multiset, and every multiset is a submultiset of itself.

Example: Let N = {a, a, b, c} (multiplicities a:2, b:1, c:1). The multiset A = {a, b} (a:1, b:1) is a submultiset of N. The multiset A′ = {a, a, a} is not, since N has only two a’s.

Submultiset relationships are preserved under addition: if A ⊆ B, then A + C ⊆ B + C for any multiset C. Multiset operations such as union and intersection are defined by combining multiplicities (for example, intersection uses the minimum multiplicity, union the maximum, depending on conventions). Submultisets arise in counting problems, combinatorics, and distribution analyses where items may repeat.