部分集合について

質問

n個の元からなる集合の部分集合は全部で2^n個と聞きましたが、証明はできるのでしょうか？数学的帰納法を使うのでしょうか？

回答No.2

liar_adan · ベストアンサー

nで成り立つとする。

Sがn+1個の要素を持つ集合とする。
Sのなかから元aを取って、残った集合をRとする。
Rの元の個数はn。だから部分集合の数は2^nである。

ここで、Sの部分集合を考えると、それは「aが含まれる」
「aが含まれない」に分けられる。

後者の集合は、Rの部分集合と同じ。
前者もまた、「Rの部分集合それぞれにaを加えたもの」と考えられるので、
数はRの部分集合の数と同じ。

この2種類はそれぞれ重なっていないので、
全部の数は2^n + 2^n = 2^(n+1)である。
よって、nのとき2^nならn+1のとき2^(n+1)である。

お礼

ありがとうございました。理解することができました。

回答No.1

liar_adan

それは、以下のように考えます。

集合Sのある元aを考えるとき、
Sの部分集合に、aは、「含まれるか」「含まれないか」のどっちかです。
場合が二つあります。×2です。

それぞれの元について×2になるので、結局2^n個の部分集合ができます。
これには、「全部含まれる(集合S全体)」と
「まったく含まれない(空集合φ)」も入ります。

感覚的には上のようになります。
きちんとした証明をするには、数学的帰納法を使うといいでしょう。

補足

ありがとうございます。しかし、数学的帰納法でやってみたところ、n=kが成り立つと仮定した後、どうやればいいのかわからなくなってしまいました。おしえていただけますか？