多重集

多重集就是允许重复元素的集合.

这样的话, $\{1,2,1\}$ 和 $\{1,2\}$ 就是不同的多重集, 但 $\{1,2,1\}$ 和 $\{1,1,2\}$ 是同一个多重集.

1定义

定义 1.1. 多重集是二元组 $(X,{\mu }_X)$, 其中:

•

$X$ 是集合,

•	${\mu }_X$ 是从 $X$ 到基数的映射. 对于元素 $x\in X$, ${\mu }_X(x)$ 是它的重数.

定义 1.2. 多重集 $(X,{\mu }_X)$ 的势为所有元素的重数之和.

在可数或者有限的情况下, 多重集有如下的等价定义:

定义 1.3. 设 $X$ 是集合. 多重集是 $X$ 上的序列商掉如下关系生成的等价关系:

$$(x_1,x_2,x_3,\cdots )\sim (x_2,x_1,x_3,\cdots )$$

若该序列有限, 则对应的多重集有限, 若该序列可数, 则对应的多重集可数.

2常用操作

•	多重集 $(X,{\mu }_X),(Y,{\mu }_Y)$ 的交集为: $$\left(X\cap Y,x\mapsto \min ({\mu }_X(x),{\mu }_Y(x))\right)$$

•	多重集 $(X,{\mu }_X),(Y,{\mu }_Y)$ 的并集为: $$\left(X\cup Y,x\mapsto \max ({\mu }_X(x),{\mu }_Y(x))\right)$$

•	多重集 $(X,{\mu }_X),(Y,{\mu }_Y)$ 的不交并为: $$\left(X\cup Y,x\mapsto {\mu }_X(x)+{\mu }_Y(x)\right)$$

•	多重集 $(X,{\mu }_X),(Y,{\mu }_Y)$ 的积为: $$\left(X\cap Y,x\mapsto {\mu }_X(x)\times {\mu }_Y(x)\right)$$

定义 2.1. 设 $(<)\subset X\times X$ 为集合 $X$ 上的严格偏序 (即不满足自反性). 定义 $<$ 的多重集扩展, 记作 ${<}_{\mu }$, 为多重集之间的二元关系, 且 $(X,{\mu }_X){<}_{\mu }(X,{\mu }_X^{\prime })$ 需要满足如下条件:

•	${\mu }_X\ne {\mu }_X^{\prime }$,

•	对于任意 $x\in X$, 如果 ${\mu }_X^{\prime }(x)<{\mu }_X(x)$, 那么必须存在 $y\in X$ 使得 ${\mu }_X(y)<{\mu }_X^{\prime }(y)$.

该关系又叫做 $R$ 的 Dershowitz–Manna 序.

如上关系可以这样直观地理解: $M^{\prime }{<}_{\mu }M$ 的意思就是可以通过将 $M$ 中的部分元素替换为有限数量个更小的元素来得到 $M^{\prime }$.

定理 2.2. 若 $<$ 是良基关系, 那么它的多重集扩展也是良基关系.

3相关概念

•

线性逻辑

术语翻译

多重集 • 英文 multiset

重数 • 英文 multiplicity