外观
Skip to content 查看源代码：
查看源代码：
set-algebra.md
---
title: 广义多重集上的代数运算
createTime: 2025/8/10
categories:
- study
tags:
- maths
---
## 示性函数
### 普通集合的示性函数
对于普通集合 $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$ 表示.
:::note
为了防止混淆，以下 $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) |.$$
:::note 定理
**若级数 $\sum_{k=1}^{\infty} \Vert S_k \Vert$ 收敛，则级数 $\sum_{k=1}^{\infty}S_k$ 也收敛.**
使用向量表示即可证明.
:::
:::note 定理
这个范数拥有次可乘性，即 $\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}
$$
:::
## 非单集合的逆元
:::note 经典结论
**若 $\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}.
$$
<!-- 若 $\Vert S \Vert = \Vert T \Vert$，则
$$
\begin{aligned}
(2S+T)^{-1} &= \sum_{k=0}^{\infty} (-(2S)^{-1}T)^k (2S)^{-1} \\
&= \sum_{k=0}^{\infty} \left(\frac{1}{2}\right)^{k+1} (-S^{-1}T)^k S^{-1}
\end{aligned}
$$
而
$$
\begin{aligned}
(2S+2T)^{-1} &= (2S+T + T)^{-1} \\
&= \sum_{k=0}^{\infty} (-(2S+T)^{-1}T)^k (2S+T)^{-1} \\
&= \sum_{n=0}^{\infty} \Biggl(-\biggl(\sum_{k=0}^{\infty} \left(\frac{1}{2}\right)^{k+1} (-S^{-1}T)^k S^{-1}\biggr)T \Biggr)^n \left(\sum_{k=0}^{\infty} \left(\frac{1}{2}\right)^{k+1} (-S^{-1}T)^k S^{-1}\right)
\end{aligned}
$$
S(1/2) STS(1/4) STSTS(1/8) STSTSTS(1/16) ...
T
S(1/2) STS(1/4) STSTS(1/8) STSTSTS(1/16) ...
T
S(1/2) STS(1/4) STSTS(1/8) STSTSTS(1/16) ...
T
.
.
.
T
S(1/2) STS(1/4) STSTS(1/8) STSTSTS(1/16) ...
（共 2n+1 行）
产生长度为 L 的字符串的概率？
这是一道 OGF 习题，答案是 $\frac{t/(2-t)}{1-t/(2-t)} = t/(2-2t)$ 的各项系数 $\frac{1}{2}$. -->
## 逐点收敛
若 $\forall x, \lim_{k\to\infty} \mathbf{1}_{S_k}(x) = \mathbf{1}_S(x)$，则称 $S_k$ 逐点收敛到 $S$.
:::caution
两个逐点收敛的集合列之积不一定逐点收敛.
:::
<!--
> [!NOTE] 不太经典的结论
> $\displaystyle(I-S)\sum_{k=0}^{\infty} S^k$ 逐点收敛到 $I$.
若 $ST_k$ 或 $T_kS$ 逐点收敛到 $I$ 且 $T_k$ 逐点收敛到 $T$，则称 $T$ 为 $S$ 的形式逆元.
> [!NOTE] TODO
>
> 形式左逆元也是形式右逆元吗？
于是对于 $\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}.
$$ -->