Talk:Multiset

Infinite multiplicity again

Article currently says:

Within set theory, a multiset may be formally defined as a 2-tuple(A, m) where A is some set and m : A → N_≥1 is a function from A to the set N_≥1 = {1, 2, 3, ...} of positive natural numbers. The set A is called the underlying set of elements.

As stated, this excludes the (rather natural) possibility of elements with infinite multiplicity.

I see that this was the very first complaint on this talk page, and references were even given, but nothing seems to have been done about it. This strikes me as rather serious. If you're allowing infinite sets, then I can't see much point in disallowing infinite multiplicities too. --Trovatore (talk) 01:54, 19 April 2012 (UTC)

"If you're allowing infinite sets ..." In fact it looks to me like everything in the article is about finite multisets (i.e., this is an article about combinatorics, with a little bit of set theoretic exposition thrown in to help make it less comprehensible ;) ). One could write an article about multisets including infinite ones, but it seems like in that case it would still be good to have an article like this one about only the finite aspects. --Joel B. Lewis (talk) 03:37, 19 April 2012 (UTC)

Well, there's nothing in the article that says it's about finite multisets, and set theory is really not that interesting/useful until you get to infinite sets, except as you say to make things less comprehensible. It's true that only one example comes to mind where I came across multisets in set theory itself, but still, the most natural notion of multiset does not seem to be restricted to the finite case. --Trovatore (talk) 03:53, 19 April 2012 (UTC)

Further on infinite versus finite

An IP editor and ‎Marc van Leeuwen just went back and forth on some changes w.r.t. the finite versus infinite problem. Right now, the article is entirely about finite multisets (though it doesn't say this in the intro) except for the section "formal definition" which allows infinite multisets (the set A can be infinite, even though the multiplicities are currently restricted to be finite). This is obviously untenable. I suggest that the intro and formal definition be rewritten to make it unambiguously clear that this article is about finite multisets. This will leave a bunch of material (some added by the IP editor then removed, some in the "formal definition" section) homeless; this material should be put into a new section somewhere that discusses the issue of infinite multisets (of both sorts: infinite base sets and infinite multiplicities). Are there any thoughts or objections? --Joel B. Lewis (talk) 15:30, 19 June 2012 (UTC)

I don't quite agree that the article is entirely about finite multisets. In fact very little is said that excludes infinite multisets (but with finite multiplicities), neither in the intro, overview, formal definition, nor multiplicity function sections (the one occurrence of a parenthesised (finite) is the only exception, and this is merely to avoid the (solvable) problem of defining the sum of an infinite collection of natural numbers, indexed by a set, as a cardinal number). But it is true that nothing is explicitly said about infinite multisets, no examples of them are given, some parts just do not apply to the infinite case (counting multisets), and the (anyway ambiguous) notation using braces with possibly repeated elements between them is not suited to write down infinite multisets (not really different from the situation for the same notation for ordinary sets). Anyway I want to stress that recent edits are only about the finite/infinite multiplicity question, which is an entirely different issue. However, if not much useful is being said about infinite multisets (and I'd love to see good practical examples of their use), then a fortiori the utility of allowing infinite multiplicities is not being made evident. Marc van Leeuwen (talk) 11:59, 21 June 2012 (UTC)

It may be the case that infinite multisets are simply not much discussed in the literature, and it is not the task of wikipedia editors to fill in the gap. You may think of the normal distribution as an infinite multiset of outcomes, but that is (at least to me) confusing and not helpful. A binomial distribution with rational probability parameter can be modelled as a finite multiset, and the normal distribution is a limiting case of binomial distributions. So the bridge leading from finite multisets of numbers to infinite multisets of numbers is the cumulant generating function. Bo Jacoby (talk) 07:37, 23 June 2012 (UTC).

The article is deficient. Infinite multisets are important even in elementary combinatorics (e.g., see Brualdi, Introductory Combinatorics). Choosing a finite sub(multi)set of given size from an infinite multiset is a basic combinatorial question. Zaslav (talk) 08:37, 25 August 2023 (UTC)

A paragraph or section specifically highlighting multiset elements with infinite representation would be welcome. Please add it. I see that the article currently includes

It is possible to extend the definition of a multiset by allowing multiplicities of individual elements to be infinite cardinals instead of positive integers, but not all properties carry over to this generalization.

From that, I conclude that we are talking about cardinal infinities rather than ordinal infinities ... unless the latter alternative is also sometimes done? I know that ordinal numbers support both sup and inf, which could be used for multiset union and intersection, respectively. Do cardinal infinities always support both sup and inf, or are union and intersection defined in some other way? Enquiring minds want to know! —Quantling (talk | contribs) 12:56, 25 August 2023 (UTC)

Applications section

Wouldn't a simple application be, say, the roots of $(x+4)(x-1)^{2}$? In set notation it's {−4, +1}, but multisets allow you to show multiplicity of roots, like {−4, +1, +1}. — Preceding unsigned comment added by 68.198.133.72 (talk) 20:53, 7 July 2014 (UTC)

Difference

{1,1,1,3}\{1,1,2}= {1,3} was it? --Peiffers (talk) 16:21, 14 July 2014 (UTC)

Sure. According to talk section 'What about set difference?'

$\mathbf {1} _{A\setminus B}(x)=\max(0,\mathbf {1} _{A}(x)-\mathbf {1} _{B}(x)).$

--Ernsts (talk) 19:38, 4 December 2017 (UTC)

Cite the use of square brackets

For non-mathematics and introductory text, to avoid confusion with set notation in the same text, is usual to adopt square brackets notation: A={1,2} is a set, B=[1,2,2] is a multiset.

See full notation here. --Krauss (talk)

Cite relationship with frequency concept in Statistics

Multiplicity and frequency are the same. To model a name/frequency table of statistics, we use the cartesian product Name X Name_frency... As multiplicity, same semantic in with the same product of sets modeling it. --Krauss (talk)

Interesting elementary formula

It can be easily proven that $\sum _{i=0}^{k}\left(\!\!{\binom {n}{i}}\!\!\right)=\left(\!\!{\binom {n+1}{k}}\!\!\right)$. I think this formula should be included in the article. Aside from its intrinsic interest, it comes handy when studying dimensions of some subspaces of vector spaces and/or problems related to polynomials.

Example 1: If we consider a polynomial of degree d in n variables along with all its first k-derivatives, this formula computes, from the number of derivatives of order i for each i, the total number of polynomials arising in the system.

Example 2: Since the homogeneous polynomials of degree i in n variables over a field form a subspace $H(n,i)$ of dimension $\left(\!\!{\binom {n}{i}}\!\!\right)$, this formula shows that $H(n+1,k)$ is isomorphic to $H(n,0)\oplus \cdots \oplus H(n,k)$, what can also be inferred from the homogeneization process.

What do you think?

Jose Brox (talk) 10:49, 21 August 2018 (UTC)

Dedekind source

A correspondent mathematician questions the whole concept of multisets, basically saying it is poorly defined. He therefore cannot believe Dedekind would have had anything to do with them (Reference 11). Does anybody here happen to know the page number where Dedekind describes/uses multisets in his book?

Failing that, is there some authoritative source which defines this concept, preferably a book on set theory? It seems that discrete maths does not count for my correspondent; it is probably not real maths ;-) KarlFrei (talk) 16:59, 11 December 2018 (UTC)

The definition in the article of a multiset being a pair of a set and a function of this set to positive integers is perfectly accurate, and cannot be qualified as poor. For an authoritative source, Knuth's book (reference 2 of the article) is the best possible reference. This book is sufficiently important to have an article in Wikipedia, and has often been qualified as the "Bible of discrete mathematics". Your correspondent is free to consider that some part of mathematics is not really mathematics, but this is clearly not the opinion of American Mathematical Society, which includes discrete mathematics in its subject classification. I guess that your correspondent consider as not "counting" everything that they does not know ;-) D.Lazard (talk) 19:03, 11 December 2018 (UTC)

Sorry for my lack of reply till now. Thank you! KarlFrei (talk) 07:44, 15 February 2019 (UTC)