Partial orders for Counter data structures

A counter data structure provides an abstract data type for a multiset. A multiset is much like a classic set, but augmented to track the multiplicity of each of its member elements. For example, $[1, 1, 1, 2, 3]$ is a multiset consisting of $1$ repeated thrice, and each of $2$ and $3$ once. If you define $A$ and $B$ to be multisets in a universe of objects $U$, and $m_A, m_B$ their respective multiplicity functions from $U\to \mathbb{N}$, you can define multiset inclusion as $$ A \subseteq B \iff \forall x \in U, \ m_A(x) \le m_B(x) $$The inclusion relation lets us define a partial order on multisets. Note that it is not a total order since it is not the case that any two multisets are comparable. For example, take $A=[1, 1, 2]$ and $B=[1, 2, 2]$. We have $m_A(1) = 2 > 1 = m_B(1)$ but $m_A(2) = 1 < 2 = m_B(2)$. Thus, neither multiset contains the other, and they are incomparable. You can define other arithmetic-like relations by delegating to their multiplicity functions in a similar…