分配束（をなす集合を始域とする写像の終域上の演算）における包除原理

rogi52.hatenablog.jp
上の記事が興味深かったのでまとめる。

分配束

集合 $L$ 上の二項演算 $\lor,\land$ からなる代数的構造 $(L,\lor,\land)$ が分配束であるとは、 $L$ の任意の元 $a,b,c$ に対して以下の公理が成り立つことである。

可換律　 $a\lor b=b\lor a,\ a\land b=b\land a$
結合律　 $a\lor (b\lor c)=(a\lor b)\lor c,\ a\land (b\land c)=(a\land b)\land c$
吸収律　 $a\lor (a\land b)=a,\ a\land (a\lor b)=a$
分配律　 $a\lor (b\land c)=(a\lor b)\land (a\lor c),\ a\land (b\lor c)=(a\land b)\lor (a\land c)$

上の公理からは以下の冪等律が導かれる。

冪等律　 $a\lor a=a,\ a\land a=a$

主張

分配束をなす集合 $L$ を始域とする写像 $f$ の終域上に、可換律と結合律が成り立ち逆元をもつ演算 $+$ が定義されているとする。逆演算を $-$ とし、総和を $\Sigma$ で表す。また、記号的に $(-1)^m a=\begin{cases}a\ (m\text{ is even})\\-a\ (m\text{ is odd})\end{cases}$ とする。
$L$ 上の任意の元 $a,b$ に対して等式 $f(a\lor b)=f(a)+f(b)-f(a\land b)$ が成り立つとき、 $L$ 上の元 $a_1,a_2,a_3,\ldots,a_n$ について以下の包除原理が成り立つ。
$\displaystyle{f{\left(\bigvee_{i=1}^n a_i\right)}=\sum_{i=1}^n f{\left(a_i\right)}-\sum_{1\leq i\lt j\leq n} f{\left(a_i\land a_j\right)}+\sum_{1\leq i\lt j\lt k\leq n} f{\left(a_i\land a_j\land a_k\right)}-\cdots+(-1)^{n-1}f{\left(\bigwedge_{i=1}^n a_i\right)}}$
公理および $f(a\lor b)=f(a)+f(b)-f(a\land b)$ において $\lor,\land$ は対称的であるため、左辺を $\land$ 、右辺を $\lor$ にした公式も得られる。
※ $+$ に対して逆元をもつことを仮定したが、式を $f(a\lor b)+f(a\land b)=f(a)+f(b)$ と解釈すれば、逆元をもたない演算についても考えることができる。その場合、得られる包除原理は右辺の $-$ の項を移項したものになる。

証明

$n=2$ の場合は $f(a\lor b)=f(a)+f(b)-f(a\land b)$ より自明。
$n=N-1$ の場合に成立すると仮定する。
$\displaystyle{\begin{align*}f{\left(\bigvee_{i=1}^N a_i\right)}&=f{\left(\left(\bigvee_{i=1}^{N-1} a_i\right)\lor a_N\right)}\\&=f{\left(\bigvee_{i=1}^{N-1} a_i\right)}+f(a_N)-f{\left(\left(\bigvee_{i=1}^{N-1} a_i\right)\land a_N\right)}\\&=f{\left(\bigvee_{i=1}^{N-1} a_i\right)}+f(a_N)-f{\left(\bigvee_{i=1}^{N-1} (a_i\land a_N)\right)}\\&=\sum_{i=1}^{N-1} f{\left(a_i\right)}-\sum_{1\leq i\lt j\leq N-1} f{\left(a_i\land a_j\right)}+\sum_{1\leq i\lt j\lt k\leq N-1} f{\left(a_i\land a_j\land a_k\right)}-\cdots+(-1)^{N-2}f{\left(\bigwedge_{i=1}^{N-1} a_i\right)}+f(a_N)-f{\left(\bigvee_{i=1}^{N-1} (a_i\land a_N)\right)}\\&=\sum_{i=1}^{N-1} f{\left(a_i\right)}-\sum_{1\leq i\lt j\leq N-1} f{\left(a_i\land a_j\right)}+\sum_{1\leq i\lt j\lt k\leq N-1} f{\left(a_i\land a_j\land a_k\right)}-\cdots+(-1)^{N-2}f{\left(\bigwedge_{i=1}^{N-1} a_i\right)}+f(a_N)-\sum_{i=1}^{N-1} f{\left(a_i\land a_N\right)}+\sum_{1\leq i\lt j\leq N-1} f{\left((a_i\land a_N)\land (a_j\land a_N)\right)}-\sum_{1\leq i\lt j\lt k\leq N-1} f{\left((a_i\land a_N)\land (a_j\land a_N)\land (a_k\land a_N)\right)}+\cdots+(-1)^{N-1}f{\left(\bigwedge_{i=1}^{N-1} (a_i\land a_N)\right)}\\&=\sum_{i=1}^{N-1} f{\left(a_i\right)}-\sum_{1\leq i\lt j\leq N-1} f{\left(a_i\land a_j\right)}+\sum_{1\leq i\lt j\lt k\leq N-1} f{\left(a_i\land a_j\land a_k\right)}-\cdots+(-1)^{N-2}f{\left(\bigwedge_{i=1}^{N-1} a_i\right)}+f(a_N)-\sum_{i=1}^{N-1} f{\left(a_i\land a_N\right)}+\sum_{1\leq i\lt j\leq N-1} f{\left(a_i\land a_j\land a_N\right)}-\sum_{1\leq i\lt j\lt k\leq N-1} f{\left(a_i\land a_j\land a_k\land a_N\right)}+\cdots+(-1)^{N-1}f{\left(\left(\bigwedge_{i=1}^{N-1} a_i\right)\land a_N\right)}\\&=\sum_{i=1}^N f{\left(a_i\right)}-\sum_{1\leq i\lt j\leq N} f{\left(a_i\land a_j\right)}+\sum_{1\leq i\lt j\lt k\leq N} f{\left(a_i\land a_j\land a_k\right)}-\cdots+(-1)^{N-1}f{\left(\bigwedge_{i=1}^N a_i\right)}\end{align*}}$
したがって、 $n=N$ の場合にも成立することが示せた。
よって、 $2$ 以上の任意の自然数 $n$ で成立することが示せた。

例

集合の和集合と共通部分

$L$ をある集合 $U$ の冪集合 $2^U$ とし、演算 $\lor,\land$ をそれぞれ $\cup,\cap$ とする。また、 $f(S)=|S|$ 、 $+$ を自然数の加算とする。
$|S\cup T|=|S|+|T|-|S\cap T|$ が成立するから、 $2^U$ 上の元 $S_1,S_2,S_3,\ldots,S_n$ について以下の包除原理が成り立つ。
$\displaystyle{\left|\bigcup_{i=1}^n S_i\right|=\sum_{i=1}^n |S_i|-\sum_{1\leq i\lt j\leq n} |S_i\cap S_j|+\sum_{1\leq i\lt j\lt k\leq n} |S_i\cap S_j\cap S_k|-\cdots+(-1)^{n-1}\left|\bigcap_{i=1}^n S_i\right|}$

確率の和事象と積事象

$L$ を標本空間 $\Omega$ とし、演算 $\lor,\land$ をそれぞれ $\cup,\cap$ とする。また、 $f(A)$ を事象 $A$ が起こる確率（以降 $p(A)$ ）、 $+$ を実数の加算とする。
$p(A\cup B)=p(A)+p(B)-p(A\cap B)$ が成立するから、 $\Omega$ 上の元 $A_1,A_2,A_3,\ldots,A_n$ について以下の包除原理が成り立つ。
$\displaystyle{p{\left(\bigcup_{i=1}^n A_i\right)}=\sum_{i=1}^n p(A_i)-\sum_{1\leq i\lt j\leq n} p(A_i\cap A_j)+\sum_{1\leq i\lt j\lt k\leq n} p(A_i\cap A_j\cap A_k)-\cdots+(-1)^{n-1}p{\left(\bigcap_{i=1}^n A_i\right)}}$

実数のmaxとmin

$L$ を $\mathbb{R}$ とし、演算 $\lor,\land$ をそれぞれ $\max,\min$ とする。また、 $f(x)=x$ 、 $+$ を実数の加算とする。
$\max\{a,b\}=a+b-\min\{a,b\}$ が成立するから、 $\mathbb{R}$ 上の元 $a_1,a_2,a_3,\ldots,a_n$ について以下の包除原理が成り立つ。
$\displaystyle{\max \{a_i\}_{1\leq i\leq n}=\sum_{i=1}^n a_i-\sum_{1\leq i\lt j\leq n} \min\{a_i,a_j\}+\sum_{1\leq i\lt j\lt k\leq n} \min\{a_i,a_j,a_k\}-\cdots+(-1)^{n-1}\min \{a_i\}_{1\leq i\leq n}}$

正整数のlcmとgcd

$L$ を $\mathbb{N}\setminus\{0\}$ とし、演算 $\lor,\land$ をそれぞれ $\operatorname{lcm},\gcd$ とする。また、 $f(n)=n$ 、 $+$ を正整数の乗算とする。
厳密には乗算は逆元を必ずもつわけではないので、逆元をもたない場合の考え方でまず立式し、割れることを証明していく形になるはずである。
$\operatorname{lcm}\{a,b\}=\dfrac{ab}{\gcd\{a,b\}}$ が成立するから、 $\mathbb{N}\setminus\{0\}$ 上の元 $a_1,a_2,a_3,\ldots,a_n$ について以下の包除原理が成り立つ。
$\displaystyle{\operatorname{lcm}\{a_i\}_{1\leq i\leq n}=\frac{\prod_{i=1}^n a_i\prod_{1\leq i\lt j\lt k\leq n} \gcd\{a_i,a_j,a_k\}\ldots}{\prod_{1\leq i\lt j\leq n} \gcd\{a_i,a_j\}\prod_{1\leq i\lt j\lt k\lt l\leq n} \gcd\{a_i,a_j,a_k,a_l\}\ldots}}$

束群 (lattice ordered group)

束でも群でもある集合 $(G,+,\leq)$ を束群 (lattice ordered group)というようである。
ただし、集合の和集合と共通部分や確率の和事象と積事象については $\lor,\land$ と $+$ で台が異なり、同じ集合上の演算として正当化するのは怪しいように思える。
また、正整数のlcmとgcdについては整数の乗算は群ではないため、束群として考えることはできない。
したがって、この包除原理は束群のみに適用できる公式というわけではないといえる。