## Multiset operations as binary operations (part 1)

June 9, 2008

Review: Associativity, commutativity, and idempotence

A binary operation $\cdot$ on a set $X$ is a function $\cdot: X\times X \to X$. It is usually written using an infix notation $x\cdot y$ rather than a functional notation such as $\cdot\left(x, y\right)$.

The operation $\cdot$ is associative if and only if $a\cdot\left(b\cdot c\right) = \left(a\cdot b\right)\cdot c$ for all $a,b,c\in X$. It is commutative if and only if $a\cdot b = b\cdot a$ for all $a,b\in X$. It is idempotent if and only if $a\cdot a = a$ for all $a\in X$.

We’ve defined four operations on families of multisets $\left\{\mathcal{M}_i\right\}_{i\in I}$ where $\mathcal{M}_i \in \mathbf{MSet}_X$ for all $i\in I$: sums, products, intersections, and unions. As I’ve already commented in a couple of places, we can restrict our attention to families where $\left|I\right| = 2$. This provides us with four binary operations on $\mathbf{MSet}_X$. Today’s post collects together the properties of these binary operations.

Proposition 1: The operations $\uplus$, $\:\cdot\!\!\!\!\cup$, $\cap$, and $\cup$ on $\mathbf{MSet}_X$ are all associative and commutative.

Proof:

Let $\mathcal{M}_1, \mathcal{M}_2, \mathcal{M}_3 \in \mathbf{MSet}_X$. The first four parts follow directly from the associativity and commutativity of $+$ and $\cdot$ as binary operations on $\mathbf{Card}$.

Associativity of $\uplus$.

$\begin{array}{r@{\:=\:}l} \mathcal{M}_1 \uplus \left(\mathcal{M}_2 \uplus \mathcal{M}_3\right) & \left(X, f_1 + \left(f_2 + f_3\right)\right) \\ & \left(X, \left(f_1 + f_2\right) + f_3\right) \\ & \left(\mathcal{M}_1 \uplus \mathcal{M}_2\right) \uplus \mathcal{M}_3\end{array}$

Commutativity of $\uplus$.

$\begin{array}{r@{\:=\:}l} \mathcal{M}_1 \uplus \mathcal{M}_2& \left(X, f_1 + f_2\right) \\ & \left(X, f_2 + f_1\right) \\ & \mathcal{M}_2 \uplus \mathcal{M}_1\end{array}$

Associativity of $\:\cdot\!\!\!\!\cup$.

$\begin{array}{r@{\:=\:}l} \mathcal{M}_1 \:\cdot\!\!\!\!\cup\: \left(\mathcal{M}_2 \:\cdot\!\!\!\!\cup\: \mathcal{M}_3\right) & \left(X, f_1 \cdot \left(f_2 \cdot f_3\right)\right) \\ & \left(X, \left(f_1 \cdot f_2\right) \cdot f_3\right) \\ & \left(\mathcal{M}_1 \:\cdot\!\!\!\!\cup\: \mathcal{M}_2\right) \:\cdot\!\!\!\!\cup\: \mathcal{M}_3\end{array}$

Commutativity of $\:\cdot\!\!\!\!\cup$.

$\begin{array}{r@{\:=\:}l} \mathcal{M}_1 \:\cdot\!\!\!\!\cup\: \mathcal{M}_2& \left(X, f_1 \cdot f_2\right) \\ & \left(X, f_2 \cdot f_1\right) \\ & \mathcal{M}_2 \:\cdot\!\!\!\!\cup\: \mathcal{M}_1\end{array}$

The remaining parts follow from the following facts:

1. Let $A, B$ be partially ordered sets. Then $\inf \left(A \cup \left\{\inf B\right\}\right) = \inf\left(A\cup B\right)$ and $\sup \left(A \cup \left\{\sup B\right\}\right) = \sup \left(A\cup B\right)$ whenever the suprema and infima exist.
2. The supremum and infimum of every set of cardinals exist.

Associativity of $\cap$.

$\begin{array}{r@{\:=\:}l} \mathcal{M}_1 \cap \left(\mathcal{M}_2 \cap \mathcal{M}_3\right) & \left(X, \inf \left\{f_1, \inf\left\{f_2, f_3\right\}\right\}\right) \\ & \left(X, \inf\left\{f_1, f_2, f_3\right\}\right) \\ & \left(X, \inf \left\{\inf\left\{f_1, f_2\right\}, f_3\right\}\right) \\ & \left(\mathcal{M}_1 \cap\mathcal{M}_2\right) \cap \mathcal{M}_3\end{array}$

Commutativity of $\cap$.

$\begin{array}{r@{\:=\:}l} \mathcal{M}_1 \cap \mathcal{M}_2& \left(X, \inf \left\{f_1, f_2\right\}\right) \\ & \mathcal{M}_2 \cap \mathcal{M}_1\end{array}$

Associativity of $\cup$.

$\begin{array}{r@{\:=\:}l} \mathcal{M}_1 \cup \left(\mathcal{M}_2 \cup \mathcal{M}_3\right) & \left(X, \sup \left\{f_1, \sup\left\{f_2, f_3\right\}\right\}\right) \\ & \left(X, \sup\left\{f_1, f_2, f_3\right\}\right) \\ & \left(X, \sup \left\{\sup\left\{f_1, f_2\right\}, f_3\right\}\right) \\ & \left(\mathcal{M}_1 \cup\mathcal{M}_2\right) \cup \mathcal{M}_3\end{array}$

Commutativity of $\cup$.

$\begin{array}{r@{\:=\:}l} \mathcal{M}_1 \cup \mathcal{M}_2& \left(X, \sup \left\{f_1, f_2\right\}\right) \\ & \mathcal{M}_2 \cup \mathcal{M}_1\end{array}$

Proposition 2: The operations $\cap$ and $\cup$ on $\mathbf{MSet}_X$ are idempotent.

Proof:

Let $\mathcal{M}\in \mathbf{MSet}_X$.

Idempotence of $\cap$.

$\begin{array}{r@{\:=\:}l} \mathcal{M} \cap \mathcal{M}& \left(X, \inf \left\{f, f\right\}\right) \\ & \left(X, f\right) \\ & \mathcal{M}\end{array}$

Idempotence of $\cup$.

$\begin{array}{r@{\:=\:}l} \mathcal{M} \cup \mathcal{M}& \left(X, \sup \left\{f, f\right\}\right) \\ & \left(X, f\right) \\ & \mathcal{M}\end{array}$

The other two operations—sum and product—are not idempotent. One counterexample is the multiset $\mathcal{M} = \left\{a^3\right\}$, for which we have

$\mathcal{M}\uplus\mathcal{M} = \left\{a^6\right\} \neq \mathcal{M}$

and

$\mathcal{M}\:\cdot\!\!\!\!\cup\:\mathcal{M} = \left\{a^9\right\} \neq \mathcal{M}$.

## Multiset intersection

May 26, 2008

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.

## Infima, suprema, and well-orders

May 21, 2008

In the last couple of posts about multisets, we’ve looked at two types of operations we can perform on the class $\mathbf{MSet}_X.$ Sums and products of multisets are defined in terms of sums and products on the class $\mathbf{Card}.$ When we talked about the characteristic function as a way to represent the subsets of a given set, we also considered what happens when we take the maximum and minimum values of the function. This gave us another way to represent intersections and unions of subsets in $\mathbf{SSet}_X,$ which we’re now going to adapt to the context of multisets.

When we discussed cardinals for the first time, we began by taking

1. $\left|A\right| \leq \left|B\right|$ to mean that there exists an injective (one-to-one) mapping of sets $A\to B;$ and
2. $\left|A\right| = \left|B\right|$ to mean that there exists a bijective (one-to-one and onto) mapping of sets $A\to B.$

Partial orders: reflexive and irreflexive

There are two common, non-equivalent definitions for a partial order on a set. The two are related in precisely the way one would expect from considering the normal order relations $<$ and $\leq$ on the real numbers.

A reflexive partial order on a class $X$ is a relation on $X$ that is reflexive, transitive, and antisymmetric. An arbitrary reflexive partial order is usually written as $\leq.$ This may also be called a non-strict or weak partial order.

An irreflexive partial order on a class $X$ is a relation on $X$ that is irreflexive and transitive. An arbitrary irreflexive partial order is usually written as $<.$ This may also be called a strict or strong partial order. Irreflexive partial orders are necessarily asymmetric.

(Since we’re using results about cardinals rather than discussing the theory of cardinals, I’m still going to sidestep the construction that justifies a number of assertions about them. I might put together a series of posts on that subject sometime later.) The class $\mathbf{Card}$ admits a (total, reflexive) order that is consistent with these ideas. That is, $\left(\mathbf{Card}, \leq\right)$ is

reflexive
$\kappa\leq\kappa$ for all $\kappa\in\mathbf{Card};$
transitive
$\kappa\leq\lambda \wedge \lambda\leq\nu \:\Rightarrow\: \kappa\leq\nu$ for all $\kappa,\lambda,\nu\in\mathbf{Card};$
antisymmetric
$\kappa\leq\lambda \wedge \lambda\leq\kappa \:\Rightarrow\: \kappa = \lambda$ for all $\kappa,\lambda\in\mathbf{Card};$ and
total
$\kappa\leq\lambda \vee \lambda\leq\kappa$ for all $\kappa,\lambda\in\mathbf{Card}.$

The last property is often expressed by saying that every pair of cardinals are comparable. The pair $\left(\mathbf{Card}, \leq\right)$ is a special case of a (reflexive) partially-ordered class. The relation $\leq$ in such a class is reflexive, transitive, and antisymmetric, but not necessarily total.

We need just a bit more of the vocabulary of partially-ordered classes.

Definition

Let $\mathcal{X} = \left(X,\leq\right)$ be a reflexive partially-ordered class, $A\subseteq X,$ and $L_A = \left\{x\in X \:|\: \left(\forall a\in A\right)x\leq a\right\}.$ $l\in L_A$ is called a lower bound of $A$ in $\mathcal{X}.$ If, furthermore, $x\leq l$ for all $x\in L_A$, then $l$ is called the infimum of $A$ and is denoted $\inf{A}$.

In general, there is no guarantee that either a lower bound or an infimum exist. If $\inf{A}$ exists, however, it is unique. (To see this, consider what happens if there are two infima for a particular set.) We also have the following dual relationship:

Definition

Let $\mathcal{X} = \left(X,\leq\right)$ be a reflexive partially-ordered class, $A\subseteq X,$ and $U_A = \left\{x\in X \:|\: \left(\forall a\in A\right)a\leq x\right\}.$ $u\in U_A$ is called an upper bound of $A$ in $\mathcal{X}.$ If, furthermore, $u\leq x$ for all $x\in U_A,$ then $u$ is called the supremum of $A$ and is denoted $\sup{A}.$

As with lower bounds and infima, upper bounds and the supremum do not necessarily exist, and the supremum is unique whenever it does exist.

$\left(\mathbf{Card}, \leq\right)$ has an additional property (at least in NBG set theory, including the axiom of choice): for every subclass $X \subseteq\mathbf{Card},$ $\inf X$ exists. Since $\leq$ has this property and is a total order on $\mathbf{Card},$ it well-orders $\mathbf{Card},$ and the partially-ordered class is said to be well-ordered.