multiset

A multiset is a set for which repeated elements are considered.

Note that the standard definition of a set also allows repeated elements, but these are not treated as repeated elements. For example, $\{1,1,3\}$ as a set is actually equal to $\{1,3\}$ . However, as a multiset, $\{1,1,3\}$ is not simplifiable further.

A definition that makes clear the distinction between set and multiset follows:

Multiset.

A multiset is a pair $(X,f)$ , where $X$ is a set, and $f$ is a function mapping $X$ to the cardinal numbers greater than zero. $X$ is called the underlying set of the multiset, and for any $x\in X$ , $f(x)$ is the multiplicity of $x$ .

Using this definition and expressing $f$ as a set of ordered pairs, we see that the multiset $\{1,3\}$ has $X=\{1,3\}$ and $f=\{(1,1),(3,1)\}$ . By contrast, the multiset $\{1,1,3\}$ has $X=\{1,3\}$ and $f=\{(1,2),(3,1)\}$ .

Generally, a multiplicity of zero is not allowed, but a few mathematicians do allow for it, such as Bogart and Stanley. It is far more common to disallow infinite multiplicity, which greatly complicates the definition of operations such as unions, intersections, complements, etc.

References

1 Kenneth P. Bogart, Introductory Combinatorics. Florence, Kentucky: Cengage Learning (2000): 93
2 John L. Hickman, “A note on the concept of multiset” Bulletin of the Australian Mathematical Society 22 (1980): 211 - 217
3 Richard P. Stanley, Enumerative Combinatorics Vol 1. Cambridge: Cambridge University Press (1997): 15

Title	multiset
Canonical name	Multiset
Date of creation	2013-03-22 12:21:44
Last modified on	2013-03-22 12:21:44
Owner	PrimeFan (13766)
Last modified by	PrimeFan (13766)
Numerical id	13
Author	PrimeFan (13766)
Entry type	Definition
Classification	msc 03E99
Synonym	bag
Related topic	AxiomsOfMetacategoriesAndSupercategories
Related topic	ETAS
Defines	multiplicity