要素n個の集合の部分集合の数(冪集合の濃度)が2のn乗になる理由
ある集合の要素を使ってつくれる集合をその集合の部分集合というよ(空集合とその集合自身も部分集合だよ)。集合の要素の数を濃度というよ。元の集合の濃度がnなら、部分集合の数は2のn乗個になるよ。ある集合の部分集合の集合を元の集合の冪集合というから、冪集合の濃度が2のn乗になるということだよ。
これはなぜかというと、部分集合というのはどれも、元の集合のすべての要素についての〈含む/含まない〉の2つの可能性の組み合わせとして定義できるからだよ。n個の要素についてそれぞれ2つの可能性があるということは、組み合わせの可能性の数は2のn乗個になるよね。
たとえば{a, b, c}という集合があるとするよ。この集合の冪集合の濃度は2の3乗で8になるはずだね。それぞれの部分集合について、各要素を〈含む〉ことを1と書き、〈含まない〉ことを0と書くことにするよ。すると、
111 {a, b, c}
110 {a, b}
101 {a, c}
100 {a}
011 {b, c}
010 {b}
001 {c}
000 φ
このように書けて、やっぱり8個だとわかるよ。