Talk:Multiset

From Wikipedia, the free encyclopedia

1 Why stop at finite cardinals?
2 References, size and set constructor notation?
3 polynomial notation
4 Definition where A is fixed and m(x) can equal zero
5 size, length or cardinality
6 Multiset coefficient wrong in example?
7 Union and join in Operations section are not well-defined
8 multisubset and corresponding sets
9 Alternative Definition for Multi sets

[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).

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)

[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).

[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)

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)

Retrieved from "http://en.wikipedia.org../../../m/u/l/Talk%7EMultiset_4f7e.html"