数学大好き宣言!

勉強メモ。おもしろいことを探していきたい。

【集合論】ベン図が書けないときの要素数の計算

集合Aの要素数を|A|で表す。
いま|A|,|B|,|A∩B|が分かっているときに、|A∪B|を求めたいとする。
このとき下のようなベン図を書いて|A∪B|=|A|+|B|-|A∩B|が分かる。
三つの場合、つまり|A∪B∪C|が求めたい場合も同様にベン図から分かる。
f:id:mochi-mochi61:20210303172512p:plain:h200
しかし4つ以上になると、円ではベン図は書けないし、一応円にこだわらなければ書けるのだが、とても複雑でかえってわかりにくい。このときどうやって要素数を求めるか。
とても単純な発想として、|A∪B|=|A|+|B|-|A∩B|を使ってどんどんばらしていく方法がある。
三つの場合の例(本当はベン図で簡単にわかるけど):
|A∪B∪C|=|(A∪B)∪C|
=|A∪B|+|C|-|(A∪B)∩C|
=|A|+|B|-|A∩B|+|C|-|(A∩C)∪(B∩C)|
=|A|+|B|-|A∩B|+|C|-|A∩B|-|B∩C|+|(A∩C)∩(B∩C)|
=|A|+|B|-|A∩B|+|C|-|A∩B|-|B∩C|+|A∩B∩C|
と求まる。4つや5つのときも時間はかかるが原理上求まる。
しかしこれでは大変すぎる。
もう少し良い方法がある。
全体集合をUとする。A⊂Uに対して、U上の関数A(x)を
x∊AのときA(x)=1, x∉AのときA(x)=0 として定めると、
これは(A∩B)(x)=A(x)B(x), Aᶜ(x)=1-A(x)(ただしAᶜはAの補集合を表す)
を満たす。
また、|A|=\sum_{x\in U}A(x)だから、|A|を求めるにはA(x)を求めればいい。
これを使って|A∪B∪C∪D|を求めよう。
以下しばらく関数のほうしか使わないので、わざわざA(x)と書かずAでA(x)を表す。
ド・モルガンの法則より(A∪B∪C∪D)ᶜ=Aᶜ∩Bᶜ∩Cᶜ∩Dᶜ だから、
(A∪B∪C∪D)=1-(Aᶜ∩Bᶜ∩Cᶜ∩Dᶜ) = 1-AᶜBᶜCᶜDᶜ
= 1-(1-A)(1-B)(1-C)(1-D)
展開して
(A∪B∪C∪D)=(A+B+C+D) - (AB+AC+AD+BC+BD+CD) + (ABC+BCD+CDA+DAB) - ABCD
(A∩B)=AB より
(A∪B∪C∪D)=(A+B+C+D) -
{(A∩B)+(A∩C)+(A∩D)+(B∩C)+(B∩D)+(C∩D)} +
{(A∩B∩C)+(B∩C∩D)+(C∩D∩A)+(D∩A∩B)} - (A∩B∩C∩D)
よって
|A∪B∪C∪D|=|A|+|B|+|C|+|D| - (|A∩B|+|A∩C|+|A∩D|+|B∩C|+|B∩D|+|C∩D|) + (|A∩B∩C|+|B∩C∩D|+|C∩D∩A|+|D∩A∩B|) - |A∩B∩C∩D|
これを使い、例えば1000以下の自然数で、2,3,5,7のいずれかで割り切れるものの個数を求めると、
500+333+200+142-(166+100+71+66+47+28)+(33+9+14+23)-4=772
で772個。