集合の要素の個数と包除原理

同義語：counting elements of sets and inclusion–exclusion

概要

前提知識: 集合, 和集合, 共通部分, 補集合

高校での出発点：重なりを引く

数学 A の「集合の要素の個数」では、有限個の要素をもつ集合 $A$ の要素の個数を $n(A)$ と書き、次の公式を習う。
$$ n(A\cup B)=n(A)+n(B)-n(A\cap B) $$
まず、この公式を使う計算を見る。

クラスの調査

40 人のクラスで、数学が好きな人が 25 人、英語が好きな人が 18 人、両方が好きな人が 10 人いる。クラス全体を $U$、数学が好きな人の集合を $A$、英語が好きな人の集合を $B$ とすると、$n(U)=40$、$n(A)=25$、$n(B)=18$、$n(A\cap B)=10$ である。

少なくとも一方が好きな人は $n(A\cup B)=25+18-10=33$ 人である。
どちらも好きでない人は $n(U)-n(A\cup B)=40-33=7$ 人である。
数学だけが好きな人は $n(A)-n(A\cap B)=25-10=15$ 人、英語だけが好きな人は $18-10=8$ 人である。
$15+10+8+7=40$ で、全員がちょうど 1 回ずつ数えられている（図 1）。

40 人のクラスを、数学が好きな人の集合 !FORMULA[15][36647][0] と英語が好きな人の集合 !FORMULA[16][36678][0] で 4 つの部分に分けた図。各部分の人数 15、10、8、7 を足すと 40 になることを見る。 40 人のクラスを、数学が好きな人の集合 $A$ と英語が好きな人の集合 $B$ で 4 つの部分に分けた図。各部分の人数 15、10、8、7 を足すと 40 になることを見る。

2 の倍数または 3 の倍数

1 から 100 までの整数のうち、2 の倍数または 3 の倍数であるものの個数を求める。2 の倍数は 50 個、3 の倍数は 33 個ある。2 の倍数でも 3 の倍数でもある数は 6 の倍数で、16 個ある。よって
$$ 50+33-16=67 $$
個である。$50+33=83$ としてしまうと、$6,12,\dots,96$ の 16 個を 2 回数えたことになる。

3 つの集合になると、公式は次のようになる。

2・3・5 の倍数

1 から 100 までの整数のうち、2、3、5 の少なくとも 1 つで割り切れるものの個数を求める。2、3、5 の倍数はそれぞれ 50、33、20 個、6、10、15 の倍数はそれぞれ 16、10、6 個、30 の倍数は 3 個ある。
$$ (50+33+20)-(16+10+6)+3=103-32+3=74 $$
で、74 個である。どれでも割り切れない数は $100-74=26$ 個である。

公式は使えるが、次のような疑問が残る。

なぜ $n(A\cap B)$ を引けばちょうどよいのか。→ thm-ces-two
3 つの集合では、なぜ最後に $n(A\cap B\cap C)$ を足すのか。→ thm-ces-three
「6 の倍数の個数」のような共通部分の個数は、どうやって数えるのか。→ prop-ces-multiples、prop-ces-common-multiples

4 つ以上の集合ではどうなるのか。なぜ符号が交互になるのか。→ rem-ces-general
この記事では、要素の個数の最も基本的な性質「重なりのない集合の個数は足せる」（prop-ces-sum-rule）から、2 つの集合と 3 つの集合の公式を証明する。このような公式を包除原理（含めて、除く原理）と呼ぶ。後半では、集合を 0 と 1 の値をとる関数で表すと、3 つの集合の公式が $(1-a)(1-b)(1-c)$ の展開そのものであることを見る。

高校の計算	この記事での見方	ボックス
重なりのない集合の個数は足す	和の法則	prop-ces-sum-rule
$n(A\cup B)=n(A)+n(B)-n(A\cap B)$	2 回数えた要素を 1 回引く	thm-ces-two
3 つの集合の公式	2 つの集合の公式を 2 回使う	thm-ces-three
図の各部分の個数	各要素が何回数えられるか	prop-ces-count-once
$1-(1-a)(1-b)(1-c)$ の展開	指示関数の積	prop-ces-indicator

要素の個数

有限集合と要素の個数

要素が有限個である集合を 有限集合 という。有限集合 $A$ の要素の個数を $n(A)$ と書く。要素を 1 つももたない集合（空集合）$\emptyset$ も有限集合で、$n(\emptyset)=0$ である。

要素の個数を数える

$A=\{1,2,3,4\}$、$B=\{3,4,5\}$ なら、$n(A)=4$、$n(B)=3$ である。$A\cup B=\{1,2,3,4,5\}$、$A\cap B=\{3,4\}$ なので $n(A\cup B)=5$、$n(A\cap B)=2$ で、$4+3-2=5$ となり公式が成り立っている。
$A=\{x\mid x\text{ は } 1\text{ 以上 }20\text{ 以下の } 3\text{ の倍数}\}=\{3,6,9,12,15,18\}$ なら $n(A)=6$ である。

1 から $N$ までの整数の中の倍数の個数は、次の命題で求められる。$\lfloor x\rfloor$ は $x$ を超えない最大の整数を表す（ガウス記号）。

倍数の個数

$N$、$d$ を正の整数とする。1 から $N$ までの整数のうち $d$ の倍数であるものの個数は $\left\lfloor\dfrac Nd\right\rfloor$ である。

倍数を小さい順に並べる

1 から $N$ までの $d$ の倍数は、正の整数 $k$ を使って $dk$ と書けて、$1\le dk\le N$ を満たす数である。$d>0$ なので、$dk\le N$ は $k\le\frac Nd$ と同じである。$k$ は正の整数なので、$k$ のとりうる値は $1,2,\dots,\bigl\lfloor\frac Nd\bigr\rfloor$ であり、その個数は $\bigl\lfloor\frac Nd\bigr\rfloor$ である（$\frac Nd<1$ なら $0$ 個で、$\bigl\lfloor\frac Nd\bigr\rfloor=0$ と一致する）。異なる $k$ は異なる $dk$ を与えるので、倍数の個数も $\bigl\lfloor\frac Nd\bigr\rfloor$ である。$\square$

倍数の個数の計算

1 から 100 までの 7 の倍数：$\frac{100}7=14.28\ldots$ なので 14 個（$7\times14=98$、$7\times15=105>100$）。
1 から 50 までの 6 の倍数：$\frac{50}6=8.33\ldots$ なので 8 個（$6,12,\dots,48$）。

ex-ces-two-or-three では「2 の倍数でも 3 の倍数でもある数は 6 の倍数」を使った。これは 2 と 3 が異なる素数だから成り立つ。

異なる素数の公倍数

$p$、$q$ を異なる素数とする。整数 $k$ が $p$ の倍数でも $q$ の倍数でもあることと、$k$ が $pq$ の倍数であることは同値である。

素数の性質を使う

$k$ が $pq$ の倍数なら、$k=pq\,m$ は $p$ の倍数でも $q$ の倍数でもある。逆に、$k$ が $p$ の倍数でも $q$ の倍数でもあるとする。$k=p\,m$ と書くと、$q$ は積 $p\,m$ を割り切る。素数 $q$ が積を割り切るので、$q$ は $p$ か $m$ を割り切る（素因数分解の一意性から出る性質）。$p$ は $q$ と異なる素数なので $q$ で割り切れない。よって $q$ は $m$ を割り切り、$m=q\,m'$ と書けて、$k=pq\,m'$ は $pq$ の倍数である。$\square$

同じ理由で、「2 の倍数かつ 3 の倍数かつ 5 の倍数」は「30 の倍数」である（まず 2 と 3 から 6 の倍数、次に 6 の倍数で 5 の倍数なら、$6m$ を 5 が割り切るので 5 は $m$ を割り切り、30 の倍数）。素数でない数どうしでは、積の倍数とは限らない（ex-ces-lcm-counterexample）。

和の法則と補集合

要素の個数についての出発点は、重なりのない 2 つの集合の個数は足せる、という性質である。

和の法則

有限集合 $A$、$B$ が共通の要素をもたない（$A\cap B=\emptyset$）とき、
$$ n(A\cup B)=n(A)+n(B) $$
である。

要素を並べて数える

$n(A)=m$、$n(B)=l$ とし、$A$ の要素を $a_1,\dots,a_m$、$B$ の要素を $b_1,\dots,b_l$ と並べる（それぞれの中に同じものは現れない）。$A\cup B$ の要素は、並び $a_1,\dots,a_m,b_1,\dots,b_l$ のどれかである。この並びに同じ要素が 2 回現れることはない。$a_i$ どうし、$b_j$ どうしは異なり、$a_i=b_j$ となると、その要素は $A\cap B$ に属することになり、$A\cap B=\emptyset$ に反するからである。よって $A\cup B$ の要素はちょうど $m+l$ 個である。$\square$

$U$ を全体集合とし、$A$ を $U$ の部分集合とする。$A$ の補集合 $\overline{A}$ は、$U$ の要素のうち $A$ に属さないもの全体である。

補集合と差の個数

$U$ を有限集合、$A$、$B$ をその部分集合とする。

$n(\overline{A})=n(U)-n(A)$
$n(A\cap\overline{B})=n(A)-n(A\cap B)$

重なりのない 2 つに分ける

1：$U$ の要素は、$A$ に属するか属さないかのどちらか一方なので、$U=A\cup\overline{A}$ で、$A\cap\overline{A}=\emptyset$ である。prop-ces-sum-rule により $n(U)=n(A)+n(\overline{A})$ で、移項すると 1 になる。
2：$A$ の要素は、$B$ に属するか属さないかのどちらか一方なので、$A=(A\cap B)\cup(A\cap\overline{B})$ で、この 2 つは共通の要素をもたない。prop-ces-sum-rule により $n(A)=n(A\cap B)+n(A\cap\overline{B})$ で、移項すると 2 になる。$\square$

補集合を使う

1 から 100 までの整数のうち、7 の倍数でないもの：ex-ces-multiples の 1 から $100-14=86$ 個である。
ex-ces-class の「数学だけが好きな人」は $A\cap\overline{B}$ で、2 により $25-10=15$ 人である。

主定理：2 つの集合と 3 つの集合

2 つの集合の和集合の個数

有限集合 $A$、$B$ について
$$ n(A\cup B)=n(A)+n(B)-n(A\cap B) $$
が成り立つ。

重なりのない 2 つに分ける

方針：$A\cup B$ を「$A$」と「$B$ のうち $A$ に属さない部分」に分け、prop-ces-sum-rule と cor-ces-complement を使う。
段 1（分ける）。$A\cup B$ の要素は、$A$ に属するか、$A$ に属さずに $B$ に属するかのどちらか一方である。よって
$$ A\cup B=A\cup(B\cap\overline{A}),\qquad A\cap(B\cap\overline{A})=\emptyset $$
である（ここで補集合は $A\cup B$ を全体集合としてとる）。
段 2（足す）。prop-ces-sum-rule により $n(A\cup B)=n(A)+n(B\cap\overline{A})$ である。
段 3（引く）。cor-ces-complement の 2 で $A$ と $B$ の役割を入れ替えると、$n(B\cap\overline{A})=n(B)-n(B\cap A)$ である。$B\cap A=A\cap B$ なので、段 2 に代入して $n(A\cup B)=n(A)+n(B)-n(A\cap B)$ を得る。$\square$

$A\cap B=\emptyset$ なら $n(A\cap B)=0$ で、prop-ces-sum-rule に戻る。$n(A)+n(B)$ は $A\cap B$ の要素を 2 回数えているので、1 回分を引く、というのが公式の意味である。

2 つの集合の公式を使う

さいころの目 $1,\dots,6$ のうち、偶数の目の集合 $A=\{2,4,6\}$ と 3 の倍数の目の集合 $B=\{3,6\}$ について、$n(A\cup B)=3+2-1=4$ である。実際 $A\cup B=\{2,3,4,6\}$ である。
1 から 100 までの 4 の倍数または 6 の倍数：4 の倍数は 25 個、6 の倍数は 16 個、両方の倍数は 12 の倍数で 8 個なので、$25+16-8=33$ 個である（4 の倍数かつ 6 の倍数が 12 の倍数であることは、ex-ces-lcm-counterexample で確かめる）。

3 つの集合では、2 つの集合の公式を 2 回使う。

3 つの集合の和集合の個数

有限集合 $A$、$B$、$C$ について
$$ n(A\cup B\cup C)=n(A)+n(B)+n(C)-n(A\cap B)-n(B\cap C)-n(C\cap A)+n(A\cap B\cap C) $$
が成り立つ。

2 つの集合の公式を 2 回使う

方針：$A\cup B$ を 1 つの集合とみて thm-ces-two を使い、現れた $n\bigl((A\cup B)\cap C\bigr)$ にもう一度 thm-ces-two を使う。
段 1（$A\cup B$ と $C$）。thm-ces-two を $A\cup B$ と $C$ に使うと
$$ n(A\cup B\cup C)=n(A\cup B)+n(C)-n\bigl((A\cup B)\cap C\bigr) $$
である。
段 2（$n(A\cup B)$）。thm-ces-two により $n(A\cup B)=n(A)+n(B)-n(A\cap B)$ である。
段 3（共通部分を分配する）。$(A\cup B)\cap C$ の要素は、「$A$ または $B$ に属し、かつ $C$ に属する」要素なので、「$A$ と $C$ に属する」か「$B$ と $C$ に属する」要素である。よって $(A\cup B)\cap C=(A\cap C)\cup(B\cap C)$ である（分配法則）。これに thm-ces-two を使うと
$$ n\bigl((A\cup B)\cap C\bigr)=n(A\cap C)+n(B\cap C)-n\bigl((A\cap C)\cap(B\cap C)\bigr) $$
である。$(A\cap C)\cap(B\cap C)$ は $A$、$B$、$C$ のすべてに属する要素の集合なので $A\cap B\cap C$ に等しい。
段 4（まとめる）。段 2 と段 3 を段 1 に代入すると
$$ n(A\cup B\cup C)=n(A)+n(B)-n(A\cap B)+n(C)-n(A\cap C)-n(B\cap C)+n(A\cap B\cap C) $$
となる。$n(A\cap C)=n(C\cap A)$ なので、項を並べかえると定理の式になる。$\square$

3 つの小さな集合

$X=\{1,2,3,4\}$、$Y=\{3,4,5,6\}$、$Z=\{1,4,6,7\}$ とする。$X\cap Y=\{3,4\}$、$Y\cap Z=\{4,6\}$、$Z\cap X=\{1,4\}$、$X\cap Y\cap Z=\{4\}$ なので
$$ n(X\cup Y\cup Z)=(4+4+4)-(2+2+2)+1=7 $$
である。実際 $X\cup Y\cup Z=\{1,2,3,4,5,6,7\}$ で 7 個ある。

ex-ces-two-three-five は thm-ces-three を $A$＝2 の倍数、$B$＝3 の倍数、$C$＝5 の倍数の集合に使ったものである。$A\cap B$ が 6 の倍数の集合になることなどは prop-ces-common-multiples による。図 2 は、100 個の整数を 8 つの部分に分けて、それぞれの個数を実際に数えたものである。
1 から 100 までの整数を、2 の倍数の集合 !FORMULA[226][36647][0]、3 の倍数の集合 !FORMULA[227][36678][0]、5 の倍数の集合 !FORMULA[228][36709][0] で 8 つの部分に分けた図。数字は各部分に入る整数の個数で、円の中の 7 つを足すと 74、外の 26 と合わせて 100 になることを見る。 1 から 100 までの整数を、2 の倍数の集合 $A$、3 の倍数の集合 $B$、5 の倍数の集合 $C$ で 8 つの部分に分けた図。数字は各部分に入る整数の個数で、円の中の 7 つを足すと 74、外の 26 と合わせて 100 になることを見る。

各要素は何回数えられるか

thm-ces-three の右辺は 7 つの項の和である。図 2 の各部分の要素が、右辺で何回数えられるかを調べると、公式が正しい理由がもう 1 つ見えてくる。

どの要素もちょうど 1 回数えられる

$A\cup B\cup C$ の要素 $x$ が、$A$、$B$、$C$ のうちちょうど $j$ 個に属するとする（$j=1,2,3$）。thm-ces-three の右辺で、$x$ は $n(A)$、$n(B)$、$n(C)$ の 3 項で合わせて $j$ 回足され、2 つの共通部分の 3 項で合わせて ${}_j\mathrm{C}_2$ 回引かれ、$n(A\cap B\cap C)$ で ${}_j\mathrm{C}_3$ 回足される（${}_1\mathrm{C}_2={}_1\mathrm{C}_3={}_2\mathrm{C}_3=0$ とする）。その合計
$$ j-{}_j\mathrm{C}_2+{}_j\mathrm{C}_3 $$
は、$j=1,2,3$ のどれでも $1$ である。

3 つの場合を計算する

段 1（足される回数）。$x$ が属する集合の個数が $j$ なので、$n(A)$、$n(B)$、$n(C)$ のうち $x$ を数える項は $j$ 個である。
段 2（引かれる回数）。$x$ が $A\cap B$ に属するのは、$x$ が $A$ と $B$ の両方に属するときである。したがって $x$ を数える 2 つの共通部分は、$x$ の属する $j$ 個の集合から 2 個を選ぶ選び方と 1 対 1 に対応し、その数は ${}_j\mathrm{C}_2$ である。同じように、$x$ が $A\cap B\cap C$ に属するのは $j=3$ のときだけで、その回数は ${}_j\mathrm{C}_3$ である。
段 3（計算）。$j=1$ なら $1-0+0=1$、$j=2$ なら $2-1+0=1$、$j=3$ なら $3-3+1=1$ である。$\square$

右辺の 7 つの項は、どれも $A\cup B\cup C$ の要素のうち条件に合うものを 1 回ずつ数えたものである。したがって、足す順番を入れ替えると、右辺の値は、要素ごとに「足された回数 − 引かれた回数」を求めて、それを $A\cup B\cup C$ の全部の要素について足したものに等しい（後の prop-ces-indicator の 3 は、同じことを式にしたものである）。どの要素もちょうど 1 回数えられるので、右辺は $A\cup B\cup C$ の要素の個数に等しい。これが thm-ces-three の 2 つ目の証明になる。$j=3$ の要素（3 つすべてに属する要素）は、1 段目で 3 回足され、2 段目で 3 回引かれて $0$ 回になってしまうので、最後に $n(A\cap B\cap C)$ で 1 回足し戻す。これが疑問 2 の答えである。

図 2 で回数を確かめる

図 2 の数で確かめる。ちょうど 1 つに属する数は $27+14+7=48$ 個、ちょうど 2 つに属する数は $13+7+3=23$ 個、3 つすべてに属する数は $3$ 個である。

1 段目の和 $50+33+20=103$ は、$48\times1+23\times2+3\times3=48+46+9=103$ と一致する。
2 段目の和 $16+10+6=32$ は、$23\times1+3\times3=23+9=32$ と一致する（ちょうど 2 つに属する数は 1 つの共通部分に、3 つに属する数は 3 つの共通部分に入る）。
合計 $103-32+3=74$ は、$48+23+3=74$ と一致する。

高校数学で解く・大学数学で見る：指示関数と展開

高校数学では、thm-ces-three は 2 つの集合の公式をくり返し使って示した。大学数学では、集合を「属すれば 1、属さなければ 0」という関数に置きかえ、集合の計算を数の掛け算と足し算に直す。すると、包除原理は展開と因数分解の公式で見た展開の計算になる。

集合の指示関数

$U$ を全体集合、$A$ をその部分集合とする。$U$ の各要素 $x$ に対して
$$ 1_A(x)=\begin{cases}1&(x\in A)\\ 0&(x\notin A)\end{cases} $$
と定めた関数 $1_A$ を、$A$ の 指示関数 という。

指示関数の値

$U=\{1,2,3,4,5\}$、$A=\{1,2,3,4\}$、$B=\{3,4,5\}$ とする。

$1_A(2)=1$、$1_A(5)=0$、$1_B(2)=0$、$1_B(5)=1$ である。
$x=1,\dots,5$ の値を並べると、$1_A$ は $1,1,1,1,0$、$1_B$ は $0,0,1,1,1$、積 $1_A1_B$ は $0,0,1,1,0$ である。積は $A\cap B=\{3,4\}$ の指示関数になっている。
$1_A$ の値をすべて足すと $4=n(A)$ である。

指示関数の計算規則

$U$ を有限集合、$A$、$B$ をその部分集合とする。$U$ のすべての要素 $x$ について次が成り立つ。

$1_{A\cap B}(x)=1_A(x)\,1_B(x)$
$1_{\overline{A}}(x)=1-1_A(x)$
$\displaystyle n(A)=\sum_{x\in U}1_A(x)$（$U$ のすべての要素についての和）

値が 0 か 1 かで場合を分ける

1：$x\in A\cap B$ なら、$x\in A$ かつ $x\in B$ なので両辺とも $1\cdot1=1$ である。$x\notin A\cap B$ なら、$x\notin A$ か $x\notin B$ なので右辺の少なくとも一方が $0$ で、両辺とも $0$ である。
2：$x\in A$ なら $x\notin\overline{A}$ なので両辺とも $0$（右辺は $1-1$）である。$x\notin A$ なら $x\in\overline{A}$ なので両辺とも $1$（右辺は $1-0$）である。
3：和の中で、$x\in A$ の項は $1$、$x\notin A$ の項は $0$ なので、和は $A$ の要素の個数に等しい。$\square$

これを使うと、thm-ces-three は展開の計算になる。

指示関数による 3 つの集合の公式の証明

方針：「どれにも属さない」を指示関数の積で書き、展開してから $U$ 全体で足す。$U$ を $A\cup B\cup C$ を含む有限集合とし、$a=1_A(x)$、$b=1_B(x)$、$c=1_C(x)$ と略記する。
段 1（どれにも属さない）。ド・モルガンの法則により、$A\cup B\cup C$ の補集合は $\overline{A}\cap\overline{B}\cap\overline{C}$ である。prop-ces-indicator の 1 と 2 により、その指示関数は
$$ 1_{\overline{A}\cap\overline{B}\cap\overline{C}}(x)=(1-a)(1-b)(1-c) $$
である。
段 2（展開する）。分配法則で展開すると
$$ (1-a)(1-b)(1-c)=1-(a+b+c)+(ab+bc+ca)-abc $$
である。prop-ces-indicator の 1 により、$ab=1_{A\cap B}(x)$、$bc=1_{B\cap C}(x)$、$ca=1_{C\cap A}(x)$、$abc=1_{A\cap B\cap C}(x)$ である。
段 3（足す）。段 1 の左辺を $U$ のすべての $x$ について足すと、prop-ces-indicator の 3 と cor-ces-complement の 1 により $n(U)-n(A\cup B\cup C)$ になる。右辺を足すと
$$ n(U)-\bigl(n(A)+n(B)+n(C)\bigr)+\bigl(n(A\cap B)+n(B\cap C)+n(C\cap A)\bigr)-n(A\cap B\cap C) $$
になる。両辺から $n(U)$ を引いて符号を変えると、thm-ces-three の式になる。$\square$

4 つ以上の集合と符号が交互になる理由

prf-thm-ces-three-indicator は、集合がいくつあっても同じように進む。$m$ 個の集合 $A_1,\dots,A_m$ について $(1-a_1)(1-a_2)\cdots(1-a_m)$ を展開すると、$k$ 個の $a_i$ を選んで掛けた項が符号 $(-1)^k$ で現れる。足し合わせると
$$ n(A_1\cup\cdots\cup A_m)=\sum_i n(A_i)-\sum_{i< j}n(A_i\cap A_j)+\sum_{i< j< l}n(A_i\cap A_j\cap A_l)-\cdots+(-1)^{m-1}n(A_1\cap\cdots\cap A_m) $$
を得る。符号が交互になるのは、$-a_i$ を $k$ 個掛けると $(-1)^k$ が出るからである。一般の場合の言明と、途中で打ち切ったときの大小（Bonferroni の不等式）は包除原理で扱う。

個数でなくても、「重なりのない 2 つの部分の値は足せる」という性質（加法性）をもち、値が有限の量なら、同じ公式が成り立つ（値が無限大になりうる量では、ex-ces-infinite と同じく引き算ができない）。prf-thm-ces-two で使ったのは prop-ces-sum-rule だけだからである。図形の面積、確率がその例である。

確率での包除原理

さいころを 1 回投げる。「偶数の目が出る」事象を $A$、「3 の倍数の目が出る」事象を $B$ とすると、$P(A)=\frac36$、$P(B)=\frac26$、$P(A\cap B)=\frac16$（6 の目）である。
$$ P(A\cup B)=P(A)+P(B)-P(A\cap B)=\frac36+\frac26-\frac16=\frac46=\frac23 $$
で、ex-ces-two の 1 の $n(A\cup B)=4$ を全体の $6$ で割ったものである。確率の加法定理は確率の定義と条件付き確率で扱う。大学では、このような加法性をもつ量を測度としてまとめて扱う。

Euler の $\varphi$ 関数

1 から 30 までの整数のうち、30 と共通の素因数をもたないもの（2、3、5 のどれでも割り切れないもの）の個数を数える。thm-ces-three と cor-ces-complement の 1 により
$$ 30-(15+10+6)+(5+3+2)-1=30-31+10-1=8 $$
である（$1,7,11,13,17,19,23,29$）。この個数は $30\bigl(1-\frac12\bigr)\bigl(1-\frac13\bigr)\bigl(1-\frac15\bigr)=30\cdot\frac12\cdot\frac23\cdot\frac45=8$ とも書ける。$30$ は $2,3,5$ のどれでも割り切れるので、$d$ の倍数の個数がちょうど $\frac{30}d$ になり、指示関数の積 $(1-a)(1-b)(1-c)$ と同じ形の積に分かれるのである。一般に、1 から $n$ までの整数のうち $n$ と共通の素因数をもたないものの個数を $\varphi(n)$ と書き、$\varphi$ を Eulerのφ関数という。この例は $\varphi(30)=8$ である。

例と反例

公式を使うときの前提を外すと、結論が崩れる。

外した前提	崩れる主張	ボックス
共通の要素がない（$A\cap B=\emptyset$）	$n(A\cup B)=n(A)+n(B)$	ex-ces-double-count
最後の項 $+n(A\cap B\cap C)$ まで足す	右辺が $n(A\cup B\cup C)$ に等しい	ex-ces-forget-last
異なる素数	「$p$ の倍数かつ $q$ の倍数」は $pq$ の倍数	ex-ces-lcm-counterexample
有限集合	引き算で個数が求まる	ex-ces-infinite
加法性をもつ量	同じ形の公式が成り立つ	ex-ces-max

反例：重なりがあるのに足すだけ

ex-ces-two-or-three で $n(A\cup B)=n(A)+n(B)$ とすると $50+33=83$ になり、正しい値 $67$ より $16$ 多い。$A\cap B$（6 の倍数）が空集合でないので prop-ces-sum-rule の仮定が成り立たず、6 の倍数 16 個が 2 回数えられている。

反例：3 つの集合で最後の項を忘れる

ex-ces-two-three-five で最後の $+3$ を忘れると $103-32=71$ になり、正しい値 $74$ より $3$ 少ない。prop-ces-count-once の $j=3$ の場合のとおり、30 の倍数 3 個（30、60、90）が $3-3=0$ 回しか数えられていない。

反例：素数でない数の公倍数

「4 の倍数かつ 6 の倍数」は「24 の倍数」ではない。12 は 4 の倍数でも 6 の倍数でもあるが、24 の倍数ではない。1 から 100 までで、4 の倍数かつ 6 の倍数の個数を 24 の倍数の個数 $\lfloor100/24\rfloor=4$ とすると誤りで、正しくは 12 の倍数の個数 8 である。
実際、「4 の倍数かつ 6 の倍数」は「12 の倍数」と同値である。12 の倍数なら $12=4\cdot3=6\cdot2$ から 4 の倍数でも 6 の倍数でもある。逆に $k=4m$ が 6 の倍数なら、$4m$ は 3 で割り切れる。素数 3 は 4 を割り切らないので $m$ を割り切り（prf-prop-ces-common-multiples と同じ理由）、$m=3m'$、$k=12m'$ である。12 は 4 と 6 の最小公倍数である。prop-ces-common-multiples の「異なる素数」の仮定を外すと、積 $pq$ を最小公倍数に替えなければならない。

反例：無限集合では引き算ができない

正の整数全体を $A$、正の偶数全体を $B$ とすると、$A\cup B=A$、$A\cap B=B$ で、どちらも要素が無限にある。「$n(A)+n(B)-n(A\cap B)$」を計算しようとしても、無限から無限を引くことになり、値が決まらない。thm-ces-two は有限集合についての主張である。無限集合の大きさの比べ方は濃度で扱う。

反例：加法性のない量

集合に「要素の最大値」を対応させる量 $M$ を考える。$A=\{1,4\}$、$B=\{1,5\}$ とすると $A\cup B=\{1,4,5\}$、$A\cap B=\{1\}$ で、
$$ M(A\cup B)=5,\qquad M(A)+M(B)-M(A\cap B)=4+5-1=8 $$
となり、一致しない。最大値は、重なりのない 2 つの集合でも $M(\{1\}\cup\{2\})=2\ne1+2$ となり、prop-ces-sum-rule にあたる性質（加法性）をもたない。包除原理の公式を支えているのは、個数の加法性である。

さらに先へ

集合が $m$ 個の場合の包除原理、途中で打ち切ったときの大小（Bonferroni の不等式）、完全順列（だれも自分の帽子を受け取らない返し方）の数え上げは包除原理で扱う。
包除原理を期待値の言葉で見る見方（指示関数の和の期待値）は期待値の線形性と数え上げで扱う。全射の個数を包除原理で数える例は場合の数の数え方の体系にある。
ex-ces-euler-phi の積の形は、約数についての和を反転する Möbius関数につながる。
面積・確率・個数に共通する加法性を取り出したものが測度である。