multiset
Primary tabs
multiset
Note that the standard definition of a set also allows repeated elements, but these are not treated as repeated elements. For example, as a set is actually equal to . However, as a multiset, is not simplifiable further.
A definition that makes clear the distinction between set and multiset follows:
Multiset.
A multiset is a pair , where is a set, and is a function mapping to the cardinal numbers greater than zero. is called the underlying set of the multiset, and for any , is the multiplicity of .
Using this definition and expressing as a set of ordered pairs, we see that the multiset has and . By contrast, the multiset has and .
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
Mathematics Subject Classification
03E99 None of the above, but in MSC2010 section 03Exx
Comments
some suggestions
Hi, I've some suggestions to improve the multiset definiton.
1) Multiset is also known as bag
2) in the formal definition represent f:X\to{1,2,3,...} - avoid the use of "function mapping"
3) in the formal definition say, "A multiset M is a pair..." and conclude saying "f(x) if the multiplicity of x in M"
4) stress two possible way of representing a multiset, as sequence of (element,multiplicity) pairs or as collection of objects, each repeated with its multiplicity {...}
Re: some suggestions
An observaton on suggestion 2:
The problem with changing the formal definition would be that f:X\to{1,2,3,...} is not the same thing as f being a cardinal-valued mapping. A mapping to the cardinal numbers (or even to the nonzero cardinals) is more general in that it allows for "infinite" multiplicities (\aleph_0, \aleph_1, etc.) that are not permitted in the mapping to the positive integers.
A question regarding suggestion 4:
I'm a bit confused by this, since I don't think every multiset can actually be represented as a *sequence* of (element, multiplicity) pairs. For example, if M = (R+, f) where R+ are the positive real numbers and f(x) = ceil(x), this should be a valid multiset, but cannot be represented as a sequence. As far as I am aware, either of these representations only works for finite multisets. Am I missing something?