有限集合のσ代数の要素数が2^n-nであることの証明
Ωを要素数nの有限集合とするとき、
Ωのσ代数の要素数は2^n-nであるという仮説を証明したいです。(有用性はさておき)
たとえばn=3とし、Ω={0, 1, 2}のσ代数を考えると、その要素は
1){φ, Ω}
2){φ, {0}, {1,2}, Ω}, {φ, {1}, {0,2}, Ω}, {φ, {2}, {0,1}, Ω},
3)Ωの部分集合全体
の5つです。これを要素1の集合の個数で考えると
1)3C0=1
2)3C1=3
3)3C3=1
となります。この総和は
3C0 + 3C1 + 3C3
= (3C0 + 3C1 + 3C2 + 3C3) - 3C2
= (1+1)^3 - 3C1
= 2^3 - 3
となるので、上記の推測を得ました。
n=4でも確認できました。帰納法による証明を試みましたが、
どう示していいかわかりませんでした。
アイデアを頂ければ幸いです。
(もし推測が間違っていたらその旨ご指摘ください)
なお、σ代数の定義は以下の通りです。
「集合Ωの部分集合の族Bがσ代数であるとは、次の3つを満たすことである。
(1)φ∈B
(2)A∈Bならば、A^C∈B
(3)A1, A2, ...∈Bならば、U_{i=1}^∞ Ai ∈ B」