莫比烏斯反演

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

目錄

• 莫比烏斯反演
  • 偏序集
    • 基本定義
    • 子偏序集
    • 偏序集間的運算
    • 常見的偏序集
  • 關聯代數
    • 代數定義
    • Zeta 函數
    • 莫比烏斯反演
  • 例子
    • 和差分
    • 排容原理
    • 數論
  • 參考文獻

偏序集

基本定義

對於集合

$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$ 就組成了偏序集

$⟨P,\le ⟩$，簡稱 poset。

這篇文將直接用

$P$ 同時表示偏序集結構

$⟨P,\le ⟩$ 以及它的奠基集合

$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⋖y$，
  $x$ 被
  $y$ 覆蓋：代表有
  $x<y$ 且不存在其他
  $z\in P$ 滿足
  $x<z<y$。
• 最小值
  $\hat{0}$：代表對於任意
  $x\in P$ 都有
  $\hat{0}\le x$。
• 最大值
  $\hat{1}$：代表對於任意
  $x\in P$ 都有
  $x\le \hat{1}$。

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

如果

$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⟺y=x\vee y\text{ 且 }x=x\wedge y.$$

這兩個東西好像很難記憶…

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

如果偏序集

$P$ 中的任兩個元素都有最大上界與最小下界，我們就說

$⟨P,\vee ,\wedge ⟩$ 是一個格；如果任兩個元素都有最大上界，或者任兩個元素都有最小下界，我們就說

$⟨P,\vee ⟩$ 或

$⟨P,\wedge ⟩$ 是一個半格。

我們可以公理地用

$\vee$ 與

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

子偏序集

對於偏序集

$P$ 與

$Q$，當函數

$\varphi :P\to Q$ 對於所有

$x{\le }_{P}y$ 都有

$\varphi (x){\le }_Q\varphi (y)$，則說

$\varphi$ 是

$P$ 到

$Q$ 的保序映射或序同態。

保序映射的英文是 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$ 上的反鏈。

偏序集間的運算

對於偏序集

$P$ 與

$Q$，如果它們之間的保序映射

$\varphi :P\to Q$ 是個雙射函數，並且反函數

${\varphi }^{-1}:Q\to P$ 也是一個保序映射，也就是說

$$x{\le }_{P}y⟺\varphi (x){\le }_Q\varphi (y),$$
我們就稱函數

$\varphi$ 是

$P$ 到

$Q$ 的序同構。

當偏序集

$P$ 與

$Q$ 之間存在這麼一個序同構，我們也會說這兩個偏序集是同構的，並記為

$P\cong Q$。

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

對於偏序集

$P$ 與

$Q$。

定義

$P+Q:=⟨P\uplus Q,{\le }_{\mathrm{\Sigma }}⟩$，稱為

$P$ 與

$Q$ 的直和或互斥聯集，其中

$$x{\le }_{\mathrm{\Sigma }}y⟺x{\le }_{P}y\text{ 或 }x{\le }_{Q}y.$$

定義

$P\times Q:=⟨P\times Q,{\le }_{\mathrm{\Pi }}⟩$，稱為

$P$ 與

$Q$ 的直積或笛卡兒積，其中

$$(x_1,y_1){\le }_{\mathrm{\Pi }}(x_2,y_2)⟺x_1{\le }_P{x}_2\text{ 且 }{y}_1{\le }_Q{y}_2.$$

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

對於偏序集

$P$，我們用

$nP$ 表示

$n$ 個

$P$ 的直和，也用

$P^n$ 表示

$n$ 個

$P$ 的直積。
從同構的意義上來看，偏序集之間的直和與直積有結合律與交換律，也有分配律

$$P\times (Q+R)\cong (P\times Q)+(P\times R).$$

常見的偏序集

我們用

$\mathbb{N}:=\{0,1,2,\dots \}$ 表示自然數集。

鏈

在自然數

$\mathbb{N}$ 中我們有常用的全序關係，它定義為

$x<x+1$，也就是說

$⟨\mathbb{N},\le ⟩$ 是全序集。
在

$\mathbb{N}$ 之中我們特別把區間

$[0,n]$ 寫作

$C_n$，它是

$\mathbb{N}$ 的子全序集，稱為長度

$n$ 的鍊。

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

布林代數

集合間的包含關係

$\subseteq$ 是偏序關係，其中空集合

$\varnothing$ 是最小值。
對於集合

$S$，考慮它的冪集合

$2^S$，也就是搜集

$S$ 所有子集的集合，那配上包含關係就是個偏序集，我們將它記為

$B_S=⟨2^S,\subseteq ⟩$。
如果

$S=\{1,2,\dots ,n\}\subseteq \mathbb{N}$，那麼我們就特別將

$B_S$ 記為

$B_n$。

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

整除關係

自然數之間除了一般的大小關係，整除關係也是一個偏序關係，它定義為

$x\mid kx$。
我們將這個偏序集記為

$D=⟨\mathbb{N},\mid ⟩$。
在

$D$ 之中我們特別把區間

$[1,n]$ 記為

$D_n$，所以

$D_n$ 搜集了所有

$n$ 的正因數。

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

關聯代數

代數定義

對於局部有限的偏序集

$P$，我們令

$\mathrm{Int}(P)$ 搜集所有

$P$ 上的區間。
注意這些區間

$[x,y]\in \mathrm{Int}(P)$ 都不是空集合（其中的

$x$ 與

$y$ 必須先可比較）。
對於任意的函數

$f:\mathrm{Int}(P)\to K$，我們直接用

$f(x,y)$ 來代表

$f([x,y])$。

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

對於局部有限的偏序集

$P$ 與體

$⟨K,+,\cdot ⟩$，搜集所有函數

$f:\mathrm{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)}$。

所謂

$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^{\mathrm{Int}(P)}$ 再配備上乘法

$\ast$ 後的結構。

由於

$P$ 是局部有限的，上述乘法定義中的總和是有限和，因此是定義良好的。
我們可以看出這個乘法是有結合律的，並且有乘法單位元素

$\delta$ 定義為

$$\delta (x,y)=\{\begin{array}{ll}1,& \text{若 }x=y\\ 0,& \text{若 }x\ne y\text{。}\end{array}$$

如果

$P$ 是有限的，我們可以將它的元素編號為

$x_1,\dots ,x_n$，使得當

$x_i<x_j$ 時都有

$i<j$。
接著考慮

$K$ 上的所有上三角矩陣

$M=(m_{ij})$，其中當

$x_i\nleqq x_j$ 時有

$m_{ij}=0$。
那麼不難看出這些上三角矩陣構成的矩陣代數同構於

$I(P,K)$，矩陣乘法就對應到

$I(P,K)$ 的乘法，而單位矩陣則對應到

$\delta$。

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

對於

$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$ 的，而不是反函數。

如果

$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<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$ 有乘法右反元素時同時會有乘法左反元素，此時這兩者必須相等。

Zeta 函數

在

$I(P,K)$ 中有一個特殊元素名叫 zeta 函數

$\zeta$，定義為

$$\zeta (x,y)=1\text{對所有 }[x,y]\in \mathrm{Int}(P)\text{。}$$

根據乘法定義可以看出

${\zeta }^2(x,y)=\sum _{x\le z\le y}1=\mathrm{\#}[x,y]$。
更一般地有

$${\zeta }^k(x,y)=\sum _{x=x_0\le x_1\le \cdots \le x_k=y}1,$$
也就是計算區間

$[x,y]$ 內有多少條鏈是

$x=x_0\le x_1\le \cdots \le x_k=y$。
另一方面也有

$$(\zeta -\delta )(x,y)=\{\begin{array}{ll}0,& \text{若 }x=y\\ 1,& \text{若 }x<y\text{。}\end{array}$$
因此

$(\zeta -\delta {)}^k(x,y)$ 就計算區間

$[x,y]$ 內有多少條鏈是

$x=x_0<x_1<\cdots <x_k=y$。

考慮

$2\delta -\zeta \in I(P,K)$，我們有

$$(2\delta -\zeta )(x,y)=\{\begin{array}{ll}1,& \text{若 }x=y\\ -1,& \text{若 }x<y\text{。}\end{array}$$
根據前面的命題我們知道

$2\delta -\zeta$ 有乘法反元素，並且可以驗證有

$$(2\delta -\zeta {)}^{-1}=\sum _{k=0}^{\mathrm{\infty }}(\zeta -\delta {)}^k=\delta +(\zeta -\delta )+(\zeta -\delta {)}^2+\cdots .$$
也就是說

$(2\delta -\zeta {)}^{-1}(x,y)$ 就計算區間

$[x,y]$ 內總共有多少條鏈。

如果我們把

$\delta$ 寫成

$1$，這就跟

$(1-x{)}^{-1}=1+x+x^2\cdots$ 道理一樣。

莫比烏斯反演

根據前面的命題，我們知道 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).}}$$

令

$f,g:P\to K$，那麼

$$\text{對於所有 }y\in P\text{，}g(y)=\sum _{z\le y}f(z),$$
若且唯若

$$\text{對於所有 }y\in P\text{，}f(y)=\sum _{z\le y}g(z)\cdot \mu (z,y).$$

令

$K^P$ 搜集所有函數

$P\to K$，則

$K^P$ 是

$K$ 上的向量空間。
現在考慮將

$I(P,K)$ 右作用在

$K^P$ 上，其中對於任意

$f\in R^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⟺f=g\mu .$$

如果

$\mathrm{\#}P=n$ 是有限的，我們就可以將

$I(P,K)$ 中的元素視為

$n\times n$ 的三角矩陣。
在這個情況下，上述的證明就是說那些

$K^P$ 中的函數能視為

$K^n$ 空間中的向量而能乘上

$I(P,K)$ 中的三角矩陣，因此我們就能直接從矩陣運算看出莫比烏斯反演。

這邊也可以用純計算去證明，比如其中一邊是

$$\begin{array}{rl}\sum _{z\le y}g(z)\cdot \mu (z,y)& =\sum _{z\le y}\mu (z,y)\cdot (\sum _{x\le z}f(x))\\ & =\sum _{x\le y}f(x)\cdot (\sum _{x\le z\le y}\mu (z,y))\\ & =\sum _{x\le y}f(x)\cdot \delta (z,y)\\ & =f(y).\end{array}$$

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

令

$f,g:P\to K$，那麼

$$\text{對於所有 }x\in P\text{，}g(x)=\sum _{x\le z}f(z),$$
若且唯若

$$\text{對於所有 }x\in P\text{，}f(x)=\sum _{x\le z}\mu (x,z)\cdot g(z).$$

跟前一個證明一模一樣，只是改考慮成定義如下的左作用

$$(\xi f)(x):=\sum _{x\le z}\xi (x,z)\cdot f(z).$$

例子

和差分

排容原理

數論

參考文獻

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

• R. P. Stanley, Enumerative Combinatorics, Volume 1, 2011.