Multisets

A multiset can be viewed as type of set, or even as a proto-set. The only difference between a set and a multiset can be seen when considering multiplicity. In the case of a set multiplicity has no meaning, i.e {a,a}={a}, but in the case of a multiset it does.

A multiset over S is a function f:S→N where f(x) is called the multiplicity, i.e. how many times the element x occurs in the multiset. If f(x)=i then each of the i x elements is called an occurrence. The elements of f are given by D(f) which is defined as

	
D(f) = {s∈S|f(s)≠0}
	
      

The multiset f is called finite if D(f) is finite. The number of elements of a finite multiset is given by

	
|f| = Σx∈D(f)f(x)
	
      

Sometimes multisets are written in a set-like notation as shown below:

	
{{1,1,0,99,99,99}}
	
      

The usual set operations (union, intersection, and difference) can be used:

	
{{1,1,0,99,99,99}} ∪ {{0,3,3}} = {{1,1,0,0,3,3,99,99,99}}
	
      

References

Doets, Kees. From Logic to Logic Programming. MIT Press, 1994.