Concept
Multiset
Overview
In mathematics, a multiset (or bag, or mset) is a modification of the concept of a set that, unlike a set, allows for multiple instances for each of its elements. The number of instances given for each element is called the multiplicity of that element in the multiset. As a consequence, an infinite number of multisets exist that contain only elements a and b, but vary in the multiplicities of their elements:
The set {a, b} contains only elements a and b, each having multiplicity 1 when {a, b} is seen as a multiset.
In the multiset {a, a, b}, the element a has multiplicity 2, and b has multiplicity 1.
In the multiset {a, a, a, b, b, b}, a and b both have multiplicity 3.
These objects are all different when viewed as multisets, although they are the same set, since they all consist of the same elements. As with sets, and in contrast to tuples, the order in which elements are listed does not matter in discriminating multisets, so {a, a, b} and {a, b, a} denote the same multiset. To distinguish between sets and multisets, a notation that incorporates square brackets is sometimes used: the multiset {a, a, b} can be denoted by [a, a, b].
The cardinality or "size" of a multiset is the sum of the multiplicities of all its elements. For example, in the multiset {a, a, b, b, b, c} the multiplicities of the members a, b, and c are respectively 2, 3, and 1, and therefore the cardinality of this multiset is 6.
Nicolaas Govert de Bruijn coined the word multiset in the 1970s, according to Donald Knuth. However, the concept of multisets predates the coinage of the word multiset by many centuries. Knuth himself attributes the first study of multisets to the Indian mathematician Bhāskarāchārya, who described permutations of multisets around 1150. Other names have been proposed or used for this concept, including list, bunch, bag, heap, sample, weighted set, collection, and suite.
Overview adapted from Wikipedia (CC BY-SA 4.0; see the article history for authors).
Possible passages
Found by search and not yet checked by a person; they may only mention the idea in passing.
Thus there arises a classification of modes of formation, or in the language commonly used by mathematicians, a classification of Functions. Any number, considered as formed from any other number, is called a function of it; and there are as many kinds of functions as there are modes of formation. The simple functions are by no means numerous, most functions being formed by the combination of several of the…
John Stuart Mill, A System of Logic, Ratiocinative and Inductive
States what Multiset is.
Any such select set is called the set of postulates, or premises, from which the reasoning proceeds. The reasoning is nothing else than the exhibition of the whole pattern of general conditions involved in the pattern derived from the selected postulates.
Alfred North Whitehead, Science and the modern world
States what Multiset is.
And reciprocally: Two sets of four straight lines are defined as having the same anharmonic ratio when (1) each set of four passes through a single point, and (2) corresponding lines of different sets pass, two by two, through four points in one straight line, or when both sets have this relation to any third set. Two sets of points or of lines, which have the same anharmonic ratio, are treated by projective…
Bertrand Russell, An essay on the foundations of geometry
States what Multiset is.
Related ideas
- Artificial intelligence
- Finite set
- Tuple
- Integer
- Function (mathematics)
- Mathematics
- Rational number
- Real number
- Natural number
- Ordered pair
- Richard Dedekind
- Set (mathematics)
- Subset
- Morphism
- Combinatorics
- Complex number
- Cardinality
- Mathematical proof
- Equivalence relation
- Athanasius Kircher
- Empty set
Place in the tradition
Part of Outline of logic.