Talk:Multiset

From Wikipedia, the free encyclopedia

Mathematics Portal

This article is within the scope of WikiProject Mathematics, which collaborates on articles related to mathematics.

Mathematics rating:

Start Class

Mid Priority

Field: Foundations, logic, and set theory

Please update this rating as the article progresses, or if the rating is inaccurate. Click to show/hide comments.
Please add to or update the comments to suggest improvements to the article.
This needs more than one referece. Geometry guy 21:55, 31 May 2007 (UTC)

[edit] Why stop at finite cardinals?

Formally multisets can be defined, within set theory, as partial functions that map elements to positive natural numbers.

Stupid question, but why stop at finite cardinals? Why can't a multiset be defined as a map from a (normal) set into Card? Why can't elements "occur infinitely many times" as members?

Would be a different concept. Charles Matthews 13:36, 4 Apr 2005 (UTC)

The reason I ask is the following: at the article graph, they say a multigraph is a graph where the edge set is a multiset. This doesn't jive with the category way of thinking of a directed multigraph as a precategory, where with a precategory, there is no restriction on the number of morphisms from one object to another, conceivably, there could be infinitely many distinct such morphisms. So, in this case, "multiset" as defined here isn't broad enough a concept to use for defining "multigraph" (or directed multigraph).

Whether elements of a multiset can have infinite multiplicities varies among the sources that discuss multisets. Brualdi (Introductory Combinatorics, 3rd. ed. 1999, p. 51) and Chen & Koh (Principles and Techniques in Combinatorics, 1992, pp. 34-37) explicitly allow infinite repetition. Other authors do not, e.g. Bogart (Introductory Combinatorics, 3rd. ed. 2000, p. 93). -- Cornazano 01:38, 7 October 2007 (UTC)

Blizard's article (Multiset Theory, now listed in the references) indicates that there is an exposition of multisets by J. L. Hickman that defines multisets as cardinal-valued functions in ZFC; I'm trying to get a copy of the article to read.

Disallowing cardinal repetition numbers seems to create a problem in the following case: Let $M_i = \{i\cdot x\}, i\in \mathbb{N}$ (in this notation, i is the multiplicity of x). Now, consider the union $M = \cup_{i\in\mathbb{N}} M_i$ . Normally, the multiplicity of x in M should be the maximum multiplicity associated with x in the sets M_i. However, in this case, the multiplicity of x is unbounded in the sets of which we are taking the union. Blizard (1998, p. 48) generally defines the multiplicity of an element x in a union of multisets to be the maximum multiplicity of x among those multisets, but takes the somewhat bizarre step of defining the multiplicity in the case of to be the minimum multiplicity in order to avoid having to deal with infinite multiplicities. -- Cornazano 02:10, 9 October 2007 (UTC)

On another note, why partial function and not just a function? Surely, 1 is a positive natural number. -- Fropuff 16:23, 2005 May 27 (UTC)

For it to be a function, every element would need to be mapped to a "positive natural number"; in other words, this particular formulation can't support a multiplicity of zero. An equivalent formulation would be ... as functions that map elements to natural numbers. -- Cornazano 01:43, 7 October 2007 (UTC)

[edit] References, size and set constructor notation?

I've been writing a paper which uses the concept of multiset. It fits very well to the problem, that is why.

First, I think I need a reference for the multiset in which all of these defs are given for curious readers. I just remembered that there is not much focus on multisets in computer science, and I am looking for a good reference for that. So, references would be appreciated.

Secondly, can I use $| x |$ to denote the size of multiset $x$ ?

Third, I want to adapt the set constructor notation ${x : P (x)}$ for defining certain multisets. Should I be talking explicitly about the representation $(A, m)$ , e.g. $A = \{ x : x \in Z , 1 < x < 10 \}, m(x)=x^2?$ or are there other ways of defining multisets?

--Exa 23:12, 13 November 2005 (UTC)

First, Multiset#References is all there is. Second, yes, |A| is very much used for the cardinality of a set A, for which this is the generalization. Third, see Family (mathematics)#Notation. Bo Jacoby 13:55, 22 December 2006 (UTC).

[edit] polynomial notation

The article says:

The infinite multiset of finite multisets of elements from the multiset x² is

Why is the infinite multiset of finite multisets of elements from the multiset {x, x} different from the infinite multiset of finite multisets of elements from the multiset {x}? Michael Hardy 23:45, 21 February 2006 (UTC)

Oh -- I see: it said

"the infinite multiset of finite multisets"

and NOT

"the infinite set of finite multisets"

OK, as Emily Litella would say....

Michael Hardy 23:47, 21 February 2006 (UTC)

Thanks for your improvements. I agree that the text is tricky. I will think about how to make it clearer. Bo Jacoby 07:18, 22 February 2006 (UTC)

[edit] Definition where A is fixed and m(x) can equal zero

My supervisor suggested that A should be a fixed universe of elements and m be a function which can take zero values. This mean e.g. that a subset of (A,m) would be (A,n) where n(x) <= m(x) for all x. Is there a reference for the way Wikipedia currently defines multisets? -- Gmatht 01:09, 17 April 2006 (UTC)

As the two definitions lead to the same concept, it doesn't really matter which one to chose. But the concept of an element of a multiset in one definition is element of the set, and in the other definition element of the set with nonzero multiplicity. The latter statement seems more complicated to me, but your supervisor may like it. Also the idea of a fixed universe of elements either limits the definition (because a larger fixed universe extends the definition), or makes matematicians talk unintelligibly about category theory for several minutes. Bo Jacoby 20:02, 17 April 2006 (UTC)

[edit] size, length or cardinality

The article defines "the size or length of the multiset (A, m)". The word "length" is not commonly used in this sense, to the best of my knowledge. The article set uses the word cardinality. Bo Jacoby 10:04, 24 July 2006 (UTC)

[edit] Multiset coefficient wrong in example?

In the example it shows the multiset coefficient as:

$\left\langle\begin{matrix} 4 \\ 18 \end{matrix}\right\rangle.$

I think that should instead be:

$\left\langle\begin{matrix} 18 \\ 4 \end{matrix}\right\rangle.$

Since it's been this way since the original author added it over two years ago, it seems I must be wrong, but it sure doesn't look correct to me. —Doug Bell ^{talk•contrib} 06:23, 9 November 2006 (UTC)

Nevermind, I see where I was confused. The article, as I suspected, is correct. —Doug Bell ^{talk•contrib} 06:43, 9 November 2006 (UTC)

[edit] Union and join in Operations section are not well-defined

In the Operations section, the union and join of two multisets $(A, m)$ and $(B, n)$ are defined. These definitions are only properly defined if the underlying sets $A$ and $B$ are equal. Namely, only then $m (x)$ and $n (x)$ are defined for all $x \in A \cup B$ .

Take for example the definition of the union: $(A \cup B, f)$ where $f (x) = m a x {m (x), n (x)}$ . According to the definition of multisets, $f$ is a function $A \cup B \to N$ , while $m$ is a function $A \to N$ and $n$ is a function $B \to N$ . Now in case $A \neq B$ , $f (x)$ is only properly defined for $x \in A \cap B$ , since only then both $m (x)$ and $n (x)$ are defined.

To correct this, function $f$ can be defined as follows:

$f (x) = m a x {m (x), n (x)}$	if $x \in A \cap B$
$f (x) = m (x)$	if $x \in A \setminus B$
$f (x) = n (x)$	if $x \in B \setminus A$

Similar changes also need to be made for the join operations. However, I am not really fond of this verbose definition. Does someone have a better solution?

eboy 12:17, 22 December 2006 (UTC)

Right. The idea 'Talk:Multiset#Definition_where_A_is_fixed_and_m.28x.29_can_equal_zero' would have solved it. This is tricky business. I'll give it some thought. Bo Jacoby 13:41, 22 December 2006 (UTC).

Please comment on this sketch for a solution:

Let A be any set. The set indicator function, 1_A, assumes values 0 and 1, where 1_A(x)=1 iff x is an element of A, and 1_A(x)=0 iff x is not an element of A. (Technically 1_A depends on some superset X, but it really doesn't matter which one). A set indicator function 1_A identifies the set A. The set indicator functions for intersection and union are:

$1_{A \cap B} = min\{1_{A},1_{B}\}$

$1_{A \cup B} = max\{1_{A},1_{B}\}$

A multiset indicator function 1_A assumes nonnegative integer values 0, 1, 2, etc. The value 1_A(x) is called the multiplicity of x, indicating how many times x is considered element of the multiset A defined by 1_A. The underlying set is {x | 1_A(x)>0}. The cardinality of the multiset is $\ |A|=\sum_x{1_A(x)}$ .

Bo Jacoby 00:00, 25 December 2006 (UTC).

The technical term for size of a (multi)set is cardinality. I have changed it. Bo Jacoby 22:11, 25 December 2006 (UTC).

Today I added a subsection on multiplicity function to the article. Your comments are welcome. It remains to clean up the repetitions introduced. Bo Jacoby 12:26, 26 December 2006 (UTC).

Sorry I didn't reply earlier. Thanks for the changes, Bo Jacoby. I do, however see some problems with the current presentation of the material. According to the first section, the multiplicity function is a function $A \to N$ , whereas in the second section it is a function $X \to N_0$ , where

X

is some superset of

A

. The problems I see here are as follows:

It looks a bit awkward to first formally define multiplicity (in the first section), and then to change that definition again in the following section.
Mixing the new definition of multiplicity with the formal definition of multisets is dangerous. From a multiset $(A, m)$ with $m: X \to N_0$ and $A \subseteq X$ , the set $A$ can easily be derived: $A = \{x \in X | m(x) > 0 \}$ . This means we should always take care that $A$ and $m$ match: $A \neq \{x \in X | m(x) > 0 \}$ may never occur. So here it seems better to me to get rid of $A$ alltogether.

In summary, in my eyes there are two different ways of defining multisets:

as a pair $(A, m)$ where $m: A \to N$ ;
as the characteristic function $m: X \to N_0$ .

Both have their own advantages and disadvantages. For example, an advantage of 1. over 2. is that you don't need to know the universe where

A

is in; an advantage of 2. over 1. is that the definitions of multiset operations are much cleaner.

eboy 14:44, 8 January 2007 (UTC)

Thank you for your comment. I completely agree with your analysis: 'It would be nice to have a unified approach, but none of the two methods is preferable in all cases'. The lazy solution is to leave the problem to the editors of indicator function, where the same problem shows up in the simpler context of sets. The indicator function of a set, say {1,2,4}, depends strictly speaking not only on the set itself, but also on the 'context' superset (say the integers Z or the reals R), because any function depends on it's domain. So the notation 1_{1,2,4} is strictly speaking ambiguous. However this formal dependence on the superset is uninteresting. Any old superset will do, and if it happens to be too narrow, just replace it by a wider one, setting 1_{1,2,4} (x)=0 for x outside the set {1,2,4}. It would be nice to have a universal superset, but we are warned that this construction leads to inconsistencies in the logic, Russell's paradox and all that. Perhaps the present state of set theory is immature and unsatisfactory, since it leaves this problem to us. I am not qualified to improve set theory, so I think I must leave the problem unsolved. Bo Jacoby 23:09, 1 February 2007 (UTC).

[edit] multisubset and corresponding sets

If A is a set, can I have B--a multisubset of A? e.g. A={x,y,z}, B={x,x,x,y,y}. What about sets with corresponding multisets? e.g. C={x,y} is the set corresponding to the multiset B. B then could also be a multiset corresponding to a subset of A. —The preceding unsigned comment was added by 220.253.88.12 (talk) 07:06, 1 February 2007 (UTC).

You are right. So I introduced the concept of a multiset with elements taken from a set. It is not the same thing as a submultiset of a multiset. Bo Jacoby 08:40, 2 February 2007 (UTC).

I believe the concept being addressed here is related to the concept of the support of a multiset. In this example, B is what is known as a multset over A. Given the set

A = {x, y, z}

, the extension listed for B arises formally as the multiset

B = (A, m)

with the function $m: A \to \mathbb{N}$ defined by

m (x) = 3, m (y) = 2, m (z) = 0

. The support of B is

{x, y}

, i. e., the subset of A with non-zero multiplicity in B. This definition of the support of a multiset is given by Syropoulos (2001, p. 349). -- Cornazano 03:26, 9 October 2007 (UTC)

[edit] Alternative Definition for Multi sets

The notion of the function m---being a a set of tuples mapping elements of the underlying set onto natural numbers seems to make having the underlying set identified separately redundant. Can we just have:

A multi-set is a set X of tuples (x,m). Where m is a natural number. Y={x|(x,m)\in X} is the underlying set...? InformationSpace 01:43, 12 February 2007 (UTC)

If I'm understanding the suggestion correctly, it is actually somewhat different from the standard definition as a function, in that it does not guarantee that a given x appears in only a single tuple in the set X. If we consider a set

X = {(x,3),(y,2),(x,2)}

, then we meet the definition with tuples. However, (multi)set differences pose a problem: what is

X - {(x,1)}

? First off, it is not well defined, and secondly it may collapse an element out of the set. The two possible results are

X - {(x,1)} = {(x,3),(y,2),(x,1)}

X - {(x,1)} = {(x,2),(y,2),(x,2)} = {(x,2),(y,2)}

. Part of what we're dealing with is the fact that every function is a relation (can be represented as tuples), but not every relation is a function. -- Cornazano 03:41, 9 October 2007 (UTC)

Thanks for your comment. Unfortunately, I can't see how this would simplify the definition of the multiset union (and join). The best way I can define this operation it using your definition of multisets is as follows:

$A \cup B = \{ (x,m) | (\exists k,l. ( (x,k) \in A \land (x,l) \in B \land m = \mathrm{max}(k,l) )) \lor ( (x,m) \in A \land x \not\in B) \lor ( x \not\in A \land (x,m) \in B) \}$

where $x \not\in A$ is defined as follows:

$x \not\in A \quad \text{iff} \quad \forall k.(x,k) \not\in A.$

But maybe someone has an idea how to improve this definition.

BTW Since Wikipedia is not meant for original research, we need to make sure the formal definition we use is already used in the literature and provide a reference to this literature. eboy 14:54, 13 February 2007 (UTC)

I think the trick to simplifying this is to define $\in$ so that $(x,0)$ is in any multiset. BTW I do like your idea of extending $\in$ so that it works for the tuple and the element of the underlying set. Point taken about original research. Doesn't mean we can't discuss it though! --InformationSpace 02:44, 2 March 2007 (UTC)

I've just been looking at how Fuzzy sets are defined---Fuzzy sets are sets of tuples just as I suggest for multisets above. Should fuzzy sets be defined as multisets are, with an indicator function $m:X\rightarrow\mathbb{R}$ with a range $[0,1]$ or should multisets be defined as fuzzy sets are!? InformationSpace 03:12, 16 March 2007 (UTC).

That is nice. A set, specified by a function assuming values 0 and 1 only, is generalized to multiset by extending the range to nonnegative integers, and to fuzzy set by extending the range to the unit interval [0,1]. Bo Jacoby 07:49, 16 March 2007 (UTC).

Mmmm... seems nice and neat to me! You can also have fuzzy-multisets where m just maps to reals. Sets, multisets, fuzzy-sets, fuzzy-multisets (and whatever...) can all be collections. Collections are objects that have certain operators defined (element, subset, union,...) Theres some heavy-duty mathematical house cleaning for you! Must publish first I guess... InformationSpace 01:01, 19 March 2007 (UTC)

Fuzzy multisets are discussed in Syropoulos (2001), as are hybrid sets. A hybrid set is like a multiset, except that the indicator function can be negative. In other words, a hybrid set H over a set A is defined as a pair

H = (A, f)

where $f: A \to\mathbb{Z}$ is a function. -- Cornazano 03:50, 9 October 2007 (UTC)

--Bo Jacoby 20:07, 10 May 2007 (UTC)== indexed families and multisets ==

"An indexed family, $(a i)$ , where i is in some index-set, defines the multiset ${a i}$ ." There are a number of problems with this statement. 1 - indexed families do not appear in the definition of multisets, so an indexed family cannot "define" a multiset. 2 - $(a i)$ is a tuple, not a set or a multiset. 3 - it is not even clear how ${a i}$ is a multiset. Some ammendment/clarification is required here. Otherwise, I shall remove this.InformationSpace 06:30, 4 May 2007 (UTC)

An indexed family does not define the concept of a multiset, but it does define a specific multiset.
Correct. $(a i)$ is a tuple. Every tuple is an indexed family. Every tuple defines a multiset of values.
${a i}$ is a multiset in the sense that if an element occurs in the list once or several times, then this element is member of the multiset that number of times. For example {1, 1, 2, 3, 3} is a multiset represented by the indexed family a defined by a₁=1, a₂=1, a₃=2, a₄=3, a₅=3. Bo Jacoby 20:07, 10 May 2007 (UTC).

No, I still think this is wrong. Either an indexed family $(a i)$ is a multiset or there is an isomorphic mapping (not defined or described in the article) from $(a i)$ to some multiset ${a i}$ . $(a i)$ cannot be a definition of a multiset. InformationSpace 04:42, 12 July 2007 (UTC)

The multiset {1,1,2} can be represented by the tuple (1,1,2) or alternatively by another tuple such as (1,2,1). The tuples (1,1,2) and (1,2,1) differ, but the multisets {1,1,2} and {1,2,1} are equal. A function f maps tuples to finite multisets: f((1,1,2)) = f((1,2,1)) = {1,1,2} . So the tuple (1,1,2) is not the same thing as the multiset {1,1,2}, but the tuple (1,1,2) defines the multiset {1,1,2}. A finite multiset is a tuple modulo order. Am I clear? Bo Jacoby 11:02, 17 July 2007 (UTC).

[edit] More clarity please

I'm a chemist with a deep fascination for all sciences, Mathematics is one of those. But despite my enthusiasm, I couldn't really understand what this article attempted to explain until I independently "discovered" a recursive algorithm (using sums) to find what only now I know is called Multiset Coefficient. I was looking for the number of different combinations of numbers you can obtain by rolling n k-faced dice (ndk in roleplayer's notation). I tried on paper different approaches until I found an "amazing pattern" which I couldn't find a way to describe mathematically. Then suspecting I rediscovered the wheel for the n-th time, I took a look at this article and tried the Multiset Coefficient formula... and the results were the same. Then I understood what a Multiset Coefficient was.

That's not the way things should be :-/ the works of mathematicians should be clearly understandable for all people, at least for all reasonably educated and willing people.

Is there somebody out there with enough knowledge in mathematics willing to work with me to make the article (and the family to which it belongs) more understandable for the layman?. Thank you for reading Pentalis 05:48, 8 July 2007 (UTC) Edit: errk, now I realize those were Binomial Coefficients instead of Multinomial... now I'm twice as confused -_- *reading the other article* Pentalis 06:02, 8 July 2007 (UTC)

I'll be glad to join you in improving the article. As there are many types of 'layman', the task of making the article understandable to the layman is not well defined, but nevertheless, your experience and enthusiasm is likely to be an asset. Bo Jacoby 17:42, 8 July 2007 (UTC).

[edit] Proposed changes, review and criticism

I didn't feel the introduction was clear, summarizing and introductory enough, but I felt it was better to rewrite it than review it. My first step in improving the article was creating this proposed new introduction, hoping it illustrates what I think could be improved in it.

Please, highlight any mistake of concepts or misleading statements, so then it can be added into the article

In mathematics, a multiset (or bag) is a generalization of a set, where its members can have more than one membership.

The total number of elements in a multiset, including repeated memberships, is represented in its cardinality, and the number of times they belong to the set is represented in their multiplicity, i.e. 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 the cardinality of the multiset is 6.

In multisets, as in sets, the order of elements does not matter; in contrast to tuples, where order is important. The following list displays the difference between the three concepts, note how a multiset can also be considered an unordered tuple:

The tuples (a, b) and (b, a) are not equal, because in tuples order is important; and the tuples (a, a) and (a) are not equal either, because in tuples and multisets multiplicity is considered.

The multisets {a, b} and {b, a} are equal, because in multisets order is unimportant; but the multisets {a, a} and {a} are not equal, as they have different multiplicities.

The sets {a, b} and {b, a} are equal, like the multisets {a, b} and {b, a}; but the sets {a, a} and {a} are equal, unlike the multisets {a, a} and {a}, this is because in sets, the concept of multiplicity does not exist, or in other words all objects, no matter how many times they belong to the set, still count as one.

Pentalis 10:16, 10 July 2007 (UTC)

Well done, Pentalis. Suggestions for clarity:

In mathematics, a multiset (or bag) is a generalization of a set. A member of a multiset can have more than one membership, while each member of a set has only one membership.
The total number of elements in a multiset, including repeated memberships, is the cardinality of the multiset, and the number of times an element belong to the multiset is the multiplicity of that member. i.e. 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 the cardinality of the multiset is 6.
... but the multisets {a, a} and {a} are not equal, as they have different cardinalities.

Bo Jacoby 20:42, 10 July 2007 (UTC).

[edit] To whom can we attribute Multisets?

Nobody? When were they invented/introduced? InformationSpace 03:57, 11 July 2007 (UTC)

Good question. Google "multiset" and follow the links! Bo Jacoby 08:37, 11 July 2007 (UTC).

We know that it dates at least as far back as 1977, when multisets are discussed in Brualdi's Introductory Combinatorics (first edition). I haven't ever had cause to do an article search for it, which means there are probably references that predate Brualdi's use of the term. -- Cornazano 01:57, 7 October 2007 (UTC)

I have added a bit on this topic. --Goochelaar 09:33, 7 October 2007 (UTC)

I added an additional reference on the early use of multisets. -- Cornazano 22:19, 7 October 2007 (UTC)

[edit] Correspondence between sets and multisets with all multiplicities = 1

The article states that "A multiset is a set if the multiplicity of every element is one." This is not strictly true, since the multiset includes as part of its structure a function that does not exist in the structure of a set. It is possible to identify a set S with a multiset (S, m) where m(x) = 1 for all x, in the sense that there is a bijection between (the category of?) sets and multisets whose multiplicity function is the constant function 1.

My question, as a relatively new contributor, is whether this distinction is this too specific for inclusion in a general encyclopedia article. Any thoughts? -- Cornazano 14:19, 7 October 2007 (UTC)

Since every ordered pair (A, B) := {{A}, {A, B}} is a set (consisting of two sets) every multiset is also a set. Therefor the statement "A multiset is a set if the multiplicity of every element is one." is strictly true but it does not state anything new ;-) --87.183.144.74 (talk) 18:18, 10 January 2008 (UTC)

I agree that this is technically correct, but only in the sense that we can say that an integer is a set, and a real number is a set, and a field is a set, and a vector space is a set, etc. We don't normally make statements like that, even if they are strictly true and don't add anything new. Nearly all of mathematics can be coded in set theory. I still find the statement misleading for several reasons, and think it needs to be changed.

First, our formal systems typically treat sets as a primitive notion (e.g., in ZFC) and multisets are being formally defined here in terms of that primitive notion. The only exception that I know of to this is Blizard's article, where he develops a first-order theory of multisets where mset is a primitive notion; however, a first-order theory of multisets does not formalize a multiset in terms of set theory.

Second, we define operations for multisets (such as $\uplus$ ) that do not apply to sets but do apply to multisets. Claiming that a multiset where all multiplcities are 1 is a set can be easily misconstrued--either to mean that the exclusively multiset operations don't apply, or that the multiset operations should apply to sets.

Third, there is a clear distinction in the literature between the categories of $\mathbf{Set}$ and $\mathbf{MSet}$ (see, e.g. the article by Syropoulos). Are there any sources that formalize the theory of multisets and claim that these particular multisets are actually sets? Cornazano (talk) 18:11, 5 May 2008 (UTC)

[edit] Alternate uses of the term multiset?

In addition to the mathematical object discussed in this article, multiset can also refer to a component of the C++ Standard Template Library, and as a software application (see, e.g., http://www.almeza.com/, and numerous references from a Google search on multiset). There are currently no Wikipedia articles on either of these uses, so I don't think a disambiguation is needed at this point. A question: should these alternate uses be acknowledged at the beginning of the article in some form? -- Cornazano 14:41, 7 October 2007 (UTC)

[edit] Codomain of the multiplicity function

At the moment, it appears that the article is inconsistent in regards to the codomain of the multiplicity function. Under Formal definition, the codomain is taken to be the positive integers ("m : A → N is a function from A to the set N = {1, 2, 3, ...}"). Under Multiplicity function, the codomain is taken to be the non-negative integers ("Now generalize the concept of set indicator function by releasing the constraint that the values are 0 and 1 only and allow the values 2, 3, 4 and so on."). This should probably be updated so that it is consistent, and supported with sources in the literature.

I don't have Stanley or Knuth ready to hand, but Bogart specifies the codomain as the non-negative integers (Kenneth P. Bogart (2000), Introductory Combinatorics, 3rd. ed., p. 93). Other sources explicitly annex the symbol $\infty$ to the codomain, allowing for unlimited repetition (see the earlier discussion of Why stop at finite cardinals? for references; I haven't yet found any sources that extend the codomain to all cardinals). Which source(s) limit the codomain to positive integers? Which sources extend it beyond natural numbers? -- Cornazano 15:18, 7 October 2007 (UTC)

[edit] Braces

There seems to be an alternative way of writing for the braces (Introduction of http://www.micropress-inc.com/60add/stmaryrd.pdf). Can anybody verify that? —Preceding unsigned comment added by 88.74.4.192 (talk) 11:41, 2 December 2007 (UTC)

[edit] Fourth kind

Taking into account whether ORDER IMPORTANT and REPEATED MEMBERSHIP IMPORTANT:

FALSE, FALSE -> set

FALSE, TRUE -> multiset

TRUE, TRUE -> tuple

What about TRUE, FALSE... The order is important, but it is unimportant whether a member is repeatedly inside this collection. Does this thing have a name? --Abdull (talk) 17:02, 2 February 2008 (UTC)

The thing (a,b,a)=(a,b) because repetition is unimported, and likewise (a,b,a)=(b,a), but (a,b)≠(b,a) because order is important. So the new concept leads to a contradiction. Bo Jacoby (talk) 21:45, 3 February 2008 (UTC).

Unless it means sequential repetition is unimportant, where (a,a,b)=(a,b,b)=(a,b) but (a,b,a)≠(a,b). This concept may have some use with coding theory. Fuzzy (talk) 16:10, 18 March 2008 (UTC)

[edit] fooled by n and k convention

On closer inspection, it seems the n and k used in the multiset article are reversed from the usage in the stars and bars (probability) article. The difference in convention appears to have fooled User:Sisodia in the case of the latter, and fooled me in the case of the former. Btyner (talk) 02:30, 16 March 2008 (UTC)

[edit] What about set difference?

Discussing about relational algebra, I came about the definition of difference for a multiset. Now this article defines intersection, union, sum (join) etc, but what about difference? Two different definitions seem plausible to me:

A - B is the multiset containing all elements from A that do not occur in B
A - B is the multiset where the multiplicity of each element is given by $1 A - B (x) = max(0,1 A (x) - 1 B (x))$

I don't have the necessary background to check which definition is used (or even makes sense), or if the set difference has any meaning at all for multisets. Also, for normal sets, difference is often defined as $A-B = A \cap \bar B$ . Since the complement of a multiset does not make sense (at least to me) this is problematic... Jonas Wagner (I'll get a username soon :-)), last edited 23 April 2008

The second definition makes the most sense to me, but we really need an authoritative reference - if the references don't agree, we need to discuss a few prominent definitions. Dcoetzee 20:41, 21 April 2008 (UTC)

The second definition of the difference of two multisets (also called the relative complement or, in at least one case, the removal of one multiset from another) is what I've encountered in the literature. Syropoulos uses the notation $A\ominus B$ to denote the relative complement of

B

A

; Hickman and Blizard both use

A - B

. Cornazano (talk) 16:02, 4 May 2008 (UTC)

Regarding the references, we can't effectively discuss their differences until we discuss the different definitions of multiset. In particular, some definitions (e.g., Hickman, planetmath) allow the multiplicity of an element to be an infinite cardinal. The operation

1 A (x) - 1 B (x)

is not well defined for arbitrary cardinals, so their definition of the relative complement necessarily differs from that given here. However, it does give the same results for finite multiplicities. Cornazano (talk) 16:19, 4 May 2008 (UTC)

[edit] Notations

Reading this article, I disagree strongly with some notations used (meaning both that I don't recognise notation I have encountered in the literature, and I don't like the notation used here). My strongest feelings are about notation like ${a, a, b, b, b}$ . By standard mathematical conventions, that is a set, and equal to ${a, b}$ , so one cannot also have it designate a multiset. Although one would not usually write the same element multiple times in the same set, it may happen that some elements "happen to be" equal, and the interpretation of pruning repetitions in this case is universally accepted, and often important. For instance the set of cosets $G / H$ will usually be defined as $\{\,gH\mid g\in G\,\}$ , with each coset appearing many times in different guises. But even if one would say an explicitly written set designates a multiset if some entries are repeated, this would leave it impossible to distinguish between a finite set and the corresponding finite multiset (in which multiplicities are at most 1). See the current description of the multiset ${a, b}$ in the section Formal definition to see the kind of confusion this ambiguity can lead to. In fact many of this article's formulas are quite ambiguous due to this matter.

It is true that I know no precedent in the literature; authors discussing multisets seem to avoid the question of writing them down explicitly. Stanley, in Enumerative Combinaotrics 1, page 15, says that ${a, a, b, b, b}$ could be written as ${a 2, b 3}$ , which causes obvious confusion if a and b should be numbers. In fact on the next page he writes a multiset ${1,1,2,3}$ rather than ${1 2,2 1,3 1}$ so maybe one should not take this as too authoratative a reference on notation. Personally I think a valid notation is to double the braces (restricting spacing to avoid another ambiguity): $\{\!\!\{a,a,b,b,b \}\!\!\}$ . (Does anybody know about blackboard bold braces?).

Another shock for me is using angles for "multiset coefficients" (somehow an awkward echo of the term "binomial coefficient") as in $\textstyle\left\langle{n\atop k}\right\rangle$ , since that notation is already used for Eulerian numbers! Here I am sure there is a more frequently used convention, which is to double the parentheses of binomial coefficients, as $\left(\!\!{n\choose k}\!\!\right)$ . I'm pretty suer these are used freely in the literature nowadays.

Finally I was also surprised to read at Indexed family#Notation that $\{\, n^2 \mid n\in\mathbf Z\,\}$ denotes a set but $\{\, n^2 \}_{n\in\mathbf Z}$ denotes a multiset (while not really ambiguous, this is confusing, and certainly many using the second notation are not aware of this interpretation). It should come as no surprise that I would prefer writing the multiset as $\{\!\!\{\, n^2 \mid n\in\mathbf Z\,\}\!\!\}$ . Marc van Leeuwen (talk) 13:08, 8 June 2008 (UTC)

Thanks for the comment. Feel free to improve.

As the multiset coefficient is easily expressed in terms of a binomial coefficient the notation is not necessary except intermediately.
As a multiset of numbers is easily expressed by a cumulant generating function, a notation is not necessary except intermediately. Multisets of elements that are not numbers are less commonly used.
When it is not necessary to distinguish between a multiset where all multiplicities are one, and the set of the same elements, then there is no reason to invent a special notation for multisets.

Bo Jacoby (talk) 00:31, 9 June 2008 (UTC).