Multiset intersection

Last Monday, I mentioned that multiset products are not the best available extension of the intersection of a family of sets so that it applies to multisets. Now that we’ve talked about the concepts of infima and well-ordering, we’re ready to define multiset intersections.

A bit further back, we discussed how characteristic functions can be used to represent subsets of a set $X$ and the operations on $\wp\left(X\right)$ . At the time, we noted that the intersection of two sets $A, B\in \wp\left(X\right)$ is represented in terms of the characteristic function as

$C=A\cap B \:\Leftrightarrow\: \chi_C = \min\left(\chi_A,\chi_B\right)$

where the minimum is taken in the ordered field $\mathbb{F}_2$ . For each $x\in X$ , this minimum is just $\inf\left\{\chi_A\left(x\right), \chi_B\left(x\right)\right\}$ .

Given a family of functions $f_i: X\to Y$ , we let

$\begin{array}{lrl}\inf \left\{f_i\right\} := &g:& X\to Y \\ &&x\mapsto \inf \left\{f_i\left(x\right)\right\} \end{array}$ .

Since $\mathbb{F}_2$ is well-ordered and the characteristic functions are taken over a common domain, our representation of intersection in terms of characteristic functions extends to any family of subsets of $X$ . That is, for any family $\left\{A_i\right\}_{i\in I}$ where each $A_i \in \wp\left(X\right)$ , we have

$A = \bigcap_{i\in I}{A_i} \:\Leftrightarrow\: \chi_A = \inf\left\{\chi_{A_i}\right\}$ .

We also saw a representation of intersections as the product of the characteristic functions. When dealing with sets in $\wp\left(X\right)$ , the two representations correspond to the same objects and operations in the class $\mathbf{SSet}_X$ . However, there is an important difference between the two: the representation in terms of products relies (exclusively) on the algebraic properties of the codomain, while the representation in terms of infima relies (exclusively) on the order properties of the codomain.

The algebraic properties of the field $\mathbb{F}_2$ and arithmetic on $\mathbf{Card}$ are quite different. However, both of them are well-ordered classes, so their order properties are similar in many respects. This leads us to the following definition:

Definition

Let $\mathrm{M} = \left\{\mathcal{M}_i = \left(X, f_i\right)\right\}_{i\in I}$ be a family of multisets over a set $X$ . The multiset intersection of $\mathrm{M}$ is the set

$\mathcal{M} = \bigcap_{i\in I}{\mathcal{M}_i} := \left(X, \inf\left\{f_i\right\}\right)$ .

The multiplicity functions $f_i$ are defined on a common domain, and $\mathbf{Card}$ is well-ordered by the usual relation $\leq$ . Just as we found with the characteristic function, these facts are sufficient to ensure that the multiset intersection is always well-defined on $\mathbf{MSet}_X$ .

As usual, when $\mathrm{M}$ contains only two multisets, we will use the infix notation $\mathcal{M}_1 \cap \mathcal{M}_2$ for the intersection. In this case, $\cap$ is an associative and commutative binary operation on $\mathbf{Mset}_X$ . Next time, we’ll look at some of the properties of multiset intersections.

2 Responses to Multiset intersection

Properties of multiset intersection « A Singular Contiguity says:

May 27, 2008 at 4:15 am

[…] Today, we’ll examine the properties of the multiset intersection that we defined […]

Reply
Properties of multiset union « A Singular Contiguity says:

June 4, 2008 at 4:03 am

[…] of multiset union We defined the union of a family of multisets last week. Today we’re going to look at some basic properties […]

Reply

M	T	W	T	F	S	S
« Apr				Jun »
			1	2	3	4
5	6	7	8	9	10	11
12	13	14	15	16	17	18
19	20	21	22	23	24	25
26	27	28	29	30	31

A Singular Contiguity

Multiset intersection

Like this:

Related

2 Responses to Multiset intersection

Leave a Reply Cancel reply

Pages

Recent Posts

Archives

Blogroll