1 Basic definitions

1.1 Multisets and multiplicity functions

A multiset extends the idea of a set by allowing repeated elements. Formally, one can model a multiset over a universe \(U\) by a multiplicity function \(m:U\to \mathbb{N}\cup\{0\}\), where \(m(x)\) records how many copies of element \(x\) are present.

Two multisets are considered equal exactly when their multiplicity functions agree at every element of the universe.

1.2 Containment relation: intuitive meaning

Given multisets \(A\) and \(B\) on the same universe, containment expresses that \(B\) has “at least enough copies” of each element to cover what \(A\) requires. Intuitively, \(A\) is contained in \(B\) if no element appears more times in \(A\) than it appears in \(B\). This is a direct analogue of subset inclusion, but with multiplicities replacing the yes/no membership test.

1.3 Notation and terminology

Common notation includes:

  • \(A \subseteq B\) for set inclusion when thinking in the multiset context, though multiset-specific symbols are often preferred to avoid confusion.
  • \(A \preceq B\) or \(A \subseteq_m B\) for multiset containment.
  • Multiplicity functions are sometimes written as \(\mu_A(x)\) and \(\mu_B(x)\), or simply \(m_A(x)\), \(m_B(x)\).

The core terminology is that containment holds when one multiset’s multiplicity counts do not exceed the other’s.

2 Formal characterization

2.1 Containment via element-wise inequalities

Let \(A\) and \(B\) be multisets with multiplicity functions \(m_A, m_B:U\to \mathbb{N}\cup\{0\}\). Define \(A\) to be contained in \(B\), written \(A\preceq B\), when \[ m_A(x)\le m_B(x)\quad \text{for all }x\in U. \]

2.1.1 Multiplicity comparison for each element

The inequality is evaluated independently for each element. If an element \(x\) is absent from \(A\) (so \(m_A(x)=0\)), the condition is automatically satisfied for that element. If \(x\) appears \(k\) times in \(A\), then \(B\) must include at least \(k\) copies of \(x\) for containment to hold.

2.1.2 Equivalent formulations using count functions

If a multiset is specified by a count function \(c_A(x)\) (also mapping elements to their multiplicities), the same criterion becomes \[ c_A(x)\le c_B(x)\quad \forall x\in U. \] In practice, different sources may use “multiplicity,” “count,” or “valuation” as terminology for the function assigning these occurrence numbers; containment is always determined by pointwise comparison.

2.2 Properties of the containment relation

2.2.1 Reflexivity

Every multiset is contained in itself because \(m_A(x)\le m_A(x)\) for each \(x\). Hence \(A\preceq A\).

2.2.2 Transitivity

If \(A\preceq B\) and \(B\preceq C\), then for every \(x\), \[ m_A(x)\le m_B(x)\le m_C(x), \] so \(m_A(x)\le m_C(x)\). Therefore \(A\preceq C\).

2.2.3 Antisymmetry and induced partial order

If \(A\preceq B\) and \(B\preceq A\), then \(m_A(x)\le m_B(x)\) and \(m_B(x)\le m_A(x)\) for all \(x\), yielding \(m_A(x)=m_B(x)\) everywhere. Thus \(A=B\). This makes containment a partial order on the set of multisets over \(U\).

3 Relationship to set inclusion

3.1 Sets as special cases of multisets

A (finite or infinite) set can be embedded into the multiset framework by restricting multiplicities to 0 or 1. For a set \(S\subseteq U\), define \[ m_S(x)= \begin{cases} 1, & x\in S,\\ 0, & x\notin S. \end{cases} \] Under this embedding, multiset containment reduces to ordinary set inclusion.

3.2 How containment generalizes set inclusion

If \(A\) and \(B\) are actually sets (i.e., multiplicities are only 0 or 1), then \(A\preceq B\) means: whenever an element appears in \(A\) (count 1), it must appear in \(B\) as well. That is exactly \(A\subseteq B\). When multiplicities exceed 1, containment becomes strictly richer than set inclusion because it compares quantities, not just presence.

3.3 Examples contrasting set vs multiset behavior

Consider universe \(U=\{a\}\). Let

  • \(A\) contain two copies of \(a\): \(m_A(a)=2\),
  • \(B\) contain one copy of \(a\): \(m_B(a)=1\).

Then containment fails: \(m_A(a)\le m_B(a)\) is false. If one were to collapse multiplicities to binary presence, both multisets would appear to “contain \(a\),” masking the actual difference in frequency.

As another contrast, suppose

  • \(A\) has one copy of \(a\),
  • \(B\) has two copies of \(a\).

Then \(A\preceq B\) holds, even though in set terms both might be indistinguishable if reduced to membership alone.

4.1 Multiset union under containment constraints

A multiset union consistent with the containment order is typically defined using maximum multiplicities. For multisets \(A,B\), \[ m_{A\vee B}(x)=\max\{m_A(x),m_B(x)\}. \] This construction produces a multiset that contains both \(A\) and \(B\) in the containment order.

4.1.1 Max-based union and when it preserves containment

Using the maximum guarantees:

  • \(A\preceq A\vee B\) and \(B\preceq A\vee B\), since \(\max\{m_A(x),m_B(x)\}\ge m_A(x)\) for each \(x\).
  • The operation is monotone: if \(A\preceq A'\) and \(B\preceq B'\), then \(A\vee B\preceq A'\vee B'\).

The role of “containment constraints” is usually about ensuring that auxiliary operations (like subtraction) remain well-defined; the max-based union itself is always containment-consistent.

4.2 Multiset intersection under containment constraints

Intersection aligns with minimum multiplicities: \[ m_{A\wedge B}(x)=\min\{m_A(x),m_B(x)\}. \] This yields a multiset contained in both operands.

4.2.1 Min-based intersection and inclusion effects

For all \(x\),

  • \(m_{A\wedge B}(x)\le m_A(x)\) and \(m_{A\wedge B}(x)\le m_B(x)\),

so \(A\wedge B\preceq A\) and \(A\wedge B\preceq B\). If \(A\preceq B\), then \(\min(m_A,m_B)=m_A\), so \(A\wedge B=A\); similarly, \(A\vee B=B\). These identities reflect how the order controls lattice-like behavior.

4.3 Multiset sum and containment monotonicity

One natural “sum” operation adds multiplicities: \[ m_{A+B}(x)=m_A(x)+m_B(x). \] This operation interacts well with containment because addition is order-preserving in \(\mathbb{N}\cup\{0\}\).

4.3.1 Conditions for sum to respect containment

If \(A\preceq A'\) and \(B\preceq B'\), then for every \(x\), \[ m_A(x)+m_B(x)\le m_{A'}(x)+m_{B'}(x), \] so \(A+B\preceq A'+B'\). Thus the sum operation is monotone in each argument without requiring extra hypotheses.

4.4 Multiset difference and containment

Difference is more subtle because subtraction can produce negative multiplicities. A common definition under nonnegativity is: \[ m_{B\setminus A}(x)=\max\{0,\, m_B(x)-m_A(x)\}. \] Equivalently, \(B\setminus A\) is the multiset of “remaining copies” of each element after removing what \(A\) asks for.

4.4.1 Difference only when containment holds

If \(A\preceq B\), then \(m_B(x)-m_A(x)\ge 0\) for all \(x\), so the max with 0 is unnecessary and the difference simplifies to \(m_{B\setminus A}(x)=m_B(x)-m_A(x)\). If containment does not hold, the definition still yields a nonnegative multiplicity multiset, but it no longer corresponds to a literal removal of all required copies from \(B\); instead it truncates at zero.

5 Lattice and algebraic perspectives

5.1 Infimum/supremum in the containment order

The containment order induces a lattice structure on multisets over a fixed universe \(U\). For any \(A,B\):

  • The supremum (least upper bound) is the max-based union \(A\vee B\).
  • The infimum (greatest lower bound) is the min-based intersection \(A\wedge B\).

On each element \(x\), these correspond to the supremum/infimum in \((\mathbb{N}\cup\{0\},\le)\).

5.2 Meets and joins as intersection and union

In lattice terms, the meet \(\wedge\) corresponds to intersection and the join \(\vee\) corresponds to union in the multiset containment order. The defining properties follow from the order comparisons:

  • \(A\wedge B\preceq A\) and \(A\wedge B\preceq B\), and any multiset \(C\) with \(C\preceq A\) and \(C\preceq B\) must satisfy \(C\preceq A\wedge B\).
  • \(A\preceq A\vee B\) and \(B\preceq A\vee B\), and any multiset \(C\) with \(A\preceq C\) and \(B\preceq C\) must satisfy \(A\vee B\preceq C\).

5.3 Combinatorial consequences of lattice structure

The lattice viewpoint supports systematic reasoning about extremal multisets and common proof strategies in combinatorics. For example:

  • If one multiset is below another, intersections collapse to the smaller object, and unions collapse to the larger.
  • Many inequalities about counts can be reframed as order-theoretic statements about meets and joins.
  • Counting arguments that proceed element-by-element often become algebraic manipulations of infima and suprema in the induced poset.

6 Worked examples and verification

6.1 Small finite-universe examples

Let \(U=\{a,b,c\}\). Suppose

  • \(A: m_A(a)=2, m_A(b)=0, m_A(c)=1\),
  • \(B: m_B(a)=3, m_B(b)=1, m_B(c)=1\).

Then \(A\preceq B\) requires checks:

  • for \(a\): \(2\le 3\) (true),
  • for \(b\): \(0\le 1\) (true),
  • for \(c\): \(1\le 1\) (true).

All inequalities hold, so \(A\preceq B\).

If instead \(B\) had \(m_B(c)=0\), then containment would fail because \(1\le 0\) is false for element \(c\).

6.2 Systematic checking of containment

To verify \(A\preceq B\), proceed element-wise over the (finite) universe:

  1. For each element \(x\), compute \(m_A(x)\) and \(m_B(x)\).
  2. Check the inequality \(m_A(x)\le m_B(x)\).
  3. If any element violates it, containment fails; otherwise it holds.

When multisets are stored sparsely (only listing elements with positive multiplicity), this check is efficient: elements absent from \(A\) contribute zeros, and only elements with positive multiplicity need explicit comparisons.

6.3 Edge cases: empty multiset and zero multiplicities

Let \(\emptyset\) denote the empty multiset with \(m_{\emptyset}(x)=0\) for all \(x\).

  • \(\emptyset\preceq A\) for every multiset \(A\), since \(0\le m_A(x)\) always.
  • \(A\preceq \emptyset\) holds only when \(A\) is also empty (all multiplicities are zero).

Zero multiplicities act like “absence,” but they still fit seamlessly into the order definition: the inequalities remain valid without special casing.

7 Applications in discrete mathematics

7.1 Counting and combinatorial constructions

Containment describes feasibility of distributing required multiplicities. In combinatorial constructions, one often starts with a demand multiset (how many of each type is needed) and checks whether a supply multiset can cover it. The condition “supply contains demand” is exactly multiset containment.

This appears in problems involving multisets of resources, selections with repetition, and constrained counting where the main question is whether multiplicity requirements can be met.

7.2 Proof techniques using multiplicity comparisons

Many proofs reduce to inequalities between multiplicity functions. Because containment is pointwise, arguments often take the form:

  • assume containment \(A\preceq B\),
  • derive inequalities for certain combined constructions using monotonicity of operations like \(\max\), \(\min\), and addition,
  • conclude a new containment relation between derived multisets.

This element-wise structure makes it easier to localize reasoning: global statements follow from checking each element independently.

7.3 Relationships to multisets in algorithm analysis

In algorithmic settings, multisets model inventories, queues with repeated labels, or counts of items. Containment can represent correctness conditions, such as:

  • whether a multiset of outputs can satisfy a multiset of requested counts,
  • whether an intermediate multiset dominates a requirement multiset during a transformation process.

The lattice-like monotonicity of union, intersection, and sum often supports invariant-based proofs.

8 Advanced generalizations

8.1 Containment with infinite multisets (where applicable)

For infinite universes, the same definition works provided multiplicities are well-defined as nonnegative integers (or other allowed values). The order \(A\preceq B\) still means \(m_A(x)\le m_B(x)\) for every \(x\in U\), even if infinitely many elements have positive multiplicity.

In applications, additional constraints are sometimes imposed (e.g., only finitely many nonzero multiplicities) to ensure operations remain manageable, but the conceptual ordering criterion is unchanged.

8.2 Multiset homomorphisms preserving containment

A homomorphism between multiset structures can be defined as a mapping that respects multiplicity composition. When such a map is order-preserving, it takes containment-related inputs to containment-related outputs: if \(A\preceq B\), then \(f(A)\preceq f(B)\). This typically occurs when the transformation is monotone on multiplicities (for instance, scaling counts by a nondecreasing rule or applying a mapping that aggregates counts without violating pointwise inequalities).

8.3 Weighted counts and scaled containment variants

Weighted generalizations replace integer multiplicities with weights from an ordered set, or interpret multiplicities via scaling factors. One variant uses a scaling function \(s:\mathbb{N}\cup\{0\}\to \mathbb{N}\cup\{0\}\) and defines a containment-like condition comparing \(s(m_A(x))\) and \(m_B(x)\). Another approach assigns weights \(w(x)\) to elements and compares weighted totals: \[ \sum_{x\in U} w(x)\,m_A(x)\le \sum_{x\in U} w(x)\,m_B(x), \] though note that such “total-weight containment” is generally weaker than pointwise containment. The most common containment order remains the pointwise inequality because it exactly captures multiplicity-by-multiplicity coverage.