示性函数

普通集合的示性函数

对于普通集合 $S$ 与全集 $U$，定义函数 $\mathbf{1}_S: U \to \{0, 1\}$

$$\mathbf{1}_S(x) = \begin{cases} 1, & x \in S, \\ 0, & x \notin S, \end{cases}$$

称 $\mathbf{1}_S$ 为 $S$ 的示性函数.

多重集的示性函数

在多重集中，示性函数代表了元素的重数，它是非负整数.

而在广义多重集中，示性函数可以扩展到实数.

方便起见，以下用 $S=\{x_1: c_1, \dots, x_n: c_n\}$ 来代表 $\mathbf{1}_S(x) = \begin{cases} c_1, & x = x_1, \\ &\vdots \\ c_n, & x=x_n. \end{cases}$

加法与数乘

定义

$$\begin{aligned} &\mathbf{1}_{S+T}(x) = \mathbf{1}_S(x) + \mathbf{1}_T(x), \\ &\mathbf{1}_{kS}(x) = k\mathbf{1}_S(x), \\ &\mathbf{1}_{-S}(x) = - \mathbf{1}_S(x). \end{aligned}$$

由于借用了实数的加法，自然也满足了相应的运算定律. 零元为 $\emptyset$，因为 $\mathbf{1}_\emptyset(x) = 0$.

[!CAUTION] 注意

以下假定 $U$ 是可数的.

集合的多项式表示与向量表示

有了加法和数乘之后，就有

$$\{x_1: c_1, \dots, x_n: c_n\} = \sum_{i=1}^n c_i\{x_i\}.$$

这称为广义多重集的多项式表示. 通过这种表示，我们可以将多项式的工具引入到多重集的运算.

同样地，可以把 $\{x_i\}$ 当作基底，而用向量 $\vec{c}$ 表示广义多重集. 由此，也可以将线性代数的工具引入多重集的运算.

乘法、单集合的乘法逆元

两个集合间的笛卡尔积定义为 $S\times T = \left\{(x,y) \mid x\in S, y\in S\right\}$，遗憾的是，笛卡尔积不具有结合律，这是因为 $((x, y), z) \ne (x, (y, z))$.

定义一种形式运算 $a, b$，表示取元组. 为了使改良的笛卡尔积有结合律，必须使取元组运算有结合律. 此时，“$,$” 运算可以由全集 $U$ 生成的自由群 $G$ 表示.

注

为了防止混淆，以下 $G$ 内的幂都会添加逗号，用 $a^{,b}$ 表示

于是，可以将改良的笛卡尔积作为广义多重集的乘法. 形式化地，

$$\mathbf{1}_{ST}(x) = \sum_{x = s,t} \mathbf{1}_S(s) \cdot \mathbf{1}_T(T).$$

是一种类似卷积的形式.

广义多重集乘法的单位元 $I=\{e\}$，其中 $e$ 是群 $G$ 的单位元.

形如 $\{x: c\} \quad (c \ne 0)$ 的集合（称为单集合）的乘法逆元是容易确定的，是 $\{x^{,-1}: c^{-1}\}$.

范数

定义

$$\Vert S \Vert = \sum_x | \mathbf{1}_S(x) |.$$

定理

若级数 $\sum_{k=1}^{\infty} \Vert S_k \Vert$ 收敛，则级数 $\sum_{k=1}^{\infty}S_k$ 也收敛.

使用向量表示即可证明.

定理

这个范数拥有次可乘性，即 $\Vert ST \Vert \le \Vert S \Vert \cdot \Vert T \Vert$.

证明

$$\begin{aligned} \Vert ST \Vert &= \sum_x |\mathbf{1}_{ST}(x)| \\ &= \sum_x \left| \sum_{x = s,t} \mathbf{1}_S(s) \cdot \mathbf{1}_T(t) \right| \\ &\le \sum_x \sum_{x = s,t} |\mathbf{1}_S(s)| \cdot |\mathbf{1}_T(t)| \\ &= \sum_s \sum_t |\mathbf{1}_S(s)| \cdot |\mathbf{1}_T(t)| \\ &= \left( \sum_s |\mathbf{1}_S(s)| \right) \left( \sum_t |\mathbf{1}_T(t)| \right) \\ &= \Vert S \Vert \cdot \Vert T \Vert \end{aligned}$$

非单集合的逆元

经典结论

若 $\Vert S \Vert < 1$，则

$$(I-S)^{-1} = \sum_{k=0}^{\infty} S^k.$$

于是对于 $\Vert S \Vert > \Vert T \Vert > 0$，

$$(S+T)^{-1} = (I+S^{-1}T)^{-1} S^{-1} = \sum_{k=0}^{\infty} (-S^{-1}T)^k S^{-1}.$$

逐点收敛

若 $\forall x, \lim_{k\to\infty} \mathbf{1}_{S_k}(x) = \mathbf{1}_S(x)$，则称 $S_k$ 逐点收敛到 $S$.

警告

两个逐点收敛的集合列之积不一定逐点收敛.