Multiset sums

On Monday, we considered how the sets A\in\wp\left(X\right) can be represented as functions \chi_A: X\to \mathbb{F}_2. In fact, for every function \chi:X\to\mathbb{F}_2, we can define A_\chi = \left\{x\in X \:|\:\chi\left(x\right) = 1\right\}. Combining this with the definition of the characteristic function, we have the identities

A_{\chi_A} = A and \chi_{A_\chi} = \chi.

This actually provides the bijection between \wp\left(X\right) and the functions \chi that I mentioned immediately following the definition of the characteristic function.

Structurally, the class

\mathbf{SSet}_X := \left\{\left(X, \chi\right) \:|\: \chi: X\to\mathbb{F}_2\right\}

is very similar to the class

\mathbf{MSet}_X := \left\{(\left(X, f\right) \:|\: f: X\to\mathbf{Card}\right\}

of multisets over X. Our ability to represent the set operations on \mathbf{SSet}_X by well-defined operations in the ordered field \mathbb{F}_2 suggests that we look at some of the well-defined operations on \mathbf{Card} as a basis for formally defining the multiset operations on \mathbf{MSet}_X.

One operation on \mathbf{Card} that we have already used is the cardinal sum \sum_{i\in I}\kappa_i, which is defined for every set of cardinals \left\{\kappa_i\right\}_{i\in I}.

Definition

Let \mathcal{M} = \left\{\mathcal{M}_i = \left(X, f_i\right)\right\}_{i\in I} be an indexed family of multisets. The multiset sum of \mathcal{M} is the multiset

\biguplus_{i\in I} \mathcal{M}_i := \left(X, \sum_{i\in I}f_i\right).

Since \mathrm{dom}\left(f_i\right) = X for all i\in I, the cardinal sum on the right is well-defined and the multiset sum does indeed give us another multiset over X. For a pair of multisets, we will generally write the multiset sum in infix notation as \mathcal{M}_1 \uplus \mathcal{M}_2.

As the notation suggests, the multiset sum is related to the union operation on sets. Multiset sums, like the union of sets are both commutative and associative—these follow directly from the corresponding properties of the cardinal sum. Cardinal sums are also monotonic nondecreasing; for any cardinal sum \kappa = \sum_{i\in I} {\kappa_i} we have \kappa_i \leq \kappa for all i\in I. One consequence of this is that a cardinal sum is 0 if and only if all of its summands are 0, and so we have the following relationship between support, multiset sums, and set unions:

\mathrm{support}\left(\biguplus_{i\in I} {\mathcal{M}_i}\right) = \bigcup_{i\in I} {\mathrm{support}\left(\mathcal{M}_i\right)}.

The monotonicity of cardinal sums also ensures that the multiset sum of a family of multisets contains each of the multisets in the family:

\mathcal{M} = \biguplus_{i\in I}{\mathcal{M}_i}\:\Rightarrow\:\left(\forall i\in I\right)\left(\mathcal{M}_i\subseteq\mathcal{M}\right).

Here’s a way in which the multiset sum differs from the union of sets. Set union is idempotent—for any set X, we have X\cup X = X. The multiset sum, on the other hand, is not idempotent, as we can see by considering the sum

\left\{a\right\}\uplus\left\{a\right\} = \left\{a, a\right\} \neq \left\{a\right\}.

This last example also shows that the class of multisets with all multiplicities equal to 1 is not closed under multiset sums.

Copyright © 2008 Michael L. McCliment.

This entry was posted on Wednesday, May 14th, 2008 at 4:00 am and is filed under Mathematics, Multisets. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.

7 Responses to Multiset sums

  1. Vishal Lama says:
    May 14, 2008 at 7:14 am

    This is a lot easier to read. And, I do like the theme as well. Thanks!

    Reply
  2. ShiftTab says:
    May 14, 2008 at 8:12 pm

    Wow! This is the reason why I took a Math Ideas class in college. All we did was write essays about math theories. =)

    Reply
  3. Michael McCliment says:
    May 14, 2008 at 9:36 pm

    Now I’m curious… what does one do in a Math Ideas class?

    I already had a year of calculus before I finished high school, and I don’t think I’ve ever encountered a course with a title like that. I did have a writing-emphasis course in my math program. We wrote a historical essay (mine was actually on Cantor), and worked quite a bit on improving our written presentation of mathematical arguments (read: lots of well-presented proofs, not just a series of equations with a box around the final answer).

    Reply
  4. ShiftTab says:
    May 15, 2008 at 1:13 am

    Well, during that semester. We studied the historical background of Pi and how that came about. We also learned about the Pythagorean theorem and where it came from, how it was created etc. (wrote papers).

    Our final projected was to get something created in this world and explain how the functions of math work it’s way around that specific object. My friend and I chose to explain a camera and we discussed the focal length, depth of field, aperture, etc.

    So it wasn’t a complete waste of class. I took the class just to get my math credit out of the way. It’s basically a class designed for students who are non-math related majors. I’m a film guy. Math is the last thing I wanted to study.

    Reply
  5. Infima, suprema, and well-orders « A Singular Contiguity says:
    May 21, 2008 at 4:03 am

    […] suprema, and well-orders In the last couple of posts about multisets, we’ve looked at two types of operations we can perform on the class […]

    Reply
  6. Multiset union « A Singular Contiguity says:
    May 28, 2008 at 4:00 am

    […] Over the past two weeks, we’ve introduced three operations on families of multisets: sums, products, and intersections. The other basic operation on families of multisets, unions, is […]

    Reply
  7. Multiset operations as binary operations (part 1) « A Singular Contiguity says:
    June 9, 2008 at 4:35 am

    […] defined four operations on families of multisets where for all : sums, products, intersections, and unions. As I’ve already commented in a couple of places, we can […]

    Reply

Leave a reply to Multiset union « A Singular Contiguity Cancel reply