{%hackmd @YuRen-tw/article-theme %}

# 莫比烏斯反演

> 礙於技術限制，各項公式未能個別標註出處。
> 參考文獻統一排列於「[參考文獻](#Reference)」節。
> 學術引用時務必完整標示所有文獻。

> :::spoiler 目錄
> [TOC]
> :::

## 偏序集
### 基本定義

<div class="definition" data-info="偏序集">

對於集合 $P$，若 $P$ 上的二元關係 $\le$ 滿足以下條件，則稱為 $P$ 上的偏序關係：
- 自反性：對於任意 $x \in P$ 都有 $x \le x$。
- 反對稱性：若 $x \le y$ 且 $y \le x$，則 $x = y$。
- 遞移性：若 $x \le y$ 且 $y \le z$，則 $x \le z$。

集合 $P$ 配備上偏序關係 $\le$ 就組成了偏序集 $\langle P, \le\rangle$，簡稱 poset。
</div>

這篇文將直接用 $P$ 同時表示偏序集結構 $\langle P, \le\rangle$ 以及它的奠基集合 $P$，而有需要時也會用 $\le_P$ 表示它的偏序關係。

> 同時表示結構與奠基集合是數學上常有的符號濫用。

要注意偏序集內的任意兩個元素並不總是有關係。
對於偏序集 $P$ 內的元素 $x, y \in P$，依照它們的關係我們有以下符號與術語：
- $x$ 與 $y$ 可比較：代表有 $x \le y$ 或 $y \le x$。
- $x < y$：代表有 $x \le y$ 且 $x \ne y$。
- $x \lessdot y$，$x$ 被 $y$ 覆蓋：代表有 $x < y$ 且不存在其他 $z \in P$ 滿足 $x < z < y$。
- 最小值 $\hat0$：代表對於任意 $x \in P$ 都有 $\hat0 \le x$。
- 最大值 $\hat1$：代表對於任意 $x \in P$ 都有 $x \le \hat1$。

> 最小值跟最大值不一定會存在，但如果存在，根據反對稱性它必定是唯一的。

如果 $P$ 之中的任兩個元素都可比較，那我們就稱 $P$ 是全序集或線性序集。

#### 格
如果 $x \le z$ 且 $y \le z$，就稱 $z$ 是 $x$ 與 $y$ 的上界；
如果進一步地對於其他 $x$ 與 $y$ 的上界 $w$ 都有 $z \le w$，就稱 $z$ 是 $x$ 與 $y$ 的最小上界。
我們能也類似地定義下界與最大下界。

如果 $x$ 與 $y$ 有最小上界，那它必定是唯一的，我們將它記為 $x \vee y$。
如果 $x$ 與 $y$ 有最大下界，那它也會是唯一的，我們將它記為 $x \wedge y$。
於是我們有
\\[
x \le y \iff \text{$y = x \vee y$ 且 $x = x \wedge y$}.
\\]

> - $x \vee y$：最大上界、接，英文是 supremum、join
> - $x \wedge y$：最小下界、交，英文是 infimum、meet

> 這兩個符號好像很難記憶……

如果偏序集 $P$ 中的任兩個元素都有最大上界與最小下界，我們就說 $\langle P, \vee, \wedge\rangle$ 是一個格；如果任兩個元素都有最大上界，或者任兩個元素都有最小下界，我們就說 $\langle P, \vee\rangle$ 或 $\langle P, \wedge\rangle$ 是一個半格。

我們可以公理地用 $\vee$ 與 $\wedge$ 運算去定義格這種代數結構，並從格反過來定義偏序集。
但這些超出了這篇文的需要，我們在這邊選擇不這麼做。

### 子偏序集

<div class="definition" data-info="保序映射">

對於偏序集 $P$ 與 $Q$，當函數 $\phi\colon P \to Q$ 對於所有 $x \le_P y$ 都有 $\phi(x) \le_Q \phi(y)$，則說 $\phi$ 是 $P$ 到 $Q$ 的保序映射或序同態。
</div>

> 保序映射的英文是 isotone mapping 或 order-preserving mapping。

對於偏序集 $P$ 與 $Q$，如果 $P \subseteq Q$ 且存在 $P$ 到 $Q$ 的保序映射，那我們就說 $P$ 是 $Q$ 的弱子偏序集。
特別地，當 $P = Q$ 時，我們就說 $Q$ 是 $P$ 的細分；
而若 $Q$ 又進一步是全序集時，我們就說 $Q$ 是 $P$ 的線性擴張或拓撲排序。

對於偏序集 $P$ 與 $Q$，如果 $P \subseteq Q$ 且 $P$ 與 $Q$ 配備相同的偏序關係（作用在 $P$ 上相同），則我們說 $P$ 是 $Q$ 的導出子偏序集。
當我們直接說子偏序集時，指的就是導出子偏序集。

我們對於偏序集 $P$ 中可比較的 $x$ 與 $y$ 定義區間 $[x, y] := \{ z \in P : x \le z \le y \}$，它是 $P$ 的子偏序集。
當 $P$ 上的所有區間都是有限集合時，我們就稱 $P$ 是局部有限的。

如果偏序集 $P$ 的子偏序集 $C$ 是全序集，我們就稱 $C$ 是 $P$ 上的鏈。
而如果偏序集 $P$ 的子集 $A$ 內元素兩兩不可比較，我們就稱 $A$ 是 $P$ 上的反鏈。

### 偏序集間的運算

<div class="definition" data-info="序同構">

對於偏序集 $P$ 與 $Q$，如果它們之間的保序映射 $\phi\colon P \to Q$ 是個雙射函數，並且反函數 $\phi^{-1}\colon Q \to P$ 也是一個保序映射，也就是說
\\[
x \le_P y \iff \phi(x) \le_Q \phi(y),
\\]
我們就稱函數 $\phi$ 是 $P$ 到 $Q$ 的序同構。

當偏序集 $P$ 與 $Q$ 之間存在這麼一個序同構，我們也會說這兩個偏序集是同構的，並記為 $P \cong Q$。
</div>

> 當我們談論的東西只牽涉到偏序關係時，我們就會將序同構的兩個偏序集視為相等，它們就只是同一個本尊的不同分身。

<div class="definition" data-info="直和與直積">

對於偏序集 $P$ 與 $Q$。

定義 $P + Q := \langle P \uplus Q, \le_\Sigma\rangle$，稱為 $P$ 與 $Q$ 的直和或互斥聯集，其中
\\[
x \le_\Sigma y \iff \text{$x \le_P y$ 或 $x \le_Q y$}.
\\]

定義 $P \times Q := \langle P \times Q, \le_\Pi\rangle$，稱為 $P$ 與 $Q$ 的直積或笛卡兒積，其中
\\[
(x_1, y_1) \le_\Pi (x_2, y_2) \iff \text{$x_1 \le_P x_2$ 且 $y_1 \le_Q y_2$}.
\\]
</div>

> 如果考慮由偏序集與保序映射所構成的範疇，那麼的這邊直積與直和的正好就是範疇中的積與餘積。

對於偏序集 $P$，我們用 $nP$ 表示 $n$ 個 $P$ 的直和，也用 $P^n$ 表示 $n$ 個 $P$ 的直積。
從同構的意義上來看，偏序集之間的直和與直積有結合律與交換律，也有分配律 \\[P \times (Q + R) \cong (P \times Q) + (P \times R).\\]

### 常見的偏序集

> 我們用 $\mathbb{N} := \{0, 1, 2, \dotsc\}$ 表示自然數集。

#### 鏈
在自然數 $\mathbb{N}$ 中我們有常用的全序關係，它定義為 $x < x+1$，也就是說 $\langle\mathbb{N}, \le\rangle$ 是全序集。
在 $\mathbb{N}$ 之中我們特別把區間 $[0, n]$ 寫作 $C_n$，它是 $\mathbb{N}$ 的子全序集，稱為長度 $n$ 的鍊。

- 全序集 $\mathbb{N}$ 是局部有限的，有最小值 $\hat0 = 0$。
- 全序集 $C_n$ 是有限的，有最小值 $\hat0 = 0$ 與最大值 $\hat1 = n$。
- 全序集 $C_n$ 是格，其中 $x \vee y = \max(x, y)$ 且 $x \wedge y = \min(x, y)$。
- 若全序集 $P$ 是有限的且 $\#P = n$，則 $P \cong C_{n-1}$。

#### 布林代數
集合間的包含關係 $\subseteq$ 是偏序關係，其中空集合 $\varnothing$ 是最小值。
對於集合 $S$，考慮它的冪集合 $2^S$，也就是搜集 $S$ 所有子集的集合，那配上包含關係就是個偏序集，我們將它記為 $B_S = \langle 2^S, \subseteq\rangle$。
如果 $S = \{1, 2, \dotsc, n\} \subseteq \mathbb{N}$，那麼我們就特別將 $B_S$ 記為 $B_n$。

- 偏序集 $B_S$ 是有限的，有最小值 $\hat0 = \varnothing$ 與最大值 $\hat1 = S$。
- 偏序集 $B_S$ 是格，其中 $x \vee y = x \cup y$ 且 $x \wedge y = x \cap y$，這種格稱為布林代數。
- 如果集合 $S$ 是有限的且 $\#S = n$，則 $B_S \cong B_n \cong (C_1)^n$。

#### 整除關係
自然數之間除了一般的大小關係，整除關係也是一個偏序關係，它定義為 $x \mid kx$。
我們將這個偏序集記為 $D = \langle \mathbb{N}, {}\mid{}\rangle$。
在 $D$ 之中我們特別把區間 $[1, n]$ 記為 $D_n$，所以 $D_n$ 搜集了所有 $n$ 的正因數。

- 偏序集 $D$ 是局部有限的，有最小值 $\hat0 = 1$ 與最大值 $\hat1 = 0$。
- 偏序集 $D_n$ 是有限的，有最小值 $\hat0 = 1$ 與最大值 $\hat1 = n$。
- 偏序集 $D$ 與 $D_n$ 都是格，其中 $x \vee y = \gcd(x,y)$ 且 $x \wedge y = \operatorname{lcm}(x,y)$。
- 在 $D$ 之中，區間 $[x, y] \cong D_{y/x}$。
- 如果 $n = p_1^{e_1}p_2^{e_2} \dotsm p_k^{e_k}$ 是 $n$ 的質因數分解，則 $D_n \cong C_{e_1} \times C_{e_2} \times \dotsb \times C_{e_k}$。

## 關聯代數
### 代數定義

對於局部有限的偏序集 $P$，我們令 $\operatorname{Int}(P)$ 搜集所有 $P$ 上的區間。
注意這些區間 $[x, y] \in \operatorname{Int}(P)$ 都不是空集合（其中的 $x$ 與 $y$ 必須先可比較）。
對於任意的函數 $f\colon \operatorname{Int}(P) \to K$，我們直接用 $f(x, y)$ 來代表 $f([x, y])$。

> 重點是要把定義域限制到可比較的兩個元素，並且區間本身是有限的。

<div class="definition" data-info="關聯代數">

對於局部有限的偏序集 $P$ 與體 $\langle K, +, {}\cdot{} \rangle$，搜集所有函數 $f\colon \operatorname{Int}(P) \to K$ 並配備下列三個運算，就構成 $P$ 在 $K$ 上的關聯代數，記為 $I(P, K)$：
- 係數積：$(af)(x, y) := a \cdot f(x, y)$。
- 加法：$(f + g)(x, y) := f(x, y) + g(x, y)$。
- 乘法（或叫捲積）：$(f \ast g)(x, y) := \displaystyle\sum_{x\le z \le y}f(x, z) \cdot g(z, y)$。
</div>

> 所謂 $K$ 上的代數，就是 $K$ 上的向量空間再配備上一個向量間的乘法；
> 如果你不知道什麼是向量空間，就請先去讀一點線性代數再來讀這篇文。

> 事實上我們可以把係數從體推廣成交換環，但我不想在這裡這麼做。

> 注意到對任何集合 $X$，令 $K^X$ 搜集所有 $X \to K$ 的函數，那麼 $K^X$ 配備下列兩個運算就能構成 $K$ 上的向量空間：
> - 係數積：$(af)(x) := a \cdot f(x)$。
> - 加法：$(f + g)(x) := f(x) + g(x)$。
>
> 而上述的關聯代數 $I(P, K)$ 其實就是 $K^{\operatorname{Int}(P)}$ 再配備上乘法 $\ast$ 後的結構。

由於 $P$ 是局部有限的，上述乘法定義中的總和是有限和，因此是定義良好的。
我們可以看出這個乘法是有結合律的，並且有乘法單位元素 $\delta$ 定義為
\\[
\delta(x, y) = \begin{cases}
1,& \text{若 $x = y$}\\
0,& \text{若 $x \ne y$。}
\end{cases}
\\]

如果 $P$ 是有限的，我們可以將它的元素編號為 $x_1, \dotsc, x_n$，使得當 $x_i < x_j$ 時都有 $i < j$。
接著考慮 $K$ 上的所有上三角矩陣 $M = (m_{ij})$，其中當 $x_i \not\le x_j$ 時有 $m_{ij} = 0$。
那麼不難看出這些上三角矩陣構成的矩陣代數同構於 $I(P, K)$，矩陣乘法就對應到 $I(P, K)$ 的乘法，而單位矩陣則對應到 $\delta$。

> 上述的同構證明留給讀者自己練習。

<div class="theorem proposition">

對於 $f \in I(P, K)$，存在乘法反元素 $f^{-1}$，若且唯若對於所有 $x \in P$ 都有 $f(x, x) \ne 0$。

更進一步地，如果 $f^{-1}$ 存在，那麼 $f^{-1}(x, y)$ 的值只被區間 $[x, y]$ 決定。

> 這裡的 $f^{-1}$ 是滿足 $f \ast f^{-1} = \delta = f^{-1} \ast f$ 的，而不是反函數。
</div>
<div class="proof">

如果 $f \ast g = \delta$，那麼根據乘法定義可知對所有 $x \in P$ 都有 $f(x,x) \cdot g(x,x) = 1$，所以 $f(x,x) \ne 0$。
並且還可知對於 $x \ne y$ 都有
\\[
g(x, y) = (-1)f(x, x)^{-1} \cdot \sum_{x \lt z \le y} f(x, z) \cdot g(z, y).
\\]
所以 $f$ 有乘法右反元素 $g$ 若且唯若 $f(x,x) \ne 0$，並且 $g(x, y)$ 的值可以只靠區間 $[x, y]$ 推算出來。

同樣的道理考慮在 $h \ast f = \delta$ 上，我們也可以得出 $f$ 有乘法左反元素 $h$ 若且唯若 $f(x,x) \ne 0$。
那就代表 $f$ 有乘法右反元素時同時會有乘法左反元素，此時這兩者必須相等。
</div>

### Zeta 函數

<div class="definition" data-info="zeta 函數">

在 $I(P, K)$ 中有一個特殊元素名叫 zeta 函數 $\zeta$，定義為
\\[
\zeta(x, y) = 1 \quad\text{對所有 $[x, y] \in \operatorname{Int}(P)$。}
\\]
</div>

根據乘法定義可以看出 $\zeta^2(x,y) = \sum_{x \le z \le y} 1 = \#[x, y]$。
更一般地有
\\[
\zeta^k(x, y) = \sum_{x = x_0 \le x_1 \le \dotsb \le x_k = y} 1,
\\]
也就是計算區間 $[x,y]$ 內有多少條鏈是 $x = x_0 \le x_1 \le \dotsb \le x_k = y$。
另一方面也有
\\[
(\zeta - \delta)(x, y) = \begin{cases}
0, &\text{若 $x = y$}\\
1, &\text{若 $x < y$。}
\end{cases}
\\]
因此 $(\zeta - \delta)^k(x, y)$ 就計算區間 $[x,y]$ 內有多少條鏈是 $x = x_0 < x_1 < \dotsb < x_k = y$。

考慮 $2\delta - \zeta \in I(P, K)$，我們有
\\[
(2\delta - \zeta)(x, y) = \begin{cases}
1, &\text{若 $x = y$}\\
-1, &\text{若 $x < y$。}
\end{cases}
\\]
根據前面的命題我們知道 $2\delta - \zeta$ 有乘法反元素，並且可以驗證有
\\[
(2\delta - \zeta)^{-1} = \sum_{k=0}^\infty (\zeta - \delta)^k = \delta + (\zeta - \delta) + (\zeta - \delta)^2 + \dotsb.
\\]
也就是說 $(2\delta - \zeta)^{-1}(x, y)$ 就計算區間 $[x,y]$ 內總共有多少條鏈。

> 如果我們把 $\delta$ 寫成 $1$，這就跟 $(1 - x)^{-1} = 1 + x + x^2 + \dotsb$ 是一樣的道理。

### 莫比烏斯反演

根據前面的命題，我們知道 zeta 函數 $\zeta$ 也有乘法反元素，我們稱之為 Möbius 函數並記為 $\mu$。
那麼根據 $\mu\ast\zeta = \delta = \zeta\ast\mu$，可知對所有 $x \in P$ 都有 $\mu(x, x) = 1$，並且對於 $x < y$ 都有
\\[
\displaystyle\sum_{x \le z \le y} \mu(x,z) =
0
= \displaystyle\sum_{x \le z \le y} \mu(z,y).
\\]

<div class="theorem" data-info="莫比烏斯反演">

令 $f,g\colon P \to K$，那麼
\\[
\text{對於所有 $y \in P$，}\quad g(y) = \sum_{z \le y}f(z),
\\]
若且唯若
\\[
\text{對於所有 $y \in P$，}\quad f(y) = \sum_{z \le y}g(z) \cdot \mu(z,y).
\\]
</div>
<div class="proof">

令 $K^P$ 搜集所有函數 $P \to K$，則 $K^P$ 是 $K$ 上的向量空間。
現在考慮將 $I(P, K)$ 右作用在 $K^P$ 上，其中對於任意 $f \in K^P$ 與 $\xi \in I(P, K)$，該作用定義為
\\[
(f \xi)(y) := \sum_{z \le y}f(z) \cdot \xi(z, t).
\\]
則 $I(P, K)$ 將如同 $K^P$ 上線性變換的代數一般。
而原本的命題則變成顯然的
\\[
f \zeta = g \iff f = g\mu.
\\]
</div>

如果 $\#P = n$ 是有限的，我們就可以將 $I(P, K)$ 中的元素視為 $n \times n$ 的三角矩陣。
在這個情況下，上述的證明就是說那些 $K^P$ 中的函數能視為 $K^n$ 空間中的向量而能乘上 $I(P,K)$ 中的三角矩陣，因此我們就能直接從矩陣運算看出莫比烏斯反演。

> 這邊也可以用純計算去證明，比如其中一邊是
> \begin{align*}
> \sum_{z \le y}g(z) \cdot \mu(z,y)
> &= \sum_{z \le y}\mu(z,y) \cdot \Bigl(\sum_{x \le z} f(x)\Bigr)\\
> &= \sum_{x \le y}f(x) \cdot \Bigl(\sum_{x \le z \le y} \mu(z,y)\Bigr)\\
> &= \sum_{x \le y}f(x) \cdot \delta(z,y)\\
> &= f(y).
> \end{align*}

我們也有對偶版的莫比烏斯反演，注意總和底下的條件差異。

<div class="theorem" data-info="莫比烏斯反演，對偶版">

令 $f,g\colon P \to K$，那麼
\\[
\text{對於所有 $x \in P$，}\quad g(x) = \sum_{x \le z}f(z),
\\]
若且唯若
\\[
\text{對於所有 $x \in P$，}\quad f(x) = \sum_{x \le z}\mu(x,z) \cdot g(z).
\\]
</div>
<div class="proof">

跟前一個證明一模一樣，只是改考慮成定義如下的左作用
\\[
(\xi f)(x) := \sum_{x \le z}\xi(x, z) \cdot f(z).
\\]
</div>

## 例子
### 和差分

### 排容原理

### 數論

## 參考文獻
> 礙於技術限制，各項公式未能個別標註出處。
> 參考文獻按數學論文慣例，以字母順序統一排列於下。
> 學術引用時務必完整標示所有文獻。

- R. P. Stanley, *Enumerative Combinatorics*, Volume 1, 2011.