包含と除去の原理

数え上げ組合せ論の記事にもあるように、一般の有限集合において、 包含と除去の原理 はつぎのようにして証明される。
$A$ が有限集合で、$A_i (i=1, 2, \ldots, n)$ がその部分集合とし、
$I\subset\{1, 2, \ldots, n\}$ に対して、$A_I=\cap_{i\in I}A_i$ と定める。
このとき、
$$\mu(I)=(-1)^{\# I}$$
と定義すると、
$$\sum_{J\subset I}\mu(J)=(1-1)^{\# I}=\left\{\begin{array}{cl} 1 & (I=\emptyset), \\ 0 & (I\neq\emptyset) \end{array}\right.$$
となる。よって $x\in A_i$ となる $i$ 全体の集合を $J(x)$ とおくと
$$\sum_{I\ni x}\mu(I)=\sum_{I\subset J(x)}\mu(I)=\left\{\begin{array}{cl} 1 & (J(x)=\emptyset), \\ 0 & (J(x)\neq\emptyset) \end{array}\right.$$
となるから
$$S=A\setminus\left(\bigcup_{i=1}^n A_i\right)$$
を $A$ の要素のうち、どの $A_i$ にも属さないもの全体の集合とすると
$$\#S = \sum_{I\subset J(x)}\mu(I)= \sum_{x\in A} \sum_{I\ni x}\mu(I)=\sum_{I\subset\{1, 2, \ldots, n\}}\mu(I) \#A_I$$
となる。

ここで、ある実数 $X$ が存在し、さらに各 $i=1, 2, \ldots, n$ に対して実数 $\delta_i$ が対応し、$\delta(I)=\prod_{i\in I} \delta_i$, $\delta(\emptyset)=1$ とおくと、各 $I\subset \{1, 2, \ldots, n\}$ について
$$\# A_I=\frac{\delta(I)}X+R_I$$
となるとする。それで $\abs{R_I}$ が小さいとき、$A_I$ は $X\delta(I)=X\prod_{i=1}^r \delta_i$ で近似されるといえる。確率論的には $A$ の要素が $A_I$ に属する確率が $\delta(I)=\prod_{i=1}^r \delta_i$ で近似されている（よって $A$ の要素が $A_i$ に属する事象は異なる $i$ についてほぼ独立である）といえる。

$A_1, A_2, \ldots, A_k$ に属する要素をすべて $A$ から取り除いた集合の要素の個数を
$$S(A, k)=\# \left[A\setminus\left(\bigcup_{i=1}^n A_i\right)\right]$$
とおくと、包含と除去の原理から
$$S(A, k)=\sum_{I\subset \{1, 2, \ldots, k\}} (-1)^{\# I} \#A_d=X\prod_{i=1}^k (1-\delta_i)+\sum_{I\subset\{1, 2, \ldots, k\}} (-1)^{\# I}R_I$$
となる。

Eratosthenes-Legendreの篩はこれをそのまま用いるものであったが、誤差項となる右辺の和は大きなものになりうる。Brun以降の篩法の出発点は、$\mu(d)$ を別の関数 $\lambda(I)$ で置き換えるところにある。