1
$\begingroup$

I remember asking about this in some Norwegian Usenet group many many years back, and as I recall (although I may be just imagining it) a mathematician at the University of Oslo gave me a good summary. But I have forgotten it all!

Background: during my student days at Heriot Watt U. (Edinburgh) I wrote dissertation about combination of uncertain evidence by means of a model called Dempster-Shafer. With this method one had to update products of the elements of multisets (by this I mean that an element could be present any number of times), where it was necessary to support both that an element was removed, and that it was added. Addition of x to a set meant just multiplying the product by x, but removal was trickier: when x was zero one could not just divide the product by x!

So, for each set I maintained a pair (P, Z) where P was the product of the elements if possible or else 1, and Z the count of zeroes in the set. It was practical to allow a negative number of occurrences of a number in a set. And then the computer implementation of updates of these pairs (when sets were updated) corresponded directly (identical to) the computer implementation of of multiplication and division of complex numbers in polar form, i.e. (P1,Z1) "times" (P2,Z2) = (P1*P2, Z1+Z2), where the main trick is that the set {0} has product (1,1).

I find it difficult to write in the math notation required by this site. To be concrete, trying to formalize things a little by defining count of an element in a multiset, and then product of set, I couldn't get nice formula result for x raised to expression with multi-character name function. So I gave up on that, and tried simple textual formulas.

But even those proved too challenging for me here (and now I can appreciate the formula editor in Word!), I'm sorry. Also, sorry about the tags. I tried "multi-set" and "pair" but they don't exist, and I don't have rating to create new tags. I was unable to find good synonyms -- so, formulas lacking and tags lacking!

But hopefully the above description gives the gist of it: updates of sets (element added or removed) corresponded to updates of pairs, and the product, if defined, is trivially deduced from the pair. I wonder what those pair beasts are called and what the common notation is. And e.g. if there is any way to cut down on the complexity of results of addition and subtraction (I can't see any way, apparently addition and subtraction produce ugly ugly things not even deserving of name "beast"...).

?

  • 0
    I don't really understand what you mean by "product." Could you give a simple example with explicit sets?2011-07-13
  • 0
    I am not 100% sure that [set-theory] is relevant.2011-07-13
  • 0
    @Asaf: Agreed. [It](http://en.wikipedia.org/wiki/Dempster%E2%80%93Shafer_theory) looks like probability and statistics to me...2011-07-13
  • 1
    Qiaochu: I'll have to invent a notation for the sets, first. Let e.g. S1={3,3,5} denote a multiset where 3 occurs twice and 5 occurs once. The product is 3*3*5=45. When the set is updated by adding 0 forming S2={3,3,5,0} the product is 0. The *pair* for this set is (45,1), which implies product 0. Update yet again to remove one count of 0, yielding S3={3,3,5}, corresponds to updating the pair to (45,0), which yields product 45. Doing that again yields a set which I don't know how to express, but with pair (45,-1) and undefined product. Now remove the sets and the (P,Z) pairs live on their own.2011-07-13
  • 0
    @Asaf: "set-theory" was tag I found closest in meaning to "multiset".2011-07-13
  • 1
    @Alf: Most questions in mathematics involve sets in one way or another, it does not mean that [set-theory] fit to all the questions on the site, or even most of them. Your question seems somewhat less about the multisets and more about some analysis related to this operation which you have defined. I'm really not sure about the nature of the tag, but I am almost certain [set-theory] is less fitting. Since I do not know which tags fit better I am reluctant to retag.2011-07-13
  • 0
    @Asaf: originally I also had tag "zero-divisor", which to me seems more directly related. Quiaochu removed it. I've now rolled back to original, since I could understand removal of the set tag but not the zero-divisor tag (which is directly related). Is that better?2011-07-13
  • 0
    @Alf: Actually, no. I believe that the zero-divisor tag is meant for something else. Qiaochu removed it (and rightfully I might add) and left only the [set-theory] tag. Had it been me seeing the question first, I might have left it only with [zero-divisor] instead and let someone else deal with the problem. Perhaps a meta thread is in order for this...2011-07-13

2 Answers 2