§E16.3Möbius 反転

証明.主張 (1)を示す。$w\in[z,y]$とすると$x\le z\le w$と$w\le y$から$w\in[x,y]$であり、$[z,y]\subseteq[x,y]$である。また$x\in[x,y]$である。$x\in[z,y]$と仮定すると$z\le x$が成り立ち、$x\le z$と合わせて反対称律により$x=z$となって仮定に反する。ゆえに$x\notin[z,y]$であり、$[z,y]$は$[x,y]$の真部分集合である。$P$が有限であるから$|[z,y]|<|[x,y]|$である。

主張 (2)を示す。$w\in[x,z]$とすると$x\le w$と$w\le z\le y$から$w\in[x,y]$であり、$[x,z]\subseteq[x,y]$である。$y\in[x,z]$と仮定すると$y\le z$が成り立ち、$z\le y$と合わせて$y=z$となって仮定に反する。ゆえに$y\notin[x,z]$であり、同様に$|[x,z]|<|[x,y]|$である。▨

証明. 和とスカラー倍は各点ごとの演算であるから、$I(P,R)$が$R$-加群であることは$R$が$R$-加群であることから従う。

双線形性を示す。$(x,y)\in\operatorname{Int}(P)$を固定すると

である。第二引数についても、同じ$(x,y)$を固定して

である。スカラー倍については、$r\in R$に対し

である。第二の等号は$R$における分配法則、第三の等号は$R$が可換であることによる。いずれの計算も$[x,y]$上の有限和についてのものであるから、項ごとの変形をそのまま総和へ移すことができる。

結合性を示す。$(x,y)\in\operatorname{Int}(P)$とする。定義を二度用いると

となる。ここで最後の和は、$x\le z\le w\le y$を満たす対$(z,w)$の全体にわたる。同様に

であり、和の走る範囲は同じく$x\le z\le w\le y$を満たす対の全体である。いずれも有限和であるから、二つの式は等しい。

単位元であることを示す。$(\delta*f)(x,y)=\sum_{z\in[x,y]}\delta(x,z)f(z,y)$において、$\delta(x,z)$は$z=x$のときだけ$1$であり、他の$z$では$0$である。ゆえに$(\delta*f)(x,y)=f(x,y)$である。$(f*\delta)(x,y)$についても、$\delta(z,y)$が$z=y$のときだけ$1$であることから$f(x,y)$を得る。▨

証明. 必要性。$g\in I(P,R)$が$f*g=\delta$を満たすとする。$x\in P$に対し$[x,x]=\{x\}$であるから$f(x,x)g(x,x)=\delta(x,x)=1$であり、$R$が可換であることから$f(x,x)$は可逆である。

十分性。すべての$x$で$f(x,x)$が可逆であるとする。$g\colon\operatorname{Int}(P)\to R$を、区間$[x,y]$の要素数$n=|[x,y]|$についての強い帰納法で定める。

$n=1$のとき$x=y$であり、$g(x,x)=f(x,x)^{-1}$と定める。

$n\ge2$のとき$x<y$である。$x<z\le y$を満たす各$z$について補題 1.2 (1)により$|[z,y]|<n$であるから、$g(z,y)$はすでに定まっている。そこで

と定める。この定義により、$x<y$のとき

であり、$x=y$のとき$(f*g)(x,x)=f(x,x)f(x,x)^{-1}=1=\delta(x,x)$である。ゆえに$f*g=\delta$である。

同様に$h\colon\operatorname{Int}(P)\to R$を、$h(x,x)=f(x,x)^{-1}$とし、$x<y$のとき

と定める。$x\le z<y$のとき補題 1.2 (2)により$|[x,z]|<|[x,y]|$であるから、この定義も区間の要素数についての強い帰納法として正当である。同じ計算により$h*f=\delta$である。

一致と一意性。命題 1.4の結合性と単位元の性質により

である。ゆえに$g$は両側逆元である。$g_1,g_2$がともに両側逆元ならば、同じ計算で$g_1=g_1*(f*g_2)=(g_1*f)*g_2=g_2$となるので一意である。▨

証明.$\mu*\zeta=\delta$を書き下すと、$(x,y)\in\operatorname{Int}(P)$に対し

である。$x=y$のときこれは$\mu(x,x)=1$を与え、$x<y$のとき$z=y$の項を移項すると主張 (1)を得る。同様に$\zeta*\mu=\delta$を書き下すと$\sum_{z\in[x,y]}\mu(z,y)=\delta(x,y)$であり、$z=x$の項を移項すると主張 (2)を得る。

一意性を示す。主張 (1)の形の漸化式を満たす二つの関数$\mu_1,\mu_2$を取り、$|[x,y]|$についての強い帰納法で$\mu_1(x,y)=\mu_2(x,y)$を示す。$|[x,y]|=1$のとき両者は$1$である。$|[x,y]|\ge2$のとき、漸化式の右辺に現れる$z$は$z\ne y$を満たすので補題 1.2 (2)により$|[x,z]|<|[x,y]|$であり、帰納法の仮定から$\mu_1(x,z)=\mu_2(x,z)$である。ゆえに右辺どうしが等しく$\mu_1(x,y)=\mu_2(x,y)$である。主張 (2)についても同様である。▨

証明. まず$\theta(x)=x'$かつ$\theta(y)=y'$である。実際、$x$は$[x,y]$の最小元である。$u'\in[x',y']$を任意に取ると、$\theta$が全射であるから$u'=\theta(u)$を満たす$u\in[x,y]$が存在し、$x\le u$と$\theta$が順序を保つことから$\theta(x)\le'u'$である。ゆえに$\theta(x)$は$[x',y']$の最小元であり、最小元は反対称律により一意であるから$\theta(x)=x'$である。$y$が$[x,y]$の最大元であることから、同じ議論で$\theta(y)=y'$を得る。

$|[x,y]|$についての強い帰納法で示す。$|[x,y]|=1$のとき$x=y$であり、$\theta$が全単射であることから$x'=y'$である。両辺とも$1$である。

$|[x,y]|\ge2$とする。$z\in[x,y]$、$z\ne y$に対し、$\theta$の制限は$[x,z]$から$[x',\theta(z)]$への順序同型を与える。実際、$u\in[x,z]$と$\theta(u)\in[x',\theta(z)]$が同値であることは$\theta$が順序同型であることから従う。補題 1.2 (2)により$|[x,z]|<|[x,y]|$であるから、帰納法の仮定により$\mu_P(x,z)=\mu_{P'}(x',\theta(z))$である。また$z\mapsto\theta(z)$は$\{z\in[x,y]:z\ne y\}$から$\{z'\in[x',y']:z'\ne y'\}$への全単射である。ゆえに命題 2.3 (1)により

である。▨

証明. 仮定のもとで右辺を計算する。$P$が有限であるから、以下の和はすべて有限和である。

である。最後の式で$z$を先に固定して集めると

となる。内側の和は$\zeta(z,x)=1$を補えば$(\zeta*\mu)(z,y)$にほかならず、定義 2.2により$\delta(z,y)$に等しい。ゆえに$z=y$の項だけが残り、右辺は$f(y)$に等しい。

逆を示す。$f(y)=\sum_{x\le y}g(x)\mu(x,y)$がすべての$y$で成り立つとする。同じ計算を$\mu$と$\zeta$を入れ替えて行うと

となる。▨

証明. 仮定のもとで右辺を計算する。

である。内側の和は$\zeta(y,w)=1$を補えば$(\mu*\zeta)(x,w)=\delta(x,w)$に等しい。ゆえに$w=x$の項だけが残り、右辺は$f(x)$である。逆については、定理 3.1の逆と同じ計算で$\zeta*\mu=\delta$を用いればよい。▨

証明.$m=|B\setminus A|$についての強い帰納法で示す。

$m=0$のとき$A=B$であり、命題 2.3により$\mu(A,A)=1=(-1)^{0}$である。

$m\ge1$とする。$A\subseteq C\subseteq B$を満たす$C$は$C=A\cup T$（$T\subseteq B\setminus A$）と一意に書くことができ、$|C\setminus A|=|T|$である。$C\ne B$であることと$T\ne B\setminus A$であることは同値である。帰納法の仮定により、$T\subsetneq B\setminus A$のとき$\mu(A,A\cup T)=(-1)^{|T|}$である。$|T|=k$を満たす$T\subseteq B\setminus A$は$\binom mk$個あるから（§D2.2 命題 3.1）、命題 2.3 (1)により

である。二項定理（§D2.2 定理 5.1）を$x=-1$、$y=1$として用いると、$m\ge1$のとき

であるから$\sum_{k=0}^{m-1}\binom mk(-1)^{k}=-(-1)^{m}$である。ゆえに$\mu(A,B)=(-1)^{m}$である。▨

証明.$P=2^{[n]}$を包含で順序づけ、$R=\Z$とする。$a\in X$に対し$I(a)=\{i\in[n]:a\in A_i\}$と置くと

である。したがって$X$の元を$I(a)$の値ごとに分類し、加法原理（§D2.2 定理 2.1）を適用すると

となる。定理 3.2を$f=N_{=}$、$g=N_{\supseteq}$として適用すると

であり、命題 4.1により$\mu(S,T)=(-1)^{|T\setminus S|}$である。$S=\emptyset$のとき、左辺はどの$A_i$にも属さない元の個数、すなわち$\bigl|X\setminus\bigcup_{i=1}^{n}A_i\bigr|$であり、右辺は$\sum_{T\subseteq[n]}(-1)^{|T|}\bigl|\bigcap_{i\in T}A_i\bigr|$である。▨

証明.$D_N$は$1$以上$N$以下の整数の部分集合であるから有限集合である。

反射律を示す。正の整数$d$に対し$d=d\cdot1$であるから$d\mid d$である。

推移律を示す。$d\mid e$かつ$e\mid f$とすると、正の整数$k,l$によって$e=dk$、$f=el$と書くことができ、$f=d(kl)$であるから$d\mid f$である。

反対称律を示す。$d\mid e$かつ$e\mid d$とすると、正の整数$k,l$によって$e=dk$、$d=el$と書くことができ、$d=dkl$である。$d>0$であるから$kl=1$であり、$k$と$l$は正の整数であるから$k=l=1$である。ゆえに$d=e$である。

以上により$(D_N,\mid)$は§D2.5 定義 3.1の意味の半順序集合であり、台集合は有限である。▨

証明.$c\in[d,e]$とすると$d\mid c$かつ$c\mid e$である。$c/d$は正の整数であり、$e/d=(c/d)\cdot(e/c)$であるから$(c/d)\mid m$である。ゆえに$\theta$は$D_m$へ値を取る。逆に$u\mid m$ならば$c=du$は$d\mid c$を満たし、$e=d m=c\cdot(m/u)$より$c\mid e$であるから$c\in[d,e]$である。$u\mapsto du$と$\theta$は互いに逆であるから$\theta$は全単射である。

順序を保つことを示す。$c,c'\in[d,e]$とする。$c\mid c'$ならば$c'=ck$と書くことができ、$c'/d=(c/d)k$であるから$(c/d)\mid(c'/d)$である。逆に$(c/d)\mid(c'/d)$ならば$c'/d=(c/d)k$と書くことができ、両辺に$d$を掛けて$c'=ck$を得るので$c\mid c'$である。ゆえに$\theta$は順序同型である。▨

証明.$k$を固定する。命題 5.3を$D_k$の中で$d=1$、$e=c$（$c\mid k$）として適用すると$\mu_{D_k}(1,c)=\mathbf m(c)$である。定義 2.2により$\mu*\zeta=\delta$であるから、$D_k$において

となる。ここで$D_k$における区間$[1,k]$が$D_k$全体に一致することを用いた。$k=1$のとき右辺は$1$であり$\mathbf m(1)=1$を得る。$k\ge2$のとき右辺は$0$である。

一意性を示す。$k$についての強い帰納法による。$k=1$では値が$1$に定まる。$k\ge2$では$\mathbf m(k)=-\sum_{c\mid k,\ c<k}\mathbf m(c)$であり、右辺に現れる$c$は$k$より小さいので帰納法の仮定により定まっている。▨

証明.命題 5.2により$D_N$は有限半順序集合であるから、定理 3.1を$P=D_N$へ適用することができ、$f(e)=\sum_{d\mid e}g(d)\mu_{D_N}(d,e)$である。系 5.4により$\mu_{D_N}(d,e)=\mathbf m(e/d)$である。▨